The ethical issues in conducting research on preventing HIV infection are among the most complex of any area of human subjects research. This article is an update of a 1987 article that addressed potential conflicts between research design and ethics with respect to AIDS prevention among injecting drug users. The present article reviews current ethical issues that arise in the design and conduct of HIV/AIDS prevention research focused on injecting drug users.

Samuel R. Buss and Aleksandar Ignjatović. Unprovability of Consistency Statements in Fragments of Bounded Arithmetic.

This volume contains articles covering a broad spectrum of proof theory, with an emphasis on its mathematical aspects. The articles should not only be interesting to specialists of proof theory, but should also be accessible to a diverse audience, including logicians, mathematicians, computer scientists and philosophers. Many of the central topics of proof theory have been included in a self-contained expository of articles, covered in great detail and depth. The chapters are arranged so that the two introductory articles come first; (...) these are then followed by articles from core classical areas of proof theory; the handbook concludes with articles that deal with topics closely related to computer science. (shrink)

In his warranted christian belief, Alvin Plantinga launches a forceful attack on apophaticism, the view that God is in some sense or other beyond description. This paper explores his attack before searching for a Plantinga-proof formulation of apophaticism.

Cook and Reckhow defined a propositional formulation of the pigeonhole principle. This paper shows that there are Frege proofs of this propositional pigeonhole principle of polynomial size. This together with a result of Haken gives another proof of Urquhart's theorem that Frege systems have an exponential speedup over resolution. We also discuss connections to provability in theories of bounded arithmetic.

Let T be a first-order theory. A T-normal Kripke structure is one in which every world is a classical model of T. This paper gives a characterization of the intuitionistic theory T of sentences intuitionistically valid in all T-normal Kripke structures and proves the corresponding soundness and completeness theorems. For Peano arithmetic , the theory PA is a proper subtheory of Heyting arithmetic , so HA is complete but not sound for PA-normal Kripke structures.

In this paper we argue that the moral value of an agent is determined solely by their dispositions to act intentionally and freely. We then put this conclusion to work. It resolves a putative moral paradox first posed by Saul Smilansky, and it undermines a prominent line of argument for a variety of Trinitarian theology. Finally, we derive our conclusion about the moral worth of agents not only from our initial series of thought experiments, but also from Abrahamic theism itself. (...) This means that Smilansky’s paradox can only possibly be rehabilitated by an atheist, and that the aforementioned line of argumentation for the Trinity is radically self-undermining, since it relies upon the denial of a corollary of Abrahamic theism. (shrink)

This paper discusses lower bounds for proof length, especially as measured by number of steps (inferences). We give the first publicly known proof of Gödel's claim that there is superrecursive (in fact. unbounded) proof speedup of (i + 1)st-order arithmetic over ith-order arithmetic, where arithmetic is formalized in Hilbert-style calculi with + and · as function symbols or with the language of PRA. The same results are established for any weakly schematic formalization of higher-order logic: this allows all tautologies as (...) axioms and allows all generalizations of axioms as axioms. Our first proof of Gödel's claim is based on self-referential sentences: we give a second proof that avoids the use of self-reference based loosely on a method of Statman. (shrink)

The bounded arithmetic theory S2 is finitely axiomatized if and only if the polynomial hierarchy provably collapses. If T2i equals S2i + 1 then T2i is equal to S2 and proves that the polynomial time hierarchy collapses to ∑i + 3p, and, in fact, to the Boolean hierarchy over ∑i + 2p and to ∑i + 1p/poly.

We study the long-standing open problem of giving$\forall {\rm{\Sigma }}_1^b$separations for fragments of bounded arithmetic in the relativized setting. Rather than considering the usual fragments defined by the amount of induction they allow, we study Jeřábek’s theories for approximate counting and their subtheories. We show that the$\forall {\rm{\Sigma }}_1^b$Herbrandized ordering principle is unprovable in a fragment of bounded arithmetic that includes the injective weak pigeonhole principle for polynomial time functions, and also in a fragment that includes the surjective weak pigeonhole (...) principle for FPNPfunctions. We further give new propositional translations, in terms of random resolution refutations, for the consequences of$T_2^1$augmented with the surjective weak pigeonhole principle for polynomial time functions. (shrink)

The four authors present their speculations about the future developments of mathematical logic in the twenty-first century. The areas of recursion theory, proof theory and logic for computer science, model theory, and set theory are discussed independently.

This article is driven by death. Thematically, death serves as a figure in the central creative works I discuss: Samuel R. Delany's sword-and-sorcery novella The Tale of Plagues and Carnivals, one of the first novels to deal directly with the AIDS pandemic,1 and Lou Reed's songs, especially the proto-punk "Heroin" and the queer soul song "Coney Island Baby." Meanwhile, the argument's methodology also concerns death. As many theorists and critics have discussed,2 the field of queer studies has seen, for (...) at least the past few decades, a general division between a methodology that isolates queerness as a singularly significant figure of identity and a more intersectional queer studies that figures sexuality within a... (shrink)

