Home | Metamath
Proof Explorer Theorem List (p. 90 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 | cdalepw 8901 | If 𝐴 is idempotent under cardinal sum and 𝐵 is dominated by the power set of 𝐴, then so is the cardinal sum of 𝐴 and 𝐵. (Contributed by Mario Carneiro, 15-May-2015.) |
⊢ (((𝐴 +𝑐 𝐴) ≈ 𝐴 ∧ 𝐵 ≼ 𝒫 𝐴) → (𝐴 +𝑐 𝐵) ≼ 𝒫 𝐴) | ||
Theorem | onacda 8902 | The cardinal and ordinal sums are always equinumerous. (Contributed by Mario Carneiro, 6-Feb-2013.) (Revised by Mario Carneiro, 30-May-2015.) |
⊢ ((𝐴 ∈ On ∧ 𝐵 ∈ On) → (𝐴 +𝑜 𝐵) ≈ (𝐴 +𝑐 𝐵)) | ||
Theorem | cardacda 8903 | The cardinal sum is equinumerous to an ordinal sum of the cardinals. (Contributed by Mario Carneiro, 6-Feb-2013.) (Revised by Mario Carneiro, 28-Apr-2015.) |
⊢ ((𝐴 ∈ dom card ∧ 𝐵 ∈ dom card) → (𝐴 +𝑐 𝐵) ≈ ((card‘𝐴) +𝑜 (card‘𝐵))) | ||
Theorem | cdanum 8904 | The cardinal sum of two numerable sets is numerable. (Contributed by Mario Carneiro, 29-Apr-2015.) |
⊢ ((𝐴 ∈ dom card ∧ 𝐵 ∈ dom card) → (𝐴 +𝑐 𝐵) ∈ dom card) | ||
Theorem | unnum 8905 | The union of two numerable sets is numerable. (Contributed by Mario Carneiro, 29-Apr-2015.) |
⊢ ((𝐴 ∈ dom card ∧ 𝐵 ∈ dom card) → (𝐴 ∪ 𝐵) ∈ dom card) | ||
Theorem | nnacda 8906 | The cardinal and ordinal sums of finite ordinals are equal. (Contributed by Paul Chapman, 11-Apr-2009.) (Revised by Mario Carneiro, 6-Feb-2013.) |
⊢ ((𝐴 ∈ ω ∧ 𝐵 ∈ ω) → (card‘(𝐴 +𝑐 𝐵)) = (𝐴 +𝑜 𝐵)) | ||
Theorem | ficardun 8907 | The cardinality of the union of disjoint, finite sets is the ordinal sum of their cardinalities. (Contributed by Paul Chapman, 5-Jun-2009.) (Proof shortened by Mario Carneiro, 28-Apr-2015.) |
⊢ ((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin ∧ (𝐴 ∩ 𝐵) = ∅) → (card‘(𝐴 ∪ 𝐵)) = ((card‘𝐴) +𝑜 (card‘𝐵))) | ||
Theorem | ficardun2 8908 | The cardinality of the union of finite sets is at most the ordinal sum of their cardinalities. (Contributed by Mario Carneiro, 5-Feb-2013.) |
⊢ ((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) → (card‘(𝐴 ∪ 𝐵)) ⊆ ((card‘𝐴) +𝑜 (card‘𝐵))) | ||
Theorem | pwsdompw 8909* | Lemma for domtriom 9148. This is the equinumerosity version of the algebraic identity Σ𝑘 ∈ 𝑛(2↑𝑘) = (2↑𝑛) − 1. (Contributed by Mario Carneiro, 7-Feb-2013.) |
⊢ ((𝑛 ∈ ω ∧ ∀𝑘 ∈ suc 𝑛(𝐵‘𝑘) ≈ 𝒫 𝑘) → ∪ 𝑘 ∈ 𝑛 (𝐵‘𝑘) ≺ (𝐵‘𝑛)) | ||
Theorem | unctb 8910 | The union of two countable sets is countable. (Contributed by FL, 25-Aug-2006.) (Proof shortened by Mario Carneiro, 30-Apr-2015.) |
⊢ ((𝐴 ≼ ω ∧ 𝐵 ≼ ω) → (𝐴 ∪ 𝐵) ≼ ω) | ||
Theorem | infcdaabs 8911 | Absorption law for addition to an infinite cardinal. (Contributed by NM, 30-Sep-2004.) (Revised by Mario Carneiro, 29-Apr-2015.) |
⊢ ((𝐴 ∈ dom card ∧ ω ≼ 𝐴 ∧ 𝐵 ≼ 𝐴) → (𝐴 +𝑐 𝐵) ≈ 𝐴) | ||
Theorem | infunabs 8912 | An infinite set is equinumerous to its union with a smaller one. (Contributed by NM, 28-Sep-2004.) (Revised by Mario Carneiro, 29-Apr-2015.) |
⊢ ((𝐴 ∈ dom card ∧ ω ≼ 𝐴 ∧ 𝐵 ≼ 𝐴) → (𝐴 ∪ 𝐵) ≈ 𝐴) | ||
Theorem | infcda 8913 | The sum of two cardinal numbers is their maximum, if one of them is infinite. Proposition 10.41 of [TakeutiZaring] p. 95. (Contributed by NM, 28-Sep-2004.) (Revised by Mario Carneiro, 29-Apr-2015.) |
⊢ ((𝐴 ∈ dom card ∧ 𝐵 ∈ dom card ∧ ω ≼ 𝐴) → (𝐴 +𝑐 𝐵) ≈ (𝐴 ∪ 𝐵)) | ||
Theorem | infdif 8914 | The cardinality of an infinite set does not change after subtracting a strictly smaller one. Example in [Enderton] p. 164. (Contributed by NM, 22-Oct-2004.) (Revised by Mario Carneiro, 29-Apr-2015.) |
⊢ ((𝐴 ∈ dom card ∧ ω ≼ 𝐴 ∧ 𝐵 ≺ 𝐴) → (𝐴 ∖ 𝐵) ≈ 𝐴) | ||
Theorem | infdif2 8915 | Cardinality ordering for an infinite class difference. (Contributed by NM, 24-Mar-2007.) (Revised by Mario Carneiro, 29-Apr-2015.) |
⊢ ((𝐴 ∈ dom card ∧ 𝐵 ∈ dom card ∧ ω ≼ 𝐴) → ((𝐴 ∖ 𝐵) ≼ 𝐵 ↔ 𝐴 ≼ 𝐵)) | ||
Theorem | infxpdom 8916 | Dominance law for multiplication with an infinite cardinal. (Contributed by NM, 26-Mar-2006.) (Revised by Mario Carneiro, 29-Apr-2015.) |
⊢ ((𝐴 ∈ dom card ∧ ω ≼ 𝐴 ∧ 𝐵 ≼ 𝐴) → (𝐴 × 𝐵) ≼ 𝐴) | ||
Theorem | infxpabs 8917 | Absorption law for multiplication with an infinite cardinal. (Contributed by NM, 30-Sep-2004.) (Revised by Mario Carneiro, 29-Apr-2015.) |
⊢ (((𝐴 ∈ dom card ∧ ω ≼ 𝐴) ∧ (𝐵 ≠ ∅ ∧ 𝐵 ≼ 𝐴)) → (𝐴 × 𝐵) ≈ 𝐴) | ||
Theorem | infunsdom1 8918 | The union of two sets that are strictly dominated by the infinite set 𝑋 is also dominated by 𝑋. This version of infunsdom 8919 assumes additionally that 𝐴 is the smaller of the two. (Contributed by Mario Carneiro, 14-Dec-2013.) (Revised by Mario Carneiro, 3-May-2015.) |
⊢ (((𝑋 ∈ dom card ∧ ω ≼ 𝑋) ∧ (𝐴 ≼ 𝐵 ∧ 𝐵 ≺ 𝑋)) → (𝐴 ∪ 𝐵) ≺ 𝑋) | ||
Theorem | infunsdom 8919 | The union of two sets that are strictly dominated by the infinite set 𝑋 is also strictly dominated by 𝑋. (Contributed by Mario Carneiro, 3-May-2015.) |
⊢ (((𝑋 ∈ dom card ∧ ω ≼ 𝑋) ∧ (𝐴 ≺ 𝑋 ∧ 𝐵 ≺ 𝑋)) → (𝐴 ∪ 𝐵) ≺ 𝑋) | ||
Theorem | infxp 8920 | Absorption law for multiplication with an infinite cardinal. Equivalent to Proposition 10.41 of [TakeutiZaring] p. 95. (Contributed by NM, 28-Sep-2004.) (Revised by Mario Carneiro, 29-Apr-2015.) |
⊢ (((𝐴 ∈ dom card ∧ ω ≼ 𝐴) ∧ (𝐵 ∈ dom card ∧ 𝐵 ≠ ∅)) → (𝐴 × 𝐵) ≈ (𝐴 ∪ 𝐵)) | ||
Theorem | pwcdadom 8921 | A property of dominance over a powerset, and a main lemma for gchac 9382. Similar to Lemma 2.3 of [KanamoriPincus] p. 420. (Contributed by Mario Carneiro, 15-May-2015.) |
⊢ (𝒫 (𝐴 +𝑐 𝐴) ≼ (𝐴 +𝑐 𝐵) → 𝒫 𝐴 ≼ 𝐵) | ||
Theorem | infpss 8922* | Every infinite set has an equinumerous proper subset, proved without AC or Infinity. Exercise 7 of [TakeutiZaring] p. 91. See also infpssALT 9018. (Contributed by NM, 23-Oct-2004.) (Revised by Mario Carneiro, 30-Apr-2015.) |
⊢ (ω ≼ 𝐴 → ∃𝑥(𝑥 ⊊ 𝐴 ∧ 𝑥 ≈ 𝐴)) | ||
Theorem | infmap2 8923* | An exponentiation law for infinite cardinals. Similar to Lemma 6.2 of [Jech] p. 43. Although this version of infmap 9277 avoids the axiom of choice, it requires the powerset of an infinite set to be well-orderable and so is usually not applicable. (Contributed by NM, 1-Oct-2004.) (Revised by Mario Carneiro, 30-Apr-2015.) |
⊢ ((ω ≼ 𝐴 ∧ 𝐵 ≼ 𝐴 ∧ (𝐴 ↑𝑚 𝐵) ∈ dom card) → (𝐴 ↑𝑚 𝐵) ≈ {𝑥 ∣ (𝑥 ⊆ 𝐴 ∧ 𝑥 ≈ 𝐵)}) | ||
Theorem | ackbij2lem1 8924 | Lemma for ackbij2 8948. (Contributed by Stefan O'Rear, 18-Nov-2014.) |
⊢ (𝐴 ∈ ω → 𝒫 𝐴 ⊆ (𝒫 ω ∩ Fin)) | ||
Theorem | ackbij1lem1 8925 | Lemma for ackbij2 8948. (Contributed by Stefan O'Rear, 18-Nov-2014.) |
⊢ (¬ 𝐴 ∈ 𝐵 → (𝐵 ∩ suc 𝐴) = (𝐵 ∩ 𝐴)) | ||
Theorem | ackbij1lem2 8926 | Lemma for ackbij2 8948. (Contributed by Stefan O'Rear, 18-Nov-2014.) |
⊢ (𝐴 ∈ 𝐵 → (𝐵 ∩ suc 𝐴) = ({𝐴} ∪ (𝐵 ∩ 𝐴))) | ||
Theorem | ackbij1lem3 8927 | Lemma for ackbij2 8948. (Contributed by Stefan O'Rear, 18-Nov-2014.) |
⊢ (𝐴 ∈ ω → 𝐴 ∈ (𝒫 ω ∩ Fin)) | ||
Theorem | ackbij1lem4 8928 | Lemma for ackbij2 8948. (Contributed by Stefan O'Rear, 19-Nov-2014.) |
⊢ (𝐴 ∈ ω → {𝐴} ∈ (𝒫 ω ∩ Fin)) | ||
Theorem | ackbij1lem5 8929 | Lemma for ackbij2 8948. (Contributed by Stefan O'Rear, 19-Nov-2014.) |
⊢ (𝐴 ∈ ω → (card‘𝒫 suc 𝐴) = ((card‘𝒫 𝐴) +𝑜 (card‘𝒫 𝐴))) | ||
Theorem | ackbij1lem6 8930 | Lemma for ackbij2 8948. (Contributed by Stefan O'Rear, 18-Nov-2014.) |
⊢ ((𝐴 ∈ (𝒫 ω ∩ Fin) ∧ 𝐵 ∈ (𝒫 ω ∩ Fin)) → (𝐴 ∪ 𝐵) ∈ (𝒫 ω ∩ Fin)) | ||
Theorem | ackbij1lem7 8931* | Lemma for ackbij1 8943. (Contributed by Stefan O'Rear, 21-Nov-2014.) |
⊢ 𝐹 = (𝑥 ∈ (𝒫 ω ∩ Fin) ↦ (card‘∪ 𝑦 ∈ 𝑥 ({𝑦} × 𝒫 𝑦))) ⇒ ⊢ (𝐴 ∈ (𝒫 ω ∩ Fin) → (𝐹‘𝐴) = (card‘∪ 𝑦 ∈ 𝐴 ({𝑦} × 𝒫 𝑦))) | ||
Theorem | ackbij1lem8 8932* | Lemma for ackbij1 8943. (Contributed by Stefan O'Rear, 19-Nov-2014.) |
⊢ 𝐹 = (𝑥 ∈ (𝒫 ω ∩ Fin) ↦ (card‘∪ 𝑦 ∈ 𝑥 ({𝑦} × 𝒫 𝑦))) ⇒ ⊢ (𝐴 ∈ ω → (𝐹‘{𝐴}) = (card‘𝒫 𝐴)) | ||
Theorem | ackbij1lem9 8933* | Lemma for ackbij1 8943. (Contributed by Stefan O'Rear, 19-Nov-2014.) |
⊢ 𝐹 = (𝑥 ∈ (𝒫 ω ∩ Fin) ↦ (card‘∪ 𝑦 ∈ 𝑥 ({𝑦} × 𝒫 𝑦))) ⇒ ⊢ ((𝐴 ∈ (𝒫 ω ∩ Fin) ∧ 𝐵 ∈ (𝒫 ω ∩ Fin) ∧ (𝐴 ∩ 𝐵) = ∅) → (𝐹‘(𝐴 ∪ 𝐵)) = ((𝐹‘𝐴) +𝑜 (𝐹‘𝐵))) | ||
Theorem | ackbij1lem10 8934* | Lemma for ackbij1 8943. (Contributed by Stefan O'Rear, 18-Nov-2014.) |
⊢ 𝐹 = (𝑥 ∈ (𝒫 ω ∩ Fin) ↦ (card‘∪ 𝑦 ∈ 𝑥 ({𝑦} × 𝒫 𝑦))) ⇒ ⊢ 𝐹:(𝒫 ω ∩ Fin)⟶ω | ||
Theorem | ackbij1lem11 8935* | Lemma for ackbij1 8943. (Contributed by Stefan O'Rear, 18-Nov-2014.) |
⊢ 𝐹 = (𝑥 ∈ (𝒫 ω ∩ Fin) ↦ (card‘∪ 𝑦 ∈ 𝑥 ({𝑦} × 𝒫 𝑦))) ⇒ ⊢ ((𝐴 ∈ (𝒫 ω ∩ Fin) ∧ 𝐵 ⊆ 𝐴) → 𝐵 ∈ (𝒫 ω ∩ Fin)) | ||
Theorem | ackbij1lem12 8936* | Lemma for ackbij1 8943. (Contributed by Stefan O'Rear, 18-Nov-2014.) |
⊢ 𝐹 = (𝑥 ∈ (𝒫 ω ∩ Fin) ↦ (card‘∪ 𝑦 ∈ 𝑥 ({𝑦} × 𝒫 𝑦))) ⇒ ⊢ ((𝐵 ∈ (𝒫 ω ∩ Fin) ∧ 𝐴 ⊆ 𝐵) → (𝐹‘𝐴) ⊆ (𝐹‘𝐵)) | ||
Theorem | ackbij1lem13 8937* | Lemma for ackbij1 8943. (Contributed by Stefan O'Rear, 18-Nov-2014.) |
⊢ 𝐹 = (𝑥 ∈ (𝒫 ω ∩ Fin) ↦ (card‘∪ 𝑦 ∈ 𝑥 ({𝑦} × 𝒫 𝑦))) ⇒ ⊢ (𝐹‘∅) = ∅ | ||
Theorem | ackbij1lem14 8938* | Lemma for ackbij1 8943. (Contributed by Stefan O'Rear, 18-Nov-2014.) |
⊢ 𝐹 = (𝑥 ∈ (𝒫 ω ∩ Fin) ↦ (card‘∪ 𝑦 ∈ 𝑥 ({𝑦} × 𝒫 𝑦))) ⇒ ⊢ (𝐴 ∈ ω → (𝐹‘{𝐴}) = suc (𝐹‘𝐴)) | ||
Theorem | ackbij1lem15 8939* | Lemma for ackbij1 8943. (Contributed by Stefan O'Rear, 18-Nov-2014.) |
⊢ 𝐹 = (𝑥 ∈ (𝒫 ω ∩ Fin) ↦ (card‘∪ 𝑦 ∈ 𝑥 ({𝑦} × 𝒫 𝑦))) ⇒ ⊢ (((𝐴 ∈ (𝒫 ω ∩ Fin) ∧ 𝐵 ∈ (𝒫 ω ∩ Fin)) ∧ (𝑐 ∈ ω ∧ 𝑐 ∈ 𝐴 ∧ ¬ 𝑐 ∈ 𝐵)) → ¬ (𝐹‘(𝐴 ∩ suc 𝑐)) = (𝐹‘(𝐵 ∩ suc 𝑐))) | ||
Theorem | ackbij1lem16 8940* | Lemma for ackbij1 8943. (Contributed by Stefan O'Rear, 18-Nov-2014.) |
⊢ 𝐹 = (𝑥 ∈ (𝒫 ω ∩ Fin) ↦ (card‘∪ 𝑦 ∈ 𝑥 ({𝑦} × 𝒫 𝑦))) ⇒ ⊢ ((𝐴 ∈ (𝒫 ω ∩ Fin) ∧ 𝐵 ∈ (𝒫 ω ∩ Fin)) → ((𝐹‘𝐴) = (𝐹‘𝐵) → 𝐴 = 𝐵)) | ||
Theorem | ackbij1lem17 8941* | Lemma for ackbij1 8943. (Contributed by Stefan O'Rear, 18-Nov-2014.) |
⊢ 𝐹 = (𝑥 ∈ (𝒫 ω ∩ Fin) ↦ (card‘∪ 𝑦 ∈ 𝑥 ({𝑦} × 𝒫 𝑦))) ⇒ ⊢ 𝐹:(𝒫 ω ∩ Fin)–1-1→ω | ||
Theorem | ackbij1lem18 8942* | Lemma for ackbij1 8943. (Contributed by Stefan O'Rear, 18-Nov-2014.) |
⊢ 𝐹 = (𝑥 ∈ (𝒫 ω ∩ Fin) ↦ (card‘∪ 𝑦 ∈ 𝑥 ({𝑦} × 𝒫 𝑦))) ⇒ ⊢ (𝐴 ∈ (𝒫 ω ∩ Fin) → ∃𝑏 ∈ (𝒫 ω ∩ Fin)(𝐹‘𝑏) = suc (𝐹‘𝐴)) | ||
Theorem | ackbij1 8943* | The Ackermann bijection, part 1: each natural number can be uniquely coded in binary as a finite set of natural numbers and conversely. (Contributed by Stefan O'Rear, 18-Nov-2014.) |
⊢ 𝐹 = (𝑥 ∈ (𝒫 ω ∩ Fin) ↦ (card‘∪ 𝑦 ∈ 𝑥 ({𝑦} × 𝒫 𝑦))) ⇒ ⊢ 𝐹:(𝒫 ω ∩ Fin)–1-1-onto→ω | ||
Theorem | ackbij1b 8944* | The Ackermann bijection, part 1b: the bijection from ackbij1 8943 restricts naturally to the powers of particular naturals. (Contributed by Stefan O'Rear, 18-Nov-2014.) |
⊢ 𝐹 = (𝑥 ∈ (𝒫 ω ∩ Fin) ↦ (card‘∪ 𝑦 ∈ 𝑥 ({𝑦} × 𝒫 𝑦))) ⇒ ⊢ (𝐴 ∈ ω → (𝐹 “ 𝒫 𝐴) = (card‘𝒫 𝐴)) | ||
Theorem | ackbij2lem2 8945* | Lemma for ackbij2 8948. (Contributed by Stefan O'Rear, 18-Nov-2014.) |
⊢ 𝐹 = (𝑥 ∈ (𝒫 ω ∩ Fin) ↦ (card‘∪ 𝑦 ∈ 𝑥 ({𝑦} × 𝒫 𝑦))) & ⊢ 𝐺 = (𝑥 ∈ V ↦ (𝑦 ∈ 𝒫 dom 𝑥 ↦ (𝐹‘(𝑥 “ 𝑦)))) ⇒ ⊢ (𝐴 ∈ ω → (rec(𝐺, ∅)‘𝐴):(𝑅1‘𝐴)–1-1-onto→(card‘(𝑅1‘𝐴))) | ||
Theorem | ackbij2lem3 8946* | Lemma for ackbij2 8948. (Contributed by Stefan O'Rear, 18-Nov-2014.) |
⊢ 𝐹 = (𝑥 ∈ (𝒫 ω ∩ Fin) ↦ (card‘∪ 𝑦 ∈ 𝑥 ({𝑦} × 𝒫 𝑦))) & ⊢ 𝐺 = (𝑥 ∈ V ↦ (𝑦 ∈ 𝒫 dom 𝑥 ↦ (𝐹‘(𝑥 “ 𝑦)))) ⇒ ⊢ (𝐴 ∈ ω → (rec(𝐺, ∅)‘𝐴) ⊆ (rec(𝐺, ∅)‘suc 𝐴)) | ||
Theorem | ackbij2lem4 8947* | Lemma for ackbij2 8948. (Contributed by Stefan O'Rear, 18-Nov-2014.) |
⊢ 𝐹 = (𝑥 ∈ (𝒫 ω ∩ Fin) ↦ (card‘∪ 𝑦 ∈ 𝑥 ({𝑦} × 𝒫 𝑦))) & ⊢ 𝐺 = (𝑥 ∈ V ↦ (𝑦 ∈ 𝒫 dom 𝑥 ↦ (𝐹‘(𝑥 “ 𝑦)))) ⇒ ⊢ (((𝐴 ∈ ω ∧ 𝐵 ∈ ω) ∧ 𝐵 ⊆ 𝐴) → (rec(𝐺, ∅)‘𝐵) ⊆ (rec(𝐺, ∅)‘𝐴)) | ||
Theorem | ackbij2 8948* | The Ackermann bijection, part 2: hereditarily finite sets can be represented by recursive binary notation. (Contributed by Stefan O'Rear, 18-Nov-2014.) |
⊢ 𝐹 = (𝑥 ∈ (𝒫 ω ∩ Fin) ↦ (card‘∪ 𝑦 ∈ 𝑥 ({𝑦} × 𝒫 𝑦))) & ⊢ 𝐺 = (𝑥 ∈ V ↦ (𝑦 ∈ 𝒫 dom 𝑥 ↦ (𝐹‘(𝑥 “ 𝑦)))) & ⊢ 𝐻 = ∪ (rec(𝐺, ∅) “ ω) ⇒ ⊢ 𝐻:∪ (𝑅1 “ ω)–1-1-onto→ω | ||
Theorem | r1om 8949 | The set of hereditarily finite sets is countable. See ackbij2 8948 for an explicit bijection that works without Infinity. See also r1omALT 9477. (Contributed by Stefan O'Rear, 18-Nov-2014.) |
⊢ (𝑅1‘ω) ≈ ω | ||
Theorem | fictb 8950 | A set is countable iff its collection of finite intersections is countable. (Contributed by Jeff Hankins, 24-Aug-2009.) (Proof shortened by Mario Carneiro, 17-May-2015.) |
⊢ (𝐴 ∈ 𝐵 → (𝐴 ≼ ω ↔ (fi‘𝐴) ≼ ω)) | ||
Theorem | cflem 8951* | A lemma used to simplify cofinality computations, showing the existence of the cardinal of an unbounded subset of a set 𝐴. (Contributed by NM, 24-Apr-2004.) |
⊢ (𝐴 ∈ 𝑉 → ∃𝑥∃𝑦(𝑥 = (card‘𝑦) ∧ (𝑦 ⊆ 𝐴 ∧ ∀𝑧 ∈ 𝐴 ∃𝑤 ∈ 𝑦 𝑧 ⊆ 𝑤))) | ||
Theorem | cfval 8952* | Value of the cofinality function. Definition B of Saharon Shelah, Cardinal Arithmetic (1994), p. xxx (Roman numeral 30). The cofinality of an ordinal number 𝐴 is the cardinality (size) of the smallest unbounded subset 𝑦 of the ordinal number. Unbounded means that for every member of 𝐴, there is a member of 𝑦 that is at least as large. Cofinality is a measure of how "reachable from below" an ordinal is. (Contributed by NM, 1-Apr-2004.) (Revised by Mario Carneiro, 15-Sep-2013.) |
⊢ (𝐴 ∈ On → (cf‘𝐴) = ∩ {𝑥 ∣ ∃𝑦(𝑥 = (card‘𝑦) ∧ (𝑦 ⊆ 𝐴 ∧ ∀𝑧 ∈ 𝐴 ∃𝑤 ∈ 𝑦 𝑧 ⊆ 𝑤))}) | ||
Theorem | cff 8953 | Cofinality is a function on the class of ordinal numbers to the class of cardinal numbers. (Contributed by Mario Carneiro, 15-Sep-2013.) |
⊢ cf:On⟶On | ||
Theorem | cfub 8954* | An upper bound on cofinality. (Contributed by NM, 25-Apr-2004.) (Revised by Mario Carneiro, 15-Sep-2013.) |
⊢ (cf‘𝐴) ⊆ ∩ {𝑥 ∣ ∃𝑦(𝑥 = (card‘𝑦) ∧ (𝑦 ⊆ 𝐴 ∧ 𝐴 ⊆ ∪ 𝑦))} | ||
Theorem | cflm 8955* | Value of the cofinality function at a limit ordinal. Part of Definition of cofinality of [Enderton] p. 257. (Contributed by NM, 26-Apr-2004.) |
⊢ ((𝐴 ∈ 𝐵 ∧ Lim 𝐴) → (cf‘𝐴) = ∩ {𝑥 ∣ ∃𝑦(𝑥 = (card‘𝑦) ∧ (𝑦 ⊆ 𝐴 ∧ 𝐴 = ∪ 𝑦))}) | ||
Theorem | cf0 8956 | Value of the cofinality function at 0. Exercise 2 of [TakeutiZaring] p. 102. (Contributed by NM, 16-Apr-2004.) |
⊢ (cf‘∅) = ∅ | ||
Theorem | cardcf 8957 | Cofinality is a cardinal number. Proposition 11.11 of [TakeutiZaring] p. 103. (Contributed by NM, 24-Apr-2004.) (Revised by Mario Carneiro, 15-Sep-2013.) |
⊢ (card‘(cf‘𝐴)) = (cf‘𝐴) | ||
Theorem | cflecard 8958 | Cofinality is bounded by the cardinality of its argument. (Contributed by NM, 24-Apr-2004.) (Revised by Mario Carneiro, 15-Sep-2013.) |
⊢ (cf‘𝐴) ⊆ (card‘𝐴) | ||
Theorem | cfle 8959 | Cofinality is bounded by its argument. Exercise 1 of [TakeutiZaring] p. 102. (Contributed by NM, 26-Apr-2004.) (Revised by Mario Carneiro, 15-Sep-2013.) |
⊢ (cf‘𝐴) ⊆ 𝐴 | ||
Theorem | cfon 8960 | The cofinality of any set is an ordinal (although it only makes sense when 𝐴 is an ordinal). (Contributed by Mario Carneiro, 9-Mar-2013.) |
⊢ (cf‘𝐴) ∈ On | ||
Theorem | cfeq0 8961 | Only the ordinal zero has cofinality zero. (Contributed by NM, 24-Apr-2004.) (Revised by Mario Carneiro, 12-Feb-2013.) |
⊢ (𝐴 ∈ On → ((cf‘𝐴) = ∅ ↔ 𝐴 = ∅)) | ||
Theorem | cfsuc 8962 | Value of the cofinality function at a successor ordinal. Exercise 3 of [TakeutiZaring] p. 102. (Contributed by NM, 23-Apr-2004.) (Revised by Mario Carneiro, 12-Feb-2013.) |
⊢ (𝐴 ∈ On → (cf‘suc 𝐴) = 1𝑜) | ||
Theorem | cff1 8963* | There is always a map from (cf‘𝐴) to 𝐴 (this is a stronger condition than the definition, which only presupposes a map from some 𝑦 ≈ (cf‘𝐴). (Contributed by Mario Carneiro, 28-Feb-2013.) |
⊢ (𝐴 ∈ On → ∃𝑓(𝑓:(cf‘𝐴)–1-1→𝐴 ∧ ∀𝑧 ∈ 𝐴 ∃𝑤 ∈ (cf‘𝐴)𝑧 ⊆ (𝑓‘𝑤))) | ||
Theorem | cfflb 8964* | If there is a cofinal map from 𝐵 to 𝐴, then 𝐵 is at least (cf‘𝐴). This theorem and cff1 8963 motivate the picture of (cf‘𝐴) as the greatest lower bound of the domain of cofinal maps into 𝐴. (Contributed by Mario Carneiro, 28-Feb-2013.) |
⊢ ((𝐴 ∈ On ∧ 𝐵 ∈ On) → (∃𝑓(𝑓:𝐵⟶𝐴 ∧ ∀𝑧 ∈ 𝐴 ∃𝑤 ∈ 𝐵 𝑧 ⊆ (𝑓‘𝑤)) → (cf‘𝐴) ⊆ 𝐵)) | ||
Theorem | cfval2 8965* | Another expression for the cofinality function. (Contributed by Mario Carneiro, 28-Feb-2013.) |
⊢ (𝐴 ∈ On → (cf‘𝐴) = ∩ 𝑥 ∈ {𝑥 ∈ 𝒫 𝐴 ∣ ∀𝑧 ∈ 𝐴 ∃𝑤 ∈ 𝑥 𝑧 ⊆ 𝑤} (card‘𝑥)) | ||
Theorem | coflim 8966* | A simpler expression for the cofinality predicate, at a limit ordinal. (Contributed by Mario Carneiro, 28-Feb-2013.) |
⊢ ((Lim 𝐴 ∧ 𝐵 ⊆ 𝐴) → (∪ 𝐵 = 𝐴 ↔ ∀𝑥 ∈ 𝐴 ∃𝑦 ∈ 𝐵 𝑥 ⊆ 𝑦)) | ||
Theorem | cflim3 8967* | Another expression for the cofinality function. (Contributed by Mario Carneiro, 28-Feb-2013.) |
⊢ 𝐴 ∈ V ⇒ ⊢ (Lim 𝐴 → (cf‘𝐴) = ∩ 𝑥 ∈ {𝑥 ∈ 𝒫 𝐴 ∣ ∪ 𝑥 = 𝐴} (card‘𝑥)) | ||
Theorem | cflim2 8968 | The cofinality function is a limit ordinal iff its argument is. (Contributed by Mario Carneiro, 28-Feb-2013.) (Revised by Mario Carneiro, 15-Sep-2013.) |
⊢ 𝐴 ∈ V ⇒ ⊢ (Lim 𝐴 ↔ Lim (cf‘𝐴)) | ||
Theorem | cfom 8969 | Value of the cofinality function at omega (the set of natural numbers). Exercise 4 of [TakeutiZaring] p. 102. (Contributed by NM, 23-Apr-2004.) (Proof shortened by Mario Carneiro, 11-Jun-2015.) |
⊢ (cf‘ω) = ω | ||
Theorem | cfss 8970* | There is a cofinal subset of 𝐴 of cardinality (cf‘𝐴). (Contributed by Mario Carneiro, 24-Jun-2013.) |
⊢ 𝐴 ∈ V ⇒ ⊢ (Lim 𝐴 → ∃𝑥(𝑥 ⊆ 𝐴 ∧ 𝑥 ≈ (cf‘𝐴) ∧ ∪ 𝑥 = 𝐴)) | ||
Theorem | cfslb 8971 | Any cofinal subset of 𝐴 is at least as large as (cf‘𝐴). (Contributed by Mario Carneiro, 24-Jun-2013.) |
⊢ 𝐴 ∈ V ⇒ ⊢ ((Lim 𝐴 ∧ 𝐵 ⊆ 𝐴 ∧ ∪ 𝐵 = 𝐴) → (cf‘𝐴) ≼ 𝐵) | ||
Theorem | cfslbn 8972 | Any subset of 𝐴 smaller than its cofinality has union less than 𝐴. (This is the contrapositive to cfslb 8971.) (Contributed by Mario Carneiro, 24-Jun-2013.) |
⊢ 𝐴 ∈ V ⇒ ⊢ ((Lim 𝐴 ∧ 𝐵 ⊆ 𝐴 ∧ 𝐵 ≺ (cf‘𝐴)) → ∪ 𝐵 ∈ 𝐴) | ||
Theorem | cfslb2n 8973* | Any small collection of small subsets of 𝐴 cannot have union 𝐴, where "small" means smaller than the cofinality. This is a stronger version of cfslb 8971. This is a common application of cofinality: under AC, (ℵ‘1) is regular, so it is not a countable union of countable sets. (Contributed by Mario Carneiro, 24-Jun-2013.) |
⊢ 𝐴 ∈ V ⇒ ⊢ ((Lim 𝐴 ∧ ∀𝑥 ∈ 𝐵 (𝑥 ⊆ 𝐴 ∧ 𝑥 ≺ (cf‘𝐴))) → (𝐵 ≺ (cf‘𝐴) → ∪ 𝐵 ≠ 𝐴)) | ||
Theorem | cofsmo 8974* | Any cofinal map implies the existence of a strictly monotone cofinal map with a domain no larger than the original. Proposition 11.7 of [TakeutiZaring] p. 101. (Contributed by Mario Carneiro, 20-Mar-2013.) |
⊢ 𝐶 = {𝑦 ∈ 𝐵 ∣ ∀𝑤 ∈ 𝑦 (𝑓‘𝑤) ∈ (𝑓‘𝑦)} & ⊢ 𝐾 = ∩ {𝑥 ∈ 𝐵 ∣ 𝑧 ⊆ (𝑓‘𝑥)} & ⊢ 𝑂 = OrdIso( E , 𝐶) ⇒ ⊢ ((Ord 𝐴 ∧ 𝐵 ∈ On) → (∃𝑓(𝑓:𝐵⟶𝐴 ∧ ∀𝑧 ∈ 𝐴 ∃𝑤 ∈ 𝐵 𝑧 ⊆ (𝑓‘𝑤)) → ∃𝑥 ∈ suc 𝐵∃𝑔(𝑔:𝑥⟶𝐴 ∧ Smo 𝑔 ∧ ∀𝑧 ∈ 𝐴 ∃𝑣 ∈ 𝑥 𝑧 ⊆ (𝑔‘𝑣)))) | ||
Theorem | cfsmolem 8975* | Lemma for cfsmo 8976. (Contributed by Mario Carneiro, 28-Feb-2013.) |
⊢ 𝐹 = (𝑧 ∈ V ↦ ((𝑔‘dom 𝑧) ∪ ∪ 𝑡 ∈ dom 𝑧 suc (𝑧‘𝑡))) & ⊢ 𝐺 = (recs(𝐹) ↾ (cf‘𝐴)) ⇒ ⊢ (𝐴 ∈ On → ∃𝑓(𝑓:(cf‘𝐴)⟶𝐴 ∧ Smo 𝑓 ∧ ∀𝑧 ∈ 𝐴 ∃𝑤 ∈ (cf‘𝐴)𝑧 ⊆ (𝑓‘𝑤))) | ||
Theorem | cfsmo 8976* | The map in cff1 8963 can be assumed to be a strictly monotone ordinal function without loss of generality. (Contributed by Mario Carneiro, 28-Feb-2013.) |
⊢ (𝐴 ∈ On → ∃𝑓(𝑓:(cf‘𝐴)⟶𝐴 ∧ Smo 𝑓 ∧ ∀𝑧 ∈ 𝐴 ∃𝑤 ∈ (cf‘𝐴)𝑧 ⊆ (𝑓‘𝑤))) | ||
Theorem | cfcoflem 8977* | Lemma for cfcof 8979, showing subset relation in one direction. (Contributed by Mario Carneiro, 9-Mar-2013.) (Revised by Mario Carneiro, 26-Dec-2014.) |
⊢ ((𝐴 ∈ On ∧ 𝐵 ∈ On) → (∃𝑓(𝑓:𝐵⟶𝐴 ∧ Smo 𝑓 ∧ ∀𝑥 ∈ 𝐴 ∃𝑦 ∈ 𝐵 𝑥 ⊆ (𝑓‘𝑦)) → (cf‘𝐴) ⊆ (cf‘𝐵))) | ||
Theorem | coftr 8978* | If there is a cofinal map from 𝐵 to 𝐴 and another from 𝐶 to 𝐴, then there is also a cofinal map from 𝐶 to 𝐵. Proposition 11.9 of [TakeutiZaring] p. 102. A limited form of transitivity for the "cof" relation. This is really a lemma for cfcof 8979. (Contributed by Mario Carneiro, 16-Mar-2013.) |
⊢ 𝐻 = (𝑡 ∈ 𝐶 ↦ ∩ {𝑛 ∈ 𝐵 ∣ (𝑔‘𝑡) ⊆ (𝑓‘𝑛)}) ⇒ ⊢ (∃𝑓(𝑓:𝐵⟶𝐴 ∧ Smo 𝑓 ∧ ∀𝑥 ∈ 𝐴 ∃𝑦 ∈ 𝐵 𝑥 ⊆ (𝑓‘𝑦)) → (∃𝑔(𝑔:𝐶⟶𝐴 ∧ ∀𝑧 ∈ 𝐴 ∃𝑤 ∈ 𝐶 𝑧 ⊆ (𝑔‘𝑤)) → ∃ℎ(ℎ:𝐶⟶𝐵 ∧ ∀𝑠 ∈ 𝐵 ∃𝑤 ∈ 𝐶 𝑠 ⊆ (ℎ‘𝑤)))) | ||
Theorem | cfcof 8979* | If there is a cofinal map from 𝐴 to 𝐵, then they have the same cofinality. This was used as Definition 11.1 of [TakeutiZaring] p. 100, who defines an equivalence relation cof (𝐴, 𝐵) and defines our cf(𝐵) as the minimum 𝐵 such that cof (𝐴, 𝐵). (Contributed by Mario Carneiro, 20-Mar-2013.) |
⊢ ((𝐴 ∈ On ∧ 𝐵 ∈ On) → (∃𝑓(𝑓:𝐵⟶𝐴 ∧ Smo 𝑓 ∧ ∀𝑧 ∈ 𝐴 ∃𝑤 ∈ 𝐵 𝑧 ⊆ (𝑓‘𝑤)) → (cf‘𝐴) = (cf‘𝐵))) | ||
Theorem | cfidm 8980 | The cofinality function is idempotent. (Contributed by Mario Carneiro, 7-Mar-2013.) (Revised by Mario Carneiro, 15-Sep-2013.) |
⊢ (cf‘(cf‘𝐴)) = (cf‘𝐴) | ||
Theorem | alephsing 8981 | The cofinality of a limit aleph is the same as the cofinality of its argument, so if (ℵ‘𝐴) < 𝐴, then (ℵ‘𝐴) is singular. Conversely, if (ℵ‘𝐴) is regular (i.e. weakly inaccessible), then (ℵ‘𝐴) = 𝐴, so 𝐴 has to be rather large (see alephfp 8814). Proposition 11.13 of [TakeutiZaring] p. 103. (Contributed by Mario Carneiro, 9-Mar-2013.) |
⊢ (Lim 𝐴 → (cf‘(ℵ‘𝐴)) = (cf‘𝐴)) | ||
Theorem | sornom 8982* | The range of a single-step monotone function from ω into a partially ordered set is a chain. (Contributed by Stefan O'Rear, 3-Nov-2014.) |
⊢ ((𝐹 Fn ω ∧ ∀𝑎 ∈ ω ((𝐹‘𝑎)𝑅(𝐹‘suc 𝑎) ∨ (𝐹‘𝑎) = (𝐹‘suc 𝑎)) ∧ 𝑅 Po ran 𝐹) → 𝑅 Or ran 𝐹) | ||
Syntax | cfin1a 8983 | Extend class notation to include the class of Ia-finite sets. |
class FinIa | ||
Syntax | cfin2 8984 | Extend class notation to include the class of II-finite sets. |
class FinII | ||
Syntax | cfin4 8985 | Extend class notation to include the class of IV-finite sets. |
class FinIV | ||
Syntax | cfin3 8986 | Extend class notation to include the class of III-finite sets. |
class FinIII | ||
Syntax | cfin5 8987 | Extend class notation to include the class of V-finite sets. |
class FinV | ||
Syntax | cfin6 8988 | Extend class notation to include the class of VI-finite sets. |
class FinVI | ||
Syntax | cfin7 8989 | Extend class notation to include the class of VII-finite sets. |
class FinVII | ||
Definition | df-fin1a 8990* | A set is Ia-finite iff it is not the union of two I-infinite sets. Equivalent to definition Ia of [Levy58] p. 2. A I-infinite Ia-finite set is also known as an amorphous set. This is the second of Levy's eight definitions of finite set. Levy's I-finite is equivalent to our df-fin 7845 and not repeated here. These eight definitions are equivalent with Choice but strictly decreasing in strength in models where Choice fails; conversely, they provide a series of increasingly stronger notions of infiniteness. (Contributed by Stefan O'Rear, 12-Nov-2014.) |
⊢ FinIa = {𝑥 ∣ ∀𝑦 ∈ 𝒫 𝑥(𝑦 ∈ Fin ∨ (𝑥 ∖ 𝑦) ∈ Fin)} | ||
Definition | df-fin2 8991* | A set is II-finite (Tarski finite) iff every nonempty chain of subsets contains a maximum element. Definition II of [Levy58] p. 2. (Contributed by Stefan O'Rear, 12-Nov-2014.) |
⊢ FinII = {𝑥 ∣ ∀𝑦 ∈ 𝒫 𝒫 𝑥((𝑦 ≠ ∅ ∧ [⊊] Or 𝑦) → ∪ 𝑦 ∈ 𝑦)} | ||
Definition | df-fin4 8992* | A set is IV-finite (Dedekind finite) iff it has no equinumerous proper subset. Definition IV of [Levy58] p. 3. (Contributed by Stefan O'Rear, 12-Nov-2014.) |
⊢ FinIV = {𝑥 ∣ ¬ ∃𝑦(𝑦 ⊊ 𝑥 ∧ 𝑦 ≈ 𝑥)} | ||
Definition | df-fin3 8993 | A set is III-finite (weakly Dedekind finite) iff its power set is Dedekind finite. Definition III of [Levy58] p. 2. (Contributed by Stefan O'Rear, 12-Nov-2014.) |
⊢ FinIII = {𝑥 ∣ 𝒫 𝑥 ∈ FinIV} | ||
Definition | df-fin5 8994 | A set is V-finite iff it behaves finitely under +𝑐. Definition V of [Levy58] p. 3. (Contributed by Stefan O'Rear, 12-Nov-2014.) |
⊢ FinV = {𝑥 ∣ (𝑥 = ∅ ∨ 𝑥 ≺ (𝑥 +𝑐 𝑥))} | ||
Definition | df-fin6 8995 | A set is VI-finite iff it behaves finitely under ×. Definition VI of [Levy58] p. 4. (Contributed by Stefan O'Rear, 12-Nov-2014.) |
⊢ FinVI = {𝑥 ∣ (𝑥 ≺ 2𝑜 ∨ 𝑥 ≺ (𝑥 × 𝑥))} | ||
Definition | df-fin7 8996* | A set is VII-finite iff it cannot be infinitely well-ordered. Equivalent to definition VII of [Levy58] p. 4. (Contributed by Stefan O'Rear, 12-Nov-2014.) |
⊢ FinVII = {𝑥 ∣ ¬ ∃𝑦 ∈ (On ∖ ω)𝑥 ≈ 𝑦} | ||
Theorem | isfin1a 8997* | Definition of a Ia-finite set. (Contributed by Stefan O'Rear, 16-May-2015.) |
⊢ (𝐴 ∈ 𝑉 → (𝐴 ∈ FinIa ↔ ∀𝑦 ∈ 𝒫 𝐴(𝑦 ∈ Fin ∨ (𝐴 ∖ 𝑦) ∈ Fin))) | ||
Theorem | fin1ai 8998 | Property of a Ia-finite set. (Contributed by Stefan O'Rear, 16-May-2015.) |
⊢ ((𝐴 ∈ FinIa ∧ 𝑋 ⊆ 𝐴) → (𝑋 ∈ Fin ∨ (𝐴 ∖ 𝑋) ∈ Fin)) | ||
Theorem | isfin2 8999* | Definition of a II-finite set. (Contributed by Stefan O'Rear, 16-May-2015.) |
⊢ (𝐴 ∈ 𝑉 → (𝐴 ∈ FinII ↔ ∀𝑦 ∈ 𝒫 𝒫 𝐴((𝑦 ≠ ∅ ∧ [⊊] Or 𝑦) → ∪ 𝑦 ∈ 𝑦))) | ||
Theorem | fin2i 9000 | Property of a II-finite set. (Contributed by Stefan O'Rear, 16-May-2015.) |
⊢ (((𝐴 ∈ FinII ∧ 𝐵 ⊆ 𝒫 𝐴) ∧ (𝐵 ≠ ∅ ∧ [⊊] Or 𝐵)) → ∪ 𝐵 ∈ 𝐵) |
< Previous Next > |
Copyright terms: Public domain | < Previous Next > |