To install click the Add extension button. That's it.

The source code for the WIKI 2 extension is being checked by specialists of the Mozilla Foundation, Google, and Apple. You could also do it yourself at any point in time.

4,5
Kelly Slayton
Congratulations on this excellent venture… what a great idea!
Alexander Grigorievskiy
I use WIKI 2 every day and almost forgot how the original Wikipedia looks like.
Live Statistics
English Articles
Improved in 24 Hours
What we do. Every page goes through several hundred of perfecting techniques; in live mode. Quite the same Wikipedia. Just better.
.
Leo
Newton
Brights
Milds

# Constructive set theory

Axiomatic constructive set theory is an approach to mathematical constructivism following the program of axiomatic set theory. The same first-order language with "${\displaystyle =}$" and "${\displaystyle \in }$" of classical set theory is usually used, so this is not to be confused with a constructive types approach. On the other hand, some constructive theories are indeed motivated by their interpretability in type theories.

In addition to rejecting the principle of excluded middle (${\displaystyle {\mathrm {PEM} }}$), constructive set theories often require some logical quantifiers in their axioms to be set bounded, motivated by results tied to impredicativity.

• 1/5
Views:
15 220
8 128
134 967
36 890
38 438
• Five Stages of Accepting Constructive Mathematics - Andrej Bauer
• Intuitionism and Constructive Mathematics 1/19
• Lecture 1: Sets, Set Operations and Mathematical Induction
• How To Figure Out Math Proofs On Your Own
• Set Representation

## Introduction

### Constructive outlook

#### Preliminary on the use of intuitionistic logic

The logic of the set theories discussed here is constructive in that it rejects the principle of excluded middle ${\displaystyle {\mathrm {PEM} }}$, i.e. that the disjunction ${\displaystyle \phi \lor \neg \phi }$ automatically holds for all propositions ${\displaystyle \phi }$. As a rule, to prove the excluded middle for a proposition ${\displaystyle P}$, i.e. to prove the particular disjunction ${\displaystyle P\lor \neg P}$, either ${\displaystyle P}$ or ${\displaystyle \neg P}$ needs to be explicitly proven. When either such proof is established, one says the proposition is decidable, and this then logically implies the disjunction holds. Similarly, a predicate ${\displaystyle Q(x)}$ for ${\displaystyle x}$ in a domain ${\displaystyle X}$ is said to be decidable when the more intricate statement ${\displaystyle \forall (x\in X).{\big (}Q(x)\lor \neg Q(x){\big )}}$ is provable. Non-constructive axioms may enable proofs that formally claim decidability of such ${\displaystyle P}$ (and/or ${\displaystyle Q}$) in the sense that they prove excluded middle for ${\displaystyle P}$ (resp. the statement using the quantifier above) without demonstrating the truth of either side of the disjunction(s). This is often the case in classical logic. In contrast, axiomatic theories deemed constructive tend to not permit many classical proofs of statements involving properties that are provenly computationally undecidable.

The law of noncontradiction is a special case of the propositional form of modus ponens. Using the former with any negated statement ${\displaystyle \neg P}$, one valid De Morgan's law thus implies ${\displaystyle \neg \neg (P\lor \neg P)}$ already in the more conservative minimal logic. In words, intuitionistic logic still posits: It is impossible to rule out a proposition and rule out its negation both at once, and thus the rejection of any instantiated excluded middle statement for an individual proposition is inconsistent. Here the double-negation captures that the disjunction statement now provenly can never be ruled out or rejected, even in cases where the disjunction may not be provable (for example, by demonstrating one of the disjuncts, thus deciding ${\displaystyle P}$) from the assumed axioms.

The intuitionistic logic underlying the set theories discussed here, unlike minimal logic, still permits double negation elimination for individual propositions ${\displaystyle P}$ for which excluded middle holds. In turn the theorem formulations regarding finite objects tends to not differ from their classical counterparts. Given a model of all natural numbers, the equivalent for predicates, namely Markov's principle, does not automatically hold, but may be considered as an additional principle.

For any only classically valid ${\displaystyle \exists (x\in X).(Q(x)\to P)}$, or even ${\displaystyle P\lor \exists (x\in X).\neg Q(x)}$, it is worth trying to establish it in its classically equivalent form ${\displaystyle {\big (}\forall (x\in X).Q(x){\big )}\to P}$. For a special case, the counter-example existence claim ${\displaystyle \exists (x\in X).\neg Q(x)}$ is generally constructively stronger than a rejection claim ${\displaystyle \neg \forall (x\in X).Q(x)}$: Exemplifying a ${\displaystyle t}$ such that ${\displaystyle Q(t)}$ is contradictory of course means it is not the case that ${\displaystyle Q}$ holds for all possible ${\displaystyle x}$. But one may also demonstrate that ${\displaystyle Q}$ holding for all ${\displaystyle x}$ would logically lead to a contradiction without the aid of a specific counter-example, and even while not being able to construct one. In the latter case, constructively, here one does not stipulate an existence claim.

More generally, constructive mathematical theories tend to prove classically equivalent reformulations of classical theorems. For example, in constructive analysis, one cannot prove the intermediate value theorem in its textbook formulation, but one can prove theorems with algorithmic content that, as soon as double negation elimination and its consequences are assumed legal, are at once classically equivalent to the classical statement. The difference is that the constructive proofs are harder to find.

#### Imposed restrictions on a set theory

A restriction to the constructive reading of existence apriori leads to stricter requirements regarding which characterizations of a set ${\displaystyle f\subset X\times Y}$ involving unbounded collections constitute a (mathematical, and so always meaning total) function. This is often because the predicate in a case-wise would-be definition may not be decidable. Compared to the classical counterpart, one is generally less likely to prove the existence of relations that cannot be realized. Adopting the standard definition of set equality via extensionality, the full Axiom of Choice is such a non-constructive principle that implies ${\displaystyle {\mathrm {PEM} }}$ for the formulas permitted in one's adopted Separation schema, by Diaconescu's theorem. Similar results hold for the Axiom of Regularity in its standard form, as shown below. So the development of a genuinely intuitionistic set theory also requires reconsideration of choice principles and the rewording of some standard axioms to classically equivalent ones. Apart from demands for computability and reservations regrading of impredicativity, technical question regarding which non-logical axioms effectively extend the underlying logic of a theory is also a research subject in its own right.

#### Metalogic

With computably undecidable propositions already arising in Robinson arithmetic, even just Predicative separation lets one define elusive subsets easily. In stark contrast to the classical framework, constructive set theories may be closed under the rule that any property that is decidable for all sets is already equivalent to ${\displaystyle \top }$ or ${\displaystyle \bot }$. Also the real line may be taken to be indecomposable in this sense. Undecidability of disjunctions also affects the claims about total orders such as that of all ordinal numbers, expressed by the provability and rejection of the clauses in the order defining disjunction ${\displaystyle (\alpha \in \beta )\lor (\alpha =\beta )\lor (\beta \in \alpha )}$. This determines whether the relation is trichotomous. A weakened theory of ordinals in turn affects the proof theoretic strength defined in ordinal analysis.

In exchange, constructive set theories can exhibit attractive disjunction and existence properties, as is familiar from the study of constructive arithmetic theories. These are features of a fixed theory which metalogically relate judgements of propositions provable in the theory. Particularly well-studied are those such features that can be expressed in Heyting arithmetic, with quantifiers over numbers and which can often be realized by numbers, as formalized in proof theory. In particular, those are the numerical existence property and the closely related disjunctive property, as well as being closed under Church's rule, witnessing any given function to be computable.[1]

A set theory does not only express theorems about numbers, and so one may consider a more general so-called strong existence property that is harder to come by, as will be discussed. A theory has this property if the following can be established: For any property ${\displaystyle \phi }$, if the theory proves that a set exist that has that property, i.e. if the theory claims the existence statement, then there is also a property ${\displaystyle \psi }$ that uniquely describes such a set instance. More formally, for any predicate ${\displaystyle \phi }$ there is a predicate ${\displaystyle \psi }$ so that

${\displaystyle {\mathsf {T}}\vdash \exists x.\phi (x)\implies {\mathsf {T}}\vdash \exists !x.\phi (x)\land \psi (x)}$

The role analogous to that of realized numbers in arithmetic is played here by defined sets proven to exist according to the theory, and so this is a subtle question concerning term construction and the theories strength. While many theories discussed tend have all the various numerical properties, the existence property can easily be spoiled, as will be discussed. Weaker forms of existence properties have been formulated.

Some classical theories can in fact also be constrained so as to exhibit the strong existence property. Zermelo–Fraenkel set theory ${\displaystyle {\mathsf {ZF}}}$ with the constructible universe postulate, ${\displaystyle {\mathsf {ZF}}+({\mathrm {V} }={\mathrm {L} })}$, or ${\displaystyle {\mathsf {ZF}}}$ with sets all taken to be ordinal-definable, ${\displaystyle {\mathsf {ZF}}+({\mathrm {V} }={\mathrm {OD} })}$, do have the existence property. For contrast, consider the theory ${\displaystyle {\mathsf {ZFC}}}$ given by ${\displaystyle {\mathsf {ZF}}}$ plus the full axiom of choice existence postulate. Recall that this collection of axioms proves the well-ordering theorem, implying well-orderings exists for any set. In particular, this means that relations ${\displaystyle W\subset {\mathbb {R} }\times {\mathbb {R} }}$ formally exist that establish the well-ordering of ${\displaystyle {\mathbb {R} }}$ (i.e. the theory claims the existence of a least element for all subsets of ${\displaystyle {\mathbb {R} }}$ with respect to those relations). This is despite the fact that definability of such an ordering is known to be independent of ${\displaystyle {\mathsf {ZFC}}}$. The latter implies that for no particular formula ${\displaystyle \psi }$ in the language of the theory does the theory prove that the corresponding set is a well-ordering relation of the reals. So ${\displaystyle {\mathsf {ZFC}}}$ formally proves the existence of a subset ${\displaystyle W\subset {\mathbb {R} }\times {\mathbb {R} }}$ with the property of being a well-ordering relation, but at the same time no particular set ${\displaystyle W}$ for which the property could be validated can possibly be defined.

#### Anti-classical principles

To motivate the discussion, here one must carefully distinguish between provable implications between two propositions, ${\displaystyle {\mathsf {T}}\vdash P\to Q}$, and metalogical properties of the form ${\displaystyle {\mathsf {T}}\vdash P\implies {\mathsf {T}}\vdash Q}$. For an example of the latter that was mentioned above, a constructive theory ${\displaystyle {\mathsf {T}}}$ may exhibit the numerical existence property, ${\displaystyle {\mathsf {T}}\vdash \exists e.\psi (e)\implies {\mathsf {T}}\vdash \psi ({\underline {\mathrm {e} }})}$, for some number ${\displaystyle {\mathrm {e} }}$ and where ${\displaystyle {\underline {\mathrm {e} }}}$ denotes the corresponding numeral in the formal theory. More broadly, a situation commonly studied is that of a fixed ${\displaystyle {\mathsf {T}}}$ exhibiting the meta-theoretical property of the following type: For an instance from some collection of formulas, here captured via ${\displaystyle \phi }$ and ${\displaystyle \psi }$, one established the existence of a number ${\displaystyle {\mathrm {e} }}$ so that ${\displaystyle {\mathsf {T}}\vdash \phi \implies {\mathsf {T}}\vdash \psi ({\underline {\mathrm {e} }})}$. When adopting any such schema as an inference rule and nothing new can be proven, one says the theory ${\displaystyle {\mathsf {T}}}$ is closed under that rule.

Coming back to just ${\displaystyle {\mathsf {T}}}$, adjoining the excluded middle principle ${\displaystyle {\mathrm {PEM} }}$ to ${\displaystyle {\mathsf {T}}}$, the theory obtained in that way may prove new, strictly classical statements for some ${\displaystyle \phi }$, and this may spoil the meta-theoretical property that was previously established for ${\displaystyle {\mathsf {T}}}$. One may instead consider adjoining the rule corresponding to the meta-theoretical property as an implication (in the sense of "${\displaystyle \to }$") to ${\displaystyle {\mathsf {T}}}$, as a schema or in quantified form. That is to say, to postulate that any such ${\displaystyle \phi }$ implies ${\displaystyle \exists (e\in {\mathbb {N} })}$ such that ${\displaystyle \psi (e)}$ holds, where the bound ${\displaystyle e}$ is a number variable in language of the theory. The new theory with the principle added might be anti-classical, in that it may not be consistent anymore to also adopt ${\displaystyle {\mathrm {PEM} }}$. To name an example for this circumstance: Church's rule is an admissible rule in first-order Heyting arithmetic ${\displaystyle {\mathsf {HA}}}$ and the corresponding Church's thesis principle ${\displaystyle {\mathrm {CT} }_{0}}$ may be adopted. The same is not possible in ${\displaystyle {\mathsf {HA}}+{\mathrm {PEM} }}$, also known as Peano arithmetic ${\displaystyle {\mathsf {PA}}}$.

The focus in this subsection shall be on set theories with quantification over a fully formal notion of an infinite sequences space, i.e. function space, as it will be introduced further below. A translation of Church's rule into the language of the theory itself may then read

${\displaystyle \forall (f\in {\mathbb {N} }^{\mathbb {N} }).\exists (e\in {\mathbb {N} }).{\Big (}\forall (n\in {\mathbb {N} }).\exists (w\in {\mathbb {N} }).T(e,n,w)\land U(w,f(n)){\Big )}}$

Kleene's T predicate together with the result extraction expresses that any input number ${\displaystyle n}$ being mapped to the number ${\displaystyle f(n)}$ is, through ${\displaystyle w}$, witnessed to be a computable mapping. Here ${\displaystyle {\mathbb {N} }}$ now denotes a set theory model of the standard natural numbers and ${\displaystyle e}$ is an index with respect to a fixed program enumeration. Stronger variants have been used, which extend this principle to functions ${\displaystyle f\in {\mathbb {N} }^{X}}$ defined on domains ${\displaystyle X\subset {\mathbb {N} }}$ of low complexity. The principle rejects decidability for the predicate ${\displaystyle Q(e)}$ defined as ${\displaystyle \exists (w\in {\mathbb {N} }).T(e,e,w)}$, expressing that ${\displaystyle e}$ is the index of a computable function halting on its own index. Weaker, double negated forms of the principle may be considered too, which do not require the existence of a recursive implementation for every ${\displaystyle f}$, but which still make principles inconsistent that claim the existence of functions which provenly have no recursive realization. Some forms of a Church's thesis as principle are even consistent with the weak classical second order arithmetic ${\displaystyle {\mathsf {RCA}}_{0}}$.

The collection of computable functions is classically subcountable, which classically is the same as being countable. But classical set theories will generally claim that ${\displaystyle {\mathbb {N} }^{\mathbb {N} }}$ holds also other functions than the computable ones. For example there is a proof in ${\displaystyle {\mathsf {ZF}}}$ that total functions (in the set theory sense) do exist that cannot be captured by a Turing machine. Taking the computable world seriously as ontology, a prime example of an anti-classical conception related the Markovian school is the permitted subcountability of various uncountable collections. Adopting the subcountability of the collection of all unending sequences of natural numbers (${\displaystyle {\mathbb {N} }^{\mathbb {N} }}$) as an axiom in a constructive theory, the "smallness" (in classical terms) of this collection, in some set theoretical realizations, is then already captured by the theory itself. A constructive theory may also adopt neither classical nor anti-classical axioms and so stay agnostic towards either possibility.

