ILE Home Intuitionistic Logic Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  ILE Home  >  Th. List  >  isbth GIF version

Theorem isbth 6666
Description: 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 6656 through sbthlemi10 6665; this final piece mainly changes bound variables to eliminate the hypotheses of sbthlemi10 6665. 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 11796. (Contributed by NM, 8-Jun-1998.)
Assertion
Ref Expression
isbth ((EXMID ∧ (𝐴𝐵𝐵𝐴)) → 𝐴𝐵)

Proof of Theorem isbth
Dummy variables 𝑥 𝑦 𝑧 𝑤 𝑓 𝑔 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 simprl 498 . 2 ((EXMID ∧ (𝐴𝐵𝐵𝐴)) → 𝐴𝐵)
2 simprr 499 . 2 ((EXMID ∧ (𝐴𝐵𝐵𝐴)) → 𝐵𝐴)
3 reldom 6452 . . . . 5 Rel ≼
43brrelexi 4476 . . . 4 (𝐵𝐴𝐵 ∈ V)
52, 4syl 14 . . 3 ((EXMID ∧ (𝐴𝐵𝐵𝐴)) → 𝐵 ∈ V)
6 breq2 3847 . . . . . 6 (𝑤 = 𝐵 → (𝐴𝑤𝐴𝐵))
7 breq1 3846 . . . . . 6 (𝑤 = 𝐵 → (𝑤𝐴𝐵𝐴))
86, 7anbi12d 457 . . . . 5 (𝑤 = 𝐵 → ((𝐴𝑤𝑤𝐴) ↔ (𝐴𝐵𝐵𝐴)))
9 breq2 3847 . . . . 5 (𝑤 = 𝐵 → (𝐴𝑤𝐴𝐵))
108, 9imbi12d 232 . . . 4 (𝑤 = 𝐵 → (((𝐴𝑤𝑤𝐴) → 𝐴𝑤) ↔ ((𝐴𝐵𝐵𝐴) → 𝐴𝐵)))
1110adantl 271 . . 3 (((EXMID ∧ (𝐴𝐵𝐵𝐴)) ∧ 𝑤 = 𝐵) → (((𝐴𝑤𝑤𝐴) → 𝐴𝑤) ↔ ((𝐴𝐵𝐵𝐴) → 𝐴𝐵)))
123brrelexi 4476 . . . . 5 (𝐴𝐵𝐴 ∈ V)
131, 12syl 14 . . . 4 ((EXMID ∧ (𝐴𝐵𝐵𝐴)) → 𝐴 ∈ V)
14 breq1 3846 . . . . . . 7 (𝑧 = 𝐴 → (𝑧𝑤𝐴𝑤))
15 breq2 3847 . . . . . . 7 (𝑧 = 𝐴 → (𝑤𝑧𝑤𝐴))
1614, 15anbi12d 457 . . . . . 6 (𝑧 = 𝐴 → ((𝑧𝑤𝑤𝑧) ↔ (𝐴𝑤𝑤𝐴)))
17 breq1 3846 . . . . . 6 (𝑧 = 𝐴 → (𝑧𝑤𝐴𝑤))
1816, 17imbi12d 232 . . . . 5 (𝑧 = 𝐴 → (((𝑧𝑤𝑤𝑧) → 𝑧𝑤) ↔ ((𝐴𝑤𝑤𝐴) → 𝐴𝑤)))
1918adantl 271 . . . 4 (((EXMID ∧ (𝐴𝐵𝐵𝐴)) ∧ 𝑧 = 𝐴) → (((𝑧𝑤𝑤𝑧) → 𝑧𝑤) ↔ ((𝐴𝑤𝑤𝐴) → 𝐴𝑤)))
20 vex 2622 . . . . . . 7 𝑧 ∈ V
21 sseq1 3047 . . . . . . . . 9 (𝑦 = 𝑥 → (𝑦𝑧𝑥𝑧))
22 imaeq2 4765 . . . . . . . . . . . 12 (𝑦 = 𝑥 → (𝑓𝑦) = (𝑓𝑥))
2322difeq2d 3118 . . . . . . . . . . 11 (𝑦 = 𝑥 → (𝑤 ∖ (𝑓𝑦)) = (𝑤 ∖ (𝑓𝑥)))
2423imaeq2d 4769 . . . . . . . . . 10 (𝑦 = 𝑥 → (𝑔 “ (𝑤 ∖ (𝑓𝑦))) = (𝑔 “ (𝑤 ∖ (𝑓𝑥))))
25 difeq2 3112 . . . . . . . . . 10 (𝑦 = 𝑥 → (𝑧𝑦) = (𝑧𝑥))
2624, 25sseq12d 3055 . . . . . . . . 9 (𝑦 = 𝑥 → ((𝑔 “ (𝑤 ∖ (𝑓𝑦))) ⊆ (𝑧𝑦) ↔ (𝑔 “ (𝑤 ∖ (𝑓𝑥))) ⊆ (𝑧𝑥)))
2721, 26anbi12d 457 . . . . . . . 8 (𝑦 = 𝑥 → ((𝑦𝑧 ∧ (𝑔 “ (𝑤 ∖ (𝑓𝑦))) ⊆ (𝑧𝑦)) ↔ (𝑥𝑧 ∧ (𝑔 “ (𝑤 ∖ (𝑓𝑥))) ⊆ (𝑧𝑥))))
2827cbvabv 2211 . . . . . . 7 {𝑦 ∣ (𝑦𝑧 ∧ (𝑔 “ (𝑤 ∖ (𝑓𝑦))) ⊆ (𝑧𝑦))} = {𝑥 ∣ (𝑥𝑧 ∧ (𝑔 “ (𝑤 ∖ (𝑓𝑥))) ⊆ (𝑧𝑥))}
29 eqid 2088 . . . . . . 7 ((𝑓 {𝑦 ∣ (𝑦𝑧 ∧ (𝑔 “ (𝑤 ∖ (𝑓𝑦))) ⊆ (𝑧𝑦))}) ∪ (𝑔 ↾ (𝑧 {𝑦 ∣ (𝑦𝑧 ∧ (𝑔 “ (𝑤 ∖ (𝑓𝑦))) ⊆ (𝑧𝑦))}))) = ((𝑓 {𝑦 ∣ (𝑦𝑧 ∧ (𝑔 “ (𝑤 ∖ (𝑓𝑦))) ⊆ (𝑧𝑦))}) ∪ (𝑔 ↾ (𝑧 {𝑦 ∣ (𝑦𝑧 ∧ (𝑔 “ (𝑤 ∖ (𝑓𝑦))) ⊆ (𝑧𝑦))})))
30 vex 2622 . . . . . . 7 𝑤 ∈ V
3120, 28, 29, 30sbthlemi10 6665 . . . . . 6 ((EXMID ∧ (𝑧𝑤𝑤𝑧)) → 𝑧𝑤)
3231ex 113 . . . . 5 (EXMID → ((𝑧𝑤𝑤𝑧) → 𝑧𝑤))
3332adantr 270 . . . 4 ((EXMID ∧ (𝐴𝐵𝐵𝐴)) → ((𝑧𝑤𝑤𝑧) → 𝑧𝑤))
3413, 19, 33vtocld 2671 . . 3 ((EXMID ∧ (𝐴𝐵𝐵𝐴)) → ((𝐴𝑤𝑤𝐴) → 𝐴𝑤))
355, 11, 34vtocld 2671 . 2 ((EXMID ∧ (𝐴𝐵𝐵𝐴)) → ((𝐴𝐵𝐵𝐴) → 𝐴𝐵))
361, 2, 35mp2and 424 1 ((EXMID ∧ (𝐴𝐵𝐵𝐴)) → 𝐴𝐵)
Colors of variables: wff set class
Syntax hints:  wi 4  wa 102  wb 103   = wceq 1289  wcel 1438  {cab 2074  Vcvv 2619  cdif 2996  cun 2997  wss 2999   cuni 3651   class class class wbr 3843  EXMIDwem 4027  ccnv 4435  cres 4438  cima 4439  cen 6445  cdom 6446
This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-mp 7  ax-ia1 104  ax-ia2 105  ax-ia3 106  ax-in1 579  ax-in2 580  ax-io 665  ax-5 1381  ax-7 1382  ax-gen 1383  ax-ie1 1427  ax-ie2 1428  ax-8 1440  ax-10 1441  ax-11 1442  ax-i12 1443  ax-bndl 1444  ax-4 1445  ax-13 1449  ax-14 1450  ax-17 1464  ax-i9 1468  ax-ial 1472  ax-i5r 1473  ax-ext 2070  ax-sep 3955  ax-nul 3963  ax-pow 4007  ax-pr 4034  ax-un 4258
This theorem depends on definitions:  df-bi 115  df-stab 776  df-dc 781  df-3an 926  df-tru 1292  df-nf 1395  df-sb 1693  df-eu 1951  df-mo 1952  df-clab 2075  df-cleq 2081  df-clel 2084  df-nfc 2217  df-ral 2364  df-rex 2365  df-rab 2368  df-v 2621  df-dif 3001  df-un 3003  df-in 3005  df-ss 3012  df-nul 3287  df-pw 3429  df-sn 3450  df-pr 3451  df-op 3453  df-uni 3652  df-br 3844  df-opab 3898  df-exmid 4028  df-id 4118  df-xp 4442  df-rel 4443  df-cnv 4444  df-co 4445  df-dm 4446  df-rn 4447  df-res 4448  df-ima 4449  df-fun 5012  df-fn 5013  df-f 5014  df-f1 5015  df-fo 5016  df-f1o 5017  df-en 6448  df-dom 6449
This theorem is referenced by:  exmidsbth  11797
  Copyright terms: Public domain W3C validator