Partial consistency statements can be expressed as polynomial-size propositional formulas. Frege proof systems have polynomial-size partial self-consistency proofs. Frege proof systems have polynomial-size proofs of partial consistency of extended Frege proof systems if and only if Frege proof systems polynomially simulate extended Frege proof systems. We give a new proof of Reckhow's theorem that any two Frege proof systems p-simulate each other. The proofs depend on polynomial size propositional formulas defining the truth of propositional formulas. These are already known to (...) exist since the Boolean formula value problem is in alternating logarithmic time; this paper presents a proof of this fact based on a construction which is somewhat simpler than the prior proofs of Buss and of Buss-Cook- Gupta-Ramachandran. (shrink)

The paper proves refined feasibility properties for the disjunction property of intuitionistic propositional logic. We prove that it is possible to eliminate all cuts from an intuitionistic proof, propositional or first-order, without increasing the Horn closure of the proof. We obtain a polynomial time, interactive, realizability algorithm for propositional intuitionistic proofs. The feasibility of the disjunction property is proved for sequents containing Harrop formulas. Under hardness assumptions for NP and for factoring, it is shown that the intuitionistic propositional calculus does (...) not always have polynomial size proofs and that the classical propositional calculus provides a superpolynomial speedup over the intuitionistic propositional calculus. The disjunction property for intuitionistic propositional logic is proved to be P-hard by a reduction to the circuit value problem. (shrink)

We survey the best known lower bounds on symbols and lines in Frege and extended Frege proofs. We prove that in minimum length sequent calculus proofs, no formula is generated twice or used twice on any single branch of the proof. We prove that the number of distinct subformulas in a minimum length Frege proof is linearly bounded by the number of lines. Depthd Frege proofs ofm lines can be transformed into depthd proofs ofO(m d+1) symbols. We show that renaming (...) Frege proof systems are p-equivalent to extended Frege systems. Some open problems in propositional proof length and in logical flow graphs are discussed. (shrink)

The author reviews the planned withdrawal of healthcare from the primary public hospital, Grady Memorial Hospital, of Atlanta, Georgia. Prior to passage of the Affordable Care Act of 2010, at least half of the patients had no public or private health insurance and their care was financially supported by State and County funding as well as supplementation from Emory University. New administration in the elected positions of the State and County and at the University reached agreement to decrease care. The (...) University President stated that the Hippocratic Oath was no longer valid for salaried physicians who must follow the direction of their business manager. The author, a tenured Professor, was forcibly transferred to the Veterans Hospital, which also was withholding standard medical care, including life-saving medications. Organizing multiple concerned organizations including members of the King Center, the Carter Center, the Open Door Community Center, Gay Rights, etc., (Grady Coalition) multiple public protests were successful in raising the necessary funds to continue adequate care at Grady and begin an investigation of the Veterans Affairs Hospital. (shrink)

Originating from work in operations research the cutting plane refutation systemCP is an extension of resolution, where unsatisfiable propositional logic formulas in conjunctive normal form are recognized by showing the non-existence of boolean solutions to associated families of linear inequalities. Polynomial sizeCP proofs are given for the undirecteds-t connectivity principle. The subsystemsCP q ofCP, forq≥2, are shown to be polynomially equivalent toCP, thus answering problem 19 from the list of open problems of [8]. We present a normal form theorem forCP (...) 2-proofs and thereby for arbitraryCP-proofs. As a corollary, we show that the coefficients and constant terms in arbitrary cutting plane proofs may be exponentially bounded by the number of steps in the proof, at the cost of an at most polynomial increase in the number of steps in the proof. The extensionCPLE +, introduced in [9] and there shown top-simulate Frege systems, is proved to be polynomially equivalent to Frege systems. Lastly, since linear inequalities are related to threshold gates, we introduce a new threshold logic and prove a completeness theorem. (shrink)

A pool resolution proof is a dag-like resolution proof which admits a depth-first traversal tree in which no variable is used as a resolution variable twice on any branch. The problem of determining whether a given dag-like resolution proof is a valid pool resolution proof is shown to be NP-complete.

Recent findings have provided evidence for the existence of non‐vertebrate acquired immunity. We survey these findings and propose that all living organisms must express both innate and acquired immunity. This is opposed to the paradigm that only vertebrates manifest the two forms of immune mechanism; other species are thought to use innate immunity alone. We suggest new definitions of innate and acquired immunity, based on whether immune recognition molecules are encoded in the inherited genome or are generated through somatic processes. (...) We reason that both forms of immunity are similarly ancient, and have co‐evolved in response to lifestyle, cost‐benefit tradeoffs and symbiosis versus parasitism. However, different species have evolved different immune solutions that are not necessarily genetically related, but serve a similar general function – allowing individuals to learn from their own immune experience; survival of species is contingent on the acquired immune experience of its individuals. (shrink)