 Home Intuitionistic Logic ExplorerTheorem List (p. 68 of 129) < Previous  Next > Bad symbols? Try the GIF version. Mirrors  >  Metamath Home Page  >  ILE Home Page  >  Theorem List Contents  >  Recent Proofs       This page: Page List

Theorem List for Intuitionistic Logic Explorer - 6701-6800   *Has distinct variable group(s)
TypeLabelDescription
Statement

Theoremdomfiexmid 6701* If any set dominated by a finite set is finite, excluded middle follows. (Contributed by Jim Kingdon, 3-Feb-2022.)
((𝑥 ∈ Fin ∧ 𝑦𝑥) → 𝑦 ∈ Fin)       (𝜑 ∨ ¬ 𝜑)

Theoremdif1en 6702 If a set 𝐴 is equinumerous to the successor of a natural number 𝑀, then 𝐴 with an element removed is equinumerous to 𝑀. (Contributed by Jeff Madsen, 2-Sep-2009.) (Revised by Stefan O'Rear, 16-Aug-2015.)
((𝑀 ∈ ω ∧ 𝐴 ≈ suc 𝑀𝑋𝐴) → (𝐴 ∖ {𝑋}) ≈ 𝑀)

Theoremdif1enen 6703 Subtracting one element from each of two equinumerous finite sets. (Contributed by Jim Kingdon, 5-Jun-2022.)
(𝜑𝐴 ∈ Fin)    &   (𝜑𝐴𝐵)    &   (𝜑𝐶𝐴)    &   (𝜑𝐷𝐵)       (𝜑 → (𝐴 ∖ {𝐶}) ≈ (𝐵 ∖ {𝐷}))

Theoremfiunsnnn 6704 Adding one element to a finite set which is equinumerous to a natural number. (Contributed by Jim Kingdon, 13-Sep-2021.)
(((𝐴 ∈ Fin ∧ 𝐵 ∈ (V ∖ 𝐴)) ∧ (𝑁 ∈ ω ∧ 𝐴𝑁)) → (𝐴 ∪ {𝐵}) ≈ suc 𝑁)

Theoremphp5fin 6705 A finite set is not equinumerous to a set which adds one element. (Contributed by Jim Kingdon, 13-Sep-2021.)
((𝐴 ∈ Fin ∧ 𝐵 ∈ (V ∖ 𝐴)) → ¬ 𝐴 ≈ (𝐴 ∪ {𝐵}))

Theoremfisbth 6706 Schroeder-Bernstein Theorem for finite sets. (Contributed by Jim Kingdon, 12-Sep-2021.)
(((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) ∧ (𝐴𝐵𝐵𝐴)) → 𝐴𝐵)

Theorem0fin 6707 The empty set is finite. (Contributed by FL, 14-Jul-2008.)
∅ ∈ Fin

Theoremfin0 6708* A nonempty finite set has at least one element. (Contributed by Jim Kingdon, 10-Sep-2021.)
(𝐴 ∈ Fin → (𝐴 ≠ ∅ ↔ ∃𝑥 𝑥𝐴))

Theoremfin0or 6709* A finite set is either empty or inhabited. (Contributed by Jim Kingdon, 30-Sep-2021.)
(𝐴 ∈ Fin → (𝐴 = ∅ ∨ ∃𝑥 𝑥𝐴))

Theoremdiffitest 6710* If subtracting any set from a finite set gives a finite set, any proposition of the form ¬ 𝜑 is decidable. This is not a proof of full excluded middle, but it is close enough to show we won't be able to prove 𝐴 ∈ Fin → (𝐴𝐵) ∈ Fin. (Contributed by Jim Kingdon, 8-Sep-2021.)
𝑎 ∈ Fin ∀𝑏(𝑎𝑏) ∈ Fin       𝜑 ∨ ¬ ¬ 𝜑)

Theoremfindcard 6711* Schema for induction on the cardinality of a finite set. The inductive hypothesis is that the result is true on the given set with any one element removed. The result is then proven to be true for all finite sets. (Contributed by Jeff Madsen, 2-Sep-2009.)
(𝑥 = ∅ → (𝜑𝜓))    &   (𝑥 = (𝑦 ∖ {𝑧}) → (𝜑𝜒))    &   (𝑥 = 𝑦 → (𝜑𝜃))    &   (𝑥 = 𝐴 → (𝜑𝜏))    &   𝜓    &   (𝑦 ∈ Fin → (∀𝑧𝑦 𝜒𝜃))       (𝐴 ∈ Fin → 𝜏)

Theoremfindcard2 6712* Schema for induction on the cardinality of a finite set. The inductive step shows that the result is true if one more element is added to the set. The result is then proven to be true for all finite sets. (Contributed by Jeff Madsen, 8-Jul-2010.)
(𝑥 = ∅ → (𝜑𝜓))    &   (𝑥 = 𝑦 → (𝜑𝜒))    &   (𝑥 = (𝑦 ∪ {𝑧}) → (𝜑𝜃))    &   (𝑥 = 𝐴 → (𝜑𝜏))    &   𝜓    &   (𝑦 ∈ Fin → (𝜒𝜃))       (𝐴 ∈ Fin → 𝜏)

Theoremfindcard2s 6713* Variation of findcard2 6712 requiring that the element added in the induction step not be a member of the original set. (Contributed by Paul Chapman, 30-Nov-2012.)
(𝑥 = ∅ → (𝜑𝜓))    &   (𝑥 = 𝑦 → (𝜑𝜒))    &   (𝑥 = (𝑦 ∪ {𝑧}) → (𝜑𝜃))    &   (𝑥 = 𝐴 → (𝜑𝜏))    &   𝜓    &   ((𝑦 ∈ Fin ∧ ¬ 𝑧𝑦) → (𝜒𝜃))       (𝐴 ∈ Fin → 𝜏)

