Theorem sbth 8121

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 8111 through sbthlem10 8120; this final piece mainly changes bound variables to eliminate the hypotheses of sbthlem10 8120. 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.

Step	Hyp	Ref	Expression
1		reldom 8003	. . . 4 ⊢ Rel ≼
2	1	brrelexi 5192	. . 3 ⊢ (𝐴 ≼ 𝐵 → 𝐴 ∈ V)
3	1	brrelexi 5192	. . 3 ⊢ (𝐵 ≼ 𝐴 → 𝐵 ∈ V)
4		breq1 4688	. . . . . 6 ⊢ (𝑧 = 𝐴 → (𝑧 ≼ 𝑤 ↔ 𝐴 ≼ 𝑤))
5		breq2 4689	. . . . . 6 ⊢ (𝑧 = 𝐴 → (𝑤 ≼ 𝑧 ↔ 𝑤 ≼ 𝐴))
6	4, 5	anbi12d 747	. . . . 5 ⊢ (𝑧 = 𝐴 → ((𝑧 ≼ 𝑤 ∧ 𝑤 ≼ 𝑧) ↔ (𝐴 ≼ 𝑤 ∧ 𝑤 ≼ 𝐴)))
7		breq1 4688	. . . . 5 ⊢ (𝑧 = 𝐴 → (𝑧 ≈ 𝑤 ↔ 𝐴 ≈ 𝑤))
8	6, 7	imbi12d 333	. . . 4 ⊢ (𝑧 = 𝐴 → (((𝑧 ≼ 𝑤 ∧ 𝑤 ≼ 𝑧) → 𝑧 ≈ 𝑤) ↔ ((𝐴 ≼ 𝑤 ∧ 𝑤 ≼ 𝐴) → 𝐴 ≈ 𝑤)))
9		breq2 4689	. . . . . 6 ⊢ (𝑤 = 𝐵 → (𝐴 ≼ 𝑤 ↔ 𝐴 ≼ 𝐵))
10		breq1 4688	. . . . . 6 ⊢ (𝑤 = 𝐵 → (𝑤 ≼ 𝐴 ↔ 𝐵 ≼ 𝐴))
11	9, 10	anbi12d 747	. . . . 5 ⊢ (𝑤 = 𝐵 → ((𝐴 ≼ 𝑤 ∧ 𝑤 ≼ 𝐴) ↔ (𝐴 ≼ 𝐵 ∧ 𝐵 ≼ 𝐴)))
12		breq2 4689	. . . . 5 ⊢ (𝑤 = 𝐵 → (𝐴 ≈ 𝑤 ↔ 𝐴 ≈ 𝐵))
13	11, 12	imbi12d 333	. . . 4 ⊢ (𝑤 = 𝐵 → (((𝐴 ≼ 𝑤 ∧ 𝑤 ≼ 𝐴) → 𝐴 ≈ 𝑤) ↔ ((𝐴 ≼ 𝐵 ∧ 𝐵 ≼ 𝐴) → 𝐴 ≈ 𝐵)))
14		vex 3234	. . . . 5 ⊢ 𝑧 ∈ V
15		sseq1 3659	. . . . . . 7 ⊢ (𝑦 = 𝑥 → (𝑦 ⊆ 𝑧 ↔ 𝑥 ⊆ 𝑧))
16		imaeq2 5497	. . . . . . . . . 10 ⊢ (𝑦 = 𝑥 → (𝑓 “ 𝑦) = (𝑓 “ 𝑥))
17	16	difeq2d 3761	. . . . . . . . 9 ⊢ (𝑦 = 𝑥 → (𝑤 ∖ (𝑓 “ 𝑦)) = (𝑤 ∖ (𝑓 “ 𝑥)))
18	17	imaeq2d 5501	. . . . . . . 8 ⊢ (𝑦 = 𝑥 → (𝑔 “ (𝑤 ∖ (𝑓 “ 𝑦))) = (𝑔 “ (𝑤 ∖ (𝑓 “ 𝑥))))
19		difeq2 3755	. . . . . . . 8 ⊢ (𝑦 = 𝑥 → (𝑧 ∖ 𝑦) = (𝑧 ∖ 𝑥))
20	18, 19	sseq12d 3667	. . . . . . 7 ⊢ (𝑦 = 𝑥 → ((𝑔 “ (𝑤 ∖ (𝑓 “ 𝑦))) ⊆ (𝑧 ∖ 𝑦) ↔ (𝑔 “ (𝑤 ∖ (𝑓 “ 𝑥))) ⊆ (𝑧 ∖ 𝑥)))
21	15, 20	anbi12d 747	. . . . . 6 ⊢ (𝑦 = 𝑥 → ((𝑦 ⊆ 𝑧 ∧ (𝑔 “ (𝑤 ∖ (𝑓 “ 𝑦))) ⊆ (𝑧 ∖ 𝑦)) ↔ (𝑥 ⊆ 𝑧 ∧ (𝑔 “ (𝑤 ∖ (𝑓 “ 𝑥))) ⊆ (𝑧 ∖ 𝑥))))
22	21	cbvabv 2776	. . . . 5 ⊢ {𝑦 ∣ (𝑦 ⊆ 𝑧 ∧ (𝑔 “ (𝑤 ∖ (𝑓 “ 𝑦))) ⊆ (𝑧 ∖ 𝑦))} = {𝑥 ∣ (𝑥 ⊆ 𝑧 ∧ (𝑔 “ (𝑤 ∖ (𝑓 “ 𝑥))) ⊆ (𝑧 ∖ 𝑥))}
23		eqid 2651	. . . . 5 ⊢ ((𝑓 ↾ ∪ {𝑦 ∣ (𝑦 ⊆ 𝑧 ∧ (𝑔 “ (𝑤 ∖ (𝑓 “ 𝑦))) ⊆ (𝑧 ∖ 𝑦))}) ∪ (◡𝑔 ↾ (𝑧 ∖ ∪ {𝑦 ∣ (𝑦 ⊆ 𝑧 ∧ (𝑔 “ (𝑤 ∖ (𝑓 “ 𝑦))) ⊆ (𝑧 ∖ 𝑦))}))) = ((𝑓 ↾ ∪ {𝑦 ∣ (𝑦 ⊆ 𝑧 ∧ (𝑔 “ (𝑤 ∖ (𝑓 “ 𝑦))) ⊆ (𝑧 ∖ 𝑦))}) ∪ (◡𝑔 ↾ (𝑧 ∖ ∪ {𝑦 ∣ (𝑦 ⊆ 𝑧 ∧ (𝑔 “ (𝑤 ∖ (𝑓 “ 𝑦))) ⊆ (𝑧 ∖ 𝑦))})))
24		vex 3234	. . . . 5 ⊢ 𝑤 ∈ V
25	14, 22, 23, 24	sbthlem10 8120	. . . 4 ⊢ ((𝑧 ≼ 𝑤 ∧ 𝑤 ≼ 𝑧) → 𝑧 ≈ 𝑤)
26	8, 13, 25	vtocl2g 3301	. . 3 ⊢ ((𝐴 ∈ V ∧ 𝐵 ∈ V) → ((𝐴 ≼ 𝐵 ∧ 𝐵 ≼ 𝐴) → 𝐴 ≈ 𝐵))
27	2, 3, 26	syl2an 493	. 2 ⊢ ((𝐴 ≼ 𝐵 ∧ 𝐵 ≼ 𝐴) → ((𝐴 ≼ 𝐵 ∧ 𝐵 ≼ 𝐴) → 𝐴 ≈ 𝐵))
28	27	pm2.43i 52	1 ⊢ ((𝐴 ≼ 𝐵 ∧ 𝐵 ≼ 𝐴) → 𝐴 ≈ 𝐵)

