Editing Disjunction and existence properties

{{No footnotes|date=July 2023}}
<!-- please note: this article uses parenthetical referencing, but not citation templates of any sort -->
In [[mathematical logic]], the '''disjunction and existence properties''' are the "hallmarks" of [[constructive mathematics|constructive]] theories such as [[Heyting arithmetic]] and [[constructive set theory|constructive set theories]] (Rathjen&nbsp;2005). 

==Definitions==
* The '''disjunction property''' is satisfied by a theory if, whenever a [[Sentence (mathematical logic)|sentence]] ''A'' &or; ''B''  is a [[theorem]], then either ''A'' is a theorem, or ''B'' is a theorem.
* The '''existence property''' or '''witness property''' is satisfied by a theory if, whenever a sentence {{nowrap|1=(∃''x'')''A''(''x'')}} is a theorem, where ''A''(''x'') has no other free variables, then there is some [[First-order logic#Formation rules|term]] ''t'' such that the theory proves {{nowrap|1=''A''(''t'')}}.

===Related properties===
Rathjen&nbsp;(2005) lists five properties that a theory may possess. These include the disjunction property ('''DP'''), the existence property ('''EP'''), and three additional properties:

* The '''numerical existence property (NEP)''' states that if the theory proves <math>(\exists x \in \mathbb{N})\varphi(x)</math>, where ''φ'' has no other free variables, then the theory proves <math>\varphi(\bar{n})</math> for some <math>n \in \mathbb{N}\text{.}</math> Here <math>\bar{n}</math> is a term in <math>T</math> representing the number ''n''.
* '''[[Church's thesis (constructive mathematics)|Church's rule]] (CR)''' states that if the theory proves <math>(\forall x \in \mathbb{N})(\exists y \in \mathbb{N})\varphi(x,y)</math> then there is a natural number ''e'' such that, letting <math>f_e</math> be the computable function with index ''e'', the theory proves <math>(\forall x)\varphi(x,f_e(x))</math>. 
* A variant of Church's rule, '''CR<sub>1</sub>''', states that if the theory proves <math>(\exists f \colon \mathbb{N}\to\mathbb{N}) \psi(f)</math> then there is a natural number ''e'' such that the theory proves <math>f_e</math> is total and proves <math>\psi(f_e)</math>.

These properties can only be directly expressed for theories that have the ability to quantify over natural numbers and, for CR<sub>1</sub>, quantify over functions from <math>\mathbb{N}</math> to <math>\mathbb{N}</math>. In practice, one may say that a theory has one of these properties if a [[definitional extension]] of the theory has the property stated above (Rathjen&nbsp;2005).

==Results==
===Non-examples and examples===
Almost by definition, a theory that accepts [[excluded middle]] while having independent statements does not have the disjunction property. So all classical theories expressing [[Robinson arithmetic]] do not have it. Most classical theories, such as [[Peano arithmetic]] and [[Zermelo-Frankel set theory|ZFC]] in turn do not validate the existence property either, e.g. because they validate the [[least number principle]] existence claim. But some classical theories, such as ZFC plus the [[axiom of constructibility]], do have a weaker form of the existence property (Rathjen&nbsp;2005).

[[Heyting arithmetic]] is well known for having the disjunction property and the (numerical) existence property.

While the earliest results were for constructive theories of arithmetic, many results are also known for constructive set theories (Rathjen 2005). [[John Myhill]]&nbsp;(1973) showed that [[IZF]] with the [[axiom of replacement]] eliminated in favor of the axiom of collection has the disjunction property, the numerical existence property, and the existence property. Michael Rathjen&nbsp;(2005) proved that [[CZF]] has the disjunction property and the numerical existence property.

[[Peter J. Freyd|Freyd]] and Scedrov&nbsp;(1990) observed that the disjunction property holds in free [[Heyting algebra]]s and free [[topoi]]. In [[category theory|categorical terms]], in the [[free topos]], that corresponds to the fact that the [[terminal object]], <math>\mathbf{1}</math>, is not the join of two proper subobjects. Together with the existence property it translates to the assertion that <math>\mathbf{1}</math> is an indecomposable [[projective object]]&mdash;the [[functor]] it represents (the global-section functor) preserves [[epimorphism]]s and [[coproduct]]s.

===Relationship between properties===
There are several relationship between the five properties discussed above.

In the setting of arithmetic, the numerical existence property implies the disjunction property. The proof uses the fact that a disjunction can be rewritten as an existential formula quantifying over natural numbers:
:<math> A \vee B \equiv (\exists n) [ (n=0 \to A) \wedge (n \neq 0 \to B)]</math>.
Therefore, if 
:<math> A \vee B </math> is a theorem of <math> T </math>, so is <math> \exists n\colon (n=0 \to A) \wedge (n \neq 0 \to B) </math>. 
Thus, assuming the numerical existence property, there exists some <math> s </math> such that 
:<math> (\bar{s}=0 \to A) \wedge (\bar{s} \neq 0 \to B) </math> 
is a theorem. Since <math> \bar{s} </math> is a numeral, one may concretely check the value of <math> s</math>: if <math> s=0 </math> then <math> A </math> is a theorem and if <math> s \neq 0 </math> then <math> B </math> is a theorem.

[[Harvey Friedman (mathematician)|Harvey Friedman]] (1974) proved that in any [[recursively enumerable set|recursively enumerable]] extension of [[intuitionistic arithmetic]], the disjunction property implies the numerical existence property. The proof uses self-referential sentences in way similar to the proof of [[Gödel's incompleteness theorems]]. The key step is to find a bound on the existential quantifier in a formula (∃''x'')A(''x''), producing a [[bounded quantifier|bounded existential formula]]
(∃''x''<''n'')A(''x''). The bounded formula may then be written as a finite disjunction A(1)&or;A(2)&or;...&or;A(n). Finally, [[disjunction elimination]] may be used to show that one of the disjuncts is provable.

== History ==
[[Kurt Gödel]]&nbsp;(1932) stated without proof that intuitionistic propositional logic (with no additional axioms) has the disjunction property; this result was proven and extended to intuitionistic predicate logic by [[Gerhard Gentzen]]&nbsp;(1934, 1935). [[Stephen Cole Kleene]]&nbsp;(1945) proved that Heyting arithmetic has the disjunction property and the existence property. Kleene's method introduced the technique of [[realizability]], which is now one of the main methods in the study of constructive theories (Kohlenbach&nbsp;2008; Troelstra&nbsp;1973).

== See also ==
* [[Constructive set theory]]
* [[Heyting arithmetic]]
* [[Law of excluded middle]]
* [[Realizability]]
* [[Existential quantifier]]

== References ==
* Peter J. Freyd and Andre Scedrov, 1990, ''Categories, Allegories''. North-Holland.
* [[Harvey Friedman (mathematician)|Harvey Friedman]], 1975, ''The disjunction property implies the numerical existence property'', State University of New York at Buffalo.
* [[Gerhard Gentzen]], 1934, "Untersuchungen über das logische Schließen. I", ''Mathematische Zeitschrift'' v.&nbsp;39 n.&nbsp;2, pp.&nbsp;176–210.
* [[Gerhard Gentzen]], 1935, "Untersuchungen über das logische Schließen. II", ''Mathematische Zeitschrift'' v.&nbsp;39 n.&nbsp;3, pp.&nbsp;405–431.
* [[Kurt Gödel]], 1932, "Zum intuitionistischen Aussagenkalkül", ''Anzeiger der Akademie der Wissenschaftischen in Wien'', v.&nbsp;69, pp.&nbsp;65–66.
* Stephen Cole Kleene, 1945, "On the interpretation of intuitionistic number theory," ''Journal of Symbolic Logic'', v.&nbsp;10, pp.&nbsp;109–124.
* [[Ulrich Kohlenbach]], 2008, ''Applied proof theory'', Springer. 
* [[John Myhill]], 1973, "Some properties of Intuitionistic Zermelo-Fraenkel set theory", in A. Mathias and H. Rogers, ''Cambridge Summer School in Mathematical Logic'', Lectures Notes in Mathematics v.&nbsp;337, pp.&nbsp;206–231, Springer.
* Michael Rathjen, 2005, "[https://www.jstor.org/stable/27588423 The Disjunction and Related Properties for Constructive Zermelo-Fraenkel Set Theory]", ''Journal of Symbolic Logic'', v.&nbsp;70 n.&nbsp;4, pp.&nbsp;1233–1254.
* [[Anne S. Troelstra]], ed. (1973), ''Metamathematical investigation of intuitionistic arithmetic and analysis'', Springer.

== External links ==
* {{Cite SEP
|last=Moschovakis
|first=Joan
|date=16 December 2022
|title=Intuitionistic Logic
|url-id=logic-intuitionistic
}}

[[Category:Proof theory]]
[[Category:Constructivism (mathematics)]]