Theoremfindcard2d 6714* Deduction version of findcard2 6712. If you also need 𝑦 ∈ Fin (which doesn't come for free due to ssfiexmid 6699), use findcard2sd 6715 instead. (Contributed by SO, 16-Jul-2018.)
(𝑥 = ∅ → (𝜓𝜒))    &   (𝑥 = 𝑦 → (𝜓𝜃))    &   (𝑥 = (𝑦 ∪ {𝑧}) → (𝜓𝜏))    &   (𝑥 = 𝐴 → (𝜓𝜂))    &   (𝜑𝜒)    &   ((𝜑 ∧ (𝑦𝐴𝑧 ∈ (𝐴𝑦))) → (𝜃𝜏))    &   (𝜑𝐴 ∈ Fin)       (𝜑𝜂)

Theoremfindcard2sd 6715* Deduction form of finite set induction . (Contributed by Jim Kingdon, 14-Sep-2021.)
(𝑥 = ∅ → (𝜓𝜒))    &   (𝑥 = 𝑦 → (𝜓𝜃))    &   (𝑥 = (𝑦 ∪ {𝑧}) → (𝜓𝜏))    &   (𝑥 = 𝐴 → (𝜓𝜂))    &   (𝜑𝜒)    &   (((𝜑𝑦 ∈ Fin) ∧ (𝑦𝐴𝑧 ∈ (𝐴𝑦))) → (𝜃𝜏))    &   (𝜑𝐴 ∈ Fin)       (𝜑𝜂)

Theoremdiffisn 6716 Subtracting a singleton from a finite set produces a finite set. (Contributed by Jim Kingdon, 11-Sep-2021.)
((𝐴 ∈ Fin ∧ 𝐵𝐴) → (𝐴 ∖ {𝐵}) ∈ Fin)

Theoremdiffifi 6717 Subtracting one finite set from another produces a finite set. (Contributed by Jim Kingdon, 8-Sep-2021.)
((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin ∧ 𝐵𝐴) → (𝐴𝐵) ∈ Fin)

Theoreminfnfi 6718 An infinite set is not finite. (Contributed by Jim Kingdon, 20-Feb-2022.)
(ω ≼ 𝐴 → ¬ 𝐴 ∈ Fin)

Theoremominf 6719 The set of natural numbers is not finite. Although we supply this theorem because we can, the more natural way to express "ω is infinite" is ω ≼ ω which is an instance of domrefg 6591. (Contributed by NM, 2-Jun-1998.)
¬ ω ∈ Fin

Theoremisinfinf 6720* An infinite set contains subsets of arbitrarily large finite cardinality. (Contributed by Jim Kingdon, 15-Jun-2022.)
(ω ≼ 𝐴 → ∀𝑛 ∈ ω ∃𝑥(𝑥𝐴𝑥𝑛))

Theoremac6sfi 6721* Existence of a choice function for finite sets. (Contributed by Jeff Hankins, 26-Jun-2009.) (Proof shortened by Mario Carneiro, 29-Jan-2014.)
(𝑦 = (𝑓𝑥) → (𝜑𝜓))       ((𝐴 ∈ Fin ∧ ∀𝑥𝐴𝑦𝐵 𝜑) → ∃𝑓(𝑓:𝐴𝐵 ∧ ∀𝑥𝐴 𝜓))

Theoremtridc 6722* A trichotomous order is decidable. (Contributed by Jim Kingdon, 5-Sep-2022.)
(𝜑𝑅 Po 𝐴)    &   (𝜑 → ∀𝑥𝐴𝑦𝐴 (𝑥𝑅𝑦𝑥 = 𝑦𝑦𝑅𝑥))    &   (𝜑𝐵𝐴)    &   (𝜑𝐶𝐴)       (𝜑DECID 𝐵𝑅𝐶)

Theoremfimax2gtrilemstep 6723* Lemma for fimax2gtri 6724. The induction step. (Contributed by Jim Kingdon, 5-Sep-2022.)
(𝜑𝑅 Po 𝐴)    &   (𝜑 → ∀𝑥𝐴𝑦𝐴 (𝑥𝑅𝑦𝑥 = 𝑦𝑦𝑅𝑥))    &   (𝜑𝐴 ∈ Fin)    &   (𝜑𝐴 ≠ ∅)    &   (𝜑𝑈 ∈ Fin)    &   (𝜑𝑈𝐴)    &   (𝜑𝑍𝐴)    &   (𝜑𝑉𝐴)    &   (𝜑 → ¬ 𝑉𝑈)    &   (𝜑 → ∀𝑦𝑈 ¬ 𝑍𝑅𝑦)       (𝜑 → ∃𝑥𝐴𝑦 ∈ (𝑈 ∪ {𝑉}) ¬ 𝑥𝑅𝑦)

Theoremfimax2gtri 6724* A finite set has a maximum under a trichotomous order. (Contributed by Jim Kingdon, 5-Sep-2022.)
(𝜑𝑅 Po 𝐴)    &   (𝜑 → ∀𝑥𝐴𝑦𝐴 (𝑥𝑅𝑦𝑥 = 𝑦𝑦𝑅𝑥))    &   (𝜑𝐴 ∈ Fin)    &   (𝜑𝐴 ≠ ∅)       (𝜑 → ∃𝑥𝐴𝑦𝐴 ¬ 𝑥𝑅𝑦)

Theoremfinexdc 6725* Decidability of existence, over a finite set and defined by a decidable proposition. (Contributed by Jim Kingdon, 12-Jul-2022.)
((𝐴 ∈ Fin ∧ ∀𝑥𝐴 DECID 𝜑) → DECID𝑥𝐴 𝜑)

Theoremdfrex2fin 6726* Relationship between universal and existential quantifiers over a finite set. Remark in Section 2.2.1 of [Pierik], p. 8. Although Pierik does not mention the decidability condition explicitly, it does say "only finitely many x to check" which means there must be some way of checking each value of x. (Contributed by Jim Kingdon, 11-Jul-2022.)
((𝐴 ∈ Fin ∧ ∀𝑥𝐴 DECID 𝜑) → (∃𝑥𝐴 𝜑 ↔ ¬ ∀𝑥𝐴 ¬ 𝜑))

Theoreminfm 6727* An infinite set is inhabited. (Contributed by Jim Kingdon, 18-Feb-2022.)
(ω ≼ 𝐴 → ∃𝑥 𝑥𝐴)

Theoreminfn0 6728 An infinite set is not empty. (Contributed by NM, 23-Oct-2004.)
(ω ≼ 𝐴𝐴 ≠ ∅)

Theoreminffiexmid 6729* If any given set is either finite or infinite, excluded middle follows. (Contributed by Jim Kingdon, 15-Jun-2022.)
(𝑥 ∈ Fin ∨ ω ≼ 𝑥)       (𝜑 ∨ ¬ 𝜑)

Theoremen2eqpr 6730 Building a set with two elements. (Contributed by FL, 11-Aug-2008.) (Revised by Mario Carneiro, 10-Sep-2015.)
((𝐶 ≈ 2o𝐴𝐶𝐵𝐶) → (𝐴𝐵𝐶 = {𝐴, 𝐵}))

Theoremexmidpw 6731 Excluded middle is equivalent to the power set of 1o having two elements. Remark of [PradicBrown2022], p. 2. (Contributed by Jim Kingdon, 30-Jun-2022.)
(EXMID ↔ 𝒫 1o ≈ 2o)

Theoremfientri3 6732 Trichotomy of dominance for finite sets. (Contributed by Jim Kingdon, 15-Sep-2021.)
((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) → (𝐴𝐵𝐵𝐴))

Theoremnnwetri 6733* A natural number is well-ordered by E. More specifically, this order both satisfies We and is trichotomous. (Contributed by Jim Kingdon, 25-Sep-2021.)
(𝐴 ∈ ω → ( E We 𝐴 ∧ ∀𝑥𝐴𝑦𝐴 (𝑥 E 𝑦𝑥 = 𝑦𝑦 E 𝑥)))

Theoremonunsnss 6734 Adding a singleton to create an ordinal. (Contributed by Jim Kingdon, 20-Oct-2021.)
((𝐵𝑉 ∧ (𝐴 ∪ {𝐵}) ∈ On) → 𝐵𝐴)

Theoremunfiexmid 6735* If the union of any two finite sets is finite, excluded middle follows. Remark 8.1.17 of [AczelRathjen], p. 74. (Contributed by Mario Carneiro and Jim Kingdon, 5-Mar-2022.)
((𝑥 ∈ Fin ∧ 𝑦 ∈ Fin) → (𝑥𝑦) ∈ Fin)       (𝜑 ∨ ¬ 𝜑)

Theoremunsnfi 6736 Adding a singleton to a finite set yields a finite set. (Contributed by Jim Kingdon, 3-Feb-2022.)
((𝐴 ∈ Fin ∧ 𝐵𝑉 ∧ ¬ 𝐵𝐴) → (𝐴 ∪ {𝐵}) ∈ Fin)

Theoremunsnfidcex 6737 The 𝐵𝑉 condition in unsnfi 6736. This is intended to show that unsnfi 6736 without that condition would not be provable but it probably would need to be strengthened (for example, to imply included middle) to fully show that. (Contributed by Jim Kingdon, 6-Feb-2022.)
((𝐴 ∈ Fin ∧ ¬ 𝐵𝐴 ∧ (𝐴 ∪ {𝐵}) ∈ Fin) → DECID ¬ 𝐵 ∈ V)

Theoremunsnfidcel 6738 The ¬ 𝐵𝐴 condition in unsnfi 6736. This is intended to show that unsnfi 6736 without that condition would not be provable but it probably would need to be strengthened (for example, to imply included middle) to fully show that. (Contributed by Jim Kingdon, 6-Feb-2022.)
((𝐴 ∈ Fin ∧ 𝐵𝑉 ∧ (𝐴 ∪ {𝐵}) ∈ Fin) → DECID ¬ 𝐵𝐴)

Theoremunfidisj 6739 The union of two disjoint finite sets is finite. (Contributed by Jim Kingdon, 25-Feb-2022.)
((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin ∧ (𝐴𝐵) = ∅) → (𝐴𝐵) ∈ Fin)

Theoremundifdcss 6740* Union of complementary parts into whole and decidability. (Contributed by Jim Kingdon, 17-Jun-2022.)
(𝐴 = (𝐵 ∪ (𝐴𝐵)) ↔ (𝐵𝐴 ∧ ∀𝑥𝐴 DECID 𝑥𝐵))

Theoremundifdc 6741* Union of complementary parts into whole. This is a case where we can strengthen undifss 3390 from subset to equality. (Contributed by Jim Kingdon, 17-Jun-2022.)
((∀𝑥𝐴𝑦𝐴 DECID 𝑥 = 𝑦𝐵 ∈ Fin ∧ 𝐵𝐴) → 𝐴 = (𝐵 ∪ (𝐴𝐵)))

Theoremundiffi 6742 Union of complementary parts into whole. This is a case where we can strengthen undifss 3390 from subset to equality. (Contributed by Jim Kingdon, 2-Mar-2022.)
((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin ∧ 𝐵𝐴) → 𝐴 = (𝐵 ∪ (𝐴𝐵)))

Theoremunfiin 6743 The union of two finite sets is finite if their intersection is. (Contributed by Jim Kingdon, 2-Mar-2022.)
((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin ∧ (𝐴𝐵) ∈ Fin) → (𝐴𝐵) ∈ Fin)

Theoremprfidisj 6744 A pair is finite if it consists of two unequal sets. For the case where 𝐴 = 𝐵, see snfig 6638. For the cases where one or both is a proper class, see prprc1 3578, prprc2 3579, or prprc 3580. (Contributed by Jim Kingdon, 31-May-2022.)
((𝐴𝑉𝐵𝑊𝐴𝐵) → {𝐴, 𝐵} ∈ Fin)

Theoremtpfidisj 6745 A triple is finite if it consists of three unequal sets. (Contributed by Jim Kingdon, 1-Oct-2022.)
(𝜑𝐴𝑉)    &   (𝜑𝐵𝑊)    &   (𝜑𝐶𝑋)    &   (𝜑𝐴𝐵)    &   (𝜑𝐴𝐶)    &   (𝜑𝐵𝐶)       (𝜑 → {𝐴, 𝐵, 𝐶} ∈ Fin)

Theoremfiintim 6746* If a class is closed under pairwise intersections, then it is closed under nonempty finite intersections. The converse would appear to require an additional condition, such as 𝑥 and 𝑦 not being equal, or 𝐴 having decidable equality.

This theorem is applicable to a topology, which (among other axioms) is closed under finite intersections. Some texts use a pairwise intersection and some texts use a finite intersection, but most topology texts assume excluded middle (in which case the two intersection properties would be equivalent). (Contributed by NM, 22-Sep-2002.) (Revised by Jim Kingdon, 14-Jan-2023.)

(∀𝑥𝐴𝑦𝐴 (𝑥𝑦) ∈ 𝐴 → ∀𝑥((𝑥𝐴𝑥 ≠ ∅ ∧ 𝑥 ∈ Fin) → 𝑥𝐴))

Theoremxpfi 6747 The Cartesian product of two finite sets is finite. Lemma 8.1.16 of [AczelRathjen], p. 74. (Contributed by Jeff Madsen, 2-Sep-2009.) (Revised by Mario Carneiro, 12-Mar-2015.)
((𝐴 ∈ Fin ∧ 𝐵 ∈ Fin) → (𝐴 × 𝐵) ∈ Fin)

Theorem3xpfi 6748 The Cartesian product of three finite sets is a finite set. (Contributed by Alexander van der Vekens, 11-Mar-2018.)
(𝑉 ∈ Fin → ((𝑉 × 𝑉) × 𝑉) ∈ Fin)

Theoremfisseneq 6749 A finite set is equal to its subset if they are equinumerous. (Contributed by FL, 11-Aug-2008.)
((𝐵 ∈ Fin ∧ 𝐴𝐵𝐴𝐵) → 𝐴 = 𝐵)

Theoremssfirab 6750* A subset of a finite set is finite if it is defined by a decidable property. (Contributed by Jim Kingdon, 27-May-2022.)
(𝜑𝐴 ∈ Fin)    &   (𝜑 → ∀𝑥𝐴 DECID 𝜓)       (𝜑 → {𝑥𝐴𝜓} ∈ Fin)

Theoremssfidc 6751* A subset of a finite set is finite if membership in the subset is decidable. (Contributed by Jim Kingdon, 27-May-2022.)
((𝐴 ∈ Fin ∧ 𝐵𝐴 ∧ ∀𝑥𝐴 DECID 𝑥𝐵) → 𝐵 ∈ Fin)

Theoremsnon0 6752 An ordinal which is a singleton is {∅}. (Contributed by Jim Kingdon, 19-Oct-2021.)
((𝐴𝑉 ∧ {𝐴} ∈ On) → 𝐴 = ∅)

Theoremfnfi 6753 A version of fnex 5574 for finite sets. (Contributed by Mario Carneiro, 16-Nov-2014.) (Revised by Mario Carneiro, 24-Jun-2015.)
((𝐹 Fn 𝐴𝐴 ∈ Fin) → 𝐹 ∈ Fin)

Theoremfundmfi 6754 The domain of a finite function is finite. (Contributed by Jim Kingdon, 5-Feb-2022.)
((𝐴 ∈ Fin ∧ Fun 𝐴) → dom 𝐴 ∈ Fin)

Theoremfundmfibi 6755 A function is finite if and only if its domain is finite. (Contributed by AV, 10-Jan-2020.)
(Fun 𝐹 → (𝐹 ∈ Fin ↔ dom 𝐹 ∈ Fin))

Theoremresfnfinfinss 6756 The restriction of a function to a finite subset of its domain is finite. (Contributed by Alexander van der Vekens, 3-Feb-2018.)
((𝐹 Fn 𝐴𝐵 ∈ Fin ∧ 𝐵𝐴) → (𝐹𝐵) ∈ Fin)

Theoremrelcnvfi 6757 If a relation is finite, its converse is as well. (Contributed by Jim Kingdon, 5-Feb-2022.)
((Rel 𝐴𝐴 ∈ Fin) → 𝐴 ∈ Fin)

Theoremfunrnfi 6758 The range of a finite relation is finite if its converse is a function. (Contributed by Jim Kingdon, 5-Feb-2022.)
((Rel 𝐴 ∧ Fun 𝐴𝐴 ∈ Fin) → ran 𝐴 ∈ Fin)

Theoremf1ofi 6759 If a 1-1 and onto function has a finite domain, its range is finite. (Contributed by Jim Kingdon, 21-Feb-2022.)
((𝐴 ∈ Fin ∧ 𝐹:𝐴1-1-onto𝐵) → 𝐵 ∈ Fin)

Theoremf1dmvrnfibi 6760 A one-to-one function whose domain is a set is finite if and only if its range is finite. See also f1vrnfibi 6761. (Contributed by AV, 10-Jan-2020.)
((𝐴𝑉𝐹:𝐴1-1𝐵) → (𝐹 ∈ Fin ↔ ran 𝐹 ∈ Fin))

Theoremf1vrnfibi 6761 A one-to-one function which is a set is finite if and only if its range is finite. See also f1dmvrnfibi 6760. (Contributed by AV, 10-Jan-2020.)
((𝐹𝑉𝐹:𝐴1-1𝐵) → (𝐹 ∈ Fin ↔ ran 𝐹 ∈ Fin))

Theoremiunfidisj 6762* The finite union of disjoint finite sets is finite. Note that 𝐵 depends on 𝑥, i.e. can be thought of as 𝐵(𝑥). (Contributed by NM, 23-Mar-2006.) (Revised by Jim Kingdon, 7-Oct-2022.)
((𝐴 ∈ Fin ∧ ∀𝑥𝐴 𝐵 ∈ Fin ∧ Disj 𝑥𝐴 𝐵) → 𝑥𝐴 𝐵 ∈ Fin)

Theoremf1finf1o 6763 Any injection from one finite set to another of equal size must be a bijection. (Contributed by Jeff Madsen, 5-Jun-2010.)
((𝐴𝐵𝐵 ∈ Fin) → (𝐹:𝐴1-1𝐵𝐹:𝐴1-1-onto𝐵))

Theoremen1eqsn 6764 A set with one element is a singleton. (Contributed by FL, 18-Aug-2008.)
((𝐴𝐵𝐵 ≈ 1o) → 𝐵 = {𝐴})

Theoremen1eqsnbi 6765 A set containing an element has exactly one element iff it is a singleton. (Contributed by FL, 13-Feb-2010.) (Revised by AV, 25-Jan-2020.)
(𝐴𝐵 → (𝐵 ≈ 1o𝐵 = {𝐴}))

Theoremsnexxph 6766* A case where the antecedent of snexg 4048 is not needed. The class {𝑥𝜑} is from dcextest 4433. (Contributed by Mario Carneiro and Jim Kingdon, 4-Jul-2022.)
{{𝑥𝜑}} ∈ V

Theorempreimaf1ofi 6767 The preimage of a finite set under a one-to-one, onto function is finite. (Contributed by Jim Kingdon, 24-Sep-2022.)
(𝜑𝐶𝐵)    &   (𝜑𝐹:𝐴1-1-onto𝐵)    &   (𝜑𝐶 ∈ Fin)       (𝜑 → (𝐹𝐶) ∈ Fin)

Theoremfidcenumlemim 6768* Lemma for fidcenum 6772. Forward direction. (Contributed by Jim Kingdon, 19-Oct-2022.)
(𝐴 ∈ Fin → (∀𝑥𝐴𝑦𝐴 DECID 𝑥 = 𝑦 ∧ ∃𝑛 ∈ ω ∃𝑓 𝑓:𝑛onto𝐴))

Theoremfidcenumlemrks 6769* Lemma for fidcenum 6772. Induction step for fidcenumlemrk 6770. (Contributed by Jim Kingdon, 20-Oct-2022.)
(𝜑 → ∀𝑥𝐴𝑦𝐴 DECID 𝑥 = 𝑦)    &   (𝜑𝐹:𝑁onto𝐴)    &   (𝜑𝐽 ∈ ω)    &   (𝜑 → suc 𝐽𝑁)    &   (𝜑 → (𝑋 ∈ (𝐹𝐽) ∨ ¬ 𝑋 ∈ (𝐹𝐽)))    &   (𝜑𝑋𝐴)       (𝜑 → (𝑋 ∈ (𝐹 “ suc 𝐽) ∨ ¬ 𝑋 ∈ (𝐹 “ suc 𝐽)))

Theoremfidcenumlemrk 6770* Lemma for fidcenum 6772. (Contributed by Jim Kingdon, 20-Oct-2022.)
(𝜑 → ∀𝑥𝐴𝑦𝐴 DECID 𝑥 = 𝑦)    &   (𝜑𝐹:𝑁onto𝐴)    &   (𝜑𝐾 ∈ ω)    &   (𝜑𝐾𝑁)    &   (𝜑𝑋𝐴)       (𝜑 → (𝑋 ∈ (𝐹𝐾) ∨ ¬ 𝑋 ∈ (𝐹𝐾)))

Theoremfidcenumlemr 6771* Lemma for fidcenum 6772. Reverse direction (put into deduction form). (Contributed by Jim Kingdon, 19-Oct-2022.)
(𝜑 → ∀𝑥𝐴𝑦𝐴 DECID 𝑥 = 𝑦)    &   (𝜑𝐹:𝑁onto𝐴)    &   (𝜑𝑁 ∈ ω)       (𝜑𝐴 ∈ Fin)

Theoremfidcenum 6772* A set is finite if and only if it has decidable equality and is finitely enumerable. Proposition 8.1.11 of [AczelRathjen], p. 72. The definition of "finitely enumerable" as 𝑛 ∈ ω∃𝑓𝑓:𝑛onto𝐴 is Definition 8.1.4 of [AczelRathjen], p. 71. (Contributed by Jim Kingdon, 19-Oct-2022.)
(𝐴 ∈ Fin ↔ (∀𝑥𝐴𝑦𝐴 DECID 𝑥 = 𝑦 ∧ ∃𝑛 ∈ ω ∃𝑓 𝑓:𝑛onto𝐴))

2.6.31  Schroeder-Bernstein Theorem

Theoremsbthlem1 6773* Lemma for isbth 6783. (Contributed by NM, 22-Mar-1998.)
𝐴 ∈ V    &   𝐷 = {𝑥 ∣ (𝑥𝐴 ∧ (𝑔 “ (𝐵 ∖ (𝑓𝑥))) ⊆ (𝐴𝑥))}        𝐷 ⊆ (𝐴 ∖ (𝑔 “ (𝐵 ∖ (𝑓 𝐷))))

Theoremsbthlem2 6774* Lemma for isbth 6783. (Contributed by NM, 22-Mar-1998.)
𝐴 ∈ V    &   𝐷 = {𝑥 ∣ (𝑥𝐴 ∧ (𝑔 “ (𝐵 ∖ (𝑓𝑥))) ⊆ (𝐴𝑥))}       (ran 𝑔𝐴 → (𝐴 ∖ (𝑔 “ (𝐵 ∖ (𝑓 𝐷)))) ⊆ 𝐷)

Theoremsbthlemi3 6775* Lemma for isbth 6783. (Contributed by NM, 22-Mar-1998.)
𝐴 ∈ V    &   𝐷 = {𝑥 ∣ (𝑥𝐴 ∧ (𝑔 “ (𝐵 ∖ (𝑓𝑥))) ⊆ (𝐴𝑥))}       ((EXMID ∧ ran 𝑔𝐴) → (𝑔 “ (𝐵 ∖ (𝑓 𝐷))) = (𝐴 𝐷))

Theoremsbthlemi4 6776* Lemma for isbth 6783. (Contributed by NM, 27-Mar-1998.)
𝐴 ∈ V    &   𝐷 = {𝑥 ∣ (𝑥𝐴 ∧ (𝑔 “ (𝐵 ∖ (𝑓𝑥))) ⊆ (𝐴𝑥))}       ((EXMID ∧ (dom 𝑔 = 𝐵 ∧ ran 𝑔𝐴) ∧ Fun 𝑔) → (𝑔 “ (𝐴 𝐷)) = (𝐵 ∖ (𝑓 𝐷)))

Theoremsbthlemi5 6777* Lemma for isbth 6783. (Contributed by NM, 22-Mar-1998.)
𝐴 ∈ V    &   𝐷 = {𝑥 ∣ (𝑥𝐴 ∧ (𝑔 “ (𝐵 ∖ (𝑓𝑥))) ⊆ (𝐴𝑥))}    &   𝐻 = ((𝑓 𝐷) ∪ (𝑔 ↾ (𝐴 𝐷)))       ((EXMID ∧ (dom 𝑓 = 𝐴 ∧ ran 𝑔𝐴)) → dom 𝐻 = 𝐴)

Theoremsbthlemi6 6778* Lemma for isbth 6783. (Contributed by NM, 27-Mar-1998.)
𝐴 ∈ V    &   𝐷 = {𝑥 ∣ (𝑥𝐴 ∧ (𝑔 “ (𝐵 ∖ (𝑓𝑥))) ⊆ (𝐴𝑥))}    &   𝐻 = ((𝑓 𝐷) ∪ (𝑔 ↾ (𝐴 𝐷)))       (((EXMID ∧ ran 𝑓𝐵) ∧ ((dom 𝑔 = 𝐵 ∧ ran 𝑔𝐴) ∧ Fun 𝑔)) → ran 𝐻 = 𝐵)

Theoremsbthlem7 6779* Lemma for isbth 6783. (Contributed by NM, 27-Mar-1998.)
𝐴 ∈ V    &   𝐷 = {𝑥 ∣ (𝑥𝐴 ∧ (𝑔 “ (𝐵 ∖ (𝑓𝑥))) ⊆ (𝐴𝑥))}    &   𝐻 = ((𝑓 𝐷) ∪ (𝑔 ↾ (𝐴 𝐷)))       ((Fun 𝑓 ∧ Fun 𝑔) → Fun 𝐻)

Theoremsbthlemi8 6780* Lemma for isbth 6783. (Contributed by NM, 27-Mar-1998.)
𝐴 ∈ V    &   𝐷 = {𝑥 ∣ (𝑥𝐴 ∧ (𝑔 “ (𝐵 ∖ (𝑓𝑥))) ⊆ (𝐴𝑥))}    &   𝐻 = ((𝑓 𝐷) ∪ (𝑔 ↾ (𝐴 𝐷)))       (((EXMID ∧ Fun 𝑓) ∧ (((Fun 𝑔 ∧ dom 𝑔 = 𝐵) ∧ ran 𝑔𝐴) ∧ Fun 𝑔)) → Fun 𝐻)

Theoremsbthlemi9 6781* Lemma for isbth 6783. (Contributed by NM, 28-Mar-1998.)
𝐴 ∈ V    &   𝐷 = {𝑥 ∣ (𝑥𝐴 ∧ (𝑔 “ (𝐵 ∖ (𝑓𝑥))) ⊆ (𝐴𝑥))}    &   𝐻 = ((𝑓 𝐷) ∪ (𝑔 ↾ (𝐴 𝐷)))       ((EXMID𝑓:𝐴1-1𝐵𝑔:𝐵1-1𝐴) → 𝐻:𝐴1-1-onto𝐵)

Theoremsbthlemi10 6782* Lemma for isbth 6783. (Contributed by NM, 28-Mar-1998.)
𝐴 ∈ V    &   𝐷 = {𝑥 ∣ (𝑥𝐴 ∧ (𝑔 “ (𝐵 ∖ (𝑓𝑥))) ⊆ (𝐴𝑥))}    &   𝐻 = ((𝑓 𝐷) ∪ (𝑔 ↾ (𝐴 𝐷)))    &   𝐵 ∈ V       ((EXMID ∧ (𝐴𝐵𝐵𝐴)) → 𝐴𝐵)

Theoremisbth 6783 Schroeder-Bernstein Theorem. Theorem 18 of [Suppes] p. 95. This theorem states that if set 𝐴 is smaller (has lower cardinality) than 𝐵 and vice-versa, then 𝐴 and 𝐵 are equinumerous (have the same cardinality). The interesting thing is that this can be proved without invoking the Axiom of Choice, as we do here, but the proof as you can see is quite difficult. (The theorem can be proved more easily if we allow AC.) The main proof consists of lemmas sbthlem1 6773 through sbthlemi10 6782; this final piece mainly changes bound variables to eliminate the hypotheses of sbthlemi10 6782. We follow closely the proof in Suppes, which you should consult to understand our proof at a higher level. Note that Suppes' proof, which is credited to J. M. Whitaker, does not require the Axiom of Infinity. The proof does require the law of the excluded middle which cannot be avoided as shown at exmidsbthr 12802. (Contributed by NM, 8-Jun-1998.)
((EXMID ∧ (𝐴𝐵𝐵𝐴)) → 𝐴𝐵)

2.6.32  Supremum and infimum

Syntaxcsup 6784 Extend class notation to include supremum of class 𝐴. Here 𝑅 is ordinarily a relation that strictly orders class 𝐵. For example, 𝑅 could be 'less than' and 𝐵 could be the set of real numbers.
class sup(𝐴, 𝐵, 𝑅)

Syntaxcinf 6785 Extend class notation to include infimum of class 𝐴. Here 𝑅 is ordinarily a relation that strictly orders class 𝐵. For example, 𝑅 could be 'less than' and 𝐵 could be the set of real numbers.
class inf(𝐴, 𝐵, 𝑅)

Definitiondf-sup 6786* Define the supremum of class 𝐴. It is meaningful when 𝑅 is a relation that strictly orders 𝐵 and when the supremum exists. (Contributed by NM, 22-May-1999.)
sup(𝐴, 𝐵, 𝑅) = {𝑥𝐵 ∣ (∀𝑦𝐴 ¬ 𝑥𝑅𝑦 ∧ ∀𝑦𝐵 (𝑦𝑅𝑥 → ∃𝑧𝐴 𝑦𝑅𝑧))}

Definitiondf-inf 6787 Define the infimum of class 𝐴. It is meaningful when 𝑅 is a relation that strictly orders 𝐵 and when the infimum exists. For example, 𝑅 could be 'less than', 𝐵 could be the set of real numbers, and 𝐴 could be the set of all positive reals; in this case the infimum is 0. The infimum is defined as the supremum using the converse ordering relation. In the given example, 0 is the supremum of all reals (greatest real number) for which all positive reals are greater. (Contributed by AV, 2-Sep-2020.)
inf(𝐴, 𝐵, 𝑅) = sup(𝐴, 𝐵, 𝑅)

Theoremsupeq1 6788 Equality theorem for supremum. (Contributed by NM, 22-May-1999.)
(𝐵 = 𝐶 → sup(𝐵, 𝐴, 𝑅) = sup(𝐶, 𝐴, 𝑅))

Theoremsupeq1d 6789 Equality deduction for supremum. (Contributed by Paul Chapman, 22-Jun-2011.)
(𝜑𝐵 = 𝐶)       (𝜑 → sup(𝐵, 𝐴, 𝑅) = sup(𝐶, 𝐴, 𝑅))

Theoremsupeq1i 6790 Equality inference for supremum. (Contributed by Paul Chapman, 22-Jun-2011.)
𝐵 = 𝐶       sup(𝐵, 𝐴, 𝑅) = sup(𝐶, 𝐴, 𝑅)

Theoremsupeq2 6791 Equality theorem for supremum. (Contributed by Jeff Madsen, 2-Sep-2009.)
(𝐵 = 𝐶 → sup(𝐴, 𝐵, 𝑅) = sup(𝐴, 𝐶, 𝑅))

Theoremsupeq3 6792 Equality theorem for supremum. (Contributed by Scott Fenton, 13-Jun-2018.)
(𝑅 = 𝑆 → sup(𝐴, 𝐵, 𝑅) = sup(𝐴, 𝐵, 𝑆))

Theoremsupeq123d 6793 Equality deduction for supremum. (Contributed by Stefan O'Rear, 20-Jan-2015.)
(𝜑𝐴 = 𝐷)    &   (𝜑𝐵 = 𝐸)    &   (𝜑𝐶 = 𝐹)       (𝜑 → sup(𝐴, 𝐵, 𝐶) = sup(𝐷, 𝐸, 𝐹))

Theoremnfsup 6794 Hypothesis builder for supremum. (Contributed by Mario Carneiro, 20-Mar-2014.)
𝑥𝐴    &   𝑥𝐵    &   𝑥𝑅       𝑥sup(𝐴, 𝐵, 𝑅)

Theoremsupmoti 6795* Any class 𝐵 has at most one supremum in 𝐴 (where 𝑅 is interpreted as 'less than'). The hypothesis is satisfied by real numbers (see lttri3 7715) or other orders which correspond to tight apartnesses. (Contributed by Jim Kingdon, 23-Nov-2021.)
((𝜑 ∧ (𝑢𝐴𝑣𝐴)) → (𝑢 = 𝑣 ↔ (¬ 𝑢𝑅𝑣 ∧ ¬ 𝑣𝑅𝑢)))       (𝜑 → ∃*𝑥𝐴 (∀𝑦𝐵 ¬ 𝑥𝑅𝑦 ∧ ∀𝑦𝐴 (𝑦𝑅𝑥 → ∃𝑧𝐵 𝑦𝑅𝑧)))

Theoremsupeuti 6796* A supremum is unique. Similar to Theorem I.26 of [Apostol] p. 24 (but for suprema in general). (Contributed by Jim Kingdon, 23-Nov-2021.)
((𝜑 ∧ (𝑢𝐴𝑣𝐴)) → (𝑢 = 𝑣 ↔ (¬ 𝑢𝑅𝑣 ∧ ¬ 𝑣𝑅𝑢)))    &   (𝜑 → ∃𝑥𝐴 (∀𝑦𝐵 ¬ 𝑥𝑅𝑦 ∧ ∀𝑦𝐴 (𝑦𝑅𝑥 → ∃𝑧𝐵 𝑦𝑅𝑧)))       (𝜑 → ∃!𝑥𝐴 (∀𝑦𝐵 ¬ 𝑥𝑅𝑦 ∧ ∀𝑦𝐴 (𝑦𝑅𝑥 → ∃𝑧𝐵 𝑦𝑅𝑧)))

Theoremsupval2ti 6797* Alternate expression for the supremum. (Contributed by Jim Kingdon, 23-Nov-2021.)
((𝜑 ∧ (𝑢𝐴𝑣𝐴)) → (𝑢 = 𝑣 ↔ (¬ 𝑢𝑅𝑣 ∧ ¬ 𝑣𝑅𝑢)))    &   (𝜑 → ∃𝑥𝐴 (∀𝑦𝐵 ¬ 𝑥𝑅𝑦 ∧ ∀𝑦𝐴 (𝑦𝑅𝑥 → ∃𝑧𝐵 𝑦𝑅𝑧)))       (𝜑 → sup(𝐵, 𝐴, 𝑅) = (𝑥𝐴 (∀𝑦𝐵 ¬ 𝑥𝑅𝑦 ∧ ∀𝑦𝐴 (𝑦𝑅𝑥 → ∃𝑧𝐵 𝑦𝑅𝑧))))

Theoremeqsupti 6798* Sufficient condition for an element to be equal to the supremum. (Contributed by Jim Kingdon, 23-Nov-2021.)
((𝜑 ∧ (𝑢𝐴𝑣𝐴)) → (𝑢 = 𝑣 ↔ (¬ 𝑢𝑅𝑣 ∧ ¬ 𝑣𝑅𝑢)))       (𝜑 → ((𝐶𝐴 ∧ ∀𝑦𝐵 ¬ 𝐶𝑅𝑦 ∧ ∀𝑦𝐴 (𝑦𝑅𝐶 → ∃𝑧𝐵 𝑦𝑅𝑧)) → sup(𝐵, 𝐴, 𝑅) = 𝐶))

Theoremeqsuptid 6799* Sufficient condition for an element to be equal to the supremum. (Contributed by Jim Kingdon, 24-Nov-2021.)
((𝜑 ∧ (𝑢𝐴𝑣𝐴)) → (𝑢 = 𝑣 ↔ (¬ 𝑢𝑅𝑣 ∧ ¬ 𝑣𝑅𝑢)))    &   (𝜑𝐶𝐴)    &   ((𝜑𝑦𝐵) → ¬ 𝐶𝑅𝑦)    &   ((𝜑 ∧ (𝑦𝐴𝑦𝑅𝐶)) → ∃𝑧𝐵 𝑦𝑅𝑧)       (𝜑 → sup(𝐵, 𝐴, 𝑅) = 𝐶)

Theoremsupclti 6800* A supremum belongs to its base class (closure law). See also supubti 6801 and suplubti 6802. (Contributed by Jim Kingdon, 24-Nov-2021.)
((𝜑 ∧ (𝑢𝐴𝑣𝐴)) → (𝑢 = 𝑣 ↔ (¬ 𝑢𝑅𝑣 ∧ ¬ 𝑣𝑅𝑢)))    &   (𝜑 → ∃𝑥𝐴 (∀𝑦𝐵 ¬ 𝑥𝑅𝑦 ∧ ∀𝑦𝐴 (𝑦𝑅𝑥 → ∃𝑧𝐵 𝑦𝑅𝑧)))       (𝜑 → sup(𝐵, 𝐴, 𝑅) ∈ 𝐴)

Page List
Jump to page: Contents  1 1-100 2 101-200 3 201-300 4 301-400 5 401-500 6 501-600 7 601-700 8 701-800 9 801-900 10 901-1000 11 1001-1100 12 1101-1200 13 1201-1300 14 1301-1400 15 1401-1500 16 1501-1600 17 1601-1700 18 1701-1800 19 1801-1900 20 1901-2000 21 2001-2100 22 2101-2200 23 2201-2300 24 2301-2400 25 2401-2500 26 2501-2600 27 2601-2700 28 2701-2800 29 2801-2900 30 2901-3000 31 3001-3100 32 3101-3200 33 3201-3300 34 3301-3400 35 3401-3500 36 3501-3600 37 3601-3700 38 3701-3800 39 3801-3900 40 3901-4000 41 4001-4100 42 4101-4200 43 4201-4300 44 4301-4400 45 4401-4500 46 4501-4600 47 4601-4700 48 4701-4800 49 4801-4900 50 4901-5000 51 5001-5100 52 5101-5200 53 5201-5300 54 5301-5400 55 5401-5500 56 5501-5600 57 5601-5700 58 5701-5800 59 5801-5900 60 5901-6000 61 6001-6100 62 6101-6200 63 6201-6300 64 6301-6400 65 6401-6500 66 6501-6600 67 6601-6700 68 6701-6800 69 6801-6900 70 6901-7000 71 7001-7100 72 7101-7200 73 7201-7300 74 7301-7400 75 7401-7500 76 7501-7600 77 7601-7700 78 7701-7800 79 7801-7900 80 7901-8000 81 8001-8100 82 8101-8200 83 8201-8300 84 8301-8400 85 8401-8500 86 8501-8600 87 8601-8700 88 8701-8800 89 8801-8900 90 8901-9000 91 9001-9100 92 9101-9200 93 9201-9300 94 9301-9400 95 9401-9500 96 9501-9600 97 9601-9700 98 9701-9800 99 9801-9900 100 9901-10000 101 10001-10100 102 10101-10200 103 10201-10300 104 10301-10400 105 10401-10500 106 10501-10600 107 10601-10700 108 10701-10800 109 10801-10900 110 10901-11000 111 11001-11100 112 11101-11200 113 11201-11300 114 11301-11400 115 11401-11500 116 11501-11600 117 11601-11700 118 11701-11800 119 11801-11900 120 11901-12000 121 12001-12100 122 12101-12200 123 12201-12300 124 12301-12400 125 12401-12500 126 12501-12600 127 12601-12700 128 12701-12800 129 12801-12832
 Copyright terms: Public domain < Previous  Next >