Theorem sbth 4464

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 4454 through sbthlem10 4463; this final piece mainly changes bound variables to eliminate the hypotheses of sbthlem10 4463. 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 2628	. . . . . 6 |- (z = A -> (z ~<_ w <-> A ~<_ w))
2		breq2 2629	. . . . . 6 |- (z = A -> (w ~<_ z <-> w ~<_ A))
3	1, 2	anbi12d 630	. . . . 5 |- (z = A -> ((z ~<_ w /\ w ~<_ z) <-> (A ~<_ w /\ w ~<_ A)))
4		breq1 2628	. . . . 5 |- (z = A -> (z ~~ w <-> A ~~ w))
5	3, 4	imbi12d 628	. . . 4 |- (z = A -> (((z ~<_ w /\ w ~<_ z) -> z ~~ w) <-> ((A ~<_ w /\ w ~<_ A) -> A ~~ w)))
6		breq2 2629	. . . . . 6 |- (w = B -> (A ~<_ w <-> A ~<_ B))
7		breq1 2628	. . . . . 6 |- (w = B -> (w ~<_ A <-> B ~<_ A))
8	6, 7	anbi12d 630	. . . . 5 |- (w = B -> ((A ~<_ w /\ w ~<_ A) <-> (A ~<_ B /\ B ~<_ A)))
9		breq2 2629	. . . . 5 |- (w = B -> (A ~~ w <-> A ~~ B))
10	8, 9	imbi12d 628	. . . 4 |- (w = B -> (((A ~<_ w /\ w ~<_ A) -> A ~~ w) <-> ((A ~<_ B /\ B ~<_ A) -> A ~~ B)))
11		visset 1816	. . . . 5 |- z e. V
12		sseq1 2086	. . . . . . 7 |- (y = x -> (y (_ z <-> x (_ z))
13		imaeq2 3409	. . . . . . . . . 10 |- (y = x -> (f"y) = (f"x))
14	13	difeq2d 2163	. . . . . . . . 9 |- (y = x -> (w \ (f"y)) = (w \ (f"x)))
15		imaeq2 3409	. . . . . . . . 9 |- ((w \ (f"y)) = (w \ (f"x)) -> (g"(w \ (f"y))) = (g"(w \ (f"x))))
16		sseq1 2086	. . . . . . . . 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 2158	. . . . . . . . 9 |- (y = x -> (z \ y) = (z \ x))
19	18	sseq2d 2093	. . . . . . . 8 |- (y = x -> ((g"(w \ (f"x))) (_ (z \ y) <-> (g"(w \ (f"x))) (_ (z \ x)))
20	17, 19	bitrd 530	. . . . . . 7 |- (y = x -> ((g"(w \ (f"y))) (_ (z \ y) <-> (g"(w \ (f"x))) (_ (z \ x)))
21	12, 20	anbi12d 630	. . . . . 6 |- (y = x -> ((y (_ z /\ (g"(w \ (f"y))) (_ (z \ y)) <-> (x (_ z /\ (g"(w \ (f"x))) (_ (z \ x))))
22	21	cbvabv 1912	. . . . 5 |- {y | (y (_ z /\ (g"(w \ (f"y))) (_ (z \ y))} = {x | (x (_ z /\ (g"(w \ (f"x))) (_ (z \ x))}
23		eqid 1478	. . . . 5 |- ((f |` U.{y | (y (_ z /\ (g"(w \ (f"y))) (_ (z \ y))}) u. (`'g |` (z \ U.{y | (y (_ z /\ (g"(w \ (f"y))) (_ (z \ y))}))) = ((f |` U.{y | (y (_ z /\ (g"(w \ (f"y))) (_ (z \ y))}) u. (`'g |` (z \ U.{y | (y (_ z /\ (g"(w \ (f"y))) (_ (z \ y))})))
24		visset 1816	. . . . 5 |- w e. V
25	11, 22, 23, 24	sbthlem10 4463	. . . 4 |- ((z ~<_ w /\ w ~<_ z) -> z ~~ w)
26	5, 10, 25	vtocl2g 1853	. . 3 |- ((A e. V /\ B e. V) -> ((A ~<_ B /\ B ~<_ A) -> A ~~ B))
27		reldom 4380	. . . 4 |- Rel ~<_
28	27	brrelexi 3215	. . 3 |- (A ~<_ B -> A e. V)
29	27	brrelexi 3215	. . 3 |- (B ~<_ A -> B e. V)
30	26, 28, 29	syl2an 456	. 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 958   e. wcel 960  {cab 1466  Vcvv 1814   \ cdif 2048   u. cun 2049   (_ wss 2051  U.cuni 2508   class class class wbr 2625  `'ccnv 3176   |` cres 3179  "cima 3180   ~~ cen 4371   ~<_ cdom 4372

This theorem is referenced by:  sbthbg 4465  sdomnsym 4469  sdomdomtr 4476  limenpsi 4512  php 4520  onomeneq 4526  unbnn 4557  xpnnen 7507  znnen 7510  qnnen 7511  infxpidmlem1 7560  infxpidmlem12 7571  infunabs 7573  infcdaabs 7574  infdif 7576  infxpabs 7578  infmap1 7581  infmap2 7590

This theorem was proved from axioms:  ax-1 4  ax-2 5  ax-3 6  ax-mp 7  ax-7 964  ax-gen 965  ax-8 966  ax-9 967  ax-10 968  ax-11 969  ax-12 970  ax-13 971  ax-14 972  ax-17 973  ax-4 975  ax-5o 977  ax-6o 980  ax-9o 1125  ax-10o 1142  ax-16 1212  ax-11o 1220  ax-ext 1462  ax-rep 2699  ax-sep 2709  ax-pow 2749  ax-pr 2786  ax-un 2873

This theorem depends on definitions:  df-bi 147  df-or 224  df-an 225  df-3an 779  df-ex 983  df-sb 1174  df-eu 1384  df-mo 1385  df-clab 1467  df-cleq 1472  df-clel 1475  df-ne 1590  df-ral 1652  df-rex 1653  df-v 1815  df-dif 2053  df-un 2054  df-in 2055  df-ss 2057  df-nul 2285  df-pw 2407  df-sn 2417  df-pr 2418  df-op 2421  df-uni 2509  df-br 2626  df-opab 2673  df-id 2842  df-xp 3191  df-rel 3192  df-cnv 3193  df-co 3194  df-dm 3195  df-rn 3196  df-res 3197  df-ima 3198  df-fun 3199  df-fn 3200  df-f 3201  df-f1 3202  df-fo 3203  df-f1o 3204  df-en 4375  df-dom 4376

Copyright terms: Public domain