Constructive principles already prove ${\displaystyle \forall (x\in X).\neg \neg {\big (}Q(x)\lor \neg Q(x){\big )}}$ for any ${\displaystyle Q}$. And so for any given element ${\displaystyle x}$ of ${\displaystyle X}$, the corresponding excluded middle statement for the proposition cannot be negated. Indeed, for any given ${\displaystyle x}$, by noncontradiction it is impossible to rule out ${\displaystyle Q(x)}$ and rule out its negation both at once, and the relevant De Morgan's rule applies as above. But a theory may in some instances also permit the rejection claim ${\displaystyle \neg \forall (x\in X).{\big (}Q(x)\lor \neg Q(x){\big )}}$. Adopting this does not necessitate providing a particular ${\displaystyle t\in X}$ witnessing the failure of excluded middle for the particular proposition ${\displaystyle Q(t)}$, i.e. witnessing the inconsistent ${\displaystyle \neg {\big (}Q(t)\lor \neg Q(t){\big )}}$. Predicates ${\displaystyle Q(x)}$ on an infinite domain ${\displaystyle X}$ correspond to decision problems. Motivated by provenly computably undecidable problems, one may reject the possibility of decidability of a predicate without also making any existence claim in ${\displaystyle X}$. As another example, such a situation is enforced in Brouwerian intuitionistic analysis, in a case where the quantifier ranges over infinitely many unending binary sequences and ${\displaystyle Q(x)}$ states that a sequence ${\displaystyle x}$ is everywhere zero. Concerning this property, of being conclusively identified as the sequence which is forever constant, adopting Brouwer's continuity principle strictly rules out that this could be proven decidable for all the sequences.

So in a constructive context with a so-called non-classical logic as used here, one may consistently adopt axioms which are both in contradiction to quantified forms of excluded middle, but also non-constructive in the computable sense or as gauged by meta-logical existence properties discussed previously. In that way, a constructive set theory can also provide the framework to study non-classical theories.

### History and overview

Historically, the subject of constructive set theory (often also "${\displaystyle {\mathsf {CST}}}$") begun with John Myhill's work on the theories also called ${\displaystyle {\mathsf {IZF}}}$ and ${\displaystyle {\mathsf {CST}}}$.[2] In 1973, he had proposed the former as a first-order set theory based on intuitionistic logic, taking the most common foundation ${\displaystyle {\mathsf {ZFC}}}$ and throwing out the Axiom of choice as well as the principle of the excluded middle, initially leaving everything else as is. However, different forms of some of the ${\displaystyle {\mathsf {ZFC}}}$ axioms which are equivalent in the classical setting are inequivalent in the constructive setting, and some forms imply ${\displaystyle {\mathrm {PEM} }}$, as will be demonstrated. In those cases, the intuitionistically weaker formulations were consequently adopted. The far more conservative system ${\displaystyle {\mathsf {CST}}}$ is also a first-order theory, but of several sorts and bounded quantification, aiming to provide a formal foundation for Errett Bishop's program of constructive mathematics.

The main discussion presents sequence of theories in the same language as ${\displaystyle {\mathsf {ZF}}}$, leading up to Peter Aczel's well studied ${\displaystyle {\mathsf {CZF}}}$,[3] and beyond. Many modern results trace back to Rathjen and his students. ${\displaystyle {\mathsf {CZF}}}$ is also characterized by the two features present also in Myhill's theory: On the one hand, it is using the Predicative Separation instead of the full, unbounded Separation schema, see also Lévy hierarchy. Boundedness can be handled as a syntactic property or, alternatively, the theories can be conservatively extended with a higher boundedness predicate and its axioms. Secondly, the impredicative Powerset axiom is discarded, generally in favor of related but weaker axioms. The strong form is very casually used in classical general topology. Adding ${\displaystyle {\mathrm {PEM} }}$ to a theory even weaker than ${\displaystyle {\mathsf {CZF}}}$ recovers ${\displaystyle {\mathsf {ZF}}}$, as detailed below.[4] The system, which has come to be known as Intuitionistic Zermelo–Fraenkel set theory (${\displaystyle {\mathsf {IZF}}}$), is a strong set theory without ${\displaystyle {\mathrm {PEM} }}$. It is similar to ${\displaystyle {\mathsf {CZF}}}$, but less conservative or predicative. The theory denoted ${\displaystyle {\mathsf {IKP}}}$ is the constructive version of ${\displaystyle {\mathsf {KP}}}$, the classical Kripke–Platek set theory without a form of Powerset and where even the Axiom of Collection is bounded.

#### Models

Many theories studied in constructive set theory are mere restrictions of Zermelo–Fraenkel set theory (${\displaystyle {\mathsf {ZF}}}$) with respect to their axiom as well as their underlying logic. Such theories can then also be interpreted in any model of ${\displaystyle {\mathsf {ZF}}}$.

For a set theory context without infinite sets, constructive first-order arithmetic can also be taken as an apology for most axioms adopted in ${\displaystyle {\mathsf {CZF}}}$: The arithmetic theory ${\displaystyle {\mathsf {HA}}}$ is bi-interpretable with a weak constructive set theory,[5] as also described in the article on Heyting arithmetic. One may arithmetically characterize a membership relation "${\displaystyle \in }$" and with it prove - instead of the existence of a set of natural numbers ${\displaystyle \omega }$ - that all sets in its theory are in bijection with a (finite) von Neumann natural, a principle denoted ${\displaystyle {\mathrm {V} }={\mathrm {Fin} }}$. This context further validates Extensionality, Pairing, Union, Binary Intersection (which is related to the Axiom schema of predicative separation) and the Set Induction schema. Taken as axioms, the aforementioned principles constitute a set theory that is already identical with the theory given by ${\displaystyle {\mathsf {CZF}}}$ minus the existence of ${\displaystyle \omega }$ but plus ${\displaystyle {\mathrm {V} }={\mathrm {Fin} }}$ as axiom. All those axioms are discussed in detail below. Relatedly, ${\displaystyle {\mathsf {CZF}}}$ also proves that the hereditarily finite sets fulfill all the previous axioms. This is a result which persists when passing on to ${\displaystyle {\mathsf {PA}}}$ and ${\displaystyle {\mathsf {ZF}}}$ minus Infinity.

As far as constructive realizations go there is a relevant realizability theory. Relatedly, Aczel's theory constructive Zermelo-Fraenkel ${\displaystyle {\mathsf {CZF}}}$ has been interpreted in a Martin-Löf type theories, as sketched in the section on ${\displaystyle {\mathsf {CZF}}}$. In this way, theorems provable in this and weaker set theories are candidates for a computer realization.

More recently, presheaf models for constructive set theories have been introduced. These are analogous to presheaf models for intuitionistic set theory developed by Dana Scott in the 1980s.[6][7] Realizability models of ${\displaystyle {\mathsf {CZF}}}$ within the effective topos have been identified, which, say, at once validate full Separation and Markov's principle ${\displaystyle {\mathrm {MP} }}$, as well as relativized dependent choice ${\displaystyle {\mathrm {RDC} }}$, but also the subcountability of all sets and Church's thesis ${\displaystyle {\mathrm {CT} _{0}}}$ in the formulation for all predicates.[8]

## Subtheories of ZF

### Notation

#### Language

The propositional connective symbols used to form syntactic formulas are standard. The axioms of set theory give a means to prove equality "${\displaystyle =}$" of sets and that symbol may, by abuse of notation, be used for classes. Negation "${\displaystyle \neg }$" of elementhood "${\displaystyle \in }$" is often written "${\displaystyle \notin }$", and usually the same goes for non-equality "${\displaystyle \neq }$". However, in a context with apartness relations, for example when dealing with sequences, the latter symbol is also used for something different.

#### Variables

Below the Greek ${\displaystyle \phi }$ denotes a proposition or predicate variable in axiom schemas and ${\displaystyle P}$ or ${\displaystyle Q}$ is used for particular such predicates. The word "predicate" is sometimes used interchangeably with "formulas" as well, even in the unary case.

Quantifiers range over sets and those are denoted by lower case letters. As is common, one may use argument brackets to express predicates, for the sake of highlighting particular free variables in their syntactic expression, as in "${\displaystyle Q(z)}$".

One abbreviates ${\displaystyle \forall z.{\big (}z\in A\to Q(z){\big )}}$ by ${\displaystyle \forall (z\in A).Q(z)}$ and ${\displaystyle \exists z.{\big (}z\in A\land Q(z){\big )}}$ by ${\displaystyle \exists (z\in A).Q(z)}$. The syntactic notion of bounded quantification in this sense can play a role in the formulation of axiom schemas, as seen below.

Two ways to express disjointness capture many of the intuitionistically valid negation rules: ${\displaystyle {\big (}\forall (x\in A).x\notin B{\big )}\leftrightarrow \neg \exists (x\in A).x\in B}$. Using the above notation, this is a purely logical equivalence and below the proposition will furthermore be expressible as ${\displaystyle A\cap B=\{\}}$.

Express the subclass claim ${\displaystyle \forall (z\in A).z\in B}$, i.e. ${\displaystyle \forall z.(z\in A\to z\in B)}$, by ${\displaystyle A\subset B}$. The similar notion of subset-bounded quantifiers, as in ${\displaystyle \forall (z\subset A).z\in B}$, has been used in set theoretical investigation as well, but will not be further highlighted here.

Unique existence ${\displaystyle \exists !x.Q(x)}$ here means ${\displaystyle \exists x.\forall y.{\big (}y=x\leftrightarrow Q(y){\big )}}$.

If there provenly exists a set inside a class, meaning ${\displaystyle \exists z.(z\in A)}$, then one calls it inhabited. One may also use quantification in ${\displaystyle A}$ to express this as ${\displaystyle \exists (z\in A).(z=z)}$. The class ${\displaystyle A}$ is then provenly not the empty set, introduced below. While classically equivalent, constructively non-empty is a weaker notion with two negations and ought to be called not uninhabited. Unfortunately, the word for the more useful notion of 'inhabited' is rarely used in classical mathematics.

#### Classes

As is also common in the study of set theories, one makes use set builder notation for classes, which, in most contexts, are not part of the object language but used for concise discussion. In particular, one may introduce notation declarations of the corresponding class via "${\displaystyle A=\{z\mid Q(z)\}}$", for the purpose of expressing ${\displaystyle Q(a)}$ as ${\displaystyle a\in A}$. Logically equivalent predicates can be used to introduce the same class. One also writes ${\displaystyle \{z\in B\mid Q(z)\}}$ as shorthand for ${\displaystyle \{z\mid z\in B\land Q(z)\}}$. For example, one may consider ${\displaystyle \{z\in B\mid z\notin C\}}$ and this is also denoted ${\displaystyle B\setminus C}$. Further extensions of such notation are in common used in set theory, giving meaning to statements like "${\displaystyle \{f(z)\mid Q(z)\}=\{\langle x,y\rangle \mid R(x,y)\}}$", and so on.

For a predicate ${\displaystyle Q}$, trivially ${\displaystyle \forall z.{\big (}(z\in B\land Q(z))\to z\in B{\big )}}$. And so follows that ${\displaystyle \{z\in B\mid Q(z)\}\subset B}$.

Through the use of a 2-ary predicate ${\displaystyle R}$, a set ${\displaystyle w}$ may be characterized as ${\displaystyle x\in w\leftrightarrow R(x,w)}$ holding for all ${\displaystyle x}$, where the right hand side may depend on the actual variable ${\displaystyle w}$, and possibly even on membership in ${\displaystyle w}$ itself. The convenient notational relation between ${\displaystyle x\in A}$ and ${\displaystyle Q(x)}$ functions akin to a simpler, special case of this.

### Equality

Denote by ${\displaystyle A\simeq B}$ the statement expressing that two classes have exactly the same elements, i.e. ${\displaystyle \forall z.(z\in A\leftrightarrow z\in B)}$, or equivalently ${\displaystyle (A\subset B)\land (B\subset A)}$. This is not to be conflated with the concept of equinumerosity also used below.

The following axiom gives a means to prove equality "${\displaystyle =}$" of two sets, so that through substitution, any predicate about ${\displaystyle x}$ translates to one of ${\displaystyle y}$.

 ${\displaystyle \forall x.\forall y.\ \ x\simeq y\to x=y}$

By the logical properties of equality, the converse direction holds automatically.

In a constructive interpretation, the elements of a subclass ${\displaystyle A=\{z\in B\mid Q(z)\lor \neg Q(z)\}}$ of ${\displaystyle B}$ may come equipped with more information than those of ${\displaystyle B}$, in the sense that being able to judge ${\displaystyle b\in A}$ is being able to judge ${\displaystyle Q(b)\lor \neg Q(b)}$. And (unless the whole disjunction follows from axioms) in the Brouwer–Heyting–Kolmogorov interpretation, this means to have proven ${\displaystyle Q(b)}$ or having rejected it. As ${\displaystyle Q}$ may be not decidable for all elements in ${\displaystyle B}$, the two classes must a priori be distinguished.

Consider a predicate ${\displaystyle Q}$ that provenly holds for all elements of a set ${\displaystyle y}$, so that ${\displaystyle \{z\in y\mid Q(z)\}\simeq y}$, and assume that the class on the left hand side is established to be a set. Note that, even if this set on the left informally also ties to proof-relevant information about the validity of ${\displaystyle Q}$ for all the elements, the Extensionality axiom postulates that, in our set theory, the set on the left hand side is judged equal to the one on the right hand side. While often adopted, this axiom has been criticized in constructive thought, as it effectively collapses differently defined properties, or at least the sets viewed as the extension of these properties, a Fregian notion.

Modern type theories may instead aim at defining the demanded equivalence "${\displaystyle \simeq }$" in terms of functions, see e.g. type equivalence. The related concept of function extensionality is often not adopted in type theory.

Other frameworks for constructive mathematics might instead demand a particular rule for equality or apartness come for the elements ${\displaystyle z\in x}$ of each and every set ${\displaystyle x}$ discussed. Even then, the above definition can be used to characterize equality of subsets ${\displaystyle u\subset x}$ and ${\displaystyle v\subset x}$. Note that adopting "${\displaystyle =}$" as a symbol in a predicate logic theory makes equality of two terms a quantifier-free expression.

### Merging sets

Define class notation for a few given elements via disjunctions, e.g. ${\displaystyle c\in \{a,b\}}$ says ${\displaystyle (c=a)\lor (c=b)}$. Denote by ${\displaystyle \langle x,y\rangle }$ the standard ordered pair model ${\displaystyle \{\{x\},\{x,y\}\}}$, so that e.g. ${\displaystyle q=\langle x,y\rangle }$ denotes another bounded formula in the formal language of the theory.

Two other basic axioms are as follows. Firstly,

 ${\displaystyle \forall x.\forall y.\ \ \exists p.\forall z.{\big (}(z=x\lor z=y)\to z\in p{\big )}}$

saying that for any two sets ${\displaystyle x}$ and ${\displaystyle y}$, there is at least one set ${\displaystyle p}$, which hold at least those two sets (${\displaystyle z}$).

And then,

 ${\displaystyle \forall x.\ \ \exists u.\forall y.{\big (}(\exists z.y\in z\land z\in x)\to y\in u{\big )}}$

saying that for any set ${\displaystyle x}$, there is at least one set ${\displaystyle u}$, which holds all members ${\displaystyle y}$, of ${\displaystyle x}$'s members ${\displaystyle z}$. The minimal such set is the union. With predicative Separation below, the two axioms together imply the existence of a binary union of two classes ${\displaystyle a}$ and ${\displaystyle b}$, when they have been established to be sets, denoted by ${\displaystyle \bigcup \{a,b\}}$ or ${\displaystyle a\cup b}$. The two axioms may also be formulated stronger in terms of "${\displaystyle \leftrightarrow }$". In the context of ${\displaystyle {\mathsf {BCST}}}$ this is not necessary.

For a fixed set ${\displaystyle y}$, to validate membership ${\displaystyle y\in a\cup b}$ in the union of two given sets ${\displaystyle z=a}$ and ${\displaystyle z=b}$, one needs to validate the ${\displaystyle y\in z}$ part of the axiom, which can be done by validating the disjunction of the predicates defining the sets ${\displaystyle a}$ and ${\displaystyle b}$, for ${\displaystyle y}$. In terms of the associated sets, it is done by validating the disjunction ${\displaystyle y\in a\lor y\in b}$.

