MPE Home Metamath Proof Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  MPE Home  >  Th. List  >  sbth Structured version   Visualization version   GIF version

Theorem sbth 7942
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 7932 through sbthlem10 7941; this final piece mainly changes bound variables to eliminate the hypotheses of sbthlem10 7941. 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. This is Metamath 100 proof #25. (Contributed by NM, 8-Jun-1998.)
Assertion
Ref Expression
sbth ((𝐴𝐵𝐵𝐴) → 𝐴𝐵)

Proof of Theorem sbth
Dummy variables 𝑥 𝑦 𝑧 𝑤 𝑓 𝑔 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 reldom 7824 . . . 4 Rel ≼
21brrelexi 5072 . . 3 (𝐴𝐵𝐴 ∈ V)
31brrelexi 5072 . . 3 (𝐵𝐴𝐵 ∈ V)
4 breq1 4580 . . . . . 6 (𝑧 = 𝐴 → (𝑧𝑤𝐴𝑤))
5 breq2 4581 . . . . . 6 (𝑧 = 𝐴 → (𝑤𝑧𝑤𝐴))
64, 5anbi12d 742 . . . . 5 (𝑧 = 𝐴 → ((𝑧𝑤𝑤𝑧) ↔ (𝐴𝑤𝑤𝐴)))
7 breq1 4580 . . . . 5 (𝑧 = 𝐴 → (𝑧𝑤𝐴𝑤))
86, 7imbi12d 332 . . . 4 (𝑧 = 𝐴 → (((𝑧𝑤𝑤𝑧) → 𝑧𝑤) ↔ ((𝐴𝑤𝑤𝐴) → 𝐴𝑤)))
9 breq2 4581 . . . . . 6 (𝑤 = 𝐵 → (𝐴𝑤𝐴𝐵))
10 breq1 4580 . . . . . 6 (𝑤 = 𝐵 → (𝑤𝐴𝐵𝐴))
119, 10anbi12d 742 . . . . 5 (𝑤 = 𝐵 → ((𝐴𝑤𝑤𝐴) ↔ (𝐴𝐵𝐵𝐴)))
12 breq2 4581 . . . . 5 (𝑤 = 𝐵 → (𝐴𝑤𝐴𝐵))
1311, 12imbi12d 332 . . . 4 (𝑤 = 𝐵 → (((𝐴𝑤𝑤𝐴) → 𝐴𝑤) ↔ ((𝐴𝐵𝐵𝐴) → 𝐴𝐵)))
14 vex 3175 . . . . 5 𝑧 ∈ V
15 sseq1 3588 . . . . . . 7 (𝑦 = 𝑥 → (𝑦𝑧𝑥𝑧))
16 imaeq2 5368 . . . . . . . . . 10 (𝑦 = 𝑥 → (𝑓𝑦) = (𝑓𝑥))
1716difeq2d 3689 . . . . . . . . 9 (𝑦 = 𝑥 → (𝑤 ∖ (𝑓𝑦)) = (𝑤 ∖ (𝑓𝑥)))
1817imaeq2d 5372 . . . . . . . 8 (𝑦 = 𝑥 → (𝑔 “ (𝑤 ∖ (𝑓𝑦))) = (𝑔 “ (𝑤 ∖ (𝑓𝑥))))
19 difeq2 3683 . . . . . . . 8 (𝑦 = 𝑥 → (𝑧𝑦) = (𝑧𝑥))
2018, 19sseq12d 3596 . . . . . . 7 (𝑦 = 𝑥 → ((𝑔 “ (𝑤 ∖ (𝑓𝑦))) ⊆ (𝑧𝑦) ↔ (𝑔 “ (𝑤 ∖ (𝑓𝑥))) ⊆ (𝑧𝑥)))
2115, 20anbi12d 742 . . . . . 6 (𝑦 = 𝑥 → ((𝑦𝑧 ∧ (𝑔 “ (𝑤 ∖ (𝑓𝑦))) ⊆ (𝑧𝑦)) ↔ (𝑥𝑧 ∧ (𝑔 “ (𝑤 ∖ (𝑓𝑥))) ⊆ (𝑧𝑥))))
2221cbvabv 2733 . . . . 5 {𝑦 ∣ (𝑦𝑧 ∧ (𝑔 “ (𝑤 ∖ (𝑓𝑦))) ⊆ (𝑧𝑦))} = {𝑥 ∣ (𝑥𝑧 ∧ (𝑔 “ (𝑤 ∖ (𝑓𝑥))) ⊆ (𝑧𝑥))}
23 eqid 2609 . . . . 5 ((𝑓 {𝑦 ∣ (𝑦𝑧 ∧ (𝑔 “ (𝑤 ∖ (𝑓𝑦))) ⊆ (𝑧𝑦))}) ∪ (𝑔 ↾ (𝑧 {𝑦 ∣ (𝑦𝑧 ∧ (𝑔 “ (𝑤 ∖ (𝑓𝑦))) ⊆ (𝑧𝑦))}))) = ((𝑓 {𝑦 ∣ (𝑦𝑧 ∧ (𝑔 “ (𝑤 ∖ (𝑓𝑦))) ⊆ (𝑧𝑦))}) ∪ (𝑔 ↾ (𝑧 {𝑦 ∣ (𝑦𝑧 ∧ (𝑔 “ (𝑤 ∖ (𝑓𝑦))) ⊆ (𝑧𝑦))})))
24 vex 3175 . . . . 5 𝑤 ∈ V
2514, 22, 23, 24sbthlem10 7941 . . . 4 ((𝑧𝑤𝑤𝑧) → 𝑧𝑤)
268, 13, 25vtocl2g 3242 . . 3 ((𝐴 ∈ V ∧ 𝐵 ∈ V) → ((𝐴𝐵𝐵𝐴) → 𝐴𝐵))
272, 3, 26syl2an 492 . 2 ((𝐴𝐵𝐵𝐴) → ((𝐴𝐵𝐵𝐴) → 𝐴𝐵))
2827pm2.43i 49 1 ((𝐴𝐵𝐵𝐴) → 𝐴𝐵)
Colors of variables: wff setvar class
Syntax hints:  wi 4  wa 382   = wceq 1474  wcel 1976  {cab 2595  Vcvv 3172  cdif 3536  cun 3537  wss 3539   cuni 4366   class class class wbr 4577  ccnv 5027  cres 5030  cima 5031  cen 7815  cdom 7816
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1712  ax-4 1727  ax-5 1826  ax-6 1874  ax-7 1921  ax-8 1978  ax-9 1985  ax-10 2005  ax-11 2020  ax-12 2032  ax-13 2232  ax-ext 2589  ax-sep 4703  ax-nul 4712  ax-pow 4764  ax-pr 4828  ax-un 6824
This theorem depends on definitions:  df-bi 195  df-or 383  df-an 384  df-3an 1032  df-tru 1477  df-ex 1695  df-nf 1700  df-sb 1867  df-eu 2461  df-mo 2462  df-clab 2596  df-cleq 2602  df-clel 2605  df-nfc 2739  df-ral 2900  df-rex 2901  df-rab 2904  df-v 3174  df-dif 3542  df-un 3544  df-in 3546  df-ss 3553  df-nul 3874  df-if 4036  df-pw 4109  df-sn 4125  df-pr 4127  df-op 4131  df-uni 4367  df-br 4578  df-opab 4638  df-id 4943  df-xp 5034  df-rel 5035  df-cnv 5036  df-co 5037  df-dm 5038  df-rn 5039  df-res 5040  df-ima 5041  df-fun 5792  df-fn 5793  df-f 5794  df-f1 5795  df-fo 5796  df-f1o 5797  df-en 7819  df-dom 7820
This theorem is referenced by:  sbthb  7943  sdomnsym  7947  domtriord  7968  xpen  7985  limenpsi  7997  php  8006  onomeneq  8012  unbnn  8078  infxpenlem  8696  fseqen  8710  infpwfien  8745  inffien  8746  alephdom  8764  mappwen  8795  infcdaabs  8888  infunabs  8889  infcda  8890  infdif  8891  infxpabs  8894  infmap2  8900  gchaleph  9349  gchhar  9357  inttsk  9452  inar1  9453  znnen  14726  qnnen  14727  rpnnen  14741  rexpen  14742  mreexfidimd  16080  acsinfdimd  16951  fislw  17809  opnreen  22374  ovolctb2  22984  vitali  23105  aannenlem3  23806  basellem4  24527  lgsqrlem4  24791  umgraex  25618  phpreu  32366  poimirlem26  32408  pellexlem4  36217  pellexlem5  36218  idomsubgmo  36598  upgrex  40320
  Copyright terms: Public domain W3C validator