Theorem sbth 4454

Description: Schroeder-Bernstein Theorem. Theorem 18 of [Suppes] p. 95. This theorem states that if set A is smaller (has lower cardinality) than B and vice-versa, then A and B 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 4444 through sbthlem10 4453; this final piece mainly changes bound variables to eliminate the hypotheses of sbthlem10 4453. We follow closely the proof in Suppes, which you should consult to understand our proof at a higher level.

Assertion

Ref	Expression
sbth	⊢ ((A ≼ B ⋀ B ≼ A) → A ≈ B)

Proof of Theorem sbth

Step	Hyp	Ref	Expression
1		breq1 2618	. . . . . 6 ⊢ (z = A → (z ≼ w ↔ A ≼ w))
2		breq2 2619	. . . . . 6 ⊢ (z = A → (w ≼ z ↔ w ≼ A))
3	1, 2	anbi12d 627	. . . . 5 ⊢ (z = A → ((z ≼ w ⋀ w ≼ z) ↔ (A ≼ w ⋀ w ≼ A)))
4		breq1 2618	. . . . 5 ⊢ (z = A → (z ≈ w ↔ A ≈ w))
5	3, 4	imbi12d 625	. . . 4 ⊢ (z = A → (((z ≼ w ⋀ w ≼ z) → z ≈ w) ↔ ((A ≼ w ⋀ w ≼ A) → A ≈ w)))
6		breq2 2619	. . . . . 6 ⊢ (w = B → (A ≼ w ↔ A ≼ B))
7		breq1 2618	. . . . . 6 ⊢ (w = B → (w ≼ A ↔ B ≼ A))
8	6, 7	anbi12d 627	. . . . 5 ⊢ (w = B → ((A ≼ w ⋀ w ≼ A) ↔ (A ≼ B ⋀ B ≼ A)))
9		breq2 2619	. . . . 5 ⊢ (w = B → (A ≈ w ↔ A ≈ B))
10	8, 9	imbi12d 625	. . . 4 ⊢ (w = B → (((A ≼ w ⋀ w ≼ A) → A ≈ w) ↔ ((A ≼ B ⋀ B ≼ A) → A ≈ B)))
11		visset 1809	. . . . 5 ⊢ z ∈ V
12		sseq1 2078	. . . . . . 7 ⊢ (y = x → (y ⊆ z ↔ x ⊆ z))
13		imaeq2 3400	. . . . . . . . . 10 ⊢ (y = x → (f “ y) = (f “ x))
14	13	difeq2d 2155	. . . . . . . . 9 ⊢ (y = x → (w ∖ (f “ y)) = (w ∖ (f “ x)))
15		imaeq2 3400	. . . . . . . . 9 ⊢ ((w ∖ (f “ y)) = (w ∖ (f “ x)) → (g “ (w ∖ (f “ y))) = (g “ (w ∖ (f “ x))))
16		sseq1 2078	. . . . . . . . 9 ⊢ ((g “ (w ∖ (f “ y))) = (g “ (w ∖ (f “ x))) → ((g “ (w ∖ (f “ y))) ⊆ (z ∖ y) ↔ (g “ (w ∖ (f “ x))) ⊆ (z ∖ y)))
17	14, 15, 16	3syl 20	. . . . . . . 8 ⊢ (y = x → ((g “ (w ∖ (f “ y))) ⊆ (z ∖ y) ↔ (g “ (w ∖ (f “ x))) ⊆ (z ∖ y)))
18		difeq2 2150	. . . . . . . . 9 ⊢ (y = x → (z ∖ y) = (z ∖ x))
19	18	sseq2d 2085	. . . . . . . 8 ⊢ (y = x → ((g “ (w ∖ (f “ x))) ⊆ (z ∖ y) ↔ (g “ (w ∖ (f “ x))) ⊆ (z ∖ x)))
20	17, 19	bitrd 527	. . . . . . 7 ⊢ (y = x → ((g “ (w ∖ (f “ y))) ⊆ (z ∖ y) ↔ (g “ (w ∖ (f “ x))) ⊆ (z ∖ x)))
21	12, 20	anbi12d 627	. . . . . 6 ⊢ (y = x → ((y ⊆ z ⋀ (g “ (w ∖ (f “ y))) ⊆ (z ∖ y)) ↔ (x ⊆ z ⋀ (g “ (w ∖ (f “ x))) ⊆ (z ∖ x))))
22	21	cbvabv 1905	. . . . 5 ⊢ {y∣(y ⊆ z ⋀ (g “ (w ∖ (f “ y))) ⊆ (z ∖ y))} = {x∣(x ⊆ z ⋀ (g “ (w ∖ (f “ x))) ⊆ (z ∖ x))}
23		eqid 1473	. . . . 5 ⊢ ((f ↾ ∪{y∣(y ⊆ z ⋀ (g “ (w ∖ (f “ y))) ⊆ (z ∖ y))}) ∪ (◡g ↾ (z ∖ ∪{y∣(y ⊆ z ⋀ (g “ (w ∖ (f “ y))) ⊆ (z ∖ y))}))) = ((f ↾ ∪{y∣(y ⊆ z ⋀ (g “ (w ∖ (f “ y))) ⊆ (z ∖ y))}) ∪ (◡g ↾ (z ∖ ∪{y∣(y ⊆ z ⋀ (g “ (w ∖ (f “ y))) ⊆ (z ∖ y))})))
24		visset 1809	. . . . 5 ⊢ w ∈ V
25	11, 22, 23, 24	sbthlem10 4453	. . . 4 ⊢ ((z ≼ w ⋀ w ≼ z) → z ≈ w)
26	5, 10, 25	vtocl2g 1846	. . 3 ⊢ ((A ∈ V ⋀ B ∈ V) → ((A ≼ B ⋀ B ≼ A) → A ≈ B))
27		reldom 4372	. . . 4 ⊢ Rel ≼
28	27	brrelexi 3208	. . 3 ⊢ (A ≼ B → A ∈ V)
29	27	brrelexi 3208	. . 3 ⊢ (B ≼ A → B ∈ V)
30	26, 28, 29	syl2an 454	. 2 ⊢ ((A ≼ B ⋀ B ≼ A) → ((A ≼ B ⋀ B ≼ A) → A ≈ B))
31	30	pm2.43i 64	1 ⊢ ((A ≼ B ⋀ B ≼ A) → A ≈ B)