The notation is also used for classes. Let ${\displaystyle B\subset A}$. Given ${\displaystyle y\in A}$, the decidability of membership in ${\displaystyle B}$, i.e. the potentially independent statement ${\displaystyle y\in B\lor y\notin B}$, can also be expressed as ${\displaystyle y\in B\cup (A\setminus B)}$. This goes to show that partitioning is also a more involved notion, constructively. But as for any excluded middle statement, ${\displaystyle B\cup (A\setminus B)}$ is not uninhabited by ${\displaystyle y}$.

### Set existence

The property that is false for any set corresponds to the empty class, which is denoted by ${\displaystyle \{\}}$ or zero, ${\displaystyle 0}$. That the empty class is a set readily follows from other axioms, such as the Axiom of Infinity below. But if, e.g., one is explicitly interested in excluding infinite sets in one's study, one may at this point adopt the

 ${\displaystyle \exists x.\forall y.\,\neg (y\in x)}$

Introduction of the symbol ${\displaystyle \{\}}$ (as abbreviating notation for expressions in involving characterizing properties) is justified as uniqueness for this set can be proven.

For a set ${\displaystyle x}$, define the successor set ${\displaystyle Sx}$ as ${\displaystyle x\cup \{x\}}$ and write ${\displaystyle 1}$ for ${\displaystyle S0}$. Its interplay with the membership relation has a recursive clause, in the sense that ${\displaystyle (y\in Sx)\leftrightarrow (y\in x\lor y=x)}$. By reflexivity of equality, ${\displaystyle x\in Sx}$, and in particular ${\displaystyle Sx}$ is always inhabited. A sort of blend between pairing and union, an axiom more readily related to the successor is the Axiom of adjunction.[9][10] This is all relevant for the standard modeling of individual Neumann ordinals.

A simple and provenly false proposition then is, for example, ${\displaystyle \{\}\in \{\}}$, corresponding to ${\displaystyle 0<0}$ in the standard arithmetic model. Again, here symbols such as ${\displaystyle \{\}}$ are treated as convenient notation and any proposition really translates to an expression using only "${\displaystyle \in }$" and logical symbols, including quantifiers. Accompanied by a metamathematical analysis that the capabilities of the new theories are equivalent in an effective manner, formal extensions by symbols such as ${\displaystyle 0}$ may also be considered.

### BCST

The following makes use of axiom schemas, i.e. axioms for some collection of predicates. Some of the stated axiom schemas shall allow for any collection of set parameters as well (meaning any particular named variables ${\displaystyle v_{0},v_{1},\dots ,v_{n}}$). That is, instantiations of the schema are permitted in which the predicate (some particular ${\displaystyle \phi }$) also depends on a number of further set variables and the statement of the axiom is understood with corresponding extra outer universal closures (as in ${\displaystyle \forall v_{0}.\forall v_{1}.\cdots \forall v_{n}.}$).

#### Separation

Basic constructive set theory ${\displaystyle {\mathsf {BCST}}}$ consists of several axioms also part of standard set theory, except the Separation axiom is weakened. Beyond the four axioms above, it the Predicative Separation as well as the Replacement schema.

 Axiom schema of predicative separation: For any bounded predicate ${\displaystyle \phi }$, with parameters and with set variable ${\displaystyle y}$ not free in it, ${\displaystyle \forall y.\,\exists s.\forall x.{\big (}x\in s\,\leftrightarrow \,(x\in y\land \phi (x)){\big )}}$

This axiom amounts to postulating the existence of a set ${\displaystyle s}$ obtained by the intersection of any set ${\displaystyle y}$ and any predicatively described class ${\displaystyle \{x\mid \phi (x)\}}$. When the predicate is taken as ${\displaystyle x\in z}$ for ${\displaystyle z}$ proven to be a set, one obtains the binary intersection of sets and writes ${\displaystyle s=y\cap z}$. Intersection corresponds to conjunction in an analog way to how union corresponds to disjunction.

As noted, from Separation and the existence of at least one set (e.g. Infinity below) and a predicate that is false of any set, like ${\displaystyle \neg (x=x)}$, will follow the existence of the empty set ${\displaystyle \{\}}$ (also denoted ${\displaystyle 0}$). Within this conservative context of ${\displaystyle {\mathsf {BCST}}}$, the Bounded Separation schema is actually equivalent to Empty Set plus the existence of the binary intersection for any two sets. The latter variant of axiomatization does not make use of a formula schema.

For a proposition ${\displaystyle P}$, a recurring trope in the constructive analysis of set theory is to view the predicate ${\displaystyle x=0\land P}$ as the subclass ${\displaystyle B:=\{x\in 1\mid P\}}$ of the second ordinal ${\displaystyle 1:=S0=\{0\}}$. If it is provable that ${\displaystyle P}$ holds, or ${\displaystyle \neg P}$, or ${\displaystyle \neg \neg P}$, then ${\displaystyle B}$ is inhabited, or empty (uninhabited), or non-empty (not uninhabited), respectively. Clearly, ${\displaystyle P}$ is equivalent to the proposition ${\displaystyle 0\in B}$ (in the model of the naturals this means ${\displaystyle 0}$ being smaller than ${\displaystyle B}$ because, equivalently, ${\displaystyle B=1}$), while ${\displaystyle \neg P}$ is equivalent to ${\displaystyle B=0}$ (so that, equivalently, ${\displaystyle \neg (0\in B)}$). The union that is part of the successor operation definition above may be used to express the excluded middle statement ${\displaystyle P\lor \neg P}$ as ${\displaystyle 0\in SB}$. In words, ${\displaystyle P}$ is decidable if and only if the successor of ${\displaystyle B}$ is larger than the smallest ordinal ${\displaystyle 0}$. The proposition ${\displaystyle P}$ is decided either way through establishing how ${\displaystyle 0}$ is smaller: By ${\displaystyle 0}$ already being smaller than ${\displaystyle B}$, or by ${\displaystyle 0}$ being ${\displaystyle SB}$'s direct predecessor. Another way to express excluded middle for ${\displaystyle P}$ is as the existence of a least number member of the inhabited class ${\displaystyle b:=B\cup \{1\}}$. If ones separation axiom allows for separation with ${\displaystyle P}$, then ${\displaystyle B}$ is a subset, which may be called the truth value associated with ${\displaystyle P}$. Two truth values can be proven equal, as sets, by proving an equivalence. In terms of this terminology, the collection of proof values can a priori understood to be rich. Unsurprisingly, decidable propositions have one of a binary set of truth values.

The axiom schema of Predicative Separation is also called Bounded Separation, as in Separation for set-bounded quantifiers only. The scope of specified subsets that can be proven to exist is enriched with further set existence postulate. Bounded Separation is a schema that takes into account syntactic aspects of set defining predicates, up to provable equivalence. The permitted formulas are denoted by ${\displaystyle \Delta _{0}}$ in the set theoretical Lévy hierarchy, in analogy to ${\displaystyle \Delta _{0}^{0}}$ in the arithmetical hierarchy. (Note however that the arithmetic classification is sometimes expressed not syntactically but in terms of subclasses of the naturals. Also, the bottom level of the arithmetical hierarchy has several common definitions, some not allowing the use of some total functions. The distinction is not relevant on the level ${\displaystyle \Sigma _{1}^{0}}$ or higher. Finally note that a ${\displaystyle \Delta _{0}}$ classification of a formula may be expressed up to equivalence in the theory.)

The schema is also the way in which Mac Lane weakens a system close to Zermelo set theory ${\displaystyle {\mathsf {Z}}}$, for mathematical foundations related to topos theory. See also Kripke-Platek set theory.

#### No universal set

By a remark in the section on merging sets, a set cannot consistently ruled out to be a member of a class of the form ${\displaystyle A\cup \{x\mid x\notin A\}}$. A constructive proof that it is in that class contains information. Now if ${\displaystyle A}$ is a set, then the class on the right is not a set. The following demonstrates this in the special case when ${\displaystyle A}$ is empty, i.e. when the right side is the universal class.

The following holds for any relation ${\displaystyle E}$, giving a purely logical condition by which two terms ${\displaystyle s}$ and ${\displaystyle y}$ non-relatable

${\displaystyle \forall x.{\big (}xEs\leftrightarrow (xEy\land \neg xEx){\big )}\to \neg (yEs\lor sEs\lor sEy)}$

The expression ${\displaystyle \neg (x\in x)}$ is a bounded one and thus allowed in separation. By virtue of the rejection of the final disjunct above, ${\displaystyle \neg sEy}$, Russel's construction shows that ${\displaystyle \{x\in y\mid x\notin x\}\notin y}$. So for any set ${\displaystyle y}$, Predicative Separation alone implies that there exists a set which is not a member of ${\displaystyle y}$. In particular, no universal set can exist in this theory.

In a theory with the axiom of regularity, like ${\displaystyle {\mathsf {ZF}}}$, of course that subset ${\displaystyle \{x\in y\mid x\notin x\}}$ can be proven to be equal to ${\displaystyle y}$ itself. As an aside, in a theory with stratification, a universal set may exist because use of the syntactic expression ${\displaystyle x\in x}$ may be disallowed in proofs of existence by, essentially, separation.

#### Predicativity

The restriction in the axiom is also gatekeeping impredicative definitions: Existence should at best not be claimed for objects that are not explicitly describable, or whose definition involves themselves or reference to a proper class, such as when a property to be checked involves a universal quantifier. So in a constructive theory without Axiom of power set, when ${\displaystyle R}$ denotes some 2-ary predicate, one should not generally expect a subclass ${\displaystyle s}$ of ${\displaystyle y}$ to be a set, in case that it is defined, for example, as in

${\displaystyle \{x\in y\mid \forall t.{\big (}(t\subset y)\to R(x,t){\big )}\}}$,

or via a similar definitions involving any quantification over the sets ${\displaystyle t\subset y}$. Note that if this subclass ${\displaystyle s}$ of ${\displaystyle y}$ is provenly a set, then this subset itself is also in the unbounded scope of set variable ${\displaystyle t}$. In other words, as the subclass property ${\displaystyle s\subset y}$ is fulfilled, this exact set ${\displaystyle s}$, defined using the expression ${\displaystyle R(x,s)}$, would play a role in its own characterization.

While predicative Separation leads to fewer given class definitions being sets, it must be emphasized that many class definitions that are classically equivalent are not so when restricting oneself to constructive logic. So in this way, one gets a broader theory, constructively. Due to the potential undecidability of general predicates, the notion of subset and subclass is more elaborate in constructive set theories than in classical ones. This remains true if full Separation is adopted, as in the theory ${\displaystyle {\mathsf {IZF}}}$, which however spoils the existence property as well as the standard type theoretical interpretations, and in this way spoils a bottom-up view of constructive sets. As an aside, as subtyping is not a necessary feature of constructive type theory, constructive set theory can be said to quite differ from that framework.

#### Replacement

Next consider the

 Axiom schema of Replacement: For any predicate ${\displaystyle \phi }$ with set variable ${\displaystyle r}$ not free in it, ${\displaystyle \forall d.\ \ \forall (x\in d).\exists !y.\phi (x,y)\to \exists r.\forall y.{\big (}y\in r\leftrightarrow \exists (x\in d).\phi (x,y){\big )}}$

It is granting existence, as sets, of the range of function-like predicates, obtained via their domains. In the above formulation, the predicate is not restricted akin to the Separation schema, but this axiom already involves an existential quantifier in the antecedent. Of course, weaker schemas could be considered as well.

With the Replacement schema, this theory proves that the equivalence classes or indexed sums are sets. In particular, the Cartesian product, holding all pairs of elements of two sets, is a set. Equality of elements inside a set ${\displaystyle x}$ is decidable if the corresponding relation as a subset of ${\displaystyle x\times x}$ is decidable.

Replacement is not necessary in the design of a weak constructive set theory that is bi-interpretable with Heyting arithmetic ${\displaystyle {\mathsf {HA}}}$. However, some form of induction is. Replacement together with Set Induction (introduced below) also suffices to axiomize hereditarily finite sets constructively and that theory is also studied without Infinity. For comparison, consider the very weak classical theory called General set theory that interprets the class of natural numbers and their arithmetic via just Extensionality, Adjunction and full Separation.

Replacement is relevant for function comprehension can be seen as a form of comprehension more generally. Only when assuming ${\displaystyle {\mathrm {PEM} }}$ does Replacement already imply full Separation. In ${\displaystyle {\mathsf {ZF}}}$, Replacement is mostly important to prove the existence of sets of high rank, namely via instances of the axiom schema where ${\displaystyle \phi (x,y)}$ relates relatively small set ${\displaystyle x}$ to bigger ones, ${\displaystyle y}$.

Constructive set theories commonly have Axiom schema of Replacement, sometimes restricted to bounded formulas. However, when other axioms are dropped, this schema is actually often strengthened - not beyond ${\displaystyle {\mathsf {ZF}}}$, but instead merely to gain back some provability strength. Such stronger axioms exist that do not spoil the strong existence properties of a theory, as discussed further below.

The discussion now proceeds with axioms granting existence of objects which, in different but related form, are also found in dependent type theories, namely products and the collection of natural numbers as a completed set. Infinite sets are particularly handy to reason about operations applied to sequences defined on unbounded domains, say the formal differentiation of a generating function or the addition of two Cauchy sequences.

### ECST

For some fixed predicate ${\displaystyle I}$ and a set ${\displaystyle a}$, the statement ${\displaystyle I(a)\land {\big (}\forall y.I(y)\to a\subset y{\big )}}$ expresses that ${\displaystyle a}$ is the smallest (in the sense of "${\displaystyle \subset }$") among all sets ${\displaystyle y}$ for which ${\displaystyle I(y)}$ holds true, and that it is always a subset of such ${\displaystyle y}$. The aim of the axiom of infinity is to eventually obtain unique smallest inductive set.

In the context of common set theory axioms, one statement of infinitude is to state that a class is inhabited and also includes a chain of membership (or alternatively a chain of supersets). That is,

${\displaystyle \exists z.(z\in A)\land \forall (x\in A).\exists (s\in A).x\in s}$.

More concretely, denote by ${\displaystyle \mathrm {Ind} _{A}}$ the inductive property,

${\displaystyle (0\in A)\land \forall (x\in A).Sx\in A}$.

In terms of a predicate ${\displaystyle Q}$ underlying the class so that ${\displaystyle \forall x.(x\in A)\leftrightarrow Q(x)}$, the latter translates to ${\displaystyle Q(0)\land \forall x.{\big (}Q(x)\to Q(Sx){\big )}}$.

Write ${\displaystyle \bigcap B}$ for the general intersection ${\displaystyle \{x\mid \forall (y\in B).x\in y\}}$. (A variant of this definition may be considered which requires ${\displaystyle \cap B\subset \cup B}$, but we only use this notion for the following auxiliary definition.)

One commonly defines a class ${\displaystyle \omega =\bigcap \{y\mid \mathrm {Ind} _{y}\}}$, the intersection of all inductive sets. (Variants of this treatment may work in terms of a formula that depends on a set parameter ${\displaystyle w}$ so that ${\displaystyle \omega \subset w}$.) The class ${\displaystyle \omega }$ exactly holds all ${\displaystyle x}$ fulfilling the unbounded property ${\displaystyle \forall y.\mathrm {Ind} _{y}\to x\in y}$. The intention is that if inductive sets exist at all, then the class ${\displaystyle \omega }$ shares each common natural number with them, and then the proposition ${\displaystyle \omega \subset A}$, by definition of "${\displaystyle \subset }$", implies that ${\displaystyle Q}$ holds for each of these naturals. While bounded separation does not suffice to prove ${\displaystyle \omega }$ to be the desired set, the language here forms the basis for the following axiom, granting natural number induction for predicates that constitute a set.

