P. 100 of Theorem List - Metamath Proof Explorer

Theorem List for Metamath Proof Explorer - 9901-10000   *Has distinct variable group(s)

Type	Label	Description
Statement
Theorem	infunsdom 9901	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 9902	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	pwdjudom 9903	A property of dominance over a powerset, and a main lemma for gchac 10368. Similar to Lemma 2.3 of [KanamoriPincus] p. 420. (Contributed by Mario Carneiro, 15-May-2015.)
⊢ (𝒫 (𝐴 ⊔ 𝐴) ≼ (𝐴 ⊔ 𝐵) → 𝒫 𝐴 ≼ 𝐵)
Theorem	infpss 9904*	Every infinite set has an equinumerous proper subset, proved without AC or Infinity. Exercise 7 of [TakeutiZaring] p. 91. See also infpssALT 10000. (Contributed by NM, 23-Oct-2004.) (Revised by Mario Carneiro, 30-Apr-2015.)
⊢ (ω ≼ 𝐴 → ∃𝑥(𝑥 ⊊ 𝐴 ∧ 𝑥 ≈ 𝐴))
Theorem	infmap2 9905*	An exponentiation law for infinite cardinals. Similar to Lemma 6.2 of [Jech] p. 43. Although this version of infmap 10263 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.)
⊢ ((ω ≼ 𝐴 ∧ 𝐵 ≼ 𝐴 ∧ (𝐴 ↑m 𝐵) ∈ dom card) → (𝐴 ↑m 𝐵) ≈ {𝑥 ∣ (𝑥 ⊆ 𝐴 ∧ 𝑥 ≈ 𝐵)})
2.6.14  The Ackermann bijection
Theorem	ackbij2lem1 9906	Lemma for ackbij2 9930. (Contributed by Stefan O'Rear, 18-Nov-2014.)
⊢ (𝐴 ∈ ω → 𝒫 𝐴 ⊆ (𝒫 ω ∩ Fin))
Theorem	ackbij1lem1 9907	Lemma for ackbij2 9930. (Contributed by Stefan O'Rear, 18-Nov-2014.)
⊢ (¬ 𝐴 ∈ 𝐵 → (𝐵 ∩ suc 𝐴) = (𝐵 ∩ 𝐴))
Theorem	ackbij1lem2 9908	Lemma for ackbij2 9930. (Contributed by Stefan O'Rear, 18-Nov-2014.)
⊢ (𝐴 ∈ 𝐵 → (𝐵 ∩ suc 𝐴) = ({𝐴} ∪ (𝐵 ∩ 𝐴)))
Theorem	ackbij1lem3 9909	Lemma for ackbij2 9930. (Contributed by Stefan O'Rear, 18-Nov-2014.)
⊢ (𝐴 ∈ ω → 𝐴 ∈ (𝒫 ω ∩ Fin))
Theorem	ackbij1lem4 9910	Lemma for ackbij2 9930. (Contributed by Stefan O'Rear, 19-Nov-2014.)
⊢ (𝐴 ∈ ω → {𝐴} ∈ (𝒫 ω ∩ Fin))
Theorem	ackbij1lem5 9911	Lemma for ackbij2 9930. (Contributed by Stefan O'Rear, 19-Nov-2014.) (Proof shortened by AV, 18-Jul-2022.)
⊢ (𝐴 ∈ ω → (card‘𝒫 suc 𝐴) = ((card‘𝒫 𝐴) +o (card‘𝒫 𝐴)))
Theorem	ackbij1lem6 9912	Lemma for ackbij2 9930. (Contributed by Stefan O'Rear, 18-Nov-2014.)
⊢ ((𝐴 ∈ (𝒫 ω ∩ Fin) ∧ 𝐵 ∈ (𝒫 ω ∩ Fin)) → (𝐴 ∪ 𝐵) ∈ (𝒫 ω ∩ Fin))
Theorem	ackbij1lem7 9913*	Lemma for ackbij1 9925. (Contributed by Stefan O'Rear, 21-Nov-2014.)
⊢ 𝐹 = (𝑥 ∈ (𝒫 ω ∩ Fin) ↦ (card‘∪ 𝑦 ∈ 𝑥 ({𝑦} × 𝒫 𝑦)))    ⇒   ⊢ (𝐴 ∈ (𝒫 ω ∩ Fin) → (𝐹‘𝐴) = (card‘∪ 𝑦 ∈ 𝐴 ({𝑦} × 𝒫 𝑦)))
Theorem	ackbij1lem8 9914*	Lemma for ackbij1 9925. (Contributed by Stefan O'Rear, 19-Nov-2014.)
⊢ 𝐹 = (𝑥 ∈ (𝒫 ω ∩ Fin) ↦ (card‘∪ 𝑦 ∈ 𝑥 ({𝑦} × 𝒫 𝑦)))    ⇒   ⊢ (𝐴 ∈ ω → (𝐹‘{𝐴}) = (card‘𝒫 𝐴))
Theorem	ackbij1lem9 9915*	Lemma for ackbij1 9925. (Contributed by Stefan O'Rear, 19-Nov-2014.)
⊢ 𝐹 = (𝑥 ∈ (𝒫 ω ∩ Fin) ↦ (card‘∪ 𝑦 ∈ 𝑥 ({𝑦} × 𝒫 𝑦)))    ⇒   ⊢ ((𝐴 ∈ (𝒫 ω ∩ Fin) ∧ 𝐵 ∈ (𝒫 ω ∩ Fin) ∧ (𝐴 ∩ 𝐵) = ∅) → (𝐹‘(𝐴 ∪ 𝐵)) = ((𝐹‘𝐴) +o (𝐹‘𝐵)))
Theorem	ackbij1lem10 9916*	Lemma for ackbij1 9925. (Contributed by Stefan O'Rear, 18-Nov-2014.)
⊢ 𝐹 = (𝑥 ∈ (𝒫 ω ∩ Fin) ↦ (card‘∪ 𝑦 ∈ 𝑥 ({𝑦} × 𝒫 𝑦)))    ⇒   ⊢ 𝐹:(𝒫 ω ∩ Fin)⟶ω
Theorem	ackbij1lem11 9917*	Lemma for ackbij1 9925. (Contributed by Stefan O'Rear, 18-Nov-2014.)
⊢ 𝐹 = (𝑥 ∈ (𝒫 ω ∩ Fin) ↦ (card‘∪ 𝑦 ∈ 𝑥 ({𝑦} × 𝒫 𝑦)))    ⇒   ⊢ ((𝐴 ∈ (𝒫 ω ∩ Fin) ∧ 𝐵 ⊆ 𝐴) → 𝐵 ∈ (𝒫 ω ∩ Fin))
Theorem	ackbij1lem12 9918*	Lemma for ackbij1 9925. (Contributed by Stefan O'Rear, 18-Nov-2014.)
⊢ 𝐹 = (𝑥 ∈ (𝒫 ω ∩ Fin) ↦ (card‘∪ 𝑦 ∈ 𝑥 ({𝑦} × 𝒫 𝑦)))    ⇒   ⊢ ((𝐵 ∈ (𝒫 ω ∩ Fin) ∧ 𝐴 ⊆ 𝐵) → (𝐹‘𝐴) ⊆ (𝐹‘𝐵))
Theorem	ackbij1lem13 9919*	Lemma for ackbij1 9925. (Contributed by Stefan O'Rear, 18-Nov-2014.)
⊢ 𝐹 = (𝑥 ∈ (𝒫 ω ∩ Fin) ↦ (card‘∪ 𝑦 ∈ 𝑥 ({𝑦} × 𝒫 𝑦)))    ⇒   ⊢ (𝐹‘∅) = ∅
Theorem	ackbij1lem14 9920*	Lemma for ackbij1 9925. (Contributed by Stefan O'Rear, 18-Nov-2014.)
⊢ 𝐹 = (𝑥 ∈ (𝒫 ω ∩ Fin) ↦ (card‘∪ 𝑦 ∈ 𝑥 ({𝑦} × 𝒫 𝑦)))    ⇒   ⊢ (𝐴 ∈ ω → (𝐹‘{𝐴}) = suc (𝐹‘𝐴))
Theorem	ackbij1lem15 9921*	Lemma for ackbij1 9925. (Contributed by Stefan O'Rear, 18-Nov-2014.)
⊢ 𝐹 = (𝑥 ∈ (𝒫 ω ∩ Fin) ↦ (card‘∪ 𝑦 ∈ 𝑥 ({𝑦} × 𝒫 𝑦)))    ⇒   ⊢ (((𝐴 ∈ (𝒫 ω ∩ Fin) ∧ 𝐵 ∈ (𝒫 ω ∩ Fin)) ∧ (𝑐 ∈ ω ∧ 𝑐 ∈ 𝐴 ∧ ¬ 𝑐 ∈ 𝐵)) → ¬ (𝐹‘(𝐴 ∩ suc 𝑐)) = (𝐹‘(𝐵 ∩ suc 𝑐)))
Theorem	ackbij1lem16 9922*	Lemma for ackbij1 9925. (Contributed by Stefan O'Rear, 18-Nov-2014.)
⊢ 𝐹 = (𝑥 ∈ (𝒫 ω ∩ Fin) ↦ (card‘∪ 𝑦 ∈ 𝑥 ({𝑦} × 𝒫 𝑦)))    ⇒   ⊢ ((𝐴 ∈ (𝒫 ω ∩ Fin) ∧ 𝐵 ∈ (𝒫 ω ∩ Fin)) → ((𝐹‘𝐴) = (𝐹‘𝐵) → 𝐴 = 𝐵))
Theorem	ackbij1lem17 9923*	Lemma for ackbij1 9925. (Contributed by Stefan O'Rear, 18-Nov-2014.)
⊢ 𝐹 = (𝑥 ∈ (𝒫 ω ∩ Fin) ↦ (card‘∪ 𝑦 ∈ 𝑥 ({𝑦} × 𝒫 𝑦)))    ⇒   ⊢ 𝐹:(𝒫 ω ∩ Fin)–1-1→ω
Theorem	ackbij1lem18 9924*	Lemma for ackbij1 9925. (Contributed by Stefan O'Rear, 18-Nov-2014.)
⊢ 𝐹 = (𝑥 ∈ (𝒫 ω ∩ Fin) ↦ (card‘∪ 𝑦 ∈ 𝑥 ({𝑦} × 𝒫 𝑦)))    ⇒   ⊢ (𝐴 ∈ (𝒫 ω ∩ Fin) → ∃𝑏 ∈ (𝒫 ω ∩ Fin)(𝐹‘𝑏) = suc (𝐹‘𝐴))
Theorem	ackbij1 9925*	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 9926*	The Ackermann bijection, part 1b: the bijection from ackbij1 9925 restricts naturally to the powers of particular naturals. (Contributed by Stefan O'Rear, 18-Nov-2014.)
⊢ 𝐹 = (𝑥 ∈ (𝒫 ω ∩ Fin) ↦ (card‘∪ 𝑦 ∈ 𝑥 ({𝑦} × 𝒫 𝑦)))    ⇒   ⊢ (𝐴 ∈ ω → (𝐹 “ 𝒫 𝐴) = (card‘𝒫 𝐴))
Theorem	ackbij2lem2 9927*	Lemma for ackbij2 9930. (Contributed by Stefan O'Rear, 18-Nov-2014.)
⊢ 𝐹 = (𝑥 ∈ (𝒫 ω ∩ Fin) ↦ (card‘∪ 𝑦 ∈ 𝑥 ({𝑦} × 𝒫 𝑦)))    &   ⊢ 𝐺 = (𝑥 ∈ V ↦ (𝑦 ∈ 𝒫 dom 𝑥 ↦ (𝐹‘(𝑥 “ 𝑦))))    ⇒   ⊢ (𝐴 ∈ ω → (rec(𝐺, ∅)‘𝐴):(𝑅1‘𝐴)–1-1-onto→(card‘(𝑅1‘𝐴)))
Theorem	ackbij2lem3 9928*	Lemma for ackbij2 9930. (Contributed by Stefan O'Rear, 18-Nov-2014.)
⊢ 𝐹 = (𝑥 ∈ (𝒫 ω ∩ Fin) ↦ (card‘∪ 𝑦 ∈ 𝑥 ({𝑦} × 𝒫 𝑦)))    &   ⊢ 𝐺 = (𝑥 ∈ V ↦ (𝑦 ∈ 𝒫 dom 𝑥 ↦ (𝐹‘(𝑥 “ 𝑦))))    ⇒   ⊢ (𝐴 ∈ ω → (rec(𝐺, ∅)‘𝐴) ⊆ (rec(𝐺, ∅)‘suc 𝐴))
Theorem	ackbij2lem4 9929*	Lemma for ackbij2 9930. (Contributed by Stefan O'Rear, 18-Nov-2014.)
⊢ 𝐹 = (𝑥 ∈ (𝒫 ω ∩ Fin) ↦ (card‘∪ 𝑦 ∈ 𝑥 ({𝑦} × 𝒫 𝑦)))    &   ⊢ 𝐺 = (𝑥 ∈ V ↦ (𝑦 ∈ 𝒫 dom 𝑥 ↦ (𝐹‘(𝑥 “ 𝑦))))    ⇒   ⊢ (((𝐴 ∈ ω ∧ 𝐵 ∈ ω) ∧ 𝐵 ⊆ 𝐴) → (rec(𝐺, ∅)‘𝐵) ⊆ (rec(𝐺, ∅)‘𝐴))
Theorem	ackbij2 9930*	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 9931	The set of hereditarily finite sets is countable. See ackbij2 9930 for an explicit bijection that works without Infinity. See also r1omALT 10463. (Contributed by Stefan O'Rear, 18-Nov-2014.)
⊢ (𝑅1‘ω) ≈ ω
Theorem	fictb 9932	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‘𝐴) ≼ ω))
2.6.15  Cofinality (without Axiom of Choice)
Theorem	cflem 9933*	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 9934*	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 9935	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 9936*	An upper bound on cofinality. (Contributed by NM, 25-Apr-2004.) (Revised by Mario Carneiro, 15-Sep-2013.)
⊢ (cf‘𝐴) ⊆ ∩ {𝑥 ∣ ∃𝑦(𝑥 = (card‘𝑦) ∧ (𝑦 ⊆ 𝐴 ∧ 𝐴 ⊆ ∪ 𝑦))}
Theorem	cflm 9937*	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 9938	Value of the cofinality function at 0. Exercise 2 of [TakeutiZaring] p. 102. (Contributed by NM, 16-Apr-2004.)
⊢ (cf‘∅) = ∅
Theorem	cardcf 9939	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 9940	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 9941	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 9942	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 9943	Only the ordinal zero has cofinality zero. (Contributed by NM, 24-Apr-2004.) (Revised by Mario Carneiro, 12-Feb-2013.)
⊢ (𝐴 ∈ On → ((cf‘𝐴) = ∅ ↔ 𝐴 = ∅))
Theorem	cfsuc 9944	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 𝐴) = 1o)
Theorem	cff1 9945*	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 9946*	If there is a cofinal map from 𝐵 to 𝐴, then 𝐵 is at least (cf‘𝐴). This theorem and cff1 9945 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 9947*	Another expression for the cofinality function. (Contributed by Mario Carneiro, 28-Feb-2013.)
⊢ (𝐴 ∈ On → (cf‘𝐴) = ∩ 𝑥 ∈ {𝑥 ∈ 𝒫 𝐴 ∣ ∀𝑧 ∈ 𝐴 ∃𝑤 ∈ 𝑥 𝑧 ⊆ 𝑤} (card‘𝑥))
Theorem	coflim 9948*	A simpler expression for the cofinality predicate, at a limit ordinal. (Contributed by Mario Carneiro, 28-Feb-2013.)
⊢ ((Lim 𝐴 ∧ 𝐵 ⊆ 𝐴) → (∪ 𝐵 = 𝐴 ↔ ∀𝑥 ∈ 𝐴 ∃𝑦 ∈ 𝐵 𝑥 ⊆ 𝑦))
Theorem	cflim3 9949*	Another expression for the cofinality function. (Contributed by Mario Carneiro, 28-Feb-2013.)
⊢ 𝐴 ∈ V    ⇒   ⊢ (Lim 𝐴 → (cf‘𝐴) = ∩ 𝑥 ∈ {𝑥 ∈ 𝒫 𝐴 ∣ ∪ 𝑥 = 𝐴} (card‘𝑥))
Theorem	cflim2 9950	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 9951	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 9952*	There is a cofinal subset of 𝐴 of cardinality (cf‘𝐴). (Contributed by Mario Carneiro, 24-Jun-2013.)
⊢ 𝐴 ∈ V    ⇒   ⊢ (Lim 𝐴 → ∃𝑥(𝑥 ⊆ 𝐴 ∧ 𝑥 ≈ (cf‘𝐴) ∧ ∪ 𝑥 = 𝐴))
Theorem	cfslb 9953	Any cofinal subset of 𝐴 is at least as large as (cf‘𝐴). (Contributed by Mario Carneiro, 24-Jun-2013.)
⊢ 𝐴 ∈ V    ⇒   ⊢ ((Lim 𝐴 ∧ 𝐵 ⊆ 𝐴 ∧ ∪ 𝐵 = 𝐴) → (cf‘𝐴) ≼ 𝐵)
Theorem	cfslbn 9954	Any subset of 𝐴 smaller than its cofinality has union less than 𝐴. (This is the contrapositive to cfslb 9953.) (Contributed by Mario Carneiro, 24-Jun-2013.)
⊢ 𝐴 ∈ V    ⇒   ⊢ ((Lim 𝐴 ∧ 𝐵 ⊆ 𝐴 ∧ 𝐵 ≺ (cf‘𝐴)) → ∪ 𝐵 ∈ 𝐴)
Theorem	cfslb2n 9955*	Any small collection of small subsets of 𝐴 cannot have union 𝐴, where "small" means smaller than the cofinality. This is a stronger version of cfslb 9953. 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 9956*	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 9957*	Lemma for cfsmo 9958. (Contributed by Mario Carneiro, 28-Feb-2013.)
⊢ 𝐹 = (𝑧 ∈ V ↦ ((𝑔‘dom 𝑧) ∪ ∪ 𝑡 ∈ dom 𝑧 suc (𝑧‘𝑡)))    &   ⊢ 𝐺 = (recs(𝐹) ↾ (cf‘𝐴))    ⇒   ⊢ (𝐴 ∈ On → ∃𝑓(𝑓:(cf‘𝐴)⟶𝐴 ∧ Smo 𝑓 ∧ ∀𝑧 ∈ 𝐴 ∃𝑤 ∈ (cf‘𝐴)𝑧 ⊆ (𝑓‘𝑤)))
Theorem	cfsmo 9958*	The map in cff1 9945 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 9959*	Lemma for cfcof 9961, 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 9960*	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 9961. (Contributed by Mario Carneiro, 16-Mar-2013.)
⊢ 𝐻 = (𝑡 ∈ 𝐶 ↦ ∩ {𝑛 ∈ 𝐵 ∣ (𝑔‘𝑡) ⊆ (𝑓‘𝑛)})    ⇒   ⊢ (∃𝑓(𝑓:𝐵⟶𝐴 ∧ Smo 𝑓 ∧ ∀𝑥 ∈ 𝐴 ∃𝑦 ∈ 𝐵 𝑥 ⊆ (𝑓‘𝑦)) → (∃𝑔(𝑔:𝐶⟶𝐴 ∧ ∀𝑧 ∈ 𝐴 ∃𝑤 ∈ 𝐶 𝑧 ⊆ (𝑔‘𝑤)) → ∃ℎ(ℎ:𝐶⟶𝐵 ∧ ∀𝑠 ∈ 𝐵 ∃𝑤 ∈ 𝐶 𝑠 ⊆ (ℎ‘𝑤))))
Theorem	cfcof 9961*	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 9962	The cofinality function is idempotent. (Contributed by Mario Carneiro, 7-Mar-2013.) (Revised by Mario Carneiro, 15-Sep-2013.)
⊢ (cf‘(cf‘𝐴)) = (cf‘𝐴)
Theorem	alephsing 9963	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 9795). Proposition 11.13 of [TakeutiZaring] p. 103. (Contributed by Mario Carneiro, 9-Mar-2013.)
⊢ (Lim 𝐴 → (cf‘(ℵ‘𝐴)) = (cf‘𝐴))
2.6.16  Eight inequivalent definitions of finite set
Theorem	sornom 9964*	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 9965	Extend class notation to include the class of Ia-finite sets.
class FinIa
Syntax	cfin2 9966	Extend class notation to include the class of II-finite sets.
class FinII
Syntax	cfin4 9967	Extend class notation to include the class of IV-finite sets.
class FinIV
Syntax	cfin3 9968	Extend class notation to include the class of III-finite sets.
class FinIII
Syntax	cfin5 9969	Extend class notation to include the class of V-finite sets.
class FinV
Syntax	cfin6 9970	Extend class notation to include the class of VI-finite sets.
class FinVI
Syntax	cfin7 9971	Extend class notation to include the class of VII-finite sets.
class FinVII
Definition	df-fin1a 9972*	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 8695 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 9973*	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 9974*	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 9975	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 9976	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 9977	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 = {𝑥 ∣ (𝑥 ≺ 2o ∨ 𝑥 ≺ (𝑥 × 𝑥))}
Definition	df-fin7 9978*	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 9979*	Definition of a Ia-finite set. (Contributed by Stefan O'Rear, 16-May-2015.)
⊢ (𝐴 ∈ 𝑉 → (𝐴 ∈ FinIa ↔ ∀𝑦 ∈ 𝒫 𝐴(𝑦 ∈ Fin ∨ (𝐴 ∖ 𝑦) ∈ Fin)))
Theorem	fin1ai 9980	Property of a Ia-finite set. (Contributed by Stefan O'Rear, 16-May-2015.)
⊢ ((𝐴 ∈ FinIa ∧ 𝑋 ⊆ 𝐴) → (𝑋 ∈ Fin ∨ (𝐴 ∖ 𝑋) ∈ Fin))
Theorem	isfin2 9981*	Definition of a II-finite set. (Contributed by Stefan O'Rear, 16-May-2015.)
⊢ (𝐴 ∈ 𝑉 → (𝐴 ∈ FinII ↔ ∀𝑦 ∈ 𝒫 𝒫 𝐴((𝑦 ≠ ∅ ∧ [⊊] Or 𝑦) → ∪ 𝑦 ∈ 𝑦)))
Theorem	fin2i 9982	Property of a II-finite set. (Contributed by Stefan O'Rear, 16-May-2015.)
⊢ (((𝐴 ∈ FinII ∧ 𝐵 ⊆ 𝒫 𝐴) ∧ (𝐵 ≠ ∅ ∧ [⊊] Or 𝐵)) → ∪ 𝐵 ∈ 𝐵)
Theorem	isfin3 9983	Definition of a III-finite set. (Contributed by Stefan O'Rear, 16-May-2015.)
⊢ (𝐴 ∈ FinIII ↔ 𝒫 𝐴 ∈ FinIV)
Theorem	isfin4 9984*	Definition of a IV-finite set. (Contributed by Stefan O'Rear, 16-May-2015.)
⊢ (𝐴 ∈ 𝑉 → (𝐴 ∈ FinIV ↔ ¬ ∃𝑦(𝑦 ⊊ 𝐴 ∧ 𝑦 ≈ 𝐴)))
Theorem	fin4i 9985	Infer that a set is IV-infinite. (Contributed by Stefan O'Rear, 16-May-2015.)
⊢ ((𝑋 ⊊ 𝐴 ∧ 𝑋 ≈ 𝐴) → ¬ 𝐴 ∈ FinIV)
Theorem	isfin5 9986	Definition of a V-finite set. (Contributed by Stefan O'Rear, 16-May-2015.)
⊢ (𝐴 ∈ FinV ↔ (𝐴 = ∅ ∨ 𝐴 ≺ (𝐴 ⊔ 𝐴)))
Theorem	isfin6 9987	Definition of a VI-finite set. (Contributed by Stefan O'Rear, 16-May-2015.)
⊢ (𝐴 ∈ FinVI ↔ (𝐴 ≺ 2o ∨ 𝐴 ≺ (𝐴 × 𝐴)))
Theorem	isfin7 9988*	Definition of a VII-finite set. (Contributed by Stefan O'Rear, 16-May-2015.)
⊢ (𝐴 ∈ 𝑉 → (𝐴 ∈ FinVII ↔ ¬ ∃𝑦 ∈ (On ∖ ω)𝐴 ≈ 𝑦))
Theorem	sdom2en01 9989	A set with less than two elements has 0 or 1. (Contributed by Stefan O'Rear, 30-Oct-2014.)
⊢ (𝐴 ≺ 2o ↔ (𝐴 = ∅ ∨ 𝐴 ≈ 1o))
Theorem	infpssrlem1 9990	Lemma for infpssr 9995. (Contributed by Stefan O'Rear, 30-Oct-2014.)
⊢ (𝜑 → 𝐵 ⊆ 𝐴)    &   ⊢ (𝜑 → 𝐹:𝐵–1-1-onto→𝐴)    &   ⊢ (𝜑 → 𝐶 ∈ (𝐴 ∖ 𝐵))    &   ⊢ 𝐺 = (rec(◡𝐹, 𝐶) ↾ ω)    ⇒   ⊢ (𝜑 → (𝐺‘∅) = 𝐶)
Theorem	infpssrlem2 9991	Lemma for infpssr 9995. (Contributed by Stefan O'Rear, 30-Oct-2014.)
⊢ (𝜑 → 𝐵 ⊆ 𝐴)    &   ⊢ (𝜑 → 𝐹:𝐵–1-1-onto→𝐴)    &   ⊢ (𝜑 → 𝐶 ∈ (𝐴 ∖ 𝐵))    &   ⊢ 𝐺 = (rec(◡𝐹, 𝐶) ↾ ω)    ⇒   ⊢ (𝑀 ∈ ω → (𝐺‘suc 𝑀) = (◡𝐹‘(𝐺‘𝑀)))
Theorem	infpssrlem3 9992	Lemma for infpssr 9995. (Contributed by Stefan O'Rear, 30-Oct-2014.)
⊢ (𝜑 → 𝐵 ⊆ 𝐴)    &   ⊢ (𝜑 → 𝐹:𝐵–1-1-onto→𝐴)    &   ⊢ (𝜑 → 𝐶 ∈ (𝐴 ∖ 𝐵))    &   ⊢ 𝐺 = (rec(◡𝐹, 𝐶) ↾ ω)    ⇒   ⊢ (𝜑 → 𝐺:ω⟶𝐴)
Theorem	infpssrlem4 9993	Lemma for infpssr 9995. (Contributed by Stefan O'Rear, 30-Oct-2014.)
⊢ (𝜑 → 𝐵 ⊆ 𝐴)    &   ⊢ (𝜑 → 𝐹:𝐵–1-1-onto→𝐴)    &   ⊢ (𝜑 → 𝐶 ∈ (𝐴 ∖ 𝐵))    &   ⊢ 𝐺 = (rec(◡𝐹, 𝐶) ↾ ω)    ⇒   ⊢ ((𝜑 ∧ 𝑀 ∈ ω ∧ 𝑁 ∈ 𝑀) → (𝐺‘𝑀) ≠ (𝐺‘𝑁))
Theorem	infpssrlem5 9994	Lemma for infpssr 9995. (Contributed by Stefan O'Rear, 30-Oct-2014.)
⊢ (𝜑 → 𝐵 ⊆ 𝐴)    &   ⊢ (𝜑 → 𝐹:𝐵–1-1-onto→𝐴)    &   ⊢ (𝜑 → 𝐶 ∈ (𝐴 ∖ 𝐵))    &   ⊢ 𝐺 = (rec(◡𝐹, 𝐶) ↾ ω)    ⇒   ⊢ (𝜑 → (𝐴 ∈ 𝑉 → ω ≼ 𝐴))
Theorem	infpssr 9995	Dedekind infinity implies existence of a denumerable subset: take a single point witnessing the proper subset relation and iterate the embedding. (Contributed by Stefan O'Rear, 30-Oct-2014.) (Revised by Mario Carneiro, 16-May-2015.)
⊢ ((𝑋 ⊊ 𝐴 ∧ 𝑋 ≈ 𝐴) → ω ≼ 𝐴)
Theorem	fin4en1 9996	Dedekind finite is a cardinal property. (Contributed by Stefan O'Rear, 30-Oct-2014.) (Revised by Mario Carneiro, 16-May-2015.)
⊢ (𝐴 ≈ 𝐵 → (𝐴 ∈ FinIV → 𝐵 ∈ FinIV))
Theorem	ssfin4 9997	Dedekind finite sets have Dedekind finite subsets. (Contributed by Stefan O'Rear, 30-Oct-2014.) (Revised by Mario Carneiro, 6-May-2015.) (Revised by Mario Carneiro, 16-May-2015.)
⊢ ((𝐴 ∈ FinIV ∧ 𝐵 ⊆ 𝐴) → 𝐵 ∈ FinIV)
Theorem	domfin4 9998	A set dominated by a Dedekind finite set is Dedekind finite. (Contributed by Mario Carneiro, 16-May-2015.)
⊢ ((𝐴 ∈ FinIV ∧ 𝐵 ≼ 𝐴) → 𝐵 ∈ FinIV)
Theorem	ominf4 9999	ω is Dedekind infinite. (Contributed by Stefan O'Rear, 30-Oct-2014.) (Proof shortened by Mario Carneiro, 16-May-2015.)
⊢ ¬ ω ∈ FinIV
Theorem	infpssALT 10000*	Alternate proof of infpss 9904, shorter but requiring Replacement (ax-rep 5205). (Contributed by Stefan O'Rear, 30-Oct-2014.) (Revised by Mario Carneiro, 16-May-2015.) (Proof modification is discouraged.) (New usage is discouraged.)
⊢ (ω ≼ 𝐴 → ∃𝑥(𝑥 ⊊ 𝐴 ∧ 𝑥 ≈ 𝐴))