Syntax hints:   → wi 3   ↔ wb 146   ⋀ wa 223   = wceq 954   ∈ wcel 956  {cab 1461  Vcvv 1807   ∖ cdif 2040   ∪ cun 2041   ⊆ wss 2043  ∪cuni 2499   class class class wbr 2615  ^◡ccnv 3169   ↾ cres 3172   “ cima 3173   ≈ cen 4365   ≼ cdom 4366

This theorem is referenced by:  sbthbg 4455  sdomnsym 4459  sdomdomtr 4466  limenpsi 4503  php 4511  onomeneq 4516  unbnn 4539  xpnnen 7461  znnen 7465  qnnen 7466  infxpidmlem1 7515  infxpidmlem12 7526  infunabs 7528  infcdaabs 7529  infdif 7531  infxpabs 7533  infmap1 7536  infmap2 7543

This theorem was proved from axioms:  ax-1 4  ax-2 5  ax-3 6  ax-mp 7  ax-7 960  ax-gen 961  ax-8 962  ax-9 963  ax-10 964  ax-11 965  ax-12 966  ax-13 967  ax-14 968  ax-17 969  ax-4 971  ax-5o 973  ax-6o 976  ax-9o 1121  ax-10o 1138  ax-16 1208  ax-11o 1216  ax-ext 1457  ax-rep 2689  ax-sep 2699  ax-pow 2738  ax-pr 2775  ax-un 2865

This theorem depends on definitions:  df-bi 147  df-or 224  df-an 225  df-3an 776  df-ex 979  df-sb 1170  df-eu 1380  df-mo 1381  df-clab 1462  df-cleq 1467  df-clel 1470  df-ne 1584  df-ral 1646  df-rex 1647  df-v 1808  df-dif 2045  df-un 2046  df-in 2047  df-ss 2049  df-nul 2277  df-pw 2398  df-sn 2408  df-pr 2409  df-op 2412  df-uni 2500  df-br 2616  df-opab 2663  df-id 2832  df-xp 3184  df-rel 3185  df-cnv 3186  df-co 3187  df-dm 3188  df-rn 3189  df-res 3190  df-ima 3191  df-fun 3192  df-fn 3193  df-f 3194  df-f1 3195  df-fo 3196  df-f1o 3197  df-en 4368  df-dom 4369

Copyright terms: Public domain