The elementary constructive Set Theory ${\displaystyle {\mathsf {ECST}}}$ has the axiom of ${\displaystyle {\mathsf {BCST}}}$ as well as the postulate

 ${\displaystyle \exists w.{\Big (}\mathrm {Ind} _{w}\,\land \,{\big (}\forall y.\mathrm {Ind} _{y}\to w\subset y{\big )}{\Big )}}$

Going on, one takes ${\displaystyle \omega }$ to denote the now unique smallest inductive set, an unbounded von Neumann ordinal. It contains the empty set and, for each set in ${\displaystyle \omega }$, another set in ${\displaystyle \omega }$ that contains one element more.

Symbols called zero and successor are in the signature of the theory of Peano. In ${\displaystyle {\mathsf {BCST}}}$, the above defined successor of any number also being in the class ${\displaystyle \omega }$ follow directly from the characterization of the natural naturals by our von Neumann model. Since the successor of such a set contains itself, one also finds that no successor equals zero. So two of the Peano axioms regarding the symbols zero and the one regarding closedness of ${\displaystyle S}$ come easily. Fourthly, in ${\displaystyle {\mathsf {ECST}}}$, where ${\displaystyle \omega }$ is a set, ${\displaystyle S}$ can be proven to be an injective operation.

The pairwise order "${\displaystyle <}$" on the naturals is captured by their membership relation "${\displaystyle \in }$". It is important to note that the theory proves the order as well as the equality relation on this set to be decidable. That said, existence of a least element for the inhabited subset ${\displaystyle b:=\{z\in 1\mid P\}\cup \{1\}\subset \omega }$ implies excluded middle for ${\displaystyle P}$, and a constructive theory will therefore not prove ${\displaystyle \omega }$ to be well-ordered.

#### Weaker formulations of infinity

Should it need motivation, the handyness of postulating an unbounded set of numbers in relation to other inductive properties becomes clear in the discussion of arithmetic in set theory further below. But as is familiar from classical set theory, also weak forms of Infinity can be formulated. For example, one may just postulate the existence of some inductive set, ${\displaystyle \exists y.\mathrm {Ind} _{y}}$ - such an existence postulate suffices when full Separation may then be used to carve out the inductive subset ${\displaystyle w}$ of natural numbers, the shared subset of all inductive classes. Alternatively, more specific mere existence postulates may be adopted. Either which way, the inductive set then fulfills the following ${\displaystyle \Delta _{0}}$ predecessor existence property in the sense of the von Neumann model:

${\displaystyle \forall m.(m\in w)\leftrightarrow {\big (}m=0\lor \exists (p\in w).Sp=m{\big )}}$

Without making use of the notation for the previously defined successor notation, the extensional equality to a successor ${\displaystyle Sp=m}$ is captured by ${\displaystyle \forall n.(n\in m)\leftrightarrow (n=p\lor n\in p)}$. This expresses that all elements ${\displaystyle m}$ are either equal to ${\displaystyle 0}$ or themselves hold a predecessor set ${\displaystyle p\in w}$ which shares all other members with ${\displaystyle m}$.

Observe that through the expression "${\displaystyle \exists (p\in w)}$" on the right hand side, the property characterizing ${\displaystyle w}$ by its members ${\displaystyle m}$ here syntactically again contains the symbol ${\displaystyle w}$ itself. Due to the bottom-up nature of the natural numbers, this is tame here. Assuming ${\displaystyle \Delta _{0}}$-set induction, no two sets have this property. Also note that there are also longer formulations of this property, avoiding "${\displaystyle \exists (p\in w)}$" in favor unbounded quantifiers.

#### Number bounds

Adopting an Axiom of Infinity, the set-bounded quantification legal in predicates used in ${\displaystyle \Delta _{0}}$-Separation then explicitly permits numerically unbounded quantifiers - the two meanings of "bounded" should not be confused. With ${\displaystyle \omega }$ at hand, call a class of numbers ${\displaystyle I\subset \omega }$ bounded if the following existence statement holds

