Home | Metamath
Proof Explorer Theorem List (p. 85 of 424) | < Previous Next > |
Bad symbols? Try the
GIF version. |
||
Mirrors > Metamath Home Page > MPE Home Page > Theorem List Contents > Recent Proofs This page: Page List |
Color key: | Metamath Proof Explorer
(1-27159) |
Hilbert Space Explorer
(27160-28684) |
Users' Mathboxes
(28685-42360) |
Type | Label | Description |
---|---|---|
Statement | ||
Theorem | inf0 8401* | Our Axiom of Infinity derived from existence of omega. The proof shows that the especially contrived class "ran (rec((𝑣 ∈ V ↦ suc 𝑣), 𝑥) ↾ ω) " exists, is a subset of its union, and contains a given set 𝑥 (and thus is nonempty). Thus, it provides an example demonstrating that a set 𝑦 exists with the necessary properties demanded by ax-inf 8418. (Contributed by NM, 15-Oct-1996.) |
⊢ ω ∈ V ⇒ ⊢ ∃𝑦(𝑥 ∈ 𝑦 ∧ ∀𝑧(𝑧 ∈ 𝑦 → ∃𝑤(𝑧 ∈ 𝑤 ∧ 𝑤 ∈ 𝑦))) | ||
Theorem | inf1 8402 | Variation of Axiom of Infinity (using zfinf 8419 as a hypothesis). Axiom of Infinity in [FreydScedrov] p. 283. (Contributed by NM, 14-Oct-1996.) (Revised by David Abernethy, 1-Oct-2013.) |
⊢ ∃𝑥(𝑦 ∈ 𝑥 ∧ ∀𝑦(𝑦 ∈ 𝑥 → ∃𝑧(𝑦 ∈ 𝑧 ∧ 𝑧 ∈ 𝑥))) ⇒ ⊢ ∃𝑥(𝑥 ≠ ∅ ∧ ∀𝑦(𝑦 ∈ 𝑥 → ∃𝑧(𝑦 ∈ 𝑧 ∧ 𝑧 ∈ 𝑥))) | ||
Theorem | inf2 8403* | Variation of Axiom of Infinity. There exists a nonempty set that is a subset of its union (using zfinf 8419 as a hypothesis). Abbreviated version of the Axiom of Infinity in [FreydScedrov] p. 283. (Contributed by NM, 28-Oct-1996.) |
⊢ ∃𝑥(𝑦 ∈ 𝑥 ∧ ∀𝑦(𝑦 ∈ 𝑥 → ∃𝑧(𝑦 ∈ 𝑧 ∧ 𝑧 ∈ 𝑥))) ⇒ ⊢ ∃𝑥(𝑥 ≠ ∅ ∧ 𝑥 ⊆ ∪ 𝑥) | ||
Theorem | inf3lema 8404* | Lemma for our Axiom of Infinity => standard Axiom of Infinity. See inf3 8415 for detailed description. (Contributed by NM, 28-Oct-1996.) |
⊢ 𝐺 = (𝑦 ∈ V ↦ {𝑤 ∈ 𝑥 ∣ (𝑤 ∩ 𝑥) ⊆ 𝑦}) & ⊢ 𝐹 = (rec(𝐺, ∅) ↾ ω) & ⊢ 𝐴 ∈ V & ⊢ 𝐵 ∈ V ⇒ ⊢ (𝐴 ∈ (𝐺‘𝐵) ↔ (𝐴 ∈ 𝑥 ∧ (𝐴 ∩ 𝑥) ⊆ 𝐵)) | ||
Theorem | inf3lemb 8405* | Lemma for our Axiom of Infinity => standard Axiom of Infinity. See inf3 8415 for detailed description. (Contributed by NM, 28-Oct-1996.) |
⊢ 𝐺 = (𝑦 ∈ V ↦ {𝑤 ∈ 𝑥 ∣ (𝑤 ∩ 𝑥) ⊆ 𝑦}) & ⊢ 𝐹 = (rec(𝐺, ∅) ↾ ω) & ⊢ 𝐴 ∈ V & ⊢ 𝐵 ∈ V ⇒ ⊢ (𝐹‘∅) = ∅ | ||
Theorem | inf3lemc 8406* | Lemma for our Axiom of Infinity => standard Axiom of Infinity. See inf3 8415 for detailed description. (Contributed by NM, 28-Oct-1996.) |
⊢ 𝐺 = (𝑦 ∈ V ↦ {𝑤 ∈ 𝑥 ∣ (𝑤 ∩ 𝑥) ⊆ 𝑦}) & ⊢ 𝐹 = (rec(𝐺, ∅) ↾ ω) & ⊢ 𝐴 ∈ V & ⊢ 𝐵 ∈ V ⇒ ⊢ (𝐴 ∈ ω → (𝐹‘suc 𝐴) = (𝐺‘(𝐹‘𝐴))) | ||
Theorem | inf3lemd 8407* | Lemma for our Axiom of Infinity => standard Axiom of Infinity. See inf3 8415 for detailed description. (Contributed by NM, 28-Oct-1996.) |
⊢ 𝐺 = (𝑦 ∈ V ↦ {𝑤 ∈ 𝑥 ∣ (𝑤 ∩ 𝑥) ⊆ 𝑦}) & ⊢ 𝐹 = (rec(𝐺, ∅) ↾ ω) & ⊢ 𝐴 ∈ V & ⊢ 𝐵 ∈ V ⇒ ⊢ (𝐴 ∈ ω → (𝐹‘𝐴) ⊆ 𝑥) | ||
Theorem | inf3lem1 8408* | Lemma for our Axiom of Infinity => standard Axiom of Infinity. See inf3 8415 for detailed description. (Contributed by NM, 28-Oct-1996.) |
⊢ 𝐺 = (𝑦 ∈ V ↦ {𝑤 ∈ 𝑥 ∣ (𝑤 ∩ 𝑥) ⊆ 𝑦}) & ⊢ 𝐹 = (rec(𝐺, ∅) ↾ ω) & ⊢ 𝐴 ∈ V & ⊢ 𝐵 ∈ V ⇒ ⊢ (𝐴 ∈ ω → (𝐹‘𝐴) ⊆ (𝐹‘suc 𝐴)) | ||
Theorem | inf3lem2 8409* | Lemma for our Axiom of Infinity => standard Axiom of Infinity. See inf3 8415 for detailed description. (Contributed by NM, 28-Oct-1996.) |
⊢ 𝐺 = (𝑦 ∈ V ↦ {𝑤 ∈ 𝑥 ∣ (𝑤 ∩ 𝑥) ⊆ 𝑦}) & ⊢ 𝐹 = (rec(𝐺, ∅) ↾ ω) & ⊢ 𝐴 ∈ V & ⊢ 𝐵 ∈ V ⇒ ⊢ ((𝑥 ≠ ∅ ∧ 𝑥 ⊆ ∪ 𝑥) → (𝐴 ∈ ω → (𝐹‘𝐴) ≠ 𝑥)) | ||
Theorem | inf3lem3 8410* | Lemma for our Axiom of Infinity => standard Axiom of Infinity. See inf3 8415 for detailed description. In the proof, we invoke the Axiom of Regularity in the form of zfreg 8383. (Contributed by NM, 29-Oct-1996.) |
⊢ 𝐺 = (𝑦 ∈ V ↦ {𝑤 ∈ 𝑥 ∣ (𝑤 ∩ 𝑥) ⊆ 𝑦}) & ⊢ 𝐹 = (rec(𝐺, ∅) ↾ ω) & ⊢ 𝐴 ∈ V & ⊢ 𝐵 ∈ V ⇒ ⊢ ((𝑥 ≠ ∅ ∧ 𝑥 ⊆ ∪ 𝑥) → (𝐴 ∈ ω → (𝐹‘𝐴) ≠ (𝐹‘suc 𝐴))) | ||
Theorem | inf3lem4 8411* | Lemma for our Axiom of Infinity => standard Axiom of Infinity. See inf3 8415 for detailed description. (Contributed by NM, 29-Oct-1996.) |
⊢ 𝐺 = (𝑦 ∈ V ↦ {𝑤 ∈ 𝑥 ∣ (𝑤 ∩ 𝑥) ⊆ 𝑦}) & ⊢ 𝐹 = (rec(𝐺, ∅) ↾ ω) & ⊢ 𝐴 ∈ V & ⊢ 𝐵 ∈ V ⇒ ⊢ ((𝑥 ≠ ∅ ∧ 𝑥 ⊆ ∪ 𝑥) → (𝐴 ∈ ω → (𝐹‘𝐴) ⊊ (𝐹‘suc 𝐴))) | ||
Theorem | inf3lem5 8412* | Lemma for our Axiom of Infinity => standard Axiom of Infinity. See inf3 8415 for detailed description. (Contributed by NM, 29-Oct-1996.) |
⊢ 𝐺 = (𝑦 ∈ V ↦ {𝑤 ∈ 𝑥 ∣ (𝑤 ∩ 𝑥) ⊆ 𝑦}) & ⊢ 𝐹 = (rec(𝐺, ∅) ↾ ω) & ⊢ 𝐴 ∈ V & ⊢ 𝐵 ∈ V ⇒ ⊢ ((𝑥 ≠ ∅ ∧ 𝑥 ⊆ ∪ 𝑥) → ((𝐴 ∈ ω ∧ 𝐵 ∈ 𝐴) → (𝐹‘𝐵) ⊊ (𝐹‘𝐴))) | ||
Theorem | inf3lem6 8413* | Lemma for our Axiom of Infinity => standard Axiom of Infinity. See inf3 8415 for detailed description. (Contributed by NM, 29-Oct-1996.) |
⊢ 𝐺 = (𝑦 ∈ V ↦ {𝑤 ∈ 𝑥 ∣ (𝑤 ∩ 𝑥) ⊆ 𝑦}) & ⊢ 𝐹 = (rec(𝐺, ∅) ↾ ω) & ⊢ 𝐴 ∈ V & ⊢ 𝐵 ∈ V ⇒ ⊢ ((𝑥 ≠ ∅ ∧ 𝑥 ⊆ ∪ 𝑥) → 𝐹:ω–1-1→𝒫 𝑥) | ||
Theorem | inf3lem7 8414* | Lemma for our Axiom of Infinity => standard Axiom of Infinity. See inf3 8415 for detailed description. In the proof, we invoke the Axiom of Replacement in the form of f1dmex 7029. (Contributed by NM, 29-Oct-1996.) (Proof shortened by Mario Carneiro, 19-Jan-2013.) |
⊢ 𝐺 = (𝑦 ∈ V ↦ {𝑤 ∈ 𝑥 ∣ (𝑤 ∩ 𝑥) ⊆ 𝑦}) & ⊢ 𝐹 = (rec(𝐺, ∅) ↾ ω) & ⊢ 𝐴 ∈ V & ⊢ 𝐵 ∈ V ⇒ ⊢ ((𝑥 ≠ ∅ ∧ 𝑥 ⊆ ∪ 𝑥) → ω ∈ V) | ||
Theorem | inf3 8415 |
Our Axiom of Infinity ax-inf 8418 implies the standard Axiom of Infinity.
The hypothesis is a variant of our Axiom of Infinity provided by
inf2 8403, and the conclusion is the version of the Axiom of Infinity
shown as Axiom 7 in [TakeutiZaring] p. 43. (Other standard versions are
proved later as axinf2 8420 and zfinf2 8422.) The main proof is provided by
inf3lema 8404 through inf3lem7 8414, and this final piece eliminates the
auxiliary hypothesis of inf3lem7 8414. This proof is due to
Ian Sutherland, Richard Heck, and Norman Megill and was posted
on Usenet as shown below. Although the result is not new, the authors
were unable to find a published proof.
(As posted to sci.logic on 30-Oct-1996, with annotations added.) Theorem: The statement "There exists a nonempty set that is a subset of its union" implies the Axiom of Infinity. Proof: Let X be a nonempty set which is a subset of its union; the latter property is equivalent to saying that for any y in X, there exists a z in X such that y is in z. Define by finite recursion a function F:omega-->(power X) such that F_0 = 0 (See inf3lemb 8405.) F_n+1 = {y<X | y^X subset F_n} (See inf3lemc 8406.) Note: ^ means intersect, < means \in ("element of"). (Finite recursion as typically done requires the existence of omega; to avoid this we can just use transfinite recursion restricted to omega. F is a class-term that is not necessarily a set at this point.) Lemma 1. F_n subset F_n+1. (See inf3lem1 8408.) Proof: By induction: F_0 subset F_1. If y < F_n+1, then y^X subset F_n, so if F_n subset F_n+1, then y^X subset F_n+1, so y < F_n+2. Lemma 2. F_n =/= X. (See inf3lem2 8409.) Proof: By induction: F_0 =/= X because X is not empty. Assume F_n =/= X. Then there is a y in X that is not in F_n. By definition of X, there is a z in X that contains y. Suppose F_n+1 = X. Then z is in F_n+1, and z^X contains y, so z^X is not a subset of F_n, contrary to the definition of F_n+1. Lemma 3. F_n =/= F_n+1. (See inf3lem3 8410.) Proof: Using the identity y^X subset F_n <-> y^(X-F_n) = 0, we have F_n+1 = {y<X | y^(X-F_n) = 0}. Let q = {y<X-F_n | y^(X-F_n) = 0}. Then q subset F_n+1. Since X-F_n is not empty by Lemma 2 and q is the set of \in-minimal elements of X-F_n, by Foundation q is not empty, so q and therefore F_n+1 have an element not in F_n. Lemma 4. F_n proper_subset F_n+1. (See inf3lem4 8411.) Proof: Lemmas 1 and 3. Lemma 5. F_m proper_subset F_n, m < n. (See inf3lem5 8412.) Proof: Fix m and use induction on n > m. Basis: F_m proper_subset F_m+1 by Lemma 4. Induction: Assume F_m proper_subset F_n. Then since F_n proper_subset F_n+1, F_m proper_subset F_n+1 by transitivity of proper subset. By Lemma 5, F_m =/= F_n for m =/= n, so F is 1-1. (See inf3lem6 8413.) Thus, the inverse of F is a function with range omega and domain a subset of power X, so omega exists by Replacement. (See inf3lem7 8414.) Q.E.D.(Contributed by NM, 29-Oct-1996.) |
⊢ ∃𝑥(𝑥 ≠ ∅ ∧ 𝑥 ⊆ ∪ 𝑥) ⇒ ⊢ ω ∈ V | ||
Theorem | infeq5i 8416 | Half of infeq5 8417. (Contributed by Mario Carneiro, 16-Nov-2014.) |
⊢ (ω ∈ V → ∃𝑥 𝑥 ⊊ ∪ 𝑥) | ||
Theorem | infeq5 8417 | The statement "there exists a set that is a proper subset of its union" is equivalent to the Axiom of Infinity (shown on the right-hand side in the form of omex 8423.) The left-hand side provides us with a very short way to express the Axiom of Infinity using only elementary symbols. This proof of equivalence does not depend on the Axiom of Infinity. (Contributed by NM, 23-Mar-2004.) (Revised by Mario Carneiro, 16-Nov-2014.) |
⊢ (∃𝑥 𝑥 ⊊ ∪ 𝑥 ↔ ω ∈ V) | ||
Axiom | ax-inf 8418* |
Axiom of Infinity. An axiom of Zermelo-Fraenkel set theory. This axiom
is the gateway to "Cantor's paradise" (an expression coined by
Hilbert).
It asserts that given a starting set 𝑥, an infinite set 𝑦 built
from it exists. Although our version is apparently not given in the
literature, it is similar to, but slightly shorter than, the Axiom of
Infinity in [FreydScedrov] p. 283
(see inf1 8402 and inf2 8403). More
standard versions, which essentially state that there exists a set
containing all the natural numbers, are shown as zfinf2 8422 and omex 8423 and
are based on the (nontrivial) proof of inf3 8415.
This version has the
advantage that when expanded to primitives, it has fewer symbols than
the standard version ax-inf2 8421. Theorem inf0 8401
shows the reverse
derivation of our axiom from a standard one. Theorem inf5 8425
shows a
very short way to state this axiom.
The standard version of Infinity ax-inf2 8421 requires this axiom along with Regularity ax-reg 8380 for its derivation (as theorem axinf2 8420 below). In order to more easily identify the normal uses of Regularity, we will usually reference ax-inf2 8421 instead of this one. The derivation of this axiom from ax-inf2 8421 is shown by theorem axinf 8424. Proofs should normally use the standard version ax-inf2 8421 instead of this axiom. (New usage is discouraged.) (Contributed by NM, 16-Aug-1993.) |
⊢ ∃𝑦(𝑥 ∈ 𝑦 ∧ ∀𝑧(𝑧 ∈ 𝑦 → ∃𝑤(𝑧 ∈ 𝑤 ∧ 𝑤 ∈ 𝑦))) | ||
Theorem | zfinf 8419* | Axiom of Infinity expressed with the fewest number of different variables. (New usage is discouraged.) (Contributed by NM, 14-Aug-2003.) |
⊢ ∃𝑥(𝑦 ∈ 𝑥 ∧ ∀𝑦(𝑦 ∈ 𝑥 → ∃𝑧(𝑦 ∈ 𝑧 ∧ 𝑧 ∈ 𝑥))) | ||
Theorem | axinf2 8420* |
A standard version of Axiom of Infinity, expanded to primitives, derived
from our version of Infinity ax-inf 8418 and Regularity ax-reg 8380.
This theorem should not be referenced in any proof. Instead, use ax-inf2 8421 below so that the ordinary uses of Regularity can be more easily identified. (New usage is discouraged.) (Contributed by NM, 3-Nov-1996.) |
⊢ ∃𝑥(∃𝑦(𝑦 ∈ 𝑥 ∧ ∀𝑧 ¬ 𝑧 ∈ 𝑦) ∧ ∀𝑦(𝑦 ∈ 𝑥 → ∃𝑧(𝑧 ∈ 𝑥 ∧ ∀𝑤(𝑤 ∈ 𝑧 ↔ (𝑤 ∈ 𝑦 ∨ 𝑤 = 𝑦))))) | ||
Axiom | ax-inf2 8421* | A standard version of Axiom of Infinity of ZF set theory. In English, it says: there exists a set that contains the empty set and the successors of all of its members. Theorem zfinf2 8422 shows it converted to abbreviations. This axiom was derived as theorem axinf2 8420 above, using our version of Infinity ax-inf 8418 and the Axiom of Regularity ax-reg 8380. We will reference ax-inf2 8421 instead of axinf2 8420 so that the ordinary uses of Regularity can be more easily identified. The reverse derivation of ax-inf 8418 from ax-inf2 8421 is shown by theorem axinf 8424. (Contributed by NM, 3-Nov-1996.) |
⊢ ∃𝑥(∃𝑦(𝑦 ∈ 𝑥 ∧ ∀𝑧 ¬ 𝑧 ∈ 𝑦) ∧ ∀𝑦(𝑦 ∈ 𝑥 → ∃𝑧(𝑧 ∈ 𝑥 ∧ ∀𝑤(𝑤 ∈ 𝑧 ↔ (𝑤 ∈ 𝑦 ∨ 𝑤 = 𝑦))))) | ||
Theorem | zfinf2 8422* | A standard version of the Axiom of Infinity, using definitions to abbreviate. Axiom Inf of [BellMachover] p. 472. (See ax-inf2 8421 for the unabbreviated version.) (Contributed by NM, 30-Aug-1993.) |
⊢ ∃𝑥(∅ ∈ 𝑥 ∧ ∀𝑦 ∈ 𝑥 suc 𝑦 ∈ 𝑥) | ||
Theorem | omex 8423 |
The existence of omega (the class of natural numbers). Axiom 7 of
[TakeutiZaring] p. 43. This
theorem is proved assuming the Axiom of
Infinity and in fact is equivalent to it, as shown by the reverse
derivation inf0 8401.
A finitist (someone who doesn't believe in infinity) could, without contradiction, replace the Axiom of Infinity by its denial ¬ ω ∈ V; this would lead to ω = On by omon 6968 and Fin = V (the universe of all sets) by fineqv 8060. The finitist could still develop natural number, integer, and rational number arithmetic but would be denied the real numbers (as well as much of the rest of mathematics). In deference to the finitist, much of our development is done, when possible, without invoking the Axiom of Infinity; an example is Peano's axioms peano1 6977 through peano5 6981 (which many textbooks prove more easily assuming Infinity). (Contributed by NM, 6-Aug-1994.) |
⊢ ω ∈ V | ||
Theorem | axinf 8424* | The first version of the Axiom of Infinity ax-inf 8418 proved from the second version ax-inf2 8421. Note that we didn't use ax-reg 8380, unlike the other direction axinf2 8420. (Contributed by NM, 24-Apr-2009.) |
⊢ ∃𝑦(𝑥 ∈ 𝑦 ∧ ∀𝑧(𝑧 ∈ 𝑦 → ∃𝑤(𝑧 ∈ 𝑤 ∧ 𝑤 ∈ 𝑦))) | ||
Theorem | inf5 8425 | The statement "there exists a set that is a proper subset of its union" is equivalent to the Axiom of Infinity (see theorem infeq5 8417). This provides us with a very compact way to express the Axiom of Infinity using only elementary symbols. (Contributed by NM, 3-Jun-2005.) |
⊢ ∃𝑥 𝑥 ⊊ ∪ 𝑥 | ||
Theorem | omelon 8426 | Omega is an ordinal number. (Contributed by NM, 10-May-1998.) (Revised by Mario Carneiro, 30-Jan-2013.) |
⊢ ω ∈ On | ||
Theorem | dfom3 8427* | The class of natural numbers omega can be defined as the smallest "inductive set," which is valid provided we assume the Axiom of Infinity. Definition 6.3 of [Eisenberg] p. 82. (Contributed by NM, 6-Aug-1994.) |
⊢ ω = ∩ {𝑥 ∣ (∅ ∈ 𝑥 ∧ ∀𝑦 ∈ 𝑥 suc 𝑦 ∈ 𝑥)} | ||
Theorem | elom3 8428* | A simplification of elom 6960 assuming the Axiom of Infinity. (Contributed by NM, 30-May-2003.) |
⊢ (𝐴 ∈ ω ↔ ∀𝑥(Lim 𝑥 → 𝐴 ∈ 𝑥)) | ||
Theorem | dfom4 8429* | A simplification of df-om 6958 assuming the Axiom of Infinity. (Contributed by NM, 30-May-2003.) |
⊢ ω = {𝑥 ∣ ∀𝑦(Lim 𝑦 → 𝑥 ∈ 𝑦)} | ||
Theorem | dfom5 8430 | ω is the smallest limit ordinal and can be defined as such (although the Axiom of Infinity is needed to ensure that at least one limit ordinal exists). (Contributed by FL, 22-Feb-2011.) (Revised by Mario Carneiro, 2-Feb-2013.) |
⊢ ω = ∩ {𝑥 ∣ Lim 𝑥} | ||
Theorem | oancom 8431 | Ordinal addition is not commutative. This theorem shows a counterexample. Remark in [TakeutiZaring] p. 60. (Contributed by NM, 10-Dec-2004.) |
⊢ (1𝑜 +𝑜 ω) ≠ (ω +𝑜 1𝑜) | ||
Theorem | isfinite 8432 | A set is finite iff it is strictly dominated by the class of natural number. Theorem 42 of [Suppes] p. 151. The Axiom of Infinity is used for the forward implication. (Contributed by FL, 16-Apr-2011.) |
⊢ (𝐴 ∈ Fin ↔ 𝐴 ≺ ω) | ||
Theorem | fict 8433 | A finite set is countable (weaker version of isfinite 8432). (Contributed by Thierry Arnoux, 27-Mar-2018.) |
⊢ (𝐴 ∈ Fin → 𝐴 ≼ ω) | ||
Theorem | nnsdom 8434 | A natural number is strictly dominated by the set of natural numbers. Example 3 of [Enderton] p. 146. (Contributed by NM, 28-Oct-2003.) |
⊢ (𝐴 ∈ ω → 𝐴 ≺ ω) | ||
Theorem | omenps 8435 | Omega is equinumerous to a proper subset of itself. Example 13.2(4) of [Eisenberg] p. 216. (Contributed by NM, 30-Jul-2003.) |
⊢ ω ≈ (ω ∖ {∅}) | ||
Theorem | omensuc 8436 | The set of natural numbers is equinumerous to its successor. (Contributed by NM, 30-Oct-2003.) |
⊢ ω ≈ suc ω | ||
Theorem | infdifsn 8437 | Removing a singleton from an infinite set does not change the cardinality of the set. (Contributed by Mario Carneiro, 30-Apr-2015.) (Revised by Mario Carneiro, 16-May-2015.) |
⊢ (ω ≼ 𝐴 → (𝐴 ∖ {𝐵}) ≈ 𝐴) | ||
Theorem | infdiffi 8438 | Removing a finite set from an infinite set does not change the cardinality of the set. (Contributed by Mario Carneiro, 30-Apr-2015.) |
⊢ ((ω ≼ 𝐴 ∧ 𝐵 ∈ Fin) → (𝐴 ∖ 𝐵) ≈ 𝐴) | ||
Theorem | unbnn3 8439* | Any unbounded subset of natural numbers is equinumerous to the set of all natural numbers. This version of unbnn 8101 eliminates its hypothesis by assuming the Axiom of Infinity. (Contributed by NM, 4-May-2005.) |
⊢ ((𝐴 ⊆ ω ∧ ∀𝑥 ∈ ω ∃𝑦 ∈ 𝐴 𝑥 ∈ 𝑦) → 𝐴 ≈ ω) | ||
Theorem | noinfep 8440* | Using the Axiom of Regularity in the form zfregfr 8392, show that there are no infinite descending ∈-chains. Proposition 7.34 of [TakeutiZaring] p. 44. (Contributed by NM, 26-Jan-2006.) (Revised by Mario Carneiro, 22-Mar-2013.) |
⊢ ∃𝑥 ∈ ω (𝐹‘suc 𝑥) ∉ (𝐹‘𝑥) | ||
Syntax | ccnf 8441 | Extend class notation with the Cantor normal form function. |
class CNF | ||
Definition | df-cnf 8442* | Define the Cantor normal form function, which takes as input a finitely supported function from 𝑦 to 𝑥 and outputs the corresponding member of the ordinal exponential 𝑥 ↑𝑜 𝑦. The content of the original Cantor Normal Form theorem is that for 𝑥 = ω this function is a bijection onto ω ↑𝑜 𝑦 for any ordinal 𝑦 (or, since the function restricts naturally to different ordinals, the statement that the composite function is a bijection to On). More can be said about the function, however, and in particular it is an order isomorphism for a certain easily defined well-ordering of the finitely supported functions, which gives an alternate definition cantnffval2 8475 of this function in terms of df-oi 8298. (Contributed by Mario Carneiro, 25-May-2015.) (Revised by AV, 28-Jun-2019.) |
⊢ CNF = (𝑥 ∈ On, 𝑦 ∈ On ↦ (𝑓 ∈ {𝑔 ∈ (𝑥 ↑𝑚 𝑦) ∣ 𝑔 finSupp ∅} ↦ ⦋OrdIso( E , (𝑓 supp ∅)) / ℎ⦌(seq𝜔((𝑘 ∈ V, 𝑧 ∈ V ↦ (((𝑥 ↑𝑜 (ℎ‘𝑘)) ·𝑜 (𝑓‘(ℎ‘𝑘))) +𝑜 𝑧)), ∅)‘dom ℎ))) | ||
Theorem | cantnffval 8443* | The value of the Cantor normal form function. (Contributed by Mario Carneiro, 25-May-2015.) (Revised by AV, 28-Jun-2019.) |
⊢ 𝑆 = {𝑔 ∈ (𝐴 ↑𝑚 𝐵) ∣ 𝑔 finSupp ∅} & ⊢ (𝜑 → 𝐴 ∈ On) & ⊢ (𝜑 → 𝐵 ∈ On) ⇒ ⊢ (𝜑 → (𝐴 CNF 𝐵) = (𝑓 ∈ 𝑆 ↦ ⦋OrdIso( E , (𝑓 supp ∅)) / ℎ⦌(seq𝜔((𝑘 ∈ V, 𝑧 ∈ V ↦ (((𝐴 ↑𝑜 (ℎ‘𝑘)) ·𝑜 (𝑓‘(ℎ‘𝑘))) +𝑜 𝑧)), ∅)‘dom ℎ))) | ||
Theorem | cantnfdm 8444* | The domain of the Cantor normal form function (in later lemmas we will use dom (𝐴 CNF 𝐵) to abbreviate "the set of finitely supported functions from 𝐵 to 𝐴"). (Contributed by Mario Carneiro, 25-May-2015.) (Revised by AV, 28-Jun-2019.) |
⊢ 𝑆 = {𝑔 ∈ (𝐴 ↑𝑚 𝐵) ∣ 𝑔 finSupp ∅} & ⊢ (𝜑 → 𝐴 ∈ On) & ⊢ (𝜑 → 𝐵 ∈ On) ⇒ ⊢ (𝜑 → dom (𝐴 CNF 𝐵) = 𝑆) | ||
Theorem | cantnfvalf 8445* | Lemma for cantnf 8473. The function appearing in cantnfval 8448 is unconditionally a function. (Contributed by Mario Carneiro, 20-May-2015.) |
⊢ 𝐹 = seq𝜔((𝑘 ∈ 𝐴, 𝑧 ∈ 𝐵 ↦ (𝐶 +𝑜 𝐷)), ∅) ⇒ ⊢ 𝐹:ω⟶On | ||
Theorem | cantnfs 8446 | Elementhood in the set of finitely supported functions from 𝐵 to 𝐴. (Contributed by Mario Carneiro, 25-May-2015.) (Revised by AV, 28-Jun-2019.) |
⊢ 𝑆 = dom (𝐴 CNF 𝐵) & ⊢ (𝜑 → 𝐴 ∈ On) & ⊢ (𝜑 → 𝐵 ∈ On) ⇒ ⊢ (𝜑 → (𝐹 ∈ 𝑆 ↔ (𝐹:𝐵⟶𝐴 ∧ 𝐹 finSupp ∅))) | ||
Theorem | cantnfcl 8447 | Basic properties of the order isomorphism 𝐺 used later. The support of an 𝐹 ∈ 𝑆 is a finite subset of 𝐴, so it is well-ordered by E and the order isomorphism has domain a finite ordinal. (Contributed by Mario Carneiro, 25-May-2015.) (Revised by AV, 28-Jun-2019.) |
⊢ 𝑆 = dom (𝐴 CNF 𝐵) & ⊢ (𝜑 → 𝐴 ∈ On) & ⊢ (𝜑 → 𝐵 ∈ On) & ⊢ 𝐺 = OrdIso( E , (𝐹 supp ∅)) & ⊢ (𝜑 → 𝐹 ∈ 𝑆) ⇒ ⊢ (𝜑 → ( E We (𝐹 supp ∅) ∧ dom 𝐺 ∈ ω)) | ||
Theorem | cantnfval 8448* | The value of the Cantor normal form function. (Contributed by Mario Carneiro, 25-May-2015.) (Revised by AV, 28-Jun-2019.) |
⊢ 𝑆 = dom (𝐴 CNF 𝐵) & ⊢ (𝜑 → 𝐴 ∈ On) & ⊢ (𝜑 → 𝐵 ∈ On) & ⊢ 𝐺 = OrdIso( E , (𝐹 supp ∅)) & ⊢ (𝜑 → 𝐹 ∈ 𝑆) & ⊢ 𝐻 = seq𝜔((𝑘 ∈ V, 𝑧 ∈ V ↦ (((𝐴 ↑𝑜 (𝐺‘𝑘)) ·𝑜 (𝐹‘(𝐺‘𝑘))) +𝑜 𝑧)), ∅) ⇒ ⊢ (𝜑 → ((𝐴 CNF 𝐵)‘𝐹) = (𝐻‘dom 𝐺)) | ||
Theorem | cantnfval2 8449* | Alternate expression for the value of the Cantor normal form function. (Contributed by Mario Carneiro, 25-May-2015.) (Revised by AV, 28-Jun-2019.) |
⊢ 𝑆 = dom (𝐴 CNF 𝐵) & ⊢ (𝜑 → 𝐴 ∈ On) & ⊢ (𝜑 → 𝐵 ∈ On) & ⊢ 𝐺 = OrdIso( E , (𝐹 supp ∅)) & ⊢ (𝜑 → 𝐹 ∈ 𝑆) & ⊢ 𝐻 = seq𝜔((𝑘 ∈ V, 𝑧 ∈ V ↦ (((𝐴 ↑𝑜 (𝐺‘𝑘)) ·𝑜 (𝐹‘(𝐺‘𝑘))) +𝑜 𝑧)), ∅) ⇒ ⊢ (𝜑 → ((𝐴 CNF 𝐵)‘𝐹) = (seq𝜔((𝑘 ∈ dom 𝐺, 𝑧 ∈ On ↦ (((𝐴 ↑𝑜 (𝐺‘𝑘)) ·𝑜 (𝐹‘(𝐺‘𝑘))) +𝑜 𝑧)), ∅)‘dom 𝐺)) | ||
Theorem | cantnfsuc 8450* | The value of the recursive function 𝐻 at a successor. (Contributed by Mario Carneiro, 25-May-2015.) (Revised by AV, 28-Jun-2019.) |
⊢ 𝑆 = dom (𝐴 CNF 𝐵) & ⊢ (𝜑 → 𝐴 ∈ On) & ⊢ (𝜑 → 𝐵 ∈ On) & ⊢ 𝐺 = OrdIso( E , (𝐹 supp ∅)) & ⊢ (𝜑 → 𝐹 ∈ 𝑆) & ⊢ 𝐻 = seq𝜔((𝑘 ∈ V, 𝑧 ∈ V ↦ (((𝐴 ↑𝑜 (𝐺‘𝑘)) ·𝑜 (𝐹‘(𝐺‘𝑘))) +𝑜 𝑧)), ∅) ⇒ ⊢ ((𝜑 ∧ 𝐾 ∈ ω) → (𝐻‘suc 𝐾) = (((𝐴 ↑𝑜 (𝐺‘𝐾)) ·𝑜 (𝐹‘(𝐺‘𝐾))) +𝑜 (𝐻‘𝐾))) | ||
Theorem | cantnfle 8451* | A lower bound on the CNF function. Since ((𝐴 CNF 𝐵)‘𝐹) is defined as the sum of (𝐴 ↑𝑜 𝑥) ·𝑜 (𝐹‘𝑥) over all 𝑥 in the support of 𝐹, it is larger than any of these terms (and all other terms are zero, so we can extend the statement to all 𝐶 ∈ 𝐵 instead of just those 𝐶 in the support). (Contributed by Mario Carneiro, 28-May-2015.) (Revised by AV, 28-Jun-2019.) |
⊢ 𝑆 = dom (𝐴 CNF 𝐵) & ⊢ (𝜑 → 𝐴 ∈ On) & ⊢ (𝜑 → 𝐵 ∈ On) & ⊢ 𝐺 = OrdIso( E , (𝐹 supp ∅)) & ⊢ (𝜑 → 𝐹 ∈ 𝑆) & ⊢ 𝐻 = seq𝜔((𝑘 ∈ V, 𝑧 ∈ V ↦ (((𝐴 ↑𝑜 (𝐺‘𝑘)) ·𝑜 (𝐹‘(𝐺‘𝑘))) +𝑜 𝑧)), ∅) & ⊢ (𝜑 → 𝐶 ∈ 𝐵) ⇒ ⊢ (𝜑 → ((𝐴 ↑𝑜 𝐶) ·𝑜 (𝐹‘𝐶)) ⊆ ((𝐴 CNF 𝐵)‘𝐹)) | ||
Theorem | cantnflt 8452* | An upper bound on the partial sums of the CNF function. Since each term dominates all previous terms, by induction we can bound the whole sum with any exponent 𝐴 ↑𝑜 𝐶 where 𝐶 is larger than any exponent (𝐺‘𝑥), 𝑥 ∈ 𝐾 which has been summed so far. (Contributed by Mario Carneiro, 28-May-2015.) (Revised by AV, 29-Jun-2019.) |
⊢ 𝑆 = dom (𝐴 CNF 𝐵) & ⊢ (𝜑 → 𝐴 ∈ On) & ⊢ (𝜑 → 𝐵 ∈ On) & ⊢ 𝐺 = OrdIso( E , (𝐹 supp ∅)) & ⊢ (𝜑 → 𝐹 ∈ 𝑆) & ⊢ 𝐻 = seq𝜔((𝑘 ∈ V, 𝑧 ∈ V ↦ (((𝐴 ↑𝑜 (𝐺‘𝑘)) ·𝑜 (𝐹‘(𝐺‘𝑘))) +𝑜 𝑧)), ∅) & ⊢ (𝜑 → ∅ ∈ 𝐴) & ⊢ (𝜑 → 𝐾 ∈ suc dom 𝐺) & ⊢ (𝜑 → 𝐶 ∈ On) & ⊢ (𝜑 → (𝐺 “ 𝐾) ⊆ 𝐶) ⇒ ⊢ (𝜑 → (𝐻‘𝐾) ∈ (𝐴 ↑𝑜 𝐶)) | ||
Theorem | cantnflt2 8453 | An upper bound on the CNF function. (Contributed by Mario Carneiro, 28-May-2015.) (Revised by AV, 29-Jun-2019.) |
⊢ 𝑆 = dom (𝐴 CNF 𝐵) & ⊢ (𝜑 → 𝐴 ∈ On) & ⊢ (𝜑 → 𝐵 ∈ On) & ⊢ (𝜑 → 𝐹 ∈ 𝑆) & ⊢ (𝜑 → ∅ ∈ 𝐴) & ⊢ (𝜑 → 𝐶 ∈ On) & ⊢ (𝜑 → (𝐹 supp ∅) ⊆ 𝐶) ⇒ ⊢ (𝜑 → ((𝐴 CNF 𝐵)‘𝐹) ∈ (𝐴 ↑𝑜 𝐶)) | ||
Theorem | cantnff 8454 | The CNF function is a function from finitely supported functions from 𝐵 to 𝐴, to the ordinal exponential 𝐴 ↑𝑜 𝐵. (Contributed by Mario Carneiro, 28-May-2015.) |
⊢ 𝑆 = dom (𝐴 CNF 𝐵) & ⊢ (𝜑 → 𝐴 ∈ On) & ⊢ (𝜑 → 𝐵 ∈ On) ⇒ ⊢ (𝜑 → (𝐴 CNF 𝐵):𝑆⟶(𝐴 ↑𝑜 𝐵)) | ||
Theorem | cantnf0 8455 | The value of the zero function. (Contributed by Mario Carneiro, 30-May-2015.) |
⊢ 𝑆 = dom (𝐴 CNF 𝐵) & ⊢ (𝜑 → 𝐴 ∈ On) & ⊢ (𝜑 → 𝐵 ∈ On) & ⊢ (𝜑 → ∅ ∈ 𝐴) ⇒ ⊢ (𝜑 → ((𝐴 CNF 𝐵)‘(𝐵 × {∅})) = ∅) | ||
Theorem | cantnfrescl 8456* | A function is finitely supported from 𝐵 to 𝐴 iff the extended function is finitely supported from 𝐷 to 𝐴. (Contributed by Mario Carneiro, 25-May-2015.) |
⊢ 𝑆 = dom (𝐴 CNF 𝐵) & ⊢ (𝜑 → 𝐴 ∈ On) & ⊢ (𝜑 → 𝐵 ∈ On) & ⊢ (𝜑 → 𝐷 ∈ On) & ⊢ (𝜑 → 𝐵 ⊆ 𝐷) & ⊢ ((𝜑 ∧ 𝑛 ∈ (𝐷 ∖ 𝐵)) → 𝑋 = ∅) & ⊢ (𝜑 → ∅ ∈ 𝐴) & ⊢ 𝑇 = dom (𝐴 CNF 𝐷) ⇒ ⊢ (𝜑 → ((𝑛 ∈ 𝐵 ↦ 𝑋) ∈ 𝑆 ↔ (𝑛 ∈ 𝐷 ↦ 𝑋) ∈ 𝑇)) | ||
Theorem | cantnfres 8457* | The CNF function respects extensions of the domain to a larger ordinal. (Contributed by Mario Carneiro, 25-May-2015.) |
⊢ 𝑆 = dom (𝐴 CNF 𝐵) & ⊢ (𝜑 → 𝐴 ∈ On) & ⊢ (𝜑 → 𝐵 ∈ On) & ⊢ (𝜑 → 𝐷 ∈ On) & ⊢ (𝜑 → 𝐵 ⊆ 𝐷) & ⊢ ((𝜑 ∧ 𝑛 ∈ (𝐷 ∖ 𝐵)) → 𝑋 = ∅) & ⊢ (𝜑 → ∅ ∈ 𝐴) & ⊢ 𝑇 = dom (𝐴 CNF 𝐷) & ⊢ (𝜑 → (𝑛 ∈ 𝐵 ↦ 𝑋) ∈ 𝑆) ⇒ ⊢ (𝜑 → ((𝐴 CNF 𝐵)‘(𝑛 ∈ 𝐵 ↦ 𝑋)) = ((𝐴 CNF 𝐷)‘(𝑛 ∈ 𝐷 ↦ 𝑋))) | ||
Theorem | cantnfp1lem1 8458* | Lemma for cantnfp1 8461. (Contributed by Mario Carneiro, 20-Jun-2015.) (Revised by AV, 30-Jun-2019.) |
⊢ 𝑆 = dom (𝐴 CNF 𝐵) & ⊢ (𝜑 → 𝐴 ∈ On) & ⊢ (𝜑 → 𝐵 ∈ On) & ⊢ (𝜑 → 𝐺 ∈ 𝑆) & ⊢ (𝜑 → 𝑋 ∈ 𝐵) & ⊢ (𝜑 → 𝑌 ∈ 𝐴) & ⊢ (𝜑 → (𝐺 supp ∅) ⊆ 𝑋) & ⊢ 𝐹 = (𝑡 ∈ 𝐵 ↦ if(𝑡 = 𝑋, 𝑌, (𝐺‘𝑡))) ⇒ ⊢ (𝜑 → 𝐹 ∈ 𝑆) | ||
Theorem | cantnfp1lem2 8459* | Lemma for cantnfp1 8461. (Contributed by Mario Carneiro, 28-May-2015.) (Revised by AV, 30-Jun-2019.) |
⊢ 𝑆 = dom (𝐴 CNF 𝐵) & ⊢ (𝜑 → 𝐴 ∈ On) & ⊢ (𝜑 → 𝐵 ∈ On) & ⊢ (𝜑 → 𝐺 ∈ 𝑆) & ⊢ (𝜑 → 𝑋 ∈ 𝐵) & ⊢ (𝜑 → 𝑌 ∈ 𝐴) & ⊢ (𝜑 → (𝐺 supp ∅) ⊆ 𝑋) & ⊢ 𝐹 = (𝑡 ∈ 𝐵 ↦ if(𝑡 = 𝑋, 𝑌, (𝐺‘𝑡))) & ⊢ (𝜑 → ∅ ∈ 𝑌) & ⊢ 𝑂 = OrdIso( E , (𝐹 supp ∅)) ⇒ ⊢ (𝜑 → dom 𝑂 = suc ∪ dom 𝑂) | ||
Theorem | cantnfp1lem3 8460* | Lemma for cantnfp1 8461. (Contributed by Mario Carneiro, 28-May-2015.) (Revised by AV, 1-Jul-2019.) |
⊢ 𝑆 = dom (𝐴 CNF 𝐵) & ⊢ (𝜑 → 𝐴 ∈ On) & ⊢ (𝜑 → 𝐵 ∈ On) & ⊢ (𝜑 → 𝐺 ∈ 𝑆) & ⊢ (𝜑 → 𝑋 ∈ 𝐵) & ⊢ (𝜑 → 𝑌 ∈ 𝐴) & ⊢ (𝜑 → (𝐺 supp ∅) ⊆ 𝑋) & ⊢ 𝐹 = (𝑡 ∈ 𝐵 ↦ if(𝑡 = 𝑋, 𝑌, (𝐺‘𝑡))) & ⊢ (𝜑 → ∅ ∈ 𝑌) & ⊢ 𝑂 = OrdIso( E , (𝐹 supp ∅)) & ⊢ 𝐻 = seq𝜔((𝑘 ∈ V, 𝑧 ∈ V ↦ (((𝐴 ↑𝑜 (𝑂‘𝑘)) ·𝑜 (𝐹‘(𝑂‘𝑘))) +𝑜 𝑧)), ∅) & ⊢ 𝐾 = OrdIso( E , (𝐺 supp ∅)) & ⊢ 𝑀 = seq𝜔((𝑘 ∈ V, 𝑧 ∈ V ↦ (((𝐴 ↑𝑜 (𝐾‘𝑘)) ·𝑜 (𝐺‘(𝐾‘𝑘))) +𝑜 𝑧)), ∅) ⇒ ⊢ (𝜑 → ((𝐴 CNF 𝐵)‘𝐹) = (((𝐴 ↑𝑜 𝑋) ·𝑜 𝑌) +𝑜 ((𝐴 CNF 𝐵)‘𝐺))) | ||
Theorem | cantnfp1 8461* | If 𝐹 is created by adding a single term (𝐹‘𝑋) = 𝑌 to 𝐺, where 𝑋 is larger than any element of the support of 𝐺, then 𝐹 is also a finitely supported function and it is assigned the value ((𝐴 ↑𝑜 𝑋) ·𝑜 𝑌) +𝑜 𝑧 where 𝑧 is the value of 𝐺. (Contributed by Mario Carneiro, 28-May-2015.) (Revised by AV, 1-Jul-2019.) |
⊢ 𝑆 = dom (𝐴 CNF 𝐵) & ⊢ (𝜑 → 𝐴 ∈ On) & ⊢ (𝜑 → 𝐵 ∈ On) & ⊢ (𝜑 → 𝐺 ∈ 𝑆) & ⊢ (𝜑 → 𝑋 ∈ 𝐵) & ⊢ (𝜑 → 𝑌 ∈ 𝐴) & ⊢ (𝜑 → (𝐺 supp ∅) ⊆ 𝑋) & ⊢ 𝐹 = (𝑡 ∈ 𝐵 ↦ if(𝑡 = 𝑋, 𝑌, (𝐺‘𝑡))) ⇒ ⊢ (𝜑 → (𝐹 ∈ 𝑆 ∧ ((𝐴 CNF 𝐵)‘𝐹) = (((𝐴 ↑𝑜 𝑋) ·𝑜 𝑌) +𝑜 ((𝐴 CNF 𝐵)‘𝐺)))) | ||
Theorem | oemapso 8462* | The relation 𝑇 is a strict order on 𝑆 (a corollary of wemapso2 8341). (Contributed by Mario Carneiro, 28-May-2015.) |
⊢ 𝑆 = dom (𝐴 CNF 𝐵) & ⊢ (𝜑 → 𝐴 ∈ On) & ⊢ (𝜑 → 𝐵 ∈ On) & ⊢ 𝑇 = {〈𝑥, 𝑦〉 ∣ ∃𝑧 ∈ 𝐵 ((𝑥‘𝑧) ∈ (𝑦‘𝑧) ∧ ∀𝑤 ∈ 𝐵 (𝑧 ∈ 𝑤 → (𝑥‘𝑤) = (𝑦‘𝑤)))} ⇒ ⊢ (𝜑 → 𝑇 Or 𝑆) | ||
Theorem | oemapval 8463* | Value of the relation 𝑇. (Contributed by Mario Carneiro, 28-May-2015.) |
⊢ 𝑆 = dom (𝐴 CNF 𝐵) & ⊢ (𝜑 → 𝐴 ∈ On) & ⊢ (𝜑 → 𝐵 ∈ On) & ⊢ 𝑇 = {〈𝑥, 𝑦〉 ∣ ∃𝑧 ∈ 𝐵 ((𝑥‘𝑧) ∈ (𝑦‘𝑧) ∧ ∀𝑤 ∈ 𝐵 (𝑧 ∈ 𝑤 → (𝑥‘𝑤) = (𝑦‘𝑤)))} & ⊢ (𝜑 → 𝐹 ∈ 𝑆) & ⊢ (𝜑 → 𝐺 ∈ 𝑆) ⇒ ⊢ (𝜑 → (𝐹𝑇𝐺 ↔ ∃𝑧 ∈ 𝐵 ((𝐹‘𝑧) ∈ (𝐺‘𝑧) ∧ ∀𝑤 ∈ 𝐵 (𝑧 ∈ 𝑤 → (𝐹‘𝑤) = (𝐺‘𝑤))))) | ||
Theorem | oemapvali 8464* | If 𝐹 < 𝐺, then there is some 𝑧 witnessing this, but we can say more and in fact there is a definable expression 𝑋 that also witnesses 𝐹 < 𝐺. (Contributed by Mario Carneiro, 25-May-2015.) |
⊢ 𝑆 = dom (𝐴 CNF 𝐵) & ⊢ (𝜑 → 𝐴 ∈ On) & ⊢ (𝜑 → 𝐵 ∈ On) & ⊢ 𝑇 = {〈𝑥, 𝑦〉 ∣ ∃𝑧 ∈ 𝐵 ((𝑥‘𝑧) ∈ (𝑦‘𝑧) ∧ ∀𝑤 ∈ 𝐵 (𝑧 ∈ 𝑤 → (𝑥‘𝑤) = (𝑦‘𝑤)))} & ⊢ (𝜑 → 𝐹 ∈ 𝑆) & ⊢ (𝜑 → 𝐺 ∈ 𝑆) & ⊢ (𝜑 → 𝐹𝑇𝐺) & ⊢ 𝑋 = ∪ {𝑐 ∈ 𝐵 ∣ (𝐹‘𝑐) ∈ (𝐺‘𝑐)} ⇒ ⊢ (𝜑 → (𝑋 ∈ 𝐵 ∧ (𝐹‘𝑋) ∈ (𝐺‘𝑋) ∧ ∀𝑤 ∈ 𝐵 (𝑋 ∈ 𝑤 → (𝐹‘𝑤) = (𝐺‘𝑤)))) | ||
Theorem | cantnflem1a 8465* | Lemma for cantnf 8473. (Contributed by Mario Carneiro, 4-Jun-2015.) (Revised by AV, 2-Jul-2019.) |
⊢ 𝑆 = dom (𝐴 CNF 𝐵) & ⊢ (𝜑 → 𝐴 ∈ On) & ⊢ (𝜑 → 𝐵 ∈ On) & ⊢ 𝑇 = {〈𝑥, 𝑦〉 ∣ ∃𝑧 ∈ 𝐵 ((𝑥‘𝑧) ∈ (𝑦‘𝑧) ∧ ∀𝑤 ∈ 𝐵 (𝑧 ∈ 𝑤 → (𝑥‘𝑤) = (𝑦‘𝑤)))} & ⊢ (𝜑 → 𝐹 ∈ 𝑆) & ⊢ (𝜑 → 𝐺 ∈ 𝑆) & ⊢ (𝜑 → 𝐹𝑇𝐺) & ⊢ 𝑋 = ∪ {𝑐 ∈ 𝐵 ∣ (𝐹‘𝑐) ∈ (𝐺‘𝑐)} ⇒ ⊢ (𝜑 → 𝑋 ∈ (𝐺 supp ∅)) | ||
Theorem | cantnflem1b 8466* | Lemma for cantnf 8473. (Contributed by Mario Carneiro, 4-Jun-2015.) (Revised by AV, 2-Jul-2019.) |
⊢ 𝑆 = dom (𝐴 CNF 𝐵) & ⊢ (𝜑 → 𝐴 ∈ On) & ⊢ (𝜑 → 𝐵 ∈ On) & ⊢ 𝑇 = {〈𝑥, 𝑦〉 ∣ ∃𝑧 ∈ 𝐵 ((𝑥‘𝑧) ∈ (𝑦‘𝑧) ∧ ∀𝑤 ∈ 𝐵 (𝑧 ∈ 𝑤 → (𝑥‘𝑤) = (𝑦‘𝑤)))} & ⊢ (𝜑 → 𝐹 ∈ 𝑆) & ⊢ (𝜑 → 𝐺 ∈ 𝑆) & ⊢ (𝜑 → 𝐹𝑇𝐺) & ⊢ 𝑋 = ∪ {𝑐 ∈ 𝐵 ∣ (𝐹‘𝑐) ∈ (𝐺‘𝑐)} & ⊢ 𝑂 = OrdIso( E , (𝐺 supp ∅)) ⇒ ⊢ ((𝜑 ∧ (suc 𝑢 ∈ dom 𝑂 ∧ (◡𝑂‘𝑋) ⊆ 𝑢)) → 𝑋 ⊆ (𝑂‘𝑢)) | ||
Theorem | cantnflem1c 8467* | Lemma for cantnf 8473. (Contributed by Mario Carneiro, 4-Jun-2015.) (Revised by AV, 2-Jul-2019.) (Proof shortened by AV, 4-Apr-2020.) |
⊢ 𝑆 = dom (𝐴 CNF 𝐵) & ⊢ (𝜑 → 𝐴 ∈ On) & ⊢ (𝜑 → 𝐵 ∈ On) & ⊢ 𝑇 = {〈𝑥, 𝑦〉 ∣ ∃𝑧 ∈ 𝐵 ((𝑥‘𝑧) ∈ (𝑦‘𝑧) ∧ ∀𝑤 ∈ 𝐵 (𝑧 ∈ 𝑤 → (𝑥‘𝑤) = (𝑦‘𝑤)))} & ⊢ (𝜑 → 𝐹 ∈ 𝑆) & ⊢ (𝜑 → 𝐺 ∈ 𝑆) & ⊢ (𝜑 → 𝐹𝑇𝐺) & ⊢ 𝑋 = ∪ {𝑐 ∈ 𝐵 ∣ (𝐹‘𝑐) ∈ (𝐺‘𝑐)} & ⊢ 𝑂 = OrdIso( E , (𝐺 supp ∅)) ⇒ ⊢ ((((𝜑 ∧ (suc 𝑢 ∈ dom 𝑂 ∧ (◡𝑂‘𝑋) ⊆ 𝑢)) ∧ 𝑥 ∈ 𝐵) ∧ ((𝐹‘𝑥) ≠ ∅ ∧ (𝑂‘𝑢) ∈ 𝑥)) → 𝑥 ∈ (𝐺 supp ∅)) | ||
Theorem | cantnflem1d 8468* | Lemma for cantnf 8473. (Contributed by Mario Carneiro, 4-Jun-2015.) (Revised by AV, 2-Jul-2019.) |
⊢ 𝑆 = dom (𝐴 CNF 𝐵) & ⊢ (𝜑 → 𝐴 ∈ On) & ⊢ (𝜑 → 𝐵 ∈ On) & ⊢ 𝑇 = {〈𝑥, 𝑦〉 ∣ ∃𝑧 ∈ 𝐵 ((𝑥‘𝑧) ∈ (𝑦‘𝑧) ∧ ∀𝑤 ∈ 𝐵 (𝑧 ∈ 𝑤 → (𝑥‘𝑤) = (𝑦‘𝑤)))} & ⊢ (𝜑 → 𝐹 ∈ 𝑆) & ⊢ (𝜑 → 𝐺 ∈ 𝑆) & ⊢ (𝜑 → 𝐹𝑇𝐺) & ⊢ 𝑋 = ∪ {𝑐 ∈ 𝐵 ∣ (𝐹‘𝑐) ∈ (𝐺‘𝑐)} & ⊢ 𝑂 = OrdIso( E , (𝐺 supp ∅)) & ⊢ 𝐻 = seq𝜔((𝑘 ∈ V, 𝑧 ∈ V ↦ (((𝐴 ↑𝑜 (𝑂‘𝑘)) ·𝑜 (𝐺‘(𝑂‘𝑘))) +𝑜 𝑧)), ∅) ⇒ ⊢ (𝜑 → ((𝐴 CNF 𝐵)‘(𝑥 ∈ 𝐵 ↦ if(𝑥 ⊆ 𝑋, (𝐹‘𝑥), ∅))) ∈ (𝐻‘suc (◡𝑂‘𝑋))) | ||
Theorem | cantnflem1 8469* | Lemma for cantnf 8473. This part of the proof is showing uniqueness of the Cantor normal form. We already know that the relation 𝑇 is a strict order, but we haven't shown it is a well-order yet. But being a strict order is enough to show that two distinct 𝐹, 𝐺 are 𝑇 -related as 𝐹 < 𝐺 or 𝐺 < 𝐹, and WLOG assuming that 𝐹 < 𝐺, we show that CNF respects this order and maps these two to different ordinals. (Contributed by Mario Carneiro, 28-May-2015.) (Revised by AV, 2-Jul-2019.) |
⊢ 𝑆 = dom (𝐴 CNF 𝐵) & ⊢ (𝜑 → 𝐴 ∈ On) & ⊢ (𝜑 → 𝐵 ∈ On) & ⊢ 𝑇 = {〈𝑥, 𝑦〉 ∣ ∃𝑧 ∈ 𝐵 ((𝑥‘𝑧) ∈ (𝑦‘𝑧) ∧ ∀𝑤 ∈ 𝐵 (𝑧 ∈ 𝑤 → (𝑥‘𝑤) = (𝑦‘𝑤)))} & ⊢ (𝜑 → 𝐹 ∈ 𝑆) & ⊢ (𝜑 → 𝐺 ∈ 𝑆) & ⊢ (𝜑 → 𝐹𝑇𝐺) & ⊢ 𝑋 = ∪ {𝑐 ∈ 𝐵 ∣ (𝐹‘𝑐) ∈ (𝐺‘𝑐)} & ⊢ 𝑂 = OrdIso( E , (𝐺 supp ∅)) & ⊢ 𝐻 = seq𝜔((𝑘 ∈ V, 𝑧 ∈ V ↦ (((𝐴 ↑𝑜 (𝑂‘𝑘)) ·𝑜 (𝐺‘(𝑂‘𝑘))) +𝑜 𝑧)), ∅) ⇒ ⊢ (𝜑 → ((𝐴 CNF 𝐵)‘𝐹) ∈ ((𝐴 CNF 𝐵)‘𝐺)) | ||
Theorem | cantnflem2 8470* | Lemma for cantnf 8473. (Contributed by Mario Carneiro, 28-May-2015.) |
⊢ 𝑆 = dom (𝐴 CNF 𝐵) & ⊢ (𝜑 → 𝐴 ∈ On) & ⊢ (𝜑 → 𝐵 ∈ On) & ⊢ 𝑇 = {〈𝑥, 𝑦〉 ∣ ∃𝑧 ∈ 𝐵 ((𝑥‘𝑧) ∈ (𝑦‘𝑧) ∧ ∀𝑤 ∈ 𝐵 (𝑧 ∈ 𝑤 → (𝑥‘𝑤) = (𝑦‘𝑤)))} & ⊢ (𝜑 → 𝐶 ∈ (𝐴 ↑𝑜 𝐵)) & ⊢ (𝜑 → 𝐶 ⊆ ran (𝐴 CNF 𝐵)) & ⊢ (𝜑 → ∅ ∈ 𝐶) ⇒ ⊢ (𝜑 → (𝐴 ∈ (On ∖ 2𝑜) ∧ 𝐶 ∈ (On ∖ 1𝑜))) | ||
Theorem | cantnflem3 8471* | Lemma for cantnf 8473. Here we show existence of Cantor normal forms. Assuming (by transfinite induction) that every number less than 𝐶 has a normal form, we can use oeeu 7570 to factor 𝐶 into the form ((𝐴 ↑𝑜 𝑋) ·𝑜 𝑌) +𝑜 𝑍 where 0 < 𝑌 < 𝐴 and 𝑍 < (𝐴 ↑𝑜 𝑋) (and a fortiori 𝑋 < 𝐵). Then since 𝑍 < (𝐴 ↑𝑜 𝑋) ≤ (𝐴 ↑𝑜 𝑋) ·𝑜 𝑌 ≤ 𝐶, 𝑍 has a normal form, and by appending the term (𝐴 ↑𝑜 𝑋) ·𝑜 𝑌 using cantnfp1 8461 we get a normal form for 𝐶. (Contributed by Mario Carneiro, 28-May-2015.) |
⊢ 𝑆 = dom (𝐴 CNF 𝐵) & ⊢ (𝜑 → 𝐴 ∈ On) & ⊢ (𝜑 → 𝐵 ∈ On) & ⊢ 𝑇 = {〈𝑥, 𝑦〉 ∣ ∃𝑧 ∈ 𝐵 ((𝑥‘𝑧) ∈ (𝑦‘𝑧) ∧ ∀𝑤 ∈ 𝐵 (𝑧 ∈ 𝑤 → (𝑥‘𝑤) = (𝑦‘𝑤)))} & ⊢ (𝜑 → 𝐶 ∈ (𝐴 ↑𝑜 𝐵)) & ⊢ (𝜑 → 𝐶 ⊆ ran (𝐴 CNF 𝐵)) & ⊢ (𝜑 → ∅ ∈ 𝐶) & ⊢ 𝑋 = ∪ ∩ {𝑐 ∈ On ∣ 𝐶 ∈ (𝐴 ↑𝑜 𝑐)} & ⊢ 𝑃 = (℩𝑑∃𝑎 ∈ On ∃𝑏 ∈ (𝐴 ↑𝑜 𝑋)(𝑑 = 〈𝑎, 𝑏〉 ∧ (((𝐴 ↑𝑜 𝑋) ·𝑜 𝑎) +𝑜 𝑏) = 𝐶)) & ⊢ 𝑌 = (1st ‘𝑃) & ⊢ 𝑍 = (2nd ‘𝑃) & ⊢ (𝜑 → 𝐺 ∈ 𝑆) & ⊢ (𝜑 → ((𝐴 CNF 𝐵)‘𝐺) = 𝑍) & ⊢ 𝐹 = (𝑡 ∈ 𝐵 ↦ if(𝑡 = 𝑋, 𝑌, (𝐺‘𝑡))) ⇒ ⊢ (𝜑 → 𝐶 ∈ ran (𝐴 CNF 𝐵)) | ||
Theorem | cantnflem4 8472* | Lemma for cantnf 8473. Complete the induction step of cantnflem3 8471. (Contributed by Mario Carneiro, 25-May-2015.) |
⊢ 𝑆 = dom (𝐴 CNF 𝐵) & ⊢ (𝜑 → 𝐴 ∈ On) & ⊢ (𝜑 → 𝐵 ∈ On) & ⊢ 𝑇 = {〈𝑥, 𝑦〉 ∣ ∃𝑧 ∈ 𝐵 ((𝑥‘𝑧) ∈ (𝑦‘𝑧) ∧ ∀𝑤 ∈ 𝐵 (𝑧 ∈ 𝑤 → (𝑥‘𝑤) = (𝑦‘𝑤)))} & ⊢ (𝜑 → 𝐶 ∈ (𝐴 ↑𝑜 𝐵)) & ⊢ (𝜑 → 𝐶 ⊆ ran (𝐴 CNF 𝐵)) & ⊢ (𝜑 → ∅ ∈ 𝐶) & ⊢ 𝑋 = ∪ ∩ {𝑐 ∈ On ∣ 𝐶 ∈ (𝐴 ↑𝑜 𝑐)} & ⊢ 𝑃 = (℩𝑑∃𝑎 ∈ On ∃𝑏 ∈ (𝐴 ↑𝑜 𝑋)(𝑑 = 〈𝑎, 𝑏〉 ∧ (((𝐴 ↑𝑜 𝑋) ·𝑜 𝑎) +𝑜 𝑏) = 𝐶)) & ⊢ 𝑌 = (1st ‘𝑃) & ⊢ 𝑍 = (2nd ‘𝑃) ⇒ ⊢ (𝜑 → 𝐶 ∈ ran (𝐴 CNF 𝐵)) | ||
Theorem | cantnf 8473* | The Cantor Normal Form theorem. The function (𝐴 CNF 𝐵), which maps a finitely supported function from 𝐵 to 𝐴 to the sum ((𝐴 ↑𝑜 𝑓(𝑎1)) ∘ 𝑎1) +𝑜 ((𝐴 ↑𝑜 𝑓(𝑎2)) ∘ 𝑎2) +𝑜 ... over all indexes 𝑎 < 𝐵 such that 𝑓(𝑎) is nonzero, is an order isomorphism from the ordering 𝑇 of finitely supported functions to the set (𝐴 ↑𝑜 𝐵) under the natural order. Setting 𝐴 = ω and letting 𝐵 be arbitrarily large, the surjectivity of this function implies that every ordinal has a Cantor normal form (and injectivity, together with coherence cantnfres 8457, implies that such a representation is unique). (Contributed by Mario Carneiro, 28-May-2015.) |
⊢ 𝑆 = dom (𝐴 CNF 𝐵) & ⊢ (𝜑 → 𝐴 ∈ On) & ⊢ (𝜑 → 𝐵 ∈ On) & ⊢ 𝑇 = {〈𝑥, 𝑦〉 ∣ ∃𝑧 ∈ 𝐵 ((𝑥‘𝑧) ∈ (𝑦‘𝑧) ∧ ∀𝑤 ∈ 𝐵 (𝑧 ∈ 𝑤 → (𝑥‘𝑤) = (𝑦‘𝑤)))} ⇒ ⊢ (𝜑 → (𝐴 CNF 𝐵) Isom 𝑇, E (𝑆, (𝐴 ↑𝑜 𝐵))) | ||
Theorem | oemapwe 8474* | The lexicographic order on a function space of ordinals gives a well-ordering with order type equal to the ordinal exponential. This provides an alternate definition of the ordinal exponential. (Contributed by Mario Carneiro, 28-May-2015.) |
⊢ 𝑆 = dom (𝐴 CNF 𝐵) & ⊢ (𝜑 → 𝐴 ∈ On) & ⊢ (𝜑 → 𝐵 ∈ On) & ⊢ 𝑇 = {〈𝑥, 𝑦〉 ∣ ∃𝑧 ∈ 𝐵 ((𝑥‘𝑧) ∈ (𝑦‘𝑧) ∧ ∀𝑤 ∈ 𝐵 (𝑧 ∈ 𝑤 → (𝑥‘𝑤) = (𝑦‘𝑤)))} ⇒ ⊢ (𝜑 → (𝑇 We 𝑆 ∧ dom OrdIso(𝑇, 𝑆) = (𝐴 ↑𝑜 𝐵))) | ||
Theorem | cantnffval2 8475* | An alternate definition of df-cnf 8442 which relies on cantnf 8473. (Note that although the use of 𝑆 seems self-referential, one can use cantnfdm 8444 to eliminate it.) (Contributed by Mario Carneiro, 28-May-2015.) |
⊢ 𝑆 = dom (𝐴 CNF 𝐵) & ⊢ (𝜑 → 𝐴 ∈ On) & ⊢ (𝜑 → 𝐵 ∈ On) & ⊢ 𝑇 = {〈𝑥, 𝑦〉 ∣ ∃𝑧 ∈ 𝐵 ((𝑥‘𝑧) ∈ (𝑦‘𝑧) ∧ ∀𝑤 ∈ 𝐵 (𝑧 ∈ 𝑤 → (𝑥‘𝑤) = (𝑦‘𝑤)))} ⇒ ⊢ (𝜑 → (𝐴 CNF 𝐵) = ◡OrdIso(𝑇, 𝑆)) | ||
Theorem | cantnff1o 8476 | Simplify the isomorphism of cantnf 8473 to simple bijection. (Contributed by Mario Carneiro, 30-May-2015.) |
⊢ 𝑆 = dom (𝐴 CNF 𝐵) & ⊢ (𝜑 → 𝐴 ∈ On) & ⊢ (𝜑 → 𝐵 ∈ On) ⇒ ⊢ (𝜑 → (𝐴 CNF 𝐵):𝑆–1-1-onto→(𝐴 ↑𝑜 𝐵)) | ||
Theorem | wemapwe 8477* | Construct lexicographic order on a function space based on a reverse well-ordering of the indexes and a well-ordering of the values. (Contributed by Mario Carneiro, 29-May-2015.) (Revised by AV, 3-Jul-2019.) |
⊢ 𝑇 = {〈𝑥, 𝑦〉 ∣ ∃𝑧 ∈ 𝐴 ((𝑥‘𝑧)𝑆(𝑦‘𝑧) ∧ ∀𝑤 ∈ 𝐴 (𝑧𝑅𝑤 → (𝑥‘𝑤) = (𝑦‘𝑤)))} & ⊢ 𝑈 = {𝑥 ∈ (𝐵 ↑𝑚 𝐴) ∣ 𝑥 finSupp 𝑍} & ⊢ (𝜑 → 𝑅 We 𝐴) & ⊢ (𝜑 → 𝑆 We 𝐵) & ⊢ (𝜑 → 𝐵 ≠ ∅) & ⊢ 𝐹 = OrdIso(𝑅, 𝐴) & ⊢ 𝐺 = OrdIso(𝑆, 𝐵) & ⊢ 𝑍 = (𝐺‘∅) ⇒ ⊢ (𝜑 → 𝑇 We 𝑈) | ||
Theorem | oef1o 8478* | A bijection of the base sets induces a bijection on ordinal exponentials. (The assumption (𝐹‘∅) = ∅ can be discharged using fveqf1o 6457.) (Contributed by Mario Carneiro, 30-May-2015.) (Revised by AV, 3-Jul-2019.) |
⊢ (𝜑 → 𝐹:𝐴–1-1-onto→𝐶) & ⊢ (𝜑 → 𝐺:𝐵–1-1-onto→𝐷) & ⊢ (𝜑 → 𝐴 ∈ (On ∖ 1𝑜)) & ⊢ (𝜑 → 𝐵 ∈ On) & ⊢ (𝜑 → 𝐶 ∈ On) & ⊢ (𝜑 → 𝐷 ∈ On) & ⊢ (𝜑 → (𝐹‘∅) = ∅) & ⊢ 𝐾 = (𝑦 ∈ {𝑥 ∈ (𝐴 ↑𝑚 𝐵) ∣ 𝑥 finSupp ∅} ↦ (𝐹 ∘ (𝑦 ∘ ◡𝐺))) & ⊢ 𝐻 = (((𝐶 CNF 𝐷) ∘ 𝐾) ∘ ◡(𝐴 CNF 𝐵)) ⇒ ⊢ (𝜑 → 𝐻:(𝐴 ↑𝑜 𝐵)–1-1-onto→(𝐶 ↑𝑜 𝐷)) | ||
Theorem | cnfcomlem 8479* | Lemma for cnfcom 8480. (Contributed by Mario Carneiro, 30-May-2015.) (Revised by AV, 3-Jul-2019.) |
⊢ 𝑆 = dom (ω CNF 𝐴) & ⊢ (𝜑 → 𝐴 ∈ On) & ⊢ (𝜑 → 𝐵 ∈ (ω ↑𝑜 𝐴)) & ⊢ 𝐹 = (◡(ω CNF 𝐴)‘𝐵) & ⊢ 𝐺 = OrdIso( E , (𝐹 supp ∅)) & ⊢ 𝐻 = seq𝜔((𝑘 ∈ V, 𝑧 ∈ V ↦ (𝑀 +𝑜 𝑧)), ∅) & ⊢ 𝑇 = seq𝜔((𝑘 ∈ V, 𝑓 ∈ V ↦ 𝐾), ∅) & ⊢ 𝑀 = ((ω ↑𝑜 (𝐺‘𝑘)) ·𝑜 (𝐹‘(𝐺‘𝑘))) & ⊢ 𝐾 = ((𝑥 ∈ 𝑀 ↦ (dom 𝑓 +𝑜 𝑥)) ∪ ◡(𝑥 ∈ dom 𝑓 ↦ (𝑀 +𝑜 𝑥))) & ⊢ (𝜑 → 𝐼 ∈ dom 𝐺) & ⊢ (𝜑 → 𝑂 ∈ (ω ↑𝑜 (𝐺‘𝐼))) & ⊢ (𝜑 → (𝑇‘𝐼):(𝐻‘𝐼)–1-1-onto→𝑂) ⇒ ⊢ (𝜑 → (𝑇‘suc 𝐼):(𝐻‘suc 𝐼)–1-1-onto→((ω ↑𝑜 (𝐺‘𝐼)) ·𝑜 (𝐹‘(𝐺‘𝐼)))) | ||
Theorem | cnfcom 8480* | Any ordinal 𝐵 is equinumerous to the leading term of its Cantor normal form. Here we show that bijection explicitly. (Contributed by Mario Carneiro, 30-May-2015.) (Revised by AV, 3-Jul-2019.) |
⊢ 𝑆 = dom (ω CNF 𝐴) & ⊢ (𝜑 → 𝐴 ∈ On) & ⊢ (𝜑 → 𝐵 ∈ (ω ↑𝑜 𝐴)) & ⊢ 𝐹 = (◡(ω CNF 𝐴)‘𝐵) & ⊢ 𝐺 = OrdIso( E , (𝐹 supp ∅)) & ⊢ 𝐻 = seq𝜔((𝑘 ∈ V, 𝑧 ∈ V ↦ (𝑀 +𝑜 𝑧)), ∅) & ⊢ 𝑇 = seq𝜔((𝑘 ∈ V, 𝑓 ∈ V ↦ 𝐾), ∅) & ⊢ 𝑀 = ((ω ↑𝑜 (𝐺‘𝑘)) ·𝑜 (𝐹‘(𝐺‘𝑘))) & ⊢ 𝐾 = ((𝑥 ∈ 𝑀 ↦ (dom 𝑓 +𝑜 𝑥)) ∪ ◡(𝑥 ∈ dom 𝑓 ↦ (𝑀 +𝑜 𝑥))) & ⊢ (𝜑 → 𝐼 ∈ dom 𝐺) ⇒ ⊢ (𝜑 → (𝑇‘suc 𝐼):(𝐻‘suc 𝐼)–1-1-onto→((ω ↑𝑜 (𝐺‘𝐼)) ·𝑜 (𝐹‘(𝐺‘𝐼)))) | ||
Theorem | cnfcom2lem 8481* | Lemma for cnfcom2 8482. (Contributed by Mario Carneiro, 30-May-2015.) (Revised by AV, 3-Jul-2019.) |
⊢ 𝑆 = dom (ω CNF 𝐴) & ⊢ (𝜑 → 𝐴 ∈ On) & ⊢ (𝜑 → 𝐵 ∈ (ω ↑𝑜 𝐴)) & ⊢ 𝐹 = (◡(ω CNF 𝐴)‘𝐵) & ⊢ 𝐺 = OrdIso( E , (𝐹 supp ∅)) & ⊢ 𝐻 = seq𝜔((𝑘 ∈ V, 𝑧 ∈ V ↦ (𝑀 +𝑜 𝑧)), ∅) & ⊢ 𝑇 = seq𝜔((𝑘 ∈ V, 𝑓 ∈ V ↦ 𝐾), ∅) & ⊢ 𝑀 = ((ω ↑𝑜 (𝐺‘𝑘)) ·𝑜 (𝐹‘(𝐺‘𝑘))) & ⊢ 𝐾 = ((𝑥 ∈ 𝑀 ↦ (dom 𝑓 +𝑜 𝑥)) ∪ ◡(𝑥 ∈ dom 𝑓 ↦ (𝑀 +𝑜 𝑥))) & ⊢ 𝑊 = (𝐺‘∪ dom 𝐺) & ⊢ (𝜑 → ∅ ∈ 𝐵) ⇒ ⊢ (𝜑 → dom 𝐺 = suc ∪ dom 𝐺) | ||
Theorem | cnfcom2 8482* | Any nonzero ordinal 𝐵 is equinumerous to the leading term of its Cantor normal form. (Contributed by Mario Carneiro, 30-May-2015.) (Revised by AV, 3-Jul-2019.) |
⊢ 𝑆 = dom (ω CNF 𝐴) & ⊢ (𝜑 → 𝐴 ∈ On) & ⊢ (𝜑 → 𝐵 ∈ (ω ↑𝑜 𝐴)) & ⊢ 𝐹 = (◡(ω CNF 𝐴)‘𝐵) & ⊢ 𝐺 = OrdIso( E , (𝐹 supp ∅)) & ⊢ 𝐻 = seq𝜔((𝑘 ∈ V, 𝑧 ∈ V ↦ (𝑀 +𝑜 𝑧)), ∅) & ⊢ 𝑇 = seq𝜔((𝑘 ∈ V, 𝑓 ∈ V ↦ 𝐾), ∅) & ⊢ 𝑀 = ((ω ↑𝑜 (𝐺‘𝑘)) ·𝑜 (𝐹‘(𝐺‘𝑘))) & ⊢ 𝐾 = ((𝑥 ∈ 𝑀 ↦ (dom 𝑓 +𝑜 𝑥)) ∪ ◡(𝑥 ∈ dom 𝑓 ↦ (𝑀 +𝑜 𝑥))) & ⊢ 𝑊 = (𝐺‘∪ dom 𝐺) & ⊢ (𝜑 → ∅ ∈ 𝐵) ⇒ ⊢ (𝜑 → (𝑇‘dom 𝐺):𝐵–1-1-onto→((ω ↑𝑜 𝑊) ·𝑜 (𝐹‘𝑊))) | ||
Theorem | cnfcom3lem 8483* | Lemma for cnfcom3 8484. (Contributed by Mario Carneiro, 30-May-2015.) (Revised by AV, 4-Jul-2019.) |
⊢ 𝑆 = dom (ω CNF 𝐴) & ⊢ (𝜑 → 𝐴 ∈ On) & ⊢ (𝜑 → 𝐵 ∈ (ω ↑𝑜 𝐴)) & ⊢ 𝐹 = (◡(ω CNF 𝐴)‘𝐵) & ⊢ 𝐺 = OrdIso( E , (𝐹 supp ∅)) & ⊢ 𝐻 = seq𝜔((𝑘 ∈ V, 𝑧 ∈ V ↦ (𝑀 +𝑜 𝑧)), ∅) & ⊢ 𝑇 = seq𝜔((𝑘 ∈ V, 𝑓 ∈ V ↦ 𝐾), ∅) & ⊢ 𝑀 = ((ω ↑𝑜 (𝐺‘𝑘)) ·𝑜 (𝐹‘(𝐺‘𝑘))) & ⊢ 𝐾 = ((𝑥 ∈ 𝑀 ↦ (dom 𝑓 +𝑜 𝑥)) ∪ ◡(𝑥 ∈ dom 𝑓 ↦ (𝑀 +𝑜 𝑥))) & ⊢ 𝑊 = (𝐺‘∪ dom 𝐺) & ⊢ (𝜑 → ω ⊆ 𝐵) ⇒ ⊢ (𝜑 → 𝑊 ∈ (On ∖ 1𝑜)) | ||
Theorem | cnfcom3 8484* | Any infinite ordinal 𝐵 is equinumerous to a power of ω. (We are being careful here to show explicit bijections rather than simple equinumerosity because we want a uniform construction for cnfcom3c 8486.) (Contributed by Mario Carneiro, 28-May-2015.) (Revised by AV, 4-Jul-2019.) |
⊢ 𝑆 = dom (ω CNF 𝐴) & ⊢ (𝜑 → 𝐴 ∈ On) & ⊢ (𝜑 → 𝐵 ∈ (ω ↑𝑜 𝐴)) & ⊢ 𝐹 = (◡(ω CNF 𝐴)‘𝐵) & ⊢ 𝐺 = OrdIso( E , (𝐹 supp ∅)) & ⊢ 𝐻 = seq𝜔((𝑘 ∈ V, 𝑧 ∈ V ↦ (𝑀 +𝑜 𝑧)), ∅) & ⊢ 𝑇 = seq𝜔((𝑘 ∈ V, 𝑓 ∈ V ↦ 𝐾), ∅) & ⊢ 𝑀 = ((ω ↑𝑜 (𝐺‘𝑘)) ·𝑜 (𝐹‘(𝐺‘𝑘))) & ⊢ 𝐾 = ((𝑥 ∈ 𝑀 ↦ (dom 𝑓 +𝑜 𝑥)) ∪ ◡(𝑥 ∈ dom 𝑓 ↦ (𝑀 +𝑜 𝑥))) & ⊢ 𝑊 = (𝐺‘∪ dom 𝐺) & ⊢ (𝜑 → ω ⊆ 𝐵) & ⊢ 𝑋 = (𝑢 ∈ (𝐹‘𝑊), 𝑣 ∈ (ω ↑𝑜 𝑊) ↦ (((𝐹‘𝑊) ·𝑜 𝑣) +𝑜 𝑢)) & ⊢ 𝑌 = (𝑢 ∈ (𝐹‘𝑊), 𝑣 ∈ (ω ↑𝑜 𝑊) ↦ (((ω ↑𝑜 𝑊) ·𝑜 𝑢) +𝑜 𝑣)) & ⊢ 𝑁 = ((𝑋 ∘ ◡𝑌) ∘ (𝑇‘dom 𝐺)) ⇒ ⊢ (𝜑 → 𝑁:𝐵–1-1-onto→(ω ↑𝑜 𝑊)) | ||
Theorem | cnfcom3clem 8485* | Lemma for cnfcom3c 8486. (Contributed by Mario Carneiro, 30-May-2015.) (Revised by AV, 4-Jul-2019.) |
⊢ 𝑆 = dom (ω CNF 𝐴) & ⊢ 𝐹 = (◡(ω CNF 𝐴)‘𝑏) & ⊢ 𝐺 = OrdIso( E , (𝐹 supp ∅)) & ⊢ 𝐻 = seq𝜔((𝑘 ∈ V, 𝑧 ∈ V ↦ (𝑀 +𝑜 𝑧)), ∅) & ⊢ 𝑇 = seq𝜔((𝑘 ∈ V, 𝑓 ∈ V ↦ 𝐾), ∅) & ⊢ 𝑀 = ((ω ↑𝑜 (𝐺‘𝑘)) ·𝑜 (𝐹‘(𝐺‘𝑘))) & ⊢ 𝐾 = ((𝑥 ∈ 𝑀 ↦ (dom 𝑓 +𝑜 𝑥)) ∪ ◡(𝑥 ∈ dom 𝑓 ↦ (𝑀 +𝑜 𝑥))) & ⊢ 𝑊 = (𝐺‘∪ dom 𝐺) & ⊢ 𝑋 = (𝑢 ∈ (𝐹‘𝑊), 𝑣 ∈ (ω ↑𝑜 𝑊) ↦ (((𝐹‘𝑊) ·𝑜 𝑣) +𝑜 𝑢)) & ⊢ 𝑌 = (𝑢 ∈ (𝐹‘𝑊), 𝑣 ∈ (ω ↑𝑜 𝑊) ↦ (((ω ↑𝑜 𝑊) ·𝑜 𝑢) +𝑜 𝑣)) & ⊢ 𝑁 = ((𝑋 ∘ ◡𝑌) ∘ (𝑇‘dom 𝐺)) & ⊢ 𝐿 = (𝑏 ∈ (ω ↑𝑜 𝐴) ↦ 𝑁) ⇒ ⊢ (𝐴 ∈ On → ∃𝑔∀𝑏 ∈ 𝐴 (ω ⊆ 𝑏 → ∃𝑤 ∈ (On ∖ 1𝑜)(𝑔‘𝑏):𝑏–1-1-onto→(ω ↑𝑜 𝑤))) | ||
Theorem | cnfcom3c 8486* | Wrap the construction of cnfcom3 8484 into an existence quantifier. For any ω ⊆ 𝑏, there is a bijection from 𝑏 to some power of ω. Furthermore, this bijection is canonical , which means that we can find a single function 𝑔 which will give such bijections for every 𝑏 less than some arbitrarily large bound 𝐴. (Contributed by Mario Carneiro, 30-May-2015.) |
⊢ (𝐴 ∈ On → ∃𝑔∀𝑏 ∈ 𝐴 (ω ⊆ 𝑏 → ∃𝑤 ∈ (On ∖ 1𝑜)(𝑔‘𝑏):𝑏–1-1-onto→(ω ↑𝑜 𝑤))) | ||
Theorem | trcl 8487* | For any set 𝐴, show the properties of its transitive closure 𝐶. Similar to Theorem 9.1 of [TakeutiZaring] p. 73 except that we show an explicit expression for the transitive closure rather than just its existence. See tz9.1 8488 for an abbreviated version showing existence. (Contributed by NM, 14-Sep-2003.) (Revised by Mario Carneiro, 11-Sep-2015.) |
⊢ 𝐴 ∈ V & ⊢ 𝐹 = (rec((𝑧 ∈ V ↦ (𝑧 ∪ ∪ 𝑧)), 𝐴) ↾ ω) & ⊢ 𝐶 = ∪ 𝑦 ∈ ω (𝐹‘𝑦) ⇒ ⊢ (𝐴 ⊆ 𝐶 ∧ Tr 𝐶 ∧ ∀𝑥((𝐴 ⊆ 𝑥 ∧ Tr 𝑥) → 𝐶 ⊆ 𝑥)) | ||
Theorem | tz9.1 8488* |
Every set has a transitive closure (the smallest transitive extension).
Theorem 9.1 of [TakeutiZaring] p.
73. See trcl 8487 for an explicit
expression for the transitive closure. Apparently open problems are
whether this theorem can be proved without the Axiom of Infinity; if
not, then whether it implies Infinity; and if not, what is the
"property" that Infinity has that the other axioms don't have
that is
weaker than Infinity itself?
(Added 22-Mar-2011) The following article seems to answer the first question, that it can't be proved without Infinity, in the affirmative: Mancini, Antonella and Zambella, Domenico (2001). "A note on recursive models of set theories." Notre Dame Journal of Formal Logic, 42(2):109-115. (Thanks to Scott Fenton.) (Contributed by NM, 15-Sep-2003.) |
⊢ 𝐴 ∈ V ⇒ ⊢ ∃𝑥(𝐴 ⊆ 𝑥 ∧ Tr 𝑥 ∧ ∀𝑦((𝐴 ⊆ 𝑦 ∧ Tr 𝑦) → 𝑥 ⊆ 𝑦)) | ||
Theorem | tz9.1c 8489* | Alternate expression for the existence of transitive closures tz9.1 8488: the intersection of all transitive sets containing 𝐴 is a set. (Contributed by Mario Carneiro, 22-Mar-2013.) |
⊢ 𝐴 ∈ V ⇒ ⊢ ∩ {𝑥 ∣ (𝐴 ⊆ 𝑥 ∧ Tr 𝑥)} ∈ V | ||
Theorem | epfrs 8490* | The strong form of the Axiom of Regularity (no sethood requirement on 𝐴), with the axiom itself present as an antecedent. See also zfregs 8491. (Contributed by Mario Carneiro, 22-Mar-2013.) |
⊢ (( E Fr 𝐴 ∧ 𝐴 ≠ ∅) → ∃𝑥 ∈ 𝐴 (𝑥 ∩ 𝐴) = ∅) | ||
Theorem | zfregs 8491* | The strong form of the Axiom of Regularity, which does not require that 𝐴 be a set. Axiom 6' of [TakeutiZaring] p. 21. See also epfrs 8490. (Contributed by NM, 17-Sep-2003.) |
⊢ (𝐴 ≠ ∅ → ∃𝑥 ∈ 𝐴 (𝑥 ∩ 𝐴) = ∅) | ||
Theorem | zfregs2 8492* | Alternate strong form of the Axiom of Regularity. Not every element of a nonempty class contains some element of that class. (Contributed by Alan Sare, 24-Oct-2011.) (Proof shortened by Wolf Lammen, 27-Sep-2013.) |
⊢ (𝐴 ≠ ∅ → ¬ ∀𝑥 ∈ 𝐴 ∃𝑦(𝑦 ∈ 𝐴 ∧ 𝑦 ∈ 𝑥)) | ||
Theorem | setind 8493* | Set (epsilon) induction. Theorem 5.22 of [TakeutiZaring] p. 21. (Contributed by NM, 17-Sep-2003.) |
⊢ (∀𝑥(𝑥 ⊆ 𝐴 → 𝑥 ∈ 𝐴) → 𝐴 = V) | ||
Theorem | setind2 8494 | Set (epsilon) induction, stated compactly. Given as a homework problem in 1992 by George Boolos (1940-1996). (Contributed by NM, 17-Sep-2003.) |
⊢ (𝒫 𝐴 ⊆ 𝐴 → 𝐴 = V) | ||
Syntax | ctc 8495 | Extend class notation to include the transitive closure function. |
class TC | ||
Definition | df-tc 8496* | The transitive closure function. (Contributed by Mario Carneiro, 23-Jun-2013.) |
⊢ TC = (𝑥 ∈ V ↦ ∩ {𝑦 ∣ (𝑥 ⊆ 𝑦 ∧ Tr 𝑦)}) | ||
Theorem | tcvalg 8497* | Value of the transitive closure function. (The fact that this intersection exists is a non-trivial fact that depends on ax-inf 8418; see tz9.1 8488.) (Contributed by Mario Carneiro, 23-Jun-2013.) |
⊢ (𝐴 ∈ 𝑉 → (TC‘𝐴) = ∩ {𝑥 ∣ (𝐴 ⊆ 𝑥 ∧ Tr 𝑥)}) | ||
Theorem | tcid 8498 | Defining property of the transitive closure function: it contains its argument as a subset. (Contributed by Mario Carneiro, 23-Jun-2013.) |
⊢ (𝐴 ∈ 𝑉 → 𝐴 ⊆ (TC‘𝐴)) | ||
Theorem | tctr 8499 | Defining property of the transitive closure function: it is transitive. (Contributed by Mario Carneiro, 23-Jun-2013.) |
⊢ Tr (TC‘𝐴) | ||
Theorem | tcmin 8500 | Defining property of the transitive closure function: it is a subset of any transitive class containing 𝐴. (Contributed by Mario Carneiro, 23-Jun-2013.) |
⊢ (𝐴 ∈ 𝑉 → ((𝐴 ⊆ 𝐵 ∧ Tr 𝐵) → (TC‘𝐴) ⊆ 𝐵)) |
< Previous Next > |
Copyright terms: Public domain | < Previous Next > |