Syntax hints:   → wi 4   ∧ wa 383   = wceq 1523   ∈ wcel 2030  {cab 2637  Vcvv 3231   ∖ cdif 3604   ∪ cun 3605   ⊆ wss 3607  ∪ cuni 4468   class class class wbr 4685  ^◡ccnv 5142   ↾ cres 5145   “ cima 5146   ≈ cen 7994   ≼ cdom 7995

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1762  ax-4 1777  ax-5 1879  ax-6 1945  ax-7 1981  ax-8 2032  ax-9 2039  ax-10 2059  ax-11 2074  ax-12 2087  ax-13 2282  ax-ext 2631  ax-sep 4814  ax-nul 4822  ax-pow 4873  ax-pr 4936  ax-un 6991

This theorem depends on definitions:  df-bi 197  df-or 384  df-an 385  df-3an 1056  df-tru 1526  df-ex 1745  df-nf 1750  df-sb 1938  df-eu 2502  df-mo 2503  df-clab 2638  df-cleq 2644  df-clel 2647  df-nfc 2782  df-ral 2946  df-rex 2947  df-rab 2950  df-v 3233  df-dif 3610  df-un 3612  df-in 3614  df-ss 3621  df-nul 3949  df-if 4120  df-pw 4193  df-sn 4211  df-pr 4213  df-op 4217  df-uni 4469  df-br 4686  df-opab 4746  df-id 5053  df-xp 5149  df-rel 5150  df-cnv 5151  df-co 5152  df-dm 5153  df-rn 5154  df-res 5155  df-ima 5156  df-fun 5928  df-fn 5929  df-f 5930  df-f1 5931  df-fo 5932  df-f1o 5933  df-en 7998  df-dom 7999

This theorem is referenced by:  sbthb  8122  sdomnsym  8126  domtriord  8147  xpen  8164  limenpsi  8176  php  8185  onomeneq  8191  unbnn  8257  infxpenlem  8874  fseqen  8888  infpwfien  8923  inffien  8924  alephdom  8942  mappwen  8973  infcdaabs  9066  infunabs  9067  infcda  9068  infdif  9069  infxpabs  9072  infmap2  9078  gchaleph  9531  gchhar  9539  inttsk  9634  inar1  9635  znnen  14985  qnnen  14986  rpnnen  15000  rexpen  15001  mreexfidimd  16358  acsinfdimd  17229  fislw  18086  opnreen  22681  ovolctb2  23306  vitali  23427  aannenlem3  24130  basellem4  24855  lgsqrlem4  25119  upgrex  26032  phpreu  33523  poimirlem26  33565  pellexlem4  37713  pellexlem5  37714  idomsubgmo  38093