${\displaystyle \exists (m\in \omega ).\forall (n\in \omega ).(n\in I\to n

This or the contrapositive variant

${\displaystyle \exists (m\in \omega ).\forall (n\in \omega ).(m\leq n\to n\notin I)}$

are statements of finiteness. For decidable properties, these are ${\displaystyle \Sigma _{2}^{0}}$-statements in arithmetic, but with the Axiom of Infinity, the two quantifiers are set-bound. Denote an initial segment of the natural numbers, i.e. ${\displaystyle \{n\in \omega \mid n for any ${\displaystyle m\in \omega }$ and including the empty set, by ${\displaystyle \{0,1,\dots ,m-1\}}$. This set equals ${\displaystyle m}$ and so at this point "${\displaystyle m-1}$" is mere notation for its predecessor (i.e. not involving subtraction function). To reflect more closely the discussion of functions below, write the above condition as

${\displaystyle \exists (m\in \omega ).\forall (n\in I).(n.

For a class ${\displaystyle C}$, the statement

${\displaystyle \forall (k\in \omega ).\exists (j\in \omega ).(k\leq j\land j\in C)}$

is now also one of infinitude. It is ${\displaystyle \Pi _{2}^{0}}$ in the decidable arithmetic case. To validate infinitude of a set, this property even works if the set holds other elements besides infinitely many of members of ${\displaystyle \omega }$.

### Functions

#### Finiteness

The function concept will be specified right below. Tying in with the previous section first, here are some definitions.

One defines three distinct notions involving surjections. For a general set to be (Bishop-)finite shall mean there is a bijective function to a natural. If the existence of such a bijection is proven impossible, the set is called non-finite. Secondly, for a notion weaker than finite, to be finitely indexed (or Kuratowski-finite) shall mean that there is a surjection from a von Neumann natural number onto it. Call a set subfinite if it is the subset of a finite set, which thus injects into that finite set. Thirdly, for a notion even weaker than finitely indexed, to be subfinitely indexed means to be in the surjective image of a subfinite set, and in ${\displaystyle {\mathsf {ETCS}}}$ this just means to be the subset of a finitely indexed set, meaning the subset can also be taken on the image side instead of the domain side. A set exhibiting either of those three notions can be understood to be majorized by a finite set, but in the second case the relation between the sets members is not necessarily fully understood, and in the third not even membership with respect to some superset it is necessary fully understood. The claim that being finite is equivalent to being subfinite, for all sets, is equivalent to ${\displaystyle {\mathrm {PEM} }}$. More finiteness properties can be defined, e.g. one expressing the existence of some large enough natural such that all functions into a set fail to be injective, for some notion of non-injectivity.

More generally than the property of infinitude above, call a set infinite if one can inject ${\displaystyle \omega }$ into it. Call an inhabited set countable if there exists a surjection from ${\displaystyle \omega }$ onto it and subcountable if this can be done from a subsets of ${\displaystyle \omega }$. Call a set enumerable if there exists an injection to ${\displaystyle \omega }$, which renders the set discrete. Notably, all of these are function existence claims. The empty set is not inhabited but generally deemed countable too, and note that the successor set of any countable set is countable. The set ${\displaystyle \omega }$ itself is clearly unbounded and not finite in any sense. It is also trivially infinite, countable and enumerable, as witnessed by the identity function. An infinite, countable sets is equinumeros to ${\displaystyle \omega }$. Observe that ${\displaystyle \omega }$, unlike any of its members, is equinumeros to infinitely many of its proper unbounded subsets, e.g. those of the form ${\displaystyle w_{m}:=\{k\in \omega \mid k>m\}}$. This makes the set Dedekind-infinite. More properties of finiteness may be defined as negations of such properties, et cetera.

Terminology for conditions of finiteness and infinitude may vary. Notably, subfinitely indexed sets (a notion necessarily involving surjections) are sometimes called subfinite (which can be defined without functions). The property of being finitely indexed could also be denoted "finitely countable", to fit the naming logic, but is by some authors also called finitely enumerable (which might be confusing as this suggest an injection in the other direction). Relatedly, the existence of a bijection with a finite set has not established, one may say a set is not finite, but this use of language is then weaker than to claim the set to be non-finite. The same issue applies to countable sets, et cetera. A surjective map may also be called an enumeration.

#### General note on programs and functions

Naturally, the meaning of existence claims is a topic of interest in constructivism, be it for a theory of sets or any other framework. Let ${\displaystyle R}$ express a property such that a mathematical framework validates what amounts to the statement

${\displaystyle \forall (a\in A).\exists (c\in C).R(a,c)}$

A constructive proof calculus may validate such a judgement in terms of programs on represented domains and some object representing a concrete assignment ${\displaystyle a\mapsto c_{a}}$, providing a particular choice of value in ${\displaystyle C}$ (a unique one), for each input from ${\displaystyle A}$. Expressed through the rewriting ${\displaystyle \forall (a\in A).R(a,c_{a})}$, this function object maybe be understood as witnessing the proposition. Consider for example the notions of proof in through realizability theory or function terms in a type theory with a notion of quantifiers. The latter captures proof of logical proposition through programs via the Curry–Howard correspondence.

Depending on the context, the word "function" may be used in association with a particular model of computation, and this is a priori narrower than what is discussed in the present set theory context. One notion of program is formalized by partial recursive "functions" in computability theory. But beware that here the word "function" is used in a way that also comprises partial functions. The scare quotes are used for clarity here, as in a set theory context there is technically no need to speak of total functions, because this requirement is part of the definition of a set theoretical function and partial function spaces can be modeled via unions. At the same time, when combined with a formal arithmetic, this notion provides one particularly sharp notion of totality for functions. By Kleene's normal form theorem, each partial recursive function on the naturals computes, for the values where it terminates, the same as ${\displaystyle a\mapsto U(\mu w.T_{1}(e,a,w))}$, for some function index ${\displaystyle e\in {\mathbb {N} }}$, and any index will constitute some partial function. A program can be associated with a ${\displaystyle e}$ and may be said to be ${\displaystyle T_{1}}$-total whenever a theory proves ${\displaystyle \forall a.\exists w.T_{1}(e,a,w)}$, where ${\displaystyle T_{1}}$ amounts to a primitive recursive program and ${\displaystyle w}$ is related to the execution of ${\displaystyle e}$. Kreisel proved that the class of partial recursive functions proven ${\displaystyle T_{1}}$-total by ${\displaystyle {\mathsf {HA}}}$ is not enriched when ${\displaystyle {\mathrm {PEM} }}$ is added.[11] As a predicate in ${\displaystyle e}$, this totality constitutes an undecidable subset indices, highlighting that that the recursive world of functions between the naturals is already captured by a set dominated by ${\displaystyle {\mathbb {N} }}$. As a third warning, note that this notion is really about programs and several indices will in fact constitute the same function, in the extensional sense.

A theory in first-order logic, such as the axiomatic set theories discussed here, comes with a joint notion of total and functional for a binary predicate ${\displaystyle R}$, namely ${\displaystyle \forall a.\exists !c.R(a,c)}$. Such theories relate to programs only indirectly. If ${\displaystyle S}$ denotes the successor operation in a formal language of a theory being studied, then any number, e.g. ${\displaystyle {\mathrm {SSS0} }}$ (the number three), may meta-logically be related to the standard numeral, e.g. ${\displaystyle {\underline {\mathrm {SSS0} }}=SSS0}$. Similarly, programs in the partial recursive sense may be unrolled to predicates and weak assumptions suffice so that such a translation respects equality of their return values. Among finitely axiomizable sub-theories of ${\displaystyle {\mathsf {PA}}}$, classical Robinson arithmetic ${\displaystyle {\mathsf {Q}}}$ exactly fulfills this. Its existence claims are intended to only concern natural numbers and instead of using the full mathematical induction schema for arithmetic formulas, the theories' axioms postulate that every number is either zero or that there exists a predecessor number to it. Focusing on ${\displaystyle T_{1}}$-total recursive functions here, it is a meta-theorem that the language of arithmetic expresses them by ${\displaystyle \Sigma _{1}}$-predicates ${\displaystyle G}$ encoding their graph such that ${\displaystyle {\mathsf {Q}}}$ represents them, in the sense that it correctly proves or rejects ${\displaystyle G({\underline {\mathrm {a} }},{\underline {\mathrm {c} }})}$ for any input-output pair of numbers ${\displaystyle \mathrm {a} }$ and ${\displaystyle \mathrm {c} }$ in the meta-theory. And given a correctly representing ${\displaystyle G}$, the predicate ${\displaystyle G_{\mathrm {least} }(a,c)}$ defined by ${\displaystyle G(a,c)\land \forall (n\leq c).G(a,n)\to n=c}$ represents the recursive function just as well, and as this only validates the smallest return value, the theory also proves functionality for all inputs ${\displaystyle {\mathrm {a} }}$ in the sense of ${\displaystyle {\mathsf {Q}}\vdash \exists !(c\in {\mathbb {N} }).G_{\mathrm {least} }({\underline {\mathrm {a} }},c)}$. Given a representing predicate, then at the cost of making use of ${\displaystyle {\mathrm {PEM} }}$, one can always also systematically prove the graph to be total functional.[12]

Which predicates are provably functional for various inputs, or even total functional on their domain, generally depends on the adopted axioms of a theory and proof calculus. For example, for the diagonal halting problem, which cannot have a ${\displaystyle T_{1}}$-total index, it is ${\displaystyle {\mathsf {HA}}}$-independent whether the corresponding graph predicate on ${\displaystyle {\mathbb {N} }\times \{0,1\}}$ (a decision problem) is total functional, but ${\displaystyle {\mathrm {PEM} }}$ implies that it is. Proof theoretical function hierarchies provide examples of predicates proven total functional in systems going beyond ${\displaystyle {\mathsf {PA}}}$. Which sets proven to exist do constitute a total function, in the sense introduced next, also always depends on the axioms and the proof calculus.

#### Total functional relations

In set theory language here, speak of a function class when ${\displaystyle f\subset A\times C}$ and provenly

${\displaystyle \forall (a\in A).\,\exists !(c\in C).\langle a,c\rangle \in f}$.

Notably, this definition involves quantifier explicitly asking for existence - an aspect which is particularly important in the constructive context. In words: For every ${\displaystyle a}$, it demands the unique existence of a ${\displaystyle c}$ so that ${\displaystyle \langle a,c\rangle \in f}$. In the case that this holds one may use function application bracket notation and write ${\displaystyle \langle a,c\rangle \in f}$. The above property may then be stated as ${\displaystyle \forall (a\in A).\,\exists !(c\in C).f(a)=c}$. By construction, such functions respect equality in the sense that ${\displaystyle x=y\to f(x)=f(y)}$, for any inputs from ${\displaystyle A}$. This is worth mentioning since also more broader concepts of "operations" exist in the literature, which may not respect this. And as noted, care must be taken with nomenclature "function", which sees use in most mathematical frameworks, also because some tie a function term itself to a particular codomain. Variants of the functional predicate definition using apartness relations on setoids have been defined as well. It is a metatheorem for theories containing ${\displaystyle {\mathsf {BCST}}}$ that adding a function symbol for a provenly total class function is a conservative extension, despite this changing the scope of bounded Separation. Some notational conveniences involving function application will only work when a set has indeed been established to be a function.

Whether a subclass (or predicate for that matter) can be judged to be a function set, or even total functional to begin with, will depend on the strength of the theory, which is to say the axioms one adopts. And notably, a general class could also fulfill the above defining predicate without being a subclass of the product ${\displaystyle A\times C}$, i.e. the property is expressing not more or less than functionality w.r.t. the inputs from ${\displaystyle A}$. Now if the domain is a set, the function comprehension principle, also called axiom of unique choice  or non-choice, says that a function as a set, with some codomain, exists well. (And this principle is valid in a theory like ${\displaystyle {\mathsf {CZF}}}$. Also compare with the Replacement axiom.) That is, the mapping information exists as set and it has a pair for each element in the domain. Of course for any set from some class, there is always the unique element of the singleton ${\displaystyle 1}$, and so merely a chosen range being a set does not suffice to be granted a function set. In summary, in the set theory context the focus is on capturing particular total relations that are functional. To delineate the notion of function in the theories of the previous subsection (a 2-ary logical predicate defined to express a functions graph, together with a proposition that it is total and functional) from the "material" set theoretical notion here, one may explicitly call the latter graph of a function, anafunction or set function. The axiom schema of Replacement can also be formulated in terms of the ranges of such set functions.

If both domain and codomain are sets, then the above predicate only involves bounded quantifiers. Common notions such as injectivity and surjectivity can be expressed in a bounded fashion as well, and thus so is bijectivity. Both of these tie in to notions of size. Importantly, injection existence between any two sets provides a preorder. A power class does not inject into its underlying set and the latter does not map onto the former. Surjectivity is formally a more complex definition. Note that injectivity shall be defined positively, not by its contrapositive, which is common practice in classical mathematics. The version without negations is sometimes called weakly injective. The existence of value collisions is a strong notion of non-injectivity. And regarding surjectivity, similar considerations exist for outlier-production in the codomain.

Let ${\displaystyle C^{A}}$ (also written ${\displaystyle ^{A}C}$) denote the class of sets that fulfill the function property. This is the class of functions from ${\displaystyle A}$ to ${\displaystyle C}$ in a pure set theory. Below the notation ${\displaystyle x\to y}$ is also used for ${\displaystyle y^{x}}$, for the sake of distinguishing it from ordinal exponentiation. When functions are understood as just function graphs as above, the membership proposition ${\displaystyle f\in C^{A}}$ is also written ${\displaystyle f\colon A\to C}$. The boolean-valued ${\displaystyle \chi _{B}\colon A\to \{0,1\}}$ are among the classes discussed next.

#### Characteristic functions

Separation lets us cut out subsets of products ${\displaystyle A\times C}$, at least when they are described in a bounded fashion. Given any ${\displaystyle B\subset A}$, one is now led to reason about classes such as

${\displaystyle X_{B}:={\big \{}\langle x,y\rangle \in A\times \{0,1\}\mid (x\in B\land y=1)\lor (x\notin B\land y=0){\big \}}.}$

Since ${\displaystyle 0\neq 1}$, one has

${\displaystyle {\big (}a\in B\ \leftrightarrow \,\langle a,1\rangle \in X_{B}{\big )}\,\land \,{\big (}a\notin B\ \leftrightarrow \,\langle a,0\rangle \in X_{B}{\big )}}$

and so

${\displaystyle {\big (}a\in B\lor a\notin B{\big )}\ \leftrightarrow \ \exists !(y\in \{0,1\}).\langle a,y\rangle \in X_{B}}$.

But be aware that in absence of any non-constructive axioms ${\displaystyle a\in B}$ may in generally not be decidable, since one requires an explicit proof of either disjunct. Constructively, when ${\displaystyle \exists (y\in \{0,1\}).\langle x,y\rangle \in X_{B}}$ cannot be witnessed for all the ${\displaystyle x\in A}$, or uniqueness of the terms ${\displaystyle y}$ associated with each ${\displaystyle x}$ cannot be proven, then one cannot judge the comprehended collection to be total functional. Case in point: The classical derivation of Schröder–Bernstein relies on case analysis - but to constitute a function, particular cases shall actually be specifiable, given any input from the domain. It has been established that Schröder–Bernstein cannot have a proof on the base of ${\displaystyle {\mathsf {IZF}}}$.[13] So to the extent that intuitionistic inference does not go beyond what is formalized here, there is no generic construction of a bijection from two injections in opposing directions.

But being compatible with ${\displaystyle {\mathsf {ZF}}}$, the development in this section still always permits "function on ${\displaystyle \omega }$" to be interpreted as a completed object that is also not necessarily given as lawlike sequence. Applications may be found in the common models for claims about probability, e.g. statements involving the notion of "being given" an unending random sequence of coin flips, even if many predictions can also be expressed in terms of spreads.

If indeed one is given a function ${\displaystyle \chi _{B}\colon A\to \{0,1\}}$, it is the characteristic function actually deciding membership in some set ${\displaystyle B\subset A}$ so that

${\displaystyle B=\{n\in \omega \mid \chi _{B}(n)=1\},}$

and then by convention ${\displaystyle B}$ and ${\displaystyle \chi _{B}}$ as well as any equivalent of the formulas ${\displaystyle n\in B}$ and ${\displaystyle \chi _{B}(n)=1}$ with ${\displaystyle n}$ free may be referred to as a decidable property or set on ${\displaystyle A}$. One may call a collection ${\displaystyle A}$ searchable for ${\displaystyle \chi _{B}}$ if existence is actually decidable,

${\displaystyle \exists (x\in A).\chi _{B}(x)=1\ \lor \ \forall (x\in A).\chi _{B}(x)=0.}$

Now consider the case ${\displaystyle A=\omega }$. If ${\displaystyle \chi _{B}(0)=0}$, say, then the range ${\displaystyle \{0\}\subset R\subset \{0,1\}}$ of ${\displaystyle \chi _{B}}$ is an inhabited, counted set, by Replacement. However, the ${\displaystyle R}$ need not be again a decidable set itself, since the claim ${\displaystyle R=\{0\}}$ is equivalent to the rather strong ${\displaystyle \forall n.\chi _{B}(n)=0}$. Moreover, ${\displaystyle R=\{0\}}$ is also equivalent to ${\displaystyle B=\{\}}$ and so one can state undecidable propositions about ${\displaystyle B}$ also when membership in ${\displaystyle B}$ is decidable. This also plays out like this classically in the sense that statements about ${\displaystyle B}$ may be independent, but any classical theory then nonetheless claims the joint proposition ${\displaystyle B=\{\}\lor B\neq \{\}}$. Consider the set ${\displaystyle B}$ of all indices of proofs of an inconsistency of the theory at hand, in which case the universally closed statement ${\displaystyle B=\{\}}$ is a consistency claim. In terms of arithmetic principles, assuming decidability of this would be ${\displaystyle \Pi _{1}^{0}}$-${\displaystyle {\mathrm {PEM} }}$ or arithmetic ${\displaystyle \forall }$-${\displaystyle {\mathrm {PEM} }}$. This and the stronger related ${\displaystyle {\mathrm {LPO} }}$, or arithmetic ${\displaystyle \exists }$-${\displaystyle {\mathrm {PEM} }}$, is discussed below.

#### Computable sets

Going back to more generality, given a general predicate ${\displaystyle Q}$ on the numbers (say one defined from Kleene's T predicate), let again

${\displaystyle B:=\{n\in \omega \mid Q(n)\}.}$

Given any natural ${\displaystyle n\in \omega }$, then

${\displaystyle {\big (}Q(n)\lor \neg Q(n){\big )}\to {\big (}n\in B\lor n\notin B{\big )}.}$

In classical set theory, ${\displaystyle \forall (n\in \omega ).Q(n)\lor \neg Q(n)}$ by ${\displaystyle {\mathrm {PEM} }}$ and so excluded middle also holds for subclass membership. If the class ${\displaystyle B}$ has no numerical bound, then successively going through the natural numbers ${\displaystyle n}$, and thus "listing" all numbers in ${\displaystyle B}$ by simply skipping those with ${\displaystyle n\notin B}$, classically always constitutes an increasing surjective sequence ${\displaystyle b\colon \omega \twoheadrightarrow B}$. There, one can obtain a bijective function. In this way, the class of functions in typical classical set theories is provenly rich, as it also contains objects that are beyond what we know to be effectively computable, or programmatically listable in praxis.

In computability theory, the computable sets are ranges of non-decreasing total functions in the recursive sense, at the level ${\displaystyle \Sigma _{1}^{0}\cap \Pi _{1}^{0}=\Delta _{1}^{0}}$ of the arithmetical hierarchy, and not higher. Deciding a predicate at that level amounts to solving the task of eventually finding a certificate that either validates or rejects membership. As not every predicate ${\displaystyle Q}$ is computably decidable, also the theory ${\displaystyle {\mathsf {CZF}}}$ alone will not claim (prove) that all unbounded ${\displaystyle B\subset \omega }$ are the range of some bijective function with domain ${\displaystyle \omega }$. See also Kripke's schema. Note that bounded Separation nonetheless proves the more complicated arithmetical predicates to still constitute sets, the next level being the computably enumerable ones at ${\displaystyle \Sigma _{1}^{0}}$.

#### Boundedness criteria

Any subset ${\displaystyle B\subset \omega }$ injects into ${\displaystyle \omega }$. If ${\displaystyle B}$ is decidable and inhabited with ${\displaystyle y_{0}\in B}$, the sequence

${\displaystyle q:={\big \{}\langle x,y\rangle \in \omega \times B\mid (x\in B\land y=x)\lor (x\notin B\land y=y_{0}){\big \}}}$

i.e.

${\displaystyle q(x):={\begin{cases}x&x\in B\\y_{0}&x\notin B\\\end{cases}}}$

is surjective onto ${\displaystyle B}$, making it a counted set. That function also has the property ${\displaystyle \forall (x\in B).q(x)=x}$.

Now consider a countable, bounded set ${\displaystyle R\subset \omega }$. With ${\displaystyle w_{m}:=\{k\in \omega \mid k>m\}}$ as above, it follows that

${\displaystyle \forall (r\colon \omega \to R).\exists (m\in \omega ).\forall (k\in w_{m}).r(k)

A set ${\displaystyle I}$ such that this loose bounding statement holds for all sequences taking values in ${\displaystyle I}$ (or an equivalent formulation of this property) is called pseudo-bounded. The intention of this property would be to still capture that ${\displaystyle I\subset \omega }$ is eventually exhausted, albeit now this is expressed in terms of the function space ${\displaystyle I^{\omega }}$ (which is bigger than ${\displaystyle I}$ in the sense that ${\displaystyle I}$ always injects into ${\displaystyle I^{\omega }}$). The related notion familiar from topological vector space theory is formulated in terms of ratios going to zero for all sequences (${\displaystyle {\tfrac {r(k)}{k}}}$ in the above notation). For a decidable, inhabited set, pseudo-boundedness using the above counting sequence provides a bound for all the elements ${\displaystyle I}$.

The principle that any inhabited, pseudo-bounded subset of ${\displaystyle \omega }$ that is just countable (but not necessarily decidable) is always also bounded is called ${\displaystyle \mathrm {BD} }$-${\displaystyle {\mathbb {N} }}$. The principle also holds generally in many constructive frameworks, such as the Markovian base theory ${\displaystyle {\mathsf {HA}}+{\mathrm {ECT} }_{0}+{\mathrm {MP} }}$, which is a theory postulating exclusively lawlike sequences with nice number search termination properties. However, ${\displaystyle \mathrm {BD} }$-${\displaystyle {\mathbb {N} }}$ is independent of ${\displaystyle {\mathsf {IZF}}}$.

### Choice functions

Not even classical ${\displaystyle {\mathsf {ZF}}}$ proves each union of a countable set of two-element sets to be countable again. Indeed, models of ${\displaystyle {\mathsf {ZF}}}$ have been defined that negate the countability of such a countable union of pairs. Assuming countable choice rules out that model as an interpretation of the resulting theory. This principle is independent of ${\displaystyle {\mathsf {ZF}}}$ - A naive proof strategy for that statement fails at the accounting of infinitely many existential instantiations.

A choice principle postulates that certain selections can always be made in a joint fashion so that they are also manifested as a single set function in the theory. Such a function existence claim can then be translated to the existence of inverses, orderings, and so on. Choice moreover implies statements about cardinalities of different sets, e.g. they imply or rule out countability of sets. As with any independent axiom, this raises the proving capabilities while restricting the scope of possible (model-theoretic) interpretations of the (syntactic) theory. The constructive development here proceeds in a fashion agnostic to any discussed choice principles, but here are well studied variants:[14]

• Axiom of countable choice ${\displaystyle {\mathrm {AC} _{\omega }}}$ (or ${\displaystyle {\mathrm {CC} }}$): If ${\displaystyle g\colon \omega \to z}$, one can form the one-to-many relation-set ${\displaystyle \{\langle n,u\rangle \mid n\in \omega \land u\in g(n)\}}$. The axiom of countable choice would grant that whenever ${\displaystyle \forall (n\in \omega ).\exists u.u\in g(n)}$, one can form a function mapping each number to a unique value. This is not provable on the base of ${\displaystyle {\mathsf {ZF}}}$. Countable choice into general sets can also be weakened further. One may consider the version of countable choice for functions into ${\displaystyle \omega }$ (called ${\displaystyle {\mathrm {AC} _{00}}}$), as is implied by ${\displaystyle {\mathrm {CT} _{0}}}$, i.e. by postulating that all total arithmetical relations are recursive. One common consideration is to restrict the possible cardinalities of the range of ${\displaystyle g}$, giving the weak countable choice into countable, finite or even just binary sets (${\displaystyle {\mathrm {AC} _{\omega ,2}}}$). Constructively, weak form of choice is required for well-behaved Cauchy reals. Another means of weakening countable choice is by restricting the involved definitions w.r.t. their place in the syntactic hierarchies (say ${\displaystyle \Pi _{1}^{0}}$-${\displaystyle {\mathrm {AC} _{\omega ,2}}}$). The weak Kőnig's lemma ${\displaystyle {\mathrm {WKL} }}$, which breaks strictly recursive mathematics as further discussed below, is stronger than ${\displaystyle \Pi _{1}^{0}}$-${\displaystyle {\mathrm {AC} _{\omega ,2}}}$ and is itself sometimes viewed as capturing a form of countable choice. In the presence of a weak form of countable choice, it become equivalent to the non-constructive principle of more logical flavor, ${\displaystyle {\mathrm {LLPO} }}$. Countable choice is not valid in the internal logic of a general topos, which can be seen as models of constructive set theories.
• Axiom of dependent choice ${\displaystyle {\mathrm {DC} }}$: Countable choice is implied by the more general axiom of dependent choice, extracting a function from any entire relation on an inhabited set. Countable choice is akin to constructive Church's thesis principle and indeed dependent choice holds in many realizability models and it is thus adopted in many constructive schools.
• Relativized dependent choice ${\displaystyle {\mathrm {RDC} }}$: The stronger relativized dependent choice principle is a variant of it - a schema involving an extra predicate variable. Adopting this for just bounded formulas in ${\displaystyle {\mathsf {ECST}}}$, the theory already proves the ${\displaystyle \Sigma _{1}}$-induction.
• ${\displaystyle \Pi \Sigma }$-${\displaystyle \mathrm {AC} }$: A family of sets is better controllable if it comes indexed by a function. A set ${\displaystyle b}$ is a base if all indexed families of sets ${\displaystyle i_{s}\colon b\to s}$ over it, have a choice function ${\displaystyle f_{s}}$, i.e. ${\displaystyle \forall (x\in b).f_{s}(x)\in i_{s}(x)}$. A collection of sets holding ${\displaystyle \omega }$ and its elements and which is closed by taking indexed sums and products (see dependent type) is called ${\displaystyle \Pi \Sigma }$-closed. While the axiom that all sets in the smallest ${\displaystyle \Pi \Sigma }$-closed class are a base does need some work to formulate, it is the strongest principle over ${\displaystyle {\mathsf {CZF}}}$ that holds in the type theoretical interpretation ${\displaystyle {\mathsf {ML_{1}V}}}$.
• Axiom of choice ${\displaystyle {\mathrm {AC} }}$: The choice function postulate concerning domains that are general sets containing inhabited sets, with the codomain given as their general union. Given a collection of sets such that the logic allows to make a choice in each, the axiom grants that there exists a set function that jointly captures a choice in all. It is typically formulated for all sets but has also been studied in classical formulations for sets only up to any particular cardinality. Striking existence claims beyond what could be defined in ${\displaystyle {\mathsf {ZF}}}$ are abound: For example, applied to the Borel algebra of the reals, the axiom postulates the existence of a function selecting a member from each non-empty such Lebesgue-measurable subset. (The set ${\displaystyle {\mathcal {B}}({\mathbb {R} })}$ is the σ-algebra generated by the finite intervals ${\displaystyle I:=\{(x,y\,]\mid x,y\in {\mathbb {R} }\}}$. It strictly includes those intervals, in the sense of ${\displaystyle I\subsetneq {\mathcal {B}}({\mathbb {R} })\subsetneq {\mathcal {P}}_{\mathbb {R} }}$, but in ${\displaystyle {\mathsf {ZF}}}$ also only has the cardinality of the reals itself.) The axiom of choice also implies Dependent choice. Critically in the present context, it moreover also implies instances of ${\displaystyle {\mathrm {PEM} }}$ via Diaconescu's theorem. For theories extending ${\displaystyle {\mathsf {ECST}}}$ this means full choice at the very least proves ${\displaystyle {\mathrm {PEM} }}$ for all ${\displaystyle \Delta _{0}}$-formulas, a non-constructive consequence not acceptable from a computability standpoint.

#### Diaconescu's theorem

To highlight the strength of full Choice and its relation to matters of intentionality, one should consider the classes

${\displaystyle a=\{u\in \{0,1\}\mid (u=0)\lor P\}}$
${\displaystyle b=\{u\in \{0,1\}\mid (u=1)\lor P\}}$

from the proof of Diaconescu's theorem. Referring back to the introductory elaboration on the meaning of such convenient class notation, as well as to the principle of distributivity, ${\displaystyle t\in a\leftrightarrow {\big (}t=0\lor (t=1\land P){\big )}}$. So unconditionally, ${\displaystyle 0\in a}$ as well as ${\displaystyle 1\in b}$. But otherwise, the classes ${\displaystyle a}$ and ${\displaystyle b}$ are as contingent as the proposition ${\displaystyle P}$ involved in their definition and they are not proven finite. Nonetheless, the setup entails several consequences, when inspecting the provable case, starting with ${\displaystyle P\to (a=\{0,1\}\land b=\{0,1\})}$. So validity of ${\displaystyle P}$ means ${\displaystyle a}$ and ${\displaystyle b}$ share all members and there are two of them and indeed the equality is equivalent and decides ${\displaystyle P}$. As ${\displaystyle a}$ are ${\displaystyle b}$ are then sets, ${\displaystyle P\to a=b}$ and ${\displaystyle P\to \{a,b\}=\{a\}}$. Similarly, ${\displaystyle \neg P\to (a=\{0\}\land b=\{1\})}$ and, as provenly ${\displaystyle \neg (0=1)}$, one actually finds in which way the sets are then different. A contrapositive thus gives ${\displaystyle \neg P\leftrightarrow \neg (a=b)}$. One may moreover reason using the disjunctive syllogism that both ${\displaystyle 0\in b}$ and ${\displaystyle 1\in a}$ are each equivalent to ${\displaystyle P}$. All together, this gives equivalence of disjuncts

${\displaystyle (P\lor \neg P)\leftrightarrow (1\in a\,\lor \,0\in b\,\lor \,a\neq b)}$.

In the following assume a context in which ${\displaystyle a,b}$ are indeed established to be sets, and thus subfinite sets. Then for inhabited such sets, the general axiom of choice claims existence of a function ${\displaystyle f\colon \{a,b\}\to a\cup b}$ with ${\displaystyle f(z)\in z}$. It is important that the elements ${\displaystyle a,b}$ of the function's domain are different than the natural numbers ${\displaystyle 0,1}$ in that a priori less is known about the former. When forming then union of the two classes, ${\displaystyle u=0\lor u=1}$ is a necessary but then also sufficient condition. Thus ${\displaystyle a\cup b=\{0,1\}}$ and one is dealing with functions ${\displaystyle f}$ into a set of two distinguishable values. With choice come the conjunction ${\displaystyle f(a)\in a\land f(b)\in b}$ in the codomain of the function, but the possible function return values are known to be just ${\displaystyle 0}$ or ${\displaystyle 1}$. Using the distributivity, there arises a list of conditions, a disjunction. Expanding what is then established, one finds that either both ${\displaystyle P}$ as well as the sets equality, or that the return values are different and ${\displaystyle P}$ can be rejected. The conclusion is that the choice postulate actually implies ${\displaystyle P\lor \neg P}$ whenever a Separation axiom allows for set comprehension using undecidable proposition ${\displaystyle P}$.

#### Analysis of Diaconescu's theorem

So full choice is non-constructive in set theory as defined here. The issue is that propositions, as part of set comprehension used to separate and define the classes ${\displaystyle a}$ and ${\displaystyle b}$ from ${\displaystyle \{0,1\}}$, ramify the notion of truth values into set terms of the theory. Equality defined by the set theoretical axiom of extensionality, which itself is not related to functions, in turn couples knowledge about the predicate to information about function values. To recap the final step in terms function values: On the one hand, witnessing ${\displaystyle f(a)=1}$ implies ${\displaystyle P}$ and ${\displaystyle a=b}$ and this conclusion independently also applies to witnessing ${\displaystyle f(b)=0}$. On the other hand, witnessing ${\displaystyle f(a)=0\land f(b)=1}$ implies the two function arguments are not equal and this rules out ${\displaystyle P}$. There are really only three combinations, as the axiom of extensionality in the given setup makes ${\displaystyle f(a)=1\land f(b)=0}$ inconsistent. So if the constructive reading of existence is to be preserved, full choice may be not adopted in the set theory, because the mere claim of function existence does not realize a particular function.

The surjection ${\displaystyle \{\langle 0,a\rangle ,\langle 1,b\rangle \}}$ witnesses that ${\displaystyle \{a,b\}}$ is finitely indexed. To better understand why we cannot expect to be granted a definitive (total) choice function with domain ${\displaystyle \{a,b\}}$, consider naive function candidates. It was noted that its members are subfinite and also inhabited, since regardless of ${\displaystyle P}$ it is the case that ${\displaystyle 0\in a}$ and ${\displaystyle 1\in b}$. So without further analysis, this would seem to make ${\displaystyle f=\{\langle a,0\rangle ,\langle b,1\rangle \}}$ a contender for a choice function. Indeed, if ${\displaystyle P}$ can be rejected, this is the only option. But in the case of provability of ${\displaystyle P}$, when ${\displaystyle \{a,b\}=\{a\}}$, there is extensionally only one possible function input to a choice function. So in that situation, a choice function would explicitly have type ${\displaystyle f\colon \{a\}\to \{0,1\}}$, for example ${\displaystyle f=\{\langle a,0\rangle \}}$ and this would rule out the initial contender. For general ${\displaystyle P}$, the domain of a would-be choice function is not concrete but contingent on ${\displaystyle P}$ and not proven finite. When considering the above functional assignment ${\displaystyle f(a)=0}$, then neither unconditionally declaring ${\displaystyle f(b)=1}$ nor ${\displaystyle f(b)=0}$ is necessarily consistent. Having identified ${\displaystyle 1}$ with ${\displaystyle \{0\}}$, the two candidates described above can be represented simultaneously via ${\displaystyle f=\{\langle a,0\rangle ,\langle b,B_{\neg }\rangle \}}$ (which is not proven finite either) with the subfinite would-be natural ${\displaystyle B_{\neg }:=\{u\in \{0\}\mid \neg P\}}$. In ${\displaystyle B_{\neg }}$, the proposition ${\displaystyle P}$ (in the "if-clause") may be replaced by ${\displaystyle a=b}$. As ${\displaystyle (P\to (B_{\neg }=0))\land (\neg P\to (B_{\neg }=1))}$, postulating ${\displaystyle P}$, or ${\displaystyle \neg P}$, or the classical principle ${\displaystyle P\lor \neg P}$ here would indeed imply that ${\displaystyle B_{\neg }}$ is a natural, so that the latter set ${\displaystyle f}$ constitutes a choice function into ${\displaystyle \{0,1\}}$. And as in the constructive case, given a particular choice function - a set holding either exactly one or exactly two pairs - one could actually infer whether ${\displaystyle P}$ or whether ${\displaystyle \neg P}$ does hold. Vice versa, the third and last candidate ${\displaystyle f=\{\langle b,1\rangle \}}$ can be captured as part of ${\displaystyle f=\{\langle a,B\rangle ,\langle b,1\rangle \}}$, where ${\displaystyle B:=\{u\in \{0\}\mid P\}}$. Such a ${\displaystyle B}$ had already been considered in the early section on the axiom of separation. Again, the latter ${\displaystyle f}$ here is a classical choice function either way also. Constructively, the domain and values of such ${\displaystyle P}$-dependent would-be functions are not understood enough to prove them to be a total functional relation into ${\displaystyle \{0,1\}}$.

For computable semantics, set theory axioms postulating (total) function existence lead to the requirement for halting recursive functions. From their function graph in individual interpretations, one can infer the branches taken by the "if-clauses" that were undecided in the interpreted theory. But on the level of the synthetic frameworks, when they broadly become classical from adopting full choice, these extensional set theories theories contradict the constructive Church's rule.

#### Regularity implies PEM

The axiom of regularity states that for every inhabited set ${\displaystyle s}$, there exists an element ${\displaystyle t}$ in ${\displaystyle s}$, which shares no elements with ${\displaystyle s}$. As opposed to the axiom of choice, this existence claim reaches for an element of every inhabited set, i.e. the "domain" are all inhabited sets. Its formulation does not involve a unique existence claim but instead guarantees a set with a specific property. As the axiom correlates membership claims at different rank, the axiom also ends up implying ${\displaystyle {\mathrm {PEM} }}$:

The proof from choice above had used a particular set ${\displaystyle \{a,b\}}$ from above. The proof in this paragraph also assumes Separation applies to ${\displaystyle P}$ and uses ${\displaystyle b}$, for which it was already explained that ${\displaystyle 0\in b\leftrightarrow P}$ and for which ${\displaystyle \{0\}\in b}$ by definition. This ${\displaystyle b}$ is defined using the clause ${\displaystyle u\in \{0,1\}}$, so that any given ${\displaystyle u\in b}$ fulfills the disjunction ${\displaystyle u=0\lor u=\{0\}}$. Now let ${\displaystyle t\in b}$ be the postulated member with the empty intersection property. If ${\displaystyle t=0}$, then ${\displaystyle 0\in b}$, while otherwise ${\displaystyle (t=\{0\})\leftrightarrow \neg (0\in b)}$. This establishes excluded middle for ${\displaystyle P}$.

Demanding that the set of naturals is well-ordered with respect to it standard order relation imposes the same condition on the inhabited set ${\displaystyle b\subset \omega }$. So the least number principle has the same non-constructive implication.

### Arithmetic

The four Peano axioms for ${\displaystyle 0}$ and ${\displaystyle S}$, characterizing ${\displaystyle \omega }$ as a model of the natural numbers in ${\displaystyle {\mathsf {ECST}}}$, have been discussed. The order "${\displaystyle <}$" of natural numbers is captured by membership "${\displaystyle \in }$" in this von Neumann model and this set is discrete, i.e. also equality is decidable. Indeed, for any quantifier-free formula ${\displaystyle \phi (n,m)}$ on the naturals, such as ${\displaystyle n=m}$,

${\displaystyle {\mathsf {HA}}\vdash \forall n.\forall m.{\big (}\phi (n,m)\lor \neg \phi (n,m){\big )}}$.

The first-order theory of Heyting arithmetic ${\displaystyle {\mathsf {HA}}}$ has the same signature and non-logical axioms as Peano arithmetic. In contrast, the signature of set theory does not contain addition "${\displaystyle +}$" or multiplication "${\displaystyle \times }$". Next, it is clarified which set theory axiom may be asserted to prove existence of the latter as a function set, together with their desired relation to zero and successor.

#### Recursion

The set theory axioms listed so far suffice as formalized framework for a good portion of basic mathematics. Even without an induction principle for general classes, many universally quantified statements can still be proven per particular set term (e.g. some particular function). That said, the constructive set theory ${\displaystyle {\mathsf {ECST}}}$ does actually not even enable primitive recursion in ${\displaystyle \omega }$ for function definitions of what would be ${\displaystyle h\colon (x\times \omega )\to y}$ (where "${\displaystyle \times }$" here denotes the Cartesian product of set, not to be confused with multiplication above). Indeed, despite having the Replacement axiom, the theory does not prove the addition function ${\displaystyle +\colon (\omega \times \omega )\to \omega }$ to be a set function. Going beyond ${\displaystyle {\mathsf {ECST}}}$ with regards to arithmetic, the axiom granting definition of set functions via iteration-step set functions must be added: For any set ${\displaystyle y}$, set ${\displaystyle z\in y}$ and ${\displaystyle f\colon y\to y}$, there must also exist a function ${\displaystyle g\colon \omega \to y}$ attained by making use of the former, namely such that ${\displaystyle g(0)=z}$ and ${\displaystyle g(Sn)=f(g(n))}$. This postulate is akin to the transfinite recursive theorem, except it is restricted to set functions and finite ordinals, i.e. there is no clause about limit ordinals. It functions as the set theoretical equivalent of a natural numbers object in category theory. This then enables a full interpretation of Heyting arithmetic ${\displaystyle {\mathsf {HA}}}$ in our set theory, including addition and multiplication functions.

With this, ${\displaystyle {\mathbb {N} }}$ and ${\displaystyle {\mathbb {Z} }}$ are well-founded, in the sense of the inductive subsets formulation. Further, arithmetic of rational numbers ${\displaystyle {\mathbb {Q} }}$ can then also be defined and its properties, like uniqueness and countability, be proven. A set theory with this will also prove that, for any naturals ${\displaystyle n}$ and ${\displaystyle m}$, the function spaces

${\displaystyle {\{0,1,\dots ,n-1\}}\to {\{0,1,\dots ,m-1\}}}$

are sets. (As an aside, note that, moreover, a bounded variant of this iteration schema that grants the existence of a unique such ${\displaystyle g}$, proves the existence of a transitive closure for every set with respect to ${\displaystyle \in }$.)

Now conversely, a proof of the spelled out ${\displaystyle {\mathsf {HA}}}$-model enabling iteration principle can be based on the collection of functions one would want to write as the union ${\displaystyle \cup _{n\in \omega }y^{\{0,1,\dots ,n-1\}}}$. The existence of this becomes provable when asserting that the individual function spaces ${\displaystyle y^{n}}$ form sets themselves, which may be written as

${\displaystyle \forall (n\in \omega ).\forall y.\ \ \exists h.h=y^{n}}$

This is modest, insofar as a collection of functions from finite domains into sets ${\displaystyle y}$ are e.g. countable in ${\displaystyle {\mathsf {ZF}}}$. Notably, adoption of such axioms has genuine set theoretical flavor, in contrast to a direct embedding arithmetic principles into our theory. It may further motivate the discussion of a stronger such exponentiation axiom below. This more set theoretical axiom will, however, still not prove the full induction schema for formulas with quantifiers over sets.

#### Moderate induction in ECST

The second universally quantified conjunct in the strong axiom of Infinity expresses mathematical induction for all ${\displaystyle y}$ in the universe of discourse, i.e. for sets. This is because sets ${\displaystyle y}$ can be read as corresponding to predicates and the consequent ${\displaystyle \omega \subset y}$ states that all ${\displaystyle n\in \omega }$ fulfill said predicate. Defining subsets of ${\displaystyle \omega }$, the theory ${\displaystyle {\mathsf {ECST}}}$ proves induction for all predicates ${\displaystyle \phi (n)}$ involving only set-bounded quantifiers, and so with it also induction as in ${\displaystyle {\mathsf {HA}}}$.

The much stronger axiom of full mathematical induction for any predicate expressed though set theory language could also be adopted at this point in our development. That induction principle follows from full (i.e. unbounded) Separation as well as from (full) Set induction.

Warning note: In naming induction statements, one must take care not to conflate terminology with arithmetic theories. The first-order induction schema of natural number arithmetic theory claims induction for all predicates definable in the language of first-order arithmetic, namely predicates of just numbers. So to interpret the axiom schema of ${\displaystyle {\mathsf {HA}}}$, one interprets these arithmetical formulas. In that context, the bounded quantification specifically means quantification over a finite range of numbers. One may also speak about the induction in second-order arithmetic, explicitly expressed for subsets of the naturals. The class of subsets can be taken to correspond to a richer collection of formulas than the first-order arithmetic definable ones. Typical set theories like the one discussed here are also first-order, but those theories are not arithmetics and so formulas may also quantify over the subsets of the naturals. When discussing the strength of axioms concerning numbers, it is also important to keep in mind that the arithmetical and the set theoretical framework do not share a common signature. Likewise, care must always be taken with insights about totality of functions. In computability theory, the μ operator enables all partial general recursive functions (or programs, in the sense that they are Turing computable), including ones e.g. non-primitive recursive but ${\displaystyle {\mathrm {PA} }}$-total, such as the Ackermann function. The definition of the operator involves predicates over the naturals and so the theoretical analysis of functions and their totality depends on the formal framework and proof calculus at hand.

In the program of reverse mathematics, all mathematical objects discussed are encoded as naturals or subsets of naturals. Second-order arithmetic theories with very low complexity comprehension have a language that does not merely express arithmetical sets, while all sets of naturals particular such theories prove to exist are just computable sets. Theorems therein can be a relevant reference point for weak set theories with a set of naturals, predicative separation and only some further restricted form of induction. Constructive reverse mathematics exists as a field but is less developed than its classical counterpart.[15]

#### Induction without infinite sets

Before discussing even classically uncountable sets, this last section takes a step back to a context more akin to ${\displaystyle {\mathsf {BCST}}}$. The addition of numbers, considered as relation on triples, is an infinite collection, just like collection of natural numbers themselves. But note that induction schemas may be adopted (for sets, ordinals or in conjunction with a natural number sort), without ever postulating that the collection of naturals exists as a set. As noted, Heyting arithmetic ${\displaystyle {\mathsf {HA}}}$ is bi-interpretable with such a constructive set theory, in which all sets are postulated to be in bijection with an ordinal. The BIT predicate is a common means to encode sets in arithmetic.

This paragraph lists a few weak natural number induction principles studied in the proof theory of arithmetic theories with addition and multiplication in their signature. This is the framework where these principles are most well understood. The theories may be defined via bounded formulations or variations on induction schemas that may furthermore only allow for predicates of restricted complexity. On the classical first-order side, this leads to theories between the Robinson arithmetic ${\displaystyle {\mathsf {Q}}}$ and Peano arithmetic ${\displaystyle {\mathsf {PA}}}$: The theory ${\displaystyle {\mathsf {Q}}}$ does not have any induction. ${\displaystyle {\mathsf {PA}}}$ has full mathematical induction for arithmetical formulas and has ordinal ${\displaystyle \varepsilon _{0}}$, meaning the theory lets one encode ordinals of weaker theories as recursive relation on just the naturals. Theories may also include additional symbols for particular functions. Many of the well studied arithmetic theories are weak regarding proof of totality for some more fast growing functions. Some of the most basic examples of arithmetics include elementary function arithmetic ${\displaystyle {\mathsf {EFA}}}$, which includes induction for just bounded arithmetical formulas, here meaning with quantifiers over finite number ranges. The theory has a proof theoretic ordinal (the least not provenly recursive well-ordering) of ${\displaystyle \omega ^{3}}$. The ${\displaystyle \Sigma _{1}^{0}}$-induction schema for arithmetical existential formulas allows for induction for those properties of naturals a validation of which is computable via a finite search with unbound (any, but finite) runtime. The schema is also classically equivalent to the ${\displaystyle \Pi _{1}^{0}}$-induction schema. The relatively weak classical first-order arithmetic which adopts that schema is denoted ${\displaystyle {\mathsf {I\Sigma }}_{1}}$ and proves the primitive recursive functions total. The theory ${\displaystyle {\mathsf {I\Sigma }}_{1}}$ is ${\displaystyle \Pi _{2}^{0}}$-conservative over primitive recursive arithmetic ${\displaystyle {\mathsf {PRA}}}$. Note that the ${\displaystyle \Sigma _{1}^{0}}$-induction is also part of the second-order reverse mathematics base system ${\displaystyle {\mathsf {RCA}}_{0}}$, its other axioms being ${\displaystyle {\mathsf {Q}}}$ plus ${\displaystyle \Delta _{1}^{0}}$-comprehension of subsets of naturals. The theory ${\displaystyle {\mathsf {RCA}}_{0}}$ is ${\displaystyle \Pi _{1}^{1}}$-conservative over ${\displaystyle {\mathsf {I\Sigma }}_{1}}$. Those last mentioned arithmetic theories all have ordinal ${\displaystyle \omega ^{\omega }}$.

Let us mention one more step beyond the ${\displaystyle \Sigma _{1}^{0}}$-induction schema. Lack of stronger induction schemas means, for example, that some infinite versions of the pigeon hole principle are unprovable. One relatively weak one being the Ramsey theorem type claim here expressed as follows: For any ${\displaystyle m>0}$ and coding of a coloring map ${\displaystyle f}$, associating each ${\displaystyle n\in \omega }$ with a color ${\displaystyle \{0,1,\dots ,m-1\}}$, it is not the case that for every color ${\displaystyle c there exists a threshold input number ${\displaystyle n_{c}}$ beyond which ${\displaystyle c}$ is not ever the mappings return value anymore. (In the classical context and in terms of sets, this claim about coloring may be phrased positively, as saying that there always exists at least one return value ${\displaystyle k}$ such that, in effect, for some infinite domain ${\displaystyle K\subset \omega }$ it holds that ${\displaystyle \forall (n\in K).f(n)=k}$. In words, when ${\displaystyle f}$ provides infinite enumerated assignments, each being of one of ${\displaystyle m}$ different possible colors, it is claimed that a particular ${\displaystyle k}$ coloring infinitely many numbers always exists and that the set can thus be specified, without even having to inspect properties of ${\displaystyle f}$. When read constructively, one would want ${\displaystyle k}$ to be concretely specifiable and so that formulation is a stronger claim.) Higher indirection, than in induction for mere existential statements, is needed to formally reformulate such a negation (the Ramsey theorem type claim in the original formulation above) and prove it. Namely to restate the problem in terms of the negation of the existence of one joint threshold number, depending on all the hypothetical ${\displaystyle n_{c}}$'s, beyond which the function would still have to attain some color value. More specifically, the strength of the required bounding principle is strictly between the induction schema in ${\displaystyle {\mathsf {I\Sigma }}_{1}^{0}}$ and ${\displaystyle {\mathsf {I\Sigma }}_{2}^{0}}$. For properties in terms of return values of functions on finite domains, brute force verification through checking all possible inputs has computational overhead which is larger the larger the size of the domain, but always finite. Acceptance of an induction schema as in ${\displaystyle {\mathsf {I\Sigma }}_{2}^{0}}$ validates the former so called infinite pigeon hole principle, which concerns unbounded domains, and so is about mappings with infinitely many inputs.

It is worth noting that in the program of predicative arithmetic, even the mathematical induction schema has been criticized as possibly being impredicative, when natural numbers are defined as the object which fulfill this schema, which itself is defined in terms of all naturals.

### Exponentiation

Classical ${\displaystyle {\mathsf {ZFC}}}$ without the Powerset axiom is still consistent with all existing sets of reals being subcountable, and there even countable.[16] Possible choice principles were discussed, a weakened form of the Separation schema was already adopted, and more of the standard ${\displaystyle {\mathsf {ZFC}}}$ axioms shall be weakened for a more predicative and constructive theory. The first one of those is the Powerset axiom, which is adopted in the form of the space of characteristic functions, itself tied to exactly the decidable subclasses. So consider the axiom ${\displaystyle {\mathrm {Exp} }}$.

 Exponentiation ${\displaystyle \forall x.\forall y.\ \ \exists h.\forall f.{\big (}f\in h\leftrightarrow f\in y^{x}{\big )}}$

The formulation here uses the convenient notation for function spaces. Otherwise the axiom is lengthier, characterizing ${\displaystyle h}$ using bounded quantifiers in the total function predicate. In words, the axiom says that given two sets ${\displaystyle x,y}$, the class ${\displaystyle y^{x}}$ of all functions is, in fact, also a set. This is certainly required, for example, to formalize the object map of an internal hom-functor like ${\displaystyle {\mathrm {hom} }({\mathbb {N} },-)}$.

Existence statements like Exponentiation, i.e. function spaces being sets, enable the derivation of more sets via bounded Separation. Adopting the axiom, quantification ${\displaystyle \forall f}$ over the elements of certain classes of functions only ranges over a set, also when such function spaces are even classically uncountable. E.g. the collection of all functions ${\displaystyle f\colon \omega \to 2}$ where ${\displaystyle 2=\{0,1\}}$, i.e. the set ${\displaystyle 2^{\mathbb {N} }}$ of points underlying the Cantor space, is uncountable, by Cantor's diagonal argument, and can at best be taken to be a subcountable set. Roughly, classically uncountable sets tend to not have computably decidable equality. Vanilla intuitionistic mathematics does not prove a function space like ${\displaystyle {\mathbb {N} }^{\mathbb {N} }}$ to be not enumerable. (In this section and beyond, the symbol for the semiring of natural numbers in expressions like ${\displaystyle y^{\mathbb {N} }}$ is used, or written ${\displaystyle \omega \to y}$, just to avoid conflation of cardinal- with ordinal exponentiation.)

#### On countable sets

Enumerable forms of the pigeon hole principle can now be proven, e.g. that on a finitely indexed set, every auto-injection is also a surjection. At last, the finitely indexed discrete sets are just the finite sets. In particular, finitely indexed subsets of ${\displaystyle \omega }$ are finite. Cartesian products of finitely indexed sets is finitely indexed. The finitely indexed union of a family of subfinitely indexed resp. subcountable sets is itself subfinitely indexed resp. subcountable. These do not hold in ${\displaystyle {\mathsf {ECTS}}}$, but not all of these need full Exponentiation to be validated.

With Exponentiation, the union of all finite sequences over a countable set is now a countable set. For any countable family of counting functions together with their ranges, the theory proves the union of those ranges to be countable. In contrast, not assuming countable choice, even ${\displaystyle {\mathsf {ZF}}}$ is consistent with the uncountable set ${\displaystyle {\mathbb {R} }}$ being the union of a countable set of countable sets.

The set theory now proves the existence of any primitive recursive function in ${\displaystyle x\times \omega \to y}$, and in particular in the uncountable function spaces out of ${\displaystyle \omega }$. Indeed, with function spaces and the finite von Neumann ordinals as domains, we can model ${\displaystyle {\mathsf {HA}}}$ as discussed, and thus encode ordinals in the arithmetic. One then furthermore obtains the ordinal-exponentiated number ${\displaystyle \omega ^{\omega }}$ as a set, which may be characterized as ${\displaystyle \cup _{n\in \omega }\omega ^{n}}$, the counted set of words over an infinite alphabet.

As far as comprehension goes, the dependent or indexed products ${\displaystyle \Pi _{i\in x}\,y_{i}}$ are now sets. The theory now proves the collection of all the countable subsets of any set (the collection is a subclass of the powerclass) to be a set.

#### The class of subsets of a set

The characterization of the class ${\displaystyle {\mathcal {P}}_{x}}$ of all subsets of a set ${\displaystyle x}$ involves unbounded universal quantification, namely ${\displaystyle \forall u.\left(u\subset x\leftrightarrow u\in {\mathcal {P}}_{x}\right)}$. Here ${\displaystyle \subset }$ has been defined in terms of the membership predicate ${\displaystyle \in }$ above. So in a mathematical set theory framework, the power class is defined not in a bottom-up construction from its constituents (like an algorithm on a list, that e.g. maps ${\displaystyle \langle a,b\rangle \mapsto \langle \langle \rangle ,\langle a\rangle ,\langle b\rangle ,\langle a,b\rangle \rangle }$) but via a comprehension over all sets. If ${\displaystyle {\mathcal {P}}_{x}}$ is a set, that defining quantification even ranges over ${\displaystyle {\mathcal {P}}_{x}}$, which makes the axiom of powerset impredicative. The statement ${\displaystyle y={\mathcal {P}}_{x}}$ itself is ${\displaystyle \Pi _{1}}$.

The richness of the powerclass in a theory without excluded middle can best be understood by considering small classically finite sets. For any proposition ${\displaystyle P}$, consider the subclass ${\displaystyle B:=\{x\in 1\mid P\}}$ of ${\displaystyle 1}$ (i.e. ${\displaystyle \{0\}}$ or ${\displaystyle S0}$). It equals ${\displaystyle B=0}$ when ${\displaystyle P}$ can be rejected and it equals ${\displaystyle B=1}$ (i.e. ${\displaystyle B=S0}$), when ${\displaystyle P}$ can be proven. But ${\displaystyle P}$ may also not be decidable at all. Consider three different undecidable proposition, none of which provenly imply another. They can ben used to define three subclasses of the singleton ${\displaystyle 1}$, none of which are provenly the same. In this view, the powerclass ${\displaystyle {\mathcal {P}}_{1}}$ of the singleton, usually denoted by ${\displaystyle \Omega }$, is called the truth value algebra and does not necessarily provenly have only two elements.

With Exponentiation, ${\displaystyle {\mathcal {P}}_{1}}$ being a set already implies Powerset for sets in general. The proof is via replacement for the association of ${\displaystyle f\in {{\mathcal {P}}_{1}}^{x}}$ to ${\displaystyle \{z\in x\mid 0\in f(z)\}\in {\mathcal {P}}_{x}}$, and an argument why all subsets are covered.

The set ${\displaystyle 2^{x}}$, of functions taking values in ${\displaystyle 2:=\{0,1\}}$ (i.e. ${\displaystyle SS0}$) on a set ${\displaystyle x}$, injects into the function space ${\displaystyle {{\mathcal {P}}_{1}}^{x}}$ and corresponds to just the decidable subsets of ${\displaystyle x}$. If the theory proves ${\displaystyle B}$ above a set (as for example ${\displaystyle {\mathsf {IZF}}}$ unconditionally does), then the subset ${\displaystyle b:=\{\langle 0,B\rangle \}}$ of ${\displaystyle 1\times {\mathcal {P}}_{1}}$ is a function ${\displaystyle b\colon 1\to {\mathcal {P}}_{1}}$ with ${\displaystyle {\big (}b(0)=1{\big )}\leftrightarrow P}$. To claim that ${\displaystyle {\mathcal {P}}_{1}=2}$ is to claim that excluded middle holds for ${\displaystyle P}$.

It has been pointed out that the empty set ${\displaystyle 0}$ and the set ${\displaystyle 1}$ itself are of course two subsets of ${\displaystyle 1}$. Whether also ${\displaystyle {\mathcal {P}}_{1}\subset 2}$ is true in a theory is contingent on a simple disjunction:

${\displaystyle {\big (}\forall x.x\subset 1\to (0\in x\lor 0\notin x){\big )}\to \,{\mathcal {P}}_{1}\subset 2}$.

So assuming ${\displaystyle {\mathrm {PEM} }}$ for just bounded formulas, predicative Separation then lets one demonstrate that the powerclass ${\displaystyle {\mathcal {P}}_{1}}$ is a set. And so in this context, also full Choice proves Powerset. Moreover, with bounded excluded middle, ${\displaystyle {\mathcal {P}}_{x}}$ is in bijection with ${\displaystyle 2^{x}}$. See also the discussion of ${\displaystyle {\mathsf {IZF}}}$ below.

Full Separation is equivalent to just assuming that each individual subclass of ${\displaystyle 1}$ is a set. Assuming full Separation, both full Choice and Regularity prove ${\displaystyle {\mathrm {PEM} }}$.

Assuming ${\displaystyle {\mathrm {PEM} }}$ in this theory, Set induction becomes equivalent to Regularity and Replacement becomes capable of proving full Separation.

#### Metalogic

While the theory ${\displaystyle {\mathsf {ECST}}+{\mathrm {Exp} }}$ does not exceed the consistency strength of Heyting arithmetic, adding Excluded Middle gives a theory proving the same theorems as classical ${\displaystyle {\mathsf {ZF}}}$ minus Regularity! Thus, adding Regularity as well as either ${\displaystyle {\mathrm {PEM} }}$ or full Separation to ${\displaystyle {\mathsf {ECST}}+{\mathrm {Exp} }}$ gives full classical ${\displaystyle {\mathsf {ZF}}}$. Adding full Choice and full Separation gives ${\displaystyle {\mathsf {ZFC}}}$ minus Regularity.

So this would thus lead to a theory beyond the strength of typical type theory.

#### Category and type theoretic notions

So in this context with Exponentiation, function spaces are more accessible than classes of subsets, as is the case with exponential objects resp. subobjects in category theory. In category theoretical terms, the theory ${\displaystyle {\mathsf {BCST}}+{\mathrm {Exp} }}$ essentially corresponds to constructively well-pointed Cartesian closed Heyting pretoposes with (whenever Infinity is adopted) a natural numbers object. Existence of powerset is what would turn a Heyting pretopos into an elementary topos. Every such topos that interprets ${\displaystyle {\mathsf {ZF}}}$ is of course a model of these weaker theories, but locally Cartesian closed pretoposes have been defined that e.g. interpret theories with Exponentiation but reject full Separation and Powerset. A form of ${\displaystyle {\mathrm {PEM} }}$ corresponds to any subobject having a complement, in which case we call the topos Boolean. Diaconescu's theorem in its original topos form says that this hold iff any coequalizer of two nonintersecting monomorphisms has a section. The latter is a formulation of choice. Barr's theorem states that any topos admits a surjection from a Boolean topos onto it, relating to classical statements being provable intuitionistically.

In type theory, the expression "${\displaystyle x\to y}$" exists on its own and denotes function spaces, a primitive notion. These types (or, in set theory, classes or sets) naturally appear, for example, as the type of the currying bijection between ${\displaystyle (z\times x)\to y}$ and ${\displaystyle z\to y^{x}}$, an adjunction. A typical type theory with general programming capability - and certainly those that can model ${\displaystyle {\mathsf {CZF}}}$, which is considered a constructive set theory - will have a type of integers and function spaces representing ${\displaystyle {\mathbb {Z} }\to {\mathbb {Z} }}$, and as such also include types that are not countable. This is just to say, or implies, that among the function terms ${\displaystyle f\colon {\mathbb {Z} }\to ({\mathbb {Z} }\to {\mathbb {Z} })}$, none have the property of being a surjection.

Constructive set theories are also studied in the context of applicative axioms.

### Analysis

In this section the strength of ${\displaystyle {\mathsf {ECST}}+{\mathrm {Exp} }}$ is elaborated on. For context, possible further principles are mentioned, which are not necessarily classical and also not generally considered constructive. Here a general warning is in order: When reading proposition equivalence claims in the computable context, one shall always be aware which choice, induction and comprehension principles are silently assumed. See also the related constructive analysis, feasible analysis and computable analysis.

The theory proves uniqueness of Archimedean, Dedekind complete (pseudo-)ordered fields, with equivalence by a unique isomorphism. The prefix "pseudo" here highlights that the order will, in any case, constructively not always be decidable. This result is relevant assuming complete such models exist as sets.

#### Cauchy sequences

Exponentiation implies recursion principles and so in ${\displaystyle {\mathsf {ECST}}+{\mathrm {Exp} }}$, one can comfortably reason about sequences ${\displaystyle s\colon \omega \to {\mathbb {Q} }}$, their regularity properties such as ${\displaystyle |s_{n}-s_{m}|\leq {\tfrac {1}{n}}+{\tfrac {1}{m}}}$, or about shrinking intervals in ${\displaystyle \omega \to ({\mathbb {Q} }\times {\mathbb {Q} })}$. So this enables speaking of Cauchy sequences and their arithmetic. This is also the approach to analysis taken in second-order arithmetic.

#### Cauchy reals

Any Cauchy real number is a collection of sequences, i.e. subset of a set of functions on ${\displaystyle \omega }$ constructed with respect to an equivalence relation. Even in the strong theory ${\displaystyle {\mathsf {IZF}}}$ with a strengthened form of Collection, the Cauchy reals are poorly behaved when not assuming a form of countable choice, and ${\displaystyle {\mathrm {AC} _{\omega ,2}}}$ suffices for most results. This concerns completeness of equivalence classes of such sequences, existence of a modulus of convergence for all Cauchy sequences and the preservation of such a modulus when taking limits.[17]An alternative approach that is slightly better behaved is to work a collection of Cauchy reals together a choice of modulus, i.e. not with just the real numbers but with a set of pairs, or even with a fixed modulus shared by all real numbers.

#### Towards the Dedekind reals

As in the classical theory, Dedekind cuts are characterized using subsets of algebraic structures such as ${\displaystyle {\mathbb {Q} }}$: The properties of being inhabited, numerically bounded above, "closed downwards" and "open upwards" are all bounded formulas with respect to the given set underlying the algebraic structure. A standard example of a cut, the first component indeed exhibiting these properties, is the representation of ${\displaystyle {\sqrt {2}}}$ given by

${\displaystyle {\big \langle }\{x\in {\mathbb {Q} }\mid x<0\lor x^{2}<2\},\,\{x\in {\mathbb {Q} }\mid 0

(Depending on the convention for cuts, either of the two parts or neither, like here, may makes use of the sign ${\displaystyle \leq }$.)

The theory given by the axioms so far validates that a Pseudo-order|pseudo-ordered field that is also Archimedean and Dedekind complete, if it exists at all, is in this way characterized uniquely, up to isomorphism. However, the existence of just function spaces such as ${\displaystyle \{0,1\}^{\mathbb {Q} }}$ does not grant ${\displaystyle {{\mathcal {P}}_{\mathbb {Q} }}}$ to be a set, and so neither is the class of all subsets of ${\displaystyle {\mathbb {Q} }}$ that do fulfill the named properties. What is required for the class of Dedekind reals to be a set is an axiom regarding existence of a set of subsets and this is discussed further below in the section on Binary refinement. In a context without ${\displaystyle {\mathrm {PEM} }}$ or Powerset, countable choice into finite sets is assumed to prove the uncountability of the Dedekind reals.

Whether Cauchy or Dedekind reals, fewer statements about the arithmetic of the reals are decidable, compared to the classical theory.

#### Constructive schools

Most schools for constructive analysis validate some choice and also ${\displaystyle \mathrm {BD} }$-${\displaystyle {\mathbb {N} }}$, as defined in the second section on number bounds. Here are some other propositions employed in theories of constructive analysis that are not provable using just base intuitionistic logic:

• On the recursive mathematics side (the "Russian" or "Markovian" constructive framework with many abbreviations, e.g. ${\displaystyle {\mathsf {RUSS}}}$), first one has Markov's principle ${\displaystyle {\mathrm {MP} }}$, which is a form of proof by contradiction motivated by (unbound memory capacity) computable search. This has notable impact on statements about real numbers, as touched upon below. In this school one further even has the anti-classical constructive Church's thesis principle ${\displaystyle {\mathrm {CT} }}$, generally adopted for number-theoretic functions. Church's thesis principle expressed in the language of set theory and formulated for set functions postulates that these all correspond to computable programs that eventually halt on any argument. In computability theory, the natural numbers corresponding to indices of codes of the computable functions which are total are ${\displaystyle \Pi _{2}^{0}}$ in the arithmetical hierarchy, meaning membership of any index is affirmed by validating a ${\displaystyle \forall x\,\exists y}$ proposition. This is to say that such a collection of functions is still a mere subclass of the naturals and so is, when put in relation to some classical function spaces, conceptually small. In this sense, adopting ${\displaystyle {\mathrm {CT} }}$ postulate makes ${\displaystyle \omega \to \omega }$ into a "sparse" set, as viewed from classical set theory. Subcountability of sets can also be postulated independently.
• So on another end, on the Brouwerian intuitionist side (${\displaystyle {\mathsf {INT}}}$), there are bar induction, the decidable fan theorem ${\displaystyle {\mathrm {FAN} }_{\Delta }}$ saying decidable bars are uniform, which are amongst the weakest often discussed principles, Kripke's schema (with countable choice turning all subclasses of ${\displaystyle \omega }$ countable), or even Brouwer's anti-classical continuity principle, determining return values of what is established a function on unending sequences already through just finite initial segments.

Certain laws in both of those schools contradict ${\displaystyle {\mathrm {WLPO} }}$, so that choosing to adopt all principles from either school disproves theorems from classical analysis. ${\displaystyle {\mathrm {CT} }_{0}}$ is still consistent with some choice, but contradicts the classical ${\displaystyle {\mathrm {WKL} }}$ and ${\displaystyle {\mathrm {LLPO} }}$, explained next. The independence of premise rule with set existence premises is not fully understood, but as a number theoretic principle it is in conflict with the Russian school axioms in some frameworks. Notably, ${\displaystyle {\mathrm {CT} }_{0}}$ also contradicts ${\displaystyle {\mathrm {FAN} }_{\Delta }}$, meaning the constructive schools also cannot be combined in full. Indeed, some of the principles cannot be combined constructively simply because they together imply forms of ${\displaystyle {\mathrm {PEM} }}$, for example ${\displaystyle {\mathrm {MP} }}$ plus the countability of all subsets of the naturals. These combinations are then naturally also not consistent with further anti-classical principles.

### Non-constructive principles

Of course ${\displaystyle {\mathrm {PEM} }}$ and many principles defining intermediate logics are non-constructive. ${\displaystyle {\mathrm {PEM} }}$ and ${\displaystyle {\mathrm {WPEM} }}$, which is ${\displaystyle {\mathrm {PEM} }}$ for just negated propositions, can be presented as De Morgan's rules. This section shall instead be concerned with statements in terms of predicates - especially weaker ones, expressed in terms of a few quantifiers over sets, on top of decidable predicates on numbers. Referring back to the section on characteristic functions, one may call a collection ${\displaystyle A}$ searchable if it is searchable for all its decidable subsets ${\displaystyle \{0,1\}^{A}}$. This is a form of ${\displaystyle \exists }$-${\displaystyle {\mathrm {PEM} }}$ for ${\displaystyle A}$. Note that in the context of Exponentiation, such proposition on sets are now set-bound.

Non-constructive claims particularly valuable in the study of constructive analysis are commonly formulated as concerning all binary sequences, the characteristic functions on the arithmetic domain ${\displaystyle A=\omega }$. Examples of famous sentences that are of Goldbach type, i.e. can be written down in this ${\displaystyle \Pi _{1}^{0}}$-fashion, are the Goldbach conjecture, Fermat's last theorem but also the Riemann hypothesis. In raw ${\displaystyle {\mathsf {PA}}}$, example functions can be defined on ${\displaystyle {\mathbb {N} }}$ such that if ${\displaystyle {\mathsf {PA}}}$ is consistent, the competing ${\displaystyle \exists }$-${\displaystyle {\mathrm {PEM} }}$ disjuncts, of low complexity, are ${\displaystyle {\mathsf {PA}}}$-unprovable.

More generally, the arithmetic ${\displaystyle \exists }$-${\displaystyle {\mathrm {PEM} }}$, a most prominent non-constructive, essentially logical statement goes by the name limited principle of omniscience ${\displaystyle {\mathrm {LPO} }}$. In the constructive set theory ${\displaystyle {\mathsf {CZF}}}$ introduced below, it implies ${\displaystyle {\mathrm {BD} }}$-${\displaystyle {\mathbb {N} }}$, ${\displaystyle {\mathrm {MP} }}$, the ${\displaystyle \Pi _{1}^{0}}$-version of the fan theorem, but also ${\displaystyle {\mathrm {WKL} }}$ discussed below. ${\displaystyle {\mathrm {LPO} }}$ postulates a disjunctive property, as does the weaker decidability statement for functions being constant (${\displaystyle \Pi _{1}^{0}}$-sentences) ${\displaystyle {\mathrm {WLPO} }}$, the arithmetic ${\displaystyle \forall }$-${\displaystyle {\mathrm {PEM} }}$. The two are related in a similar way as is ${\displaystyle {\mathrm {PEM} }}$ versus ${\displaystyle {\mathrm {WPEM} }}$ and they essentially differ by ${\displaystyle {\mathrm {MP} }}$. ${\displaystyle {\mathrm {LPO} }}$ in turn implies the so-called "lesser" version ${\displaystyle {\mathrm {LLPO} }}$. This is the (arithmetic) ${\displaystyle \exists }$-version of the non-constructive De Morgan's rule for a negated conjunction. There are, for example, models of the strong set theory ${\displaystyle {\mathsf {IZF}}}$ which separate such statements, in the sense that they may validate ${\displaystyle {\mathrm {LLPO} }}$ but reject ${\displaystyle {\mathrm {WLPO} }}$.

Disjunctive principles about ${\displaystyle \Pi _{1}^{0}}$-sentences generally hint at equivalent formulations deciding apartness in analysis in a context with mild choice or ${\displaystyle {\mathrm {MP} }}$. The claim expressed by ${\displaystyle {\mathrm {LPO} }}$ translated to real numbers is equivalent to the claim that either equality or apartness of any two reals is decidable (it in fact decides the trichotomy). It is then also equivalent to the statement that every real is either rational or irrational - without the requirement for or construction of a witness for either disjunct. Likewise, the claim expressed by ${\displaystyle {\mathrm {LLPO} }}$ for real numbers is equivalent that the ordering ${\displaystyle \leq }$ of any two reals is decidable (dichotomy). It is then also equivalent to the statement that if the product of two reals is zero, then either of the reals is zero - again without a witness. Indeed, formulations of the three omniscience principles are then each equivalent to theorems of the apartness, equality or order of two reals in this way. Yet more can be said about the Cauchy sequences that are augmented with a modulus of convergence.

A famous source of computable undecidability - and in turn also of a broad range of undecidable propositions - is the predicate expressing a computer program to be total.

#### Infinite trees

Through the relation between computability and the arithmetical hierarchy, insights in this classical study are also revealing for constructive considerations. A basic insight of reverse mathematics concerns computable infinite finitely branching binary trees. Such a tree may e.g. be encoded as an infinite set of finite sets

${\displaystyle T\,\subset \,\bigcup _{n\in \omega }\{0,1\}^{\{0,1,\dots ,n-1\}}}$,

with decidable membership, and those trees then provenly contain elements of arbitrary big finite size. The so called Weak Kőnig's lemma ${\displaystyle {\mathrm {WKL} }}$ states: For such ${\displaystyle T}$, there always exists an infinite path in ${\displaystyle \omega \to \{0,1\}}$, i.e. an infinite sequence such that all its initial segments are part of the tree. In reverse mathematics, the second-order arithmetic ${\displaystyle {\mathsf {RCA}}_{0}}$ does not prove ${\displaystyle {\mathrm {WKL} }}$. To understand this, note that there are computable trees ${\displaystyle K}$ for which no computable such path through it exists. To prove this, one enumerates the partial computable sequences and then diagonalizes all total computable sequences in one partial computable sequences ${\displaystyle d}$. One can then roll out a certain tree ${\displaystyle K}$, one exactly compatible with the still possible values of ${\displaystyle d}$ everywhere, which by constr