P. 139 of Theorem List - Intuitionistic Logic Explorer

Theorem List for Intuitionistic Logic Explorer - 13801-13900   *Has distinct variable group(s)

Type	Label	Description
Statement
Theorem	bj-unex 13801	unex 4419 from bounded separation. (Contributed by BJ, 13-Nov-2019.) (Proof modification is discouraged.)
|- A e. _V   &    |- B e. _V   =>    |- ( A u. B ) e. _V
Theorem	bdunexb 13802	Bounded version of unexb 4420. (Contributed by BJ, 13-Nov-2019.) (Proof modification is discouraged.)
|- BOUNDED A   &    |- BOUNDED B   =>    |- ( ( A e. _V /\ B e. _V ) <-> ( A u. B ) e. _V )
Theorem	bj-unexg 13803	unexg 4421 from bounded separation. (Contributed by BJ, 13-Nov-2019.) (Proof modification is discouraged.)
|- ( ( A e. V /\ B e. W ) -> ( A u. B ) e. _V )
Theorem	bj-sucexg 13804	sucexg 4475 from bounded separation. (Contributed by BJ, 13-Nov-2019.) (Proof modification is discouraged.)
|- ( A e. V -> suc A e. _V )
Theorem	bj-sucex 13805	sucex 4476 from bounded separation. (Contributed by BJ, 13-Nov-2019.) (Proof modification is discouraged.)
|- A e. _V   =>    |- suc A e. _V
12.2.9.1  Delta_0-classical logic
Axiom	ax-bj-d0cl 13806	Axiom for Δ0-classical logic. (Contributed by BJ, 2-Jan-2020.)
|- BOUNDED ph   =>    |- DECID ph
Theorem	bj-d0clsepcl 13807	Δ0-classical logic and separation implies classical logic. (Contributed by BJ, 2-Jan-2020.) (Proof modification is discouraged.)
|- DECID ph
12.2.9.2  Inductive classes and the class of natural number ordinals
Syntax	wind 13808	Syntax for inductive classes.
wff Ind A
Definition	df-bj-ind 13809*	Define the property of being an inductive class. (Contributed by BJ, 30-Nov-2019.)
|- (Ind A <-> ( (/) e. A /\ A. x e. A suc x e. A ) )
Theorem	bj-indsuc 13810	A direct consequence of the definition of Ind. (Contributed by BJ, 30-Nov-2019.)
|- (Ind A -> ( B e. A -> suc B e. A ) )
Theorem	bj-indeq 13811	Equality property for Ind. (Contributed by BJ, 30-Nov-2019.)
|- ( A = B -> (Ind A <-> Ind B ) )
Theorem	bj-bdind 13812	Boundedness of the formula "the setvar x is an inductive class". (Contributed by BJ, 30-Nov-2019.)
|- BOUNDED Ind x
Theorem	bj-indint 13813*	The property of being an inductive class is closed under intersections. (Contributed by BJ, 30-Nov-2019.)
|- Ind |^| { x e. A | Ind x }
Theorem	bj-indind 13814*	If A is inductive and B is "inductive in A", then ( A i^i B ) is inductive. (Contributed by BJ, 25-Oct-2020.)
|- ( (Ind A /\ ( (/) e. B /\ A. x e. A ( x e. B -> suc x e. B ) ) ) -> Ind ( A i^i B ) )
Theorem	bj-dfom 13815	Alternate definition of om, as the intersection of all the inductive sets. Proposal: make this the definition. (Contributed by BJ, 30-Nov-2019.)
|- om = |^| { x | Ind x }
Theorem	bj-omind 13816	om is an inductive class. (Contributed by BJ, 30-Nov-2019.)
|- Ind om
Theorem	bj-omssind 13817	om is included in all the inductive sets (but for the moment, we cannot prove that it is included in all the inductive classes). (Contributed by BJ, 30-Nov-2019.) (Proof modification is discouraged.)
|- ( A e. V -> (Ind A -> om C_ A ) )
Theorem	bj-ssom 13818*	A characterization of subclasses of om. (Contributed by BJ, 30-Nov-2019.) (Proof modification is discouraged.)
|- ( A. x (Ind x -> A C_ x ) <-> A C_ om )
Theorem	bj-om 13819*	A set is equal to om if and only if it is the smallest inductive set. (Contributed by BJ, 30-Nov-2019.) (Proof modification is discouraged.)
|- ( A e. V -> ( A = om <-> (Ind A /\ A. x (Ind x -> A C_ x ) ) ) )
Theorem	bj-2inf 13820*	Two formulations of the axiom of infinity (see ax-infvn 13823 and bj-omex 13824) . (Contributed by BJ, 30-Nov-2019.) (Proof modification is discouraged.)
|- ( om e. _V <-> E. x (Ind x /\ A. y (Ind y -> x C_ y ) ) )
12.2.9.3  The first three Peano postulates The first three Peano postulates follow from constructive set theory (actually, from its core axioms). The proofs peano1 4571 and peano3 4573 already show this. In this section, we prove bj-peano2 13821 to complete this program. We also prove a preliminary version of the fifth Peano postulate from the core axioms.
Theorem	bj-peano2 13821	Constructive proof of peano2 4572. Temporary note: another possibility is to simply replace sucexg 4475 with bj-sucexg 13804 in the proof of peano2 4572. (Contributed by BJ, 18-Nov-2019.) (Proof modification is discouraged.)
|- ( A e. om -> suc A e. om )
Theorem	peano5set 13822*	Version of peano5 4575 when om i^i A is assumed to be a set, allowing a proof from the core axioms of CZF. (Contributed by BJ, 19-Nov-2019.) (Proof modification is discouraged.)
|- ( ( om i^i A ) e. V -> ( ( (/) e. A /\ A. x e. om ( x e. A -> suc x e. A ) ) -> om C_ A ) )
12.2.10  CZF: Infinity In the absence of full separation, the axiom of infinity has to be stated more precisely, as the existence of the smallest class containing the empty set and the successor of each of its elements.
12.2.10.1  The set of natural number ordinals In this section, we introduce the axiom of infinity in a constructive setting (ax-infvn 13823) and deduce that the class om of natural number ordinals is a set (bj-omex 13824).
Axiom	ax-infvn 13823*	Axiom of infinity in a constructive setting. This asserts the existence of the special set we want (the set of natural numbers), instead of the existence of a set with some properties (ax-iinf 4565) from which one then proves, using full separation, that the wanted set exists (omex 4570). "vn" is for "von Neumann". (Contributed by BJ, 14-Nov-2019.)
|- E. x (Ind x /\ A. y (Ind y -> x C_ y ) )
Theorem	bj-omex 13824	Proof of omex 4570 from ax-infvn 13823. (Contributed by BJ, 14-Nov-2019.) (Proof modification is discouraged.)
|- om e. _V
12.2.10.2  Peano's fifth postulate In this section, we give constructive proofs of two versions of Peano's fifth postulate.
Theorem	bdpeano5 13825*	Bounded version of peano5 4575. (Contributed by BJ, 19-Nov-2019.) (Proof modification is discouraged.)
|- BOUNDED A   =>    |- ( ( (/) e. A /\ A. x e. om ( x e. A -> suc x e. A ) ) -> om C_ A )
Theorem	speano5 13826*	Version of peano5 4575 when A is assumed to be a set, allowing a proof from the core axioms of CZF. (Contributed by BJ, 19-Nov-2019.) (Proof modification is discouraged.)
|- ( ( A e. V /\ (/) e. A /\ A. x e. om ( x e. A -> suc x e. A ) ) -> om C_ A )
12.2.10.3  Bounded induction and Peano's fourth postulate In this section, we prove various versions of bounded induction from the basic axioms of CZF (in particular, without the axiom of set induction). We also prove Peano's fourth postulate. Together with the results from the previous sections, this proves from the core axioms of CZF (with infinity) that the set of natural number ordinals satisfies the five Peano postulates and thus provides a model for the set of natural numbers.
Theorem	findset 13827*	Bounded induction (principle of induction when A is assumed to be a set) allowing a proof from basic constructive axioms. See find 4576 for a nonconstructive proof of the general case. See bdfind 13828 for a proof when A is assumed to be bounded. (Contributed by BJ, 22-Nov-2019.) (Proof modification is discouraged.)
|- ( A e. V -> ( ( A C_ om /\ (/) e. A /\ A. x e. A suc x e. A ) -> A = om ) )
Theorem	bdfind 13828*	Bounded induction (principle of induction when A is assumed to be bounded), proved from basic constructive axioms. See find 4576 for a nonconstructive proof of the general case. See findset 13827 for a proof when A is assumed to be a set. (Contributed by BJ, 22-Nov-2019.) (Proof modification is discouraged.)
|- BOUNDED A   =>    |- ( ( A C_ om /\ (/) e. A /\ A. x e. A suc x e. A ) -> A = om )
Theorem	bj-bdfindis 13829*	Bounded induction (principle of induction for bounded formulas), using implicit substitutions (the biconditional versions of the hypotheses are implicit substitutions, and we have weakened them to implications). Constructive proof (from CZF). See finds 4577 for a proof of full induction in IZF. From this version, it is easy to prove bounded versions of finds 4577, finds2 4578, finds1 4579. (Contributed by BJ, 21-Nov-2019.) (Proof modification is discouraged.)
|- BOUNDED ph   &    |- F/ x ps   &    |- F/ x ch   &    |- F/ x th   &    |- ( x = (/) -> ( ps -> ph ) )   &    |- ( x = y -> ( ph -> ch ) )   &    |- ( x = suc y -> ( th -> ph ) )   =>    |- ( ( ps /\ A. y e. om ( ch -> th ) ) -> A. x e. om ph )
Theorem	bj-bdfindisg 13830*	Version of bj-bdfindis 13829 using a class term in the consequent. Constructive proof (from CZF). See the comment of bj-bdfindis 13829 for explanations. (Contributed by BJ, 21-Nov-2019.) (Proof modification is discouraged.)
|- BOUNDED ph   &    |- F/ x ps   &    |- F/ x ch   &    |- F/ x th   &    |- ( x = (/) -> ( ps -> ph ) )   &    |- ( x = y -> ( ph -> ch ) )   &    |- ( x = suc y -> ( th -> ph ) )   &    |- F/_ x A   &    |- F/ x ta   &    |- ( x = A -> ( ph -> ta ) )   =>    |- ( ( ps /\ A. y e. om ( ch -> th ) ) -> ( A e. om -> ta ) )
Theorem	bj-bdfindes 13831	Bounded induction (principle of induction for bounded formulas), using explicit substitutions. Constructive proof (from CZF). See the comment of bj-bdfindis 13829 for explanations. From this version, it is easy to prove the bounded version of findes 4580. (Contributed by BJ, 21-Nov-2019.) (Proof modification is discouraged.)
|- BOUNDED ph   =>    |- ( ( [. (/) / x ]. ph /\ A. x e. om ( ph -> [. suc x / x ]. ph ) ) -> A. x e. om ph )
Theorem	bj-nn0suc0 13832*	Constructive proof of a variant of nn0suc 4581. For a constructive proof of nn0suc 4581, see bj-nn0suc 13846. (Contributed by BJ, 19-Nov-2019.) (Proof modification is discouraged.)
|- ( A e. om -> ( A = (/) \/ E. x e. A A = suc x ) )
Theorem	bj-nntrans 13833	A natural number is a transitive set. (Contributed by BJ, 22-Nov-2019.) (Proof modification is discouraged.)
|- ( A e. om -> ( B e. A -> B C_ A ) )
Theorem	bj-nntrans2 13834	A natural number is a transitive set. (Contributed by BJ, 22-Nov-2019.) (Proof modification is discouraged.)
|- ( A e. om -> Tr A )
Theorem	bj-nnelirr 13835	A natural number does not belong to itself. Version of elirr 4518 for natural numbers, which does not require ax-setind 4514. (Contributed by BJ, 24-Nov-2019.) (Proof modification is discouraged.)
|- ( A e. om -> -. A e. A )
Theorem	bj-nnen2lp 13836	A version of en2lp 4531 for natural numbers, which does not require ax-setind 4514. Note: using this theorem and bj-nnelirr 13835, one can remove dependency on ax-setind 4514 from nntri2 6462 and nndcel 6468; one can actually remove more dependencies from these. (Contributed by BJ, 28-Nov-2019.) (Proof modification is discouraged.)
|- ( ( A e. om /\ B e. om ) -> -. ( A e. B /\ B e. A ) )
Theorem	bj-peano4 13837	Remove from peano4 4574 dependency on ax-setind 4514. Therefore, it only requires core constructive axioms (albeit more of them). (Contributed by BJ, 28-Nov-2019.) (Proof modification is discouraged.)
|- ( ( A e. om /\ B e. om ) -> ( suc A = suc B <-> A = B ) )
Theorem	bj-omtrans 13838	The set om is transitive. A natural number is included in om. Constructive proof of elnn 4583. The idea is to use bounded induction with the formula x C_ om. This formula, in a logic with terms, is bounded. So in our logic without terms, we need to temporarily replace it with x C_ a and then deduce the original claim. (Contributed by BJ, 29-Dec-2019.) (Proof modification is discouraged.)
|- ( A e. om -> A C_ om )
Theorem	bj-omtrans2 13839	The set om is transitive. (Contributed by BJ, 29-Dec-2019.) (Proof modification is discouraged.)
|- Tr om
Theorem	bj-nnord 13840	A natural number is an ordinal class. Constructive proof of nnord 4589. Can also be proved from bj-nnelon 13841 if the latter is proved from bj-omssonALT 13845. (Contributed by BJ, 27-Oct-2020.) (Proof modification is discouraged.)
|- ( A e. om -> Ord A )
Theorem	bj-nnelon 13841	A natural number is an ordinal. Constructive proof of nnon 4587. Can also be proved from bj-omssonALT 13845. (Contributed by BJ, 27-Oct-2020.) (Proof modification is discouraged.)
|- ( A e. om -> A e. On )
Theorem	bj-omord 13842	The set om is an ordinal class. Constructive proof of ordom 4584. (Contributed by BJ, 29-Dec-2019.) (Proof modification is discouraged.)
|- Ord om
Theorem	bj-omelon 13843	The set om is an ordinal. Constructive proof of omelon 4586. (Contributed by BJ, 29-Dec-2019.) (Proof modification is discouraged.)
|- om e. On
Theorem	bj-omsson 13844	Constructive proof of omsson 4590. See also bj-omssonALT 13845. (Contributed by BJ, 27-Oct-2020.) (Proof modification is discouraged.) (New usage is discouraged.
|- om C_ On
Theorem	bj-omssonALT 13845	Alternate proof of bj-omsson 13844. (Contributed by BJ, 27-Oct-2020.) (Proof modification is discouraged.) (New usage is discouraged.)
|- om C_ On
Theorem	bj-nn0suc 13846*	Proof of (biconditional form of) nn0suc 4581 from the core axioms of CZF. See also bj-nn0sucALT 13860. As a characterization of the elements of om, this could be labeled "elom". (Contributed by BJ, 19-Nov-2019.) (Proof modification is discouraged.)
|- ( A e. om <-> ( A = (/) \/ E. x e. om A = suc x ) )
12.2.11  CZF: Set induction In this section, we add the axiom of set induction to the core axioms of CZF.
12.2.11.1  Set induction In this section, we prove some variants of the axiom of set induction.
Theorem	setindft 13847*	Axiom of set-induction with a disjoint variable condition replaced with a nonfreeness hypothesis. (Contributed by BJ, 22-Nov-2019.)
|- ( A. x F/ y ph -> ( A. x ( A. y e. x [ y / x ] ph -> ph ) -> A. x ph ) )
Theorem	setindf 13848*	Axiom of set-induction with a disjoint variable condition replaced with a nonfreeness hypothesis. (Contributed by BJ, 22-Nov-2019.)
|- F/ y ph   =>    |- ( A. x ( A. y e. x [ y / x ] ph -> ph ) -> A. x ph )
Theorem	setindis 13849*	Axiom of set induction using implicit substitutions. (Contributed by BJ, 22-Nov-2019.)
|- F/ x ps   &    |- F/ x ch   &    |- F/ y ph   &    |- F/ y ps   &    |- ( x = z -> ( ph -> ps ) )   &    |- ( x = y -> ( ch -> ph ) )   =>    |- ( A. y ( A. z e. y ps -> ch ) -> A. x ph )
Axiom	ax-bdsetind 13850*	Axiom of bounded set induction. (Contributed by BJ, 28-Nov-2019.)
|- BOUNDED ph   =>    |- ( A. a ( A. y e. a [ y / a ] ph -> ph ) -> A. a ph )
Theorem	bdsetindis 13851*	Axiom of bounded set induction using implicit substitutions. (Contributed by BJ, 22-Nov-2019.) (Proof modification is discouraged.)
|- BOUNDED ph   &    |- F/ x ps   &    |- F/ x ch   &    |- F/ y ph   &    |- F/ y ps   &    |- ( x = z -> ( ph -> ps ) )   &    |- ( x = y -> ( ch -> ph ) )   =>    |- ( A. y ( A. z e. y ps -> ch ) -> A. x ph )
Theorem	bj-inf2vnlem1 13852*	Lemma for bj-inf2vn 13856. Remark: unoptimized proof (have to use more deduction style). (Contributed by BJ, 8-Dec-2019.) (Proof modification is discouraged.)
|- ( A. x ( x e. A <-> ( x = (/) \/ E. y e. A x = suc y ) ) -> Ind A )
Theorem	bj-inf2vnlem2 13853*	Lemma for bj-inf2vnlem3 13854 and bj-inf2vnlem4 13855. Remark: unoptimized proof (have to use more deduction style). (Contributed by BJ, 8-Dec-2019.) (Proof modification is discouraged.)
|- ( A. x e. A ( x = (/) \/ E. y e. A x = suc y ) -> (Ind Z -> A. u ( A. t e. u ( t e. A -> t e. Z ) -> ( u e. A -> u e. Z ) ) ) )
Theorem	bj-inf2vnlem3 13854*	Lemma for bj-inf2vn 13856. (Contributed by BJ, 8-Dec-2019.) (Proof modification is discouraged.)
|- BOUNDED A   &    |- BOUNDED Z   =>    |- ( A. x e. A ( x = (/) \/ E. y e. A x = suc y ) -> (Ind Z -> A C_ Z ) )
Theorem	bj-inf2vnlem4 13855*	Lemma for bj-inf2vn2 13857. (Contributed by BJ, 8-Dec-2019.) (Proof modification is discouraged.)
|- ( A. x e. A ( x = (/) \/ E. y e. A x = suc y ) -> (Ind Z -> A C_ Z ) )
Theorem	bj-inf2vn 13856*	A sufficient condition for om to be a set. See bj-inf2vn2 13857 for the unbounded version from full set induction. (Contributed by BJ, 8-Dec-2019.) (Proof modification is discouraged.)
|- BOUNDED A   =>    |- ( A e. V -> ( A. x ( x e. A <-> ( x = (/) \/ E. y e. A x = suc y ) ) -> A = om ) )
Theorem	bj-inf2vn2 13857*	A sufficient condition for om to be a set; unbounded version of bj-inf2vn 13856. (Contributed by BJ, 8-Dec-2019.) (Proof modification is discouraged.)
|- ( A e. V -> ( A. x ( x e. A <-> ( x = (/) \/ E. y e. A x = suc y ) ) -> A = om ) )
Axiom	ax-inf2 13858*	Another axiom of infinity in a constructive setting (see ax-infvn 13823). (Contributed by BJ, 14-Nov-2019.) (New usage is discouraged.)
|- E. a A. x ( x e. a <-> ( x = (/) \/ E. y e. a x = suc y ) )
Theorem	bj-omex2 13859	Using bounded set induction and the strong axiom of infinity, om is a set, that is, we recover ax-infvn 13823 (see bj-2inf 13820 for the equivalence of the latter with bj-omex 13824). (Contributed by BJ, 8-Dec-2019.) (Proof modification is discouraged.) (New usage is discouraged.)
|- om e. _V
Theorem	bj-nn0sucALT 13860*	Alternate proof of bj-nn0suc 13846, also constructive but from ax-inf2 13858, hence requiring ax-bdsetind 13850. (Contributed by BJ, 8-Dec-2019.) (Proof modification is discouraged.) (New usage is discouraged.)
|- ( A e. om <-> ( A = (/) \/ E. x e. om A = suc x ) )
12.2.11.2  Full induction In this section, using the axiom of set induction, we prove full induction on the set of natural numbers.
Theorem	bj-findis 13861*	Principle of induction, using implicit substitutions (the biconditional versions of the hypotheses are implicit substitutions, and we have weakened them to implications). Constructive proof (from CZF). See bj-bdfindis 13829 for a bounded version not requiring ax-setind 4514. See finds 4577 for a proof in IZF. From this version, it is easy to prove of finds 4577, finds2 4578, finds1 4579. (Contributed by BJ, 22-Dec-2019.) (Proof modification is discouraged.)
|- F/ x ps   &    |- F/ x ch   &    |- F/ x th   &    |- ( x = (/) -> ( ps -> ph ) )   &    |- ( x = y -> ( ph -> ch ) )   &    |- ( x = suc y -> ( th -> ph ) )   =>    |- ( ( ps /\ A. y e. om ( ch -> th ) ) -> A. x e. om ph )
Theorem	bj-findisg 13862*	Version of bj-findis 13861 using a class term in the consequent. Constructive proof (from CZF). See the comment of bj-findis 13861 for explanations. (Contributed by BJ, 21-Nov-2019.) (Proof modification is discouraged.)
|- F/ x ps   &    |- F/ x ch   &    |- F/ x th   &    |- ( x = (/) -> ( ps -> ph ) )   &    |- ( x = y -> ( ph -> ch ) )   &    |- ( x = suc y -> ( th -> ph ) )   &    |- F/_ x A   &    |- F/ x ta   &    |- ( x = A -> ( ph -> ta ) )   =>    |- ( ( ps /\ A. y e. om ( ch -> th ) ) -> ( A e. om -> ta ) )
Theorem	bj-findes 13863	Principle of induction, using explicit substitutions. Constructive proof (from CZF). See the comment of bj-findis 13861 for explanations. From this version, it is easy to prove findes 4580. (Contributed by BJ, 21-Nov-2019.) (Proof modification is discouraged.)
|- ( ( [. (/) / x ]. ph /\ A. x e. om ( ph -> [. suc x / x ]. ph ) ) -> A. x e. om ph )
12.2.12  CZF: Strong collection In this section, we state the axiom scheme of strong collection, which is part of CZF set theory.
Axiom	ax-strcoll 13864*	Axiom scheme of strong collection. It is stated with all possible disjoint variable conditions, to show that this weak form is sufficient. The antecedent means that ph represents a multivalued function on a, or equivalently a collection of nonempty classes indexed by a, and the axiom asserts the existence of a set b which "collects" at least one element in the image of each x e. a and which is made only of such elements. That second conjunct is what makes it "strong", compared to the axiom scheme of collection ax-coll 4097. (Contributed by BJ, 5-Oct-2019.)
|- A. a ( A. x e. a E. y ph -> E. b ( A. x e. a E. y e. b ph /\ A. y e. b E. x e. a ph ) )
Theorem	strcoll2 13865*	Version of ax-strcoll 13864 with one disjoint variable condition removed and without initial universal quantifier. (Contributed by BJ, 5-Oct-2019.)
|- ( A. x e. a E. y ph -> E. b ( A. x e. a E. y e. b ph /\ A. y e. b E. x e. a ph ) )
Theorem	strcollnft 13866*	Closed form of strcollnf 13867. (Contributed by BJ, 21-Oct-2019.)
|- ( A. x A. y F/ b ph -> ( A. x e. a E. y ph -> E. b ( A. x e. a E. y e. b ph /\ A. y e. b E. x e. a ph ) ) )
Theorem	strcollnf 13867*	Version of ax-strcoll 13864 with one disjoint variable condition removed, the other disjoint variable condition replaced with a nonfreeness hypothesis, and without initial universal quantifier. Version of strcoll2 13865 with the disjoint variable condition on b , ph replaced with a nonfreeness hypothesis. This proof aims to demonstrate a standard technique, but strcoll2 13865 will generally suffice: since the theorem asserts the existence of a set b, supposing that that setvar does not occur in the already defined ph is not a big constraint. (Contributed by BJ, 21-Oct-2019.)
|- F/ b ph   =>    |- ( A. x e. a E. y ph -> E. b ( A. x e. a E. y e. b ph /\ A. y e. b E. x e. a ph ) )
Theorem	strcollnfALT 13868*	Alternate proof of strcollnf 13867, not using strcollnft 13866. (Contributed by BJ, 5-Oct-2019.) (Proof modification is discouraged.) (New usage is discouraged.)
|- F/ b ph   =>    |- ( A. x e. a E. y ph -> E. b ( A. x e. a E. y e. b ph /\ A. y e. b E. x e. a ph ) )
12.2.13  CZF: Subset collection In this section, we state the axiom scheme of subset collection, which is part of CZF set theory.
Axiom	ax-sscoll 13869*	Axiom scheme of subset collection. It is stated with all possible disjoint variable conditions, to show that this weak form is sufficient. The antecedent means that ph represents a multivalued function from a to b, or equivalently a collection of nonempty subsets of b indexed by a, and the consequent asserts the existence of a subset of c which "collects" at least one element in the image of each x e. a and which is made only of such elements. The axiom asserts the existence, for any sets a , b, of a set c such that that implication holds for any value of the parameter z of ph. (Contributed by BJ, 5-Oct-2019.)
|- A. a A. b E. c A. z ( A. x e. a E. y e. b ph -> E. d e. c ( A. x e. a E. y e. d ph /\ A. y e. d E. x e. a ph ) )
Theorem	sscoll2 13870*	Version of ax-sscoll 13869 with two disjoint variable conditions removed and without initial universal quantifiers. (Contributed by BJ, 5-Oct-2019.)
|- E. c A. z ( A. x e. a E. y e. b ph -> E. d e. c ( A. x e. a E. y e. d ph /\ A. y e. d E. x e. a ph ) )
12.2.14  Real numbers
Axiom	ax-ddkcomp 13871	Axiom of Dedekind completeness for Dedekind real numbers: every inhabited upper-bounded located set of reals has a real upper bound. Ideally, this axiom should be "proved" as "axddkcomp" for the real numbers constructed from IZF, and then Axiom ax-ddkcomp 13871 should be used in place of construction specific results. In particular, axcaucvg 7841 should be proved from it. (Contributed by BJ, 24-Oct-2021.)
|- ( ( ( A C_ RR /\ E. x x e. A ) /\ E. x e. RR A. y e. A y < x /\ A. x e. RR A. y e. RR ( x < y -> ( E. z e. A x < z \/ A. z e. A z < y ) ) ) -> E. x e. RR ( A. y e. A y <_ x /\ ( ( B e. R /\ A. y e. A y <_ B ) -> x <_ B ) ) )
12.3  Mathbox for Jim Kingdon
12.3.1  Propositional and predicate logic
Theorem	nnnotnotr 13872	Double negation of double negation elimination. Suggested by an online post by Martin Escardo. Although this statement resembles nnexmid 840, it can be proved with reference only to implication and negation (that is, without use of disjunction). (Contributed by Jim Kingdon, 21-Oct-2024.)
|- -. -. ( -. -. ph -> ph )
12.3.2  Natural numbers
Theorem	ss1oel2o 13873	Any subset of ordinal one being an element of ordinal two is equivalent to excluded middle. A variation of exmid01 4177 which more directly illustrates the contrast with el2oss1o 6411. (Contributed by Jim Kingdon, 8-Aug-2022.)
|- (EXMID <-> A. x ( x C_ 1o -> x e. 2o ) )
Theorem	nnti 13874	Ordering on a natural number generates a tight apartness. (Contributed by Jim Kingdon, 7-Aug-2022.)
|- ( ph -> A e. om )   =>    |- ( ( ph /\ ( u e. A /\ v e. A ) ) -> ( u = v <-> ( -. u _E v /\ -. v _E u ) ) )
Theorem	012of 13875	Mapping zero and one between NN0 and om style integers. (Contributed by Jim Kingdon, 28-Jun-2024.)
|- G = frec ( ( x e. ZZ |-> ( x + 1 ) ) , 0 )   =>    |- ( `' G |` { 0 , 1 } ) : { 0 , 1 } --> 2o
Theorem	2o01f 13876	Mapping zero and one between om and NN0 style integers. (Contributed by Jim Kingdon, 28-Jun-2024.)
|- G = frec ( ( x e. ZZ |-> ( x + 1 ) ) , 0 )   =>    |- ( G |` 2o ) : 2o --> { 0 , 1 }
12.3.3  The power set of a singleton
Theorem	pwtrufal 13877	A subset of the singleton { (/) } cannot be anything other than (/) or { (/) }. Removing the double negation would change the meaning, as seen at exmid01 4177. If we view a subset of a singleton as a truth value (as seen in theorems like exmidexmid 4175), then this theorem states there are no truth values other than true and false, as described in section 1.1 of [Bauer], p. 481. (Contributed by Mario Carneiro and Jim Kingdon, 11-Sep-2023.)
|- ( A C_ { (/) } -> -. -. ( A = (/) \/ A = { (/) } ) )
Theorem	pwle2 13878*	An exercise related to N copies of a singleton and the power set of a singleton (where the latter can also be thought of as representing truth values). Posed as an exercise by Martin Escardo online. (Contributed by Jim Kingdon, 3-Sep-2023.)
|- T = U_ x e. N ( { x } X. 1o )   =>    |- ( ( N e. om /\ G : T -1-1-> ~P 1o ) -> N C_ 2o )
Theorem	pwf1oexmid 13879*	An exercise related to N copies of a singleton and the power set of a singleton (where the latter can also be thought of as representing truth values). Posed as an exercise by Martin Escardo online. (Contributed by Jim Kingdon, 3-Sep-2023.)
|- T = U_ x e. N ( { x } X. 1o )   =>    |- ( ( N e. om /\ G : T -1-1-> ~P 1o ) -> ( ran G = ~P 1o <-> ( N = 2o /\ EXMID ) ) )
Theorem	exmid1stab 13880*	If any proposition is stable, excluded middle follows. We are thinking of x as a proposition and x = { (/) } as "x is true". (Contributed by Jim Kingdon, 28-Nov-2023.)
|- ( ( ph /\ x C_ { (/) } ) -> STAB x = { (/) } )   =>    |- ( ph -> EXMID )
Theorem	subctctexmid 13881*	If every subcountable set is countable and Markov's principle holds, excluded middle follows. Proposition 2.6 of [BauerSwan], p. 14:4. The proof is taken from that paper. (Contributed by Jim Kingdon, 29-Nov-2023.)
|- ( ph -> A. x ( E. s ( s C_ om /\ E. f f : s -onto-> x ) -> E. g g : om -onto-> ( x ⊔ 1o ) ) )   &    |- ( ph -> om e. Markov )   =>    |- ( ph -> EXMID )
Theorem	sssneq 13882*	Any two elements of a subset of a singleton are equal. (Contributed by Jim Kingdon, 28-May-2024.)
|- ( A C_ { B } -> A. y e. A A. z e. A y = z )
Theorem	pw1nct 13883*	A condition which ensures that the powerset of a singleton is not countable. The antecedent here can be referred to as the uniformity principle. Based on Mastodon posts by Andrej Bauer and Rahul Chhabra. (Contributed by Jim Kingdon, 29-May-2024.)
|- ( A. r ( r C_ ( ~P 1o X. om ) -> ( A. p e. ~P 1o E. n e. om p r n -> E. m e. om A. q e. ~P 1o q r m ) ) -> -. E. f f : om -onto-> ( ~P 1o ⊔ 1o ) )
12.3.4  Omniscience of NN+oo
Theorem	0nninf 13884	The zero element of ℕ∞ (the constant sequence equal to (/)). (Contributed by Jim Kingdon, 14-Jul-2022.)
|- ( om X. { (/) } ) e. ℕ∞
Theorem	nnsf 13885*	Domain and range of S. Part of Definition 3.3 of [PradicBrown2022], p. 5. (Contributed by Jim Kingdon, 30-Jul-2022.)
|- S = ( p e. ℕ∞ |-> ( i e. om |-> if ( i = (/) , 1o , ( p ` U. i ) ) ) )   =>    |- S :ℕ∞ -->ℕ∞
Theorem	peano4nninf 13886*	The successor function on ℕ∞ is one to one. Half of Lemma 3.4 of [PradicBrown2022], p. 5. (Contributed by Jim Kingdon, 31-Jul-2022.)
|- S = ( p e. ℕ∞ |-> ( i e. om |-> if ( i = (/) , 1o , ( p ` U. i ) ) ) )   =>    |- S :ℕ∞ -1-1->ℕ∞
Theorem	peano3nninf 13887*	The successor function on ℕ∞ is never zero. Half of Lemma 3.4 of [PradicBrown2022], p. 5. (Contributed by Jim Kingdon, 1-Aug-2022.)
|- S = ( p e. ℕ∞ |-> ( i e. om |-> if ( i = (/) , 1o , ( p ` U. i ) ) ) )   =>    |- ( A e. ℕ∞ -> ( S ` A ) =/= ( x e. om |-> (/) ) )
Theorem	nninfalllem1 13888*	Lemma for nninfall 13889. (Contributed by Jim Kingdon, 1-Aug-2022.)
|- ( ph -> Q e. ( 2o ^m ℕ∞ ) )   &    |- ( ph -> ( Q ` ( x e. om |-> 1o ) ) = 1o )   &    |- ( ph -> A. n e. om ( Q ` ( i e. om |-> if ( i e. n , 1o , (/) ) ) ) = 1o )   &    |- ( ph -> P e. ℕ∞ )   &    |- ( ph -> ( Q ` P ) = (/) )   =>    |- ( ph -> A. n e. om ( P ` n ) = 1o )
Theorem	nninfall 13889*	Given a decidable predicate on ℕ∞, showing it holds for natural numbers and the point at infinity suffices to show it holds everywhere. The sense in which Q is a decidable predicate is that it assigns a value of either (/) or 1o (which can be thought of as false and true) to every element of ℕ∞. Lemma 3.5 of [PradicBrown2022], p. 5. (Contributed by Jim Kingdon, 1-Aug-2022.)
|- ( ph -> Q e. ( 2o ^m ℕ∞ ) )   &    |- ( ph -> ( Q ` ( x e. om |-> 1o ) ) = 1o )   &    |- ( ph -> A. n e. om ( Q ` ( i e. om |-> if ( i e. n , 1o , (/) ) ) ) = 1o )   =>    |- ( ph -> A. p e. ℕ∞ ( Q ` p ) = 1o )
Theorem	nninfsellemdc 13890*	Lemma for nninfself 13893. Showing that the selection function is well defined. (Contributed by Jim Kingdon, 8-Aug-2022.)
|- ( ( Q e. ( 2o ^m ℕ∞ ) /\ N e. om ) -> DECID A. k e. suc N ( Q ` ( i e. om |-> if ( i e. k , 1o , (/) ) ) ) = 1o )
Theorem	nninfsellemcl 13891*	Lemma for nninfself 13893. (Contributed by Jim Kingdon, 8-Aug-2022.)
|- ( ( Q e. ( 2o ^m ℕ∞ ) /\ N e. om ) -> if ( A. k e. suc N ( Q ` ( i e. om |-> if ( i e. k , 1o , (/) ) ) ) = 1o , 1o , (/) ) e. 2o )
Theorem	nninfsellemsuc 13892*	Lemma for nninfself 13893. (Contributed by Jim Kingdon, 6-Aug-2022.)
|- ( ( Q e. ( 2o ^m ℕ∞ ) /\ J e. om ) -> if ( A. k e. suc suc J ( Q ` ( i e. om |-> if ( i e. k , 1o , (/) ) ) ) = 1o , 1o , (/) ) C_ if ( A. k e. suc J ( Q ` ( i e. om |-> if ( i e. k , 1o , (/) ) ) ) = 1o , 1o , (/) ) )
Theorem	nninfself 13893*	Domain and range of the selection function for ℕ∞. (Contributed by Jim Kingdon, 6-Aug-2022.)
|- E = ( q e. ( 2o ^m ℕ∞ ) |-> ( n e. om |-> if ( A. k e. suc n ( q ` ( i e. om |-> if ( i e. k , 1o , (/) ) ) ) = 1o , 1o , (/) ) ) )   =>    |- E : ( 2o ^m ℕ∞ ) -->ℕ∞
Theorem	nninfsellemeq 13894*	Lemma for nninfsel 13897. (Contributed by Jim Kingdon, 9-Aug-2022.)
|- E = ( q e. ( 2o ^m ℕ∞ ) |-> ( n e. om |-> if ( A. k e. suc n ( q ` ( i e. om |-> if ( i e. k , 1o , (/) ) ) ) = 1o , 1o , (/) ) ) )   &    |- ( ph -> Q e. ( 2o ^m ℕ∞ ) )   &    |- ( ph -> ( Q ` ( E ` Q ) ) = 1o )   &    |- ( ph -> N e. om )   &    |- ( ph -> A. k e. N ( Q ` ( i e. om |-> if ( i e. k , 1o , (/) ) ) ) = 1o )   &    |- ( ph -> ( Q ` ( i e. om |-> if ( i e. N , 1o , (/) ) ) ) = (/) )   =>    |- ( ph -> ( E ` Q ) = ( i e. om |-> if ( i e. N , 1o , (/) ) ) )
Theorem	nninfsellemqall 13895*	Lemma for nninfsel 13897. (Contributed by Jim Kingdon, 9-Aug-2022.)
|- E = ( q e. ( 2o ^m ℕ∞ ) |-> ( n e. om |-> if ( A. k e. suc n ( q ` ( i e. om |-> if ( i e. k , 1o , (/) ) ) ) = 1o , 1o , (/) ) ) )   &    |- ( ph -> Q e. ( 2o ^m ℕ∞ ) )   &    |- ( ph -> ( Q ` ( E ` Q ) ) = 1o )   &    |- ( ph -> N e. om )   =>    |- ( ph -> ( Q ` ( i e. om |-> if ( i e. N , 1o , (/) ) ) ) = 1o )
Theorem	nninfsellemeqinf 13896*	Lemma for nninfsel 13897. (Contributed by Jim Kingdon, 9-Aug-2022.)
|- E = ( q e. ( 2o ^m ℕ∞ ) |-> ( n e. om |-> if ( A. k e. suc n ( q ` ( i e. om |-> if ( i e. k , 1o , (/) ) ) ) = 1o , 1o , (/) ) ) )   &    |- ( ph -> Q e. ( 2o ^m ℕ∞ ) )   &    |- ( ph -> ( Q ` ( E ` Q ) ) = 1o )   =>    |- ( ph -> ( E ` Q ) = ( i e. om |-> 1o ) )
Theorem	nninfsel 13897*	E is a selection function for ℕ∞. Theorem 3.6 of [PradicBrown2022], p. 5. (Contributed by Jim Kingdon, 9-Aug-2022.)
|- E = ( q e. ( 2o ^m ℕ∞ ) |-> ( n e. om |-> if ( A. k e. suc n ( q ` ( i e. om |-> if ( i e. k , 1o , (/) ) ) ) = 1o , 1o , (/) ) ) )   &    |- ( ph -> Q e. ( 2o ^m ℕ∞ ) )   &    |- ( ph -> ( Q ` ( E ` Q ) ) = 1o )   =>    |- ( ph -> A. p e. ℕ∞ ( Q ` p ) = 1o )
Theorem	nninfomnilem 13898*	Lemma for nninfomni 13899. (Contributed by Jim Kingdon, 10-Aug-2022.)
|- E = ( q e. ( 2o ^m ℕ∞ ) |-> ( n e. om |-> if ( A. k e. suc n ( q ` ( i e. om |-> if ( i e. k , 1o , (/) ) ) ) = 1o , 1o , (/) ) ) )   =>    |- ℕ∞ e. Omni
Theorem	nninfomni 13899	ℕ∞ is omniscient. Corollary 3.7 of [PradicBrown2022], p. 5. (Contributed by Jim Kingdon, 10-Aug-2022.)
|- ℕ∞ e. Omni
Theorem	nninffeq 13900*	Equality of two functions on ℕ∞ which agree at every integer and at the point at infinity. From an online post by Martin Escardo. Remark: the last two hypotheses can be grouped into one, |- ( ph -> A. n e. suc om ... ). (Contributed by Jim Kingdon, 4-Aug-2023.)
|- ( ph -> F :ℕ∞ --> NN0 )   &    |- ( ph -> G :ℕ∞ --> NN0 )   &    |- ( ph -> ( F ` ( x e. om |-> 1o ) ) = ( G ` ( x e. om |-> 1o ) ) )   &    |- ( ph -> A. n e. om ( F ` ( i e. om |-> if ( i e. n , 1o , (/) ) ) ) = ( G ` ( i e. om |-> if ( i e. n , 1o , (/) ) ) ) )   =>    |- ( ph -> F = G )