Theorem sbth 4457

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 4447 through sbthlem10 4456; this final piece mainly changes bound variables to eliminate the hypotheses of sbthlem10 4456. 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 2622	. . . . . 6 |- (z = A -> (z ~<_ w <-> A ~<_ w))
2		breq2 2623	. . . . . 6 |- (z = A -> (w ~<_ z <-> w ~<_ A))
3	1, 2	anbi12d 628	. . . . 5 |- (z = A -> ((z ~<_ w /\ w ~<_ z) <-> (A ~<_ w /\ w ~<_ A)))
4		breq1 2622	. . . . 5 |- (z = A -> (z ~~ w <-> A ~~ w))
5	3, 4	imbi12d 626	. . . 4 |- (z = A -> (((z ~<_ w /\ w ~<_ z) -> z ~~ w) <-> ((A ~<_ w /\ w ~<_ A) -> A ~~ w)))
6		breq2 2623	. . . . . 6 |- (w = B -> (A ~<_ w <-> A ~<_ B))
7		breq1 2622	. . . . . 6 |- (w = B -> (w ~<_ A <-> B ~<_ A))
8	6, 7	anbi12d 628	. . . . 5 |- (w = B -> ((A ~<_ w /\ w ~<_ A) <-> (A ~<_ B /\ B ~<_ A)))
9		breq2 2623	. . . . 5 |- (w = B -> (A ~~ w <-> A ~~ B))
10	8, 9	imbi12d 626	. . . 4 |- (w = B -> (((A ~<_ w /\ w ~<_ A) -> A ~~ w) <-> ((A ~<_ B /\ B ~<_ A) -> A ~~ B)))
11		visset 1813	. . . . 5 |- z e. V
12		sseq1 2082	. . . . . . 7 |- (y = x -> (y (_ z <-> x (_ z))
13		imaeq2 3402	. . . . . . . . . 10 |- (y = x -> (f"y) = (f"x))
14	13	difeq2d 2159	. . . . . . . . 9 |- (y = x -> (w \ (f"y)) = (w \ (f"x)))
15		imaeq2 3402	. . . . . . . . 9 |- ((w \ (f"y)) = (w \ (f"x)) -> (g"(w \ (f"y))) = (g"(w \ (f"x))))
16		sseq1 2082	. . . . . . . . 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 2154	. . . . . . . . 9 |- (y = x -> (z \ y) = (z \ x))
19	18	sseq2d 2089	. . . . . . . 8 |- (y = x -> ((g"(w \ (f"x))) (_ (z \ y) <-> (g"(w \ (f"x))) (_ (z \ x)))
20	17, 19	bitrd 528	. . . . . . 7 |- (y = x -> ((g"(w \ (f"y))) (_ (z \ y) <-> (g"(w \ (f"x))) (_ (z \ x)))
21	12, 20	anbi12d 628	. . . . . 6 |- (y = x -> ((y (_ z /\ (g"(w \ (f"y))) (_ (z \ y)) <-> (x (_ z /\ (g"(w \ (f"x))) (_ (z \ x))))
22	21	cbvabv 1909	. . . . 5 |- {y | (y (_ z /\ (g"(w \ (f"y))) (_ (z \ y))} = {x | (x (_ z /\ (g"(w \ (f"x))) (_ (z \ x))}
23		eqid 1475	. . . . 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 1813	. . . . 5 |- w e. V
25	11, 22, 23, 24	sbthlem10 4456	. . . 4 |- ((z ~<_ w /\ w ~<_ z) -> z ~~ w)
26	5, 10, 25	vtocl2g 1850	. . 3 |- ((A e. V /\ B e. V) -> ((A ~<_ B /\ B ~<_ A) -> A ~~ B))
27		reldom 4373	. . . 4 |- Rel ~<_
28	27	brrelexi 3208	. . 3 |- (A ~<_ B -> A e. V)
29	27	brrelexi 3208	. . 3 |- (B ~<_ A -> B e. 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 956   e. wcel 958  {cab 1463  Vcvv 1811   \ cdif 2044   u. cun 2045   (_ wss 2047  U.cuni 2503   class class class wbr 2619  `'ccnv 3169   |` cres 3172  "cima 3173   ~~ cen 4364   ~<_ cdom 4365

This theorem is referenced by:  sbthbg 4458  sdomnsym 4462  sdomdomtr 4469  limenpsi 4505  php 4513  onomeneq 4519  unbnn 4544  xpnnen 7499  znnen 7502  qnnen 7503  infxpidmlem1 7552  infxpidmlem12 7563  infunabs 7565  infcdaabs 7566  infdif 7568  infxpabs 7570  infmap1 7573  infmap2 7581

This theorem was proved from axioms:  ax-1 4  ax-2 5  ax-3 6  ax-mp 7  ax-7 962  ax-gen 963  ax-8 964  ax-9 965  ax-10 966  ax-11 967  ax-12 968  ax-13 969  ax-14 970  ax-17 971  ax-4 973  ax-5o 975  ax-6o 978  ax-9o 1123  ax-10o 1140  ax-16 1210  ax-11o 1218  ax-ext 1459  ax-rep 2693  ax-sep 2703  ax-pow 2742  ax-pr 2779  ax-un 2866

This theorem depends on definitions:  df-bi 147  df-or 224  df-an 225  df-3an 777  df-ex 981  df-sb 1172  df-eu 1382  df-mo 1383  df-clab 1464  df-cleq 1469  df-clel 1472  df-ne 1587  df-ral 1649  df-rex 1650  df-v 1812  df-dif 2049  df-un 2050  df-in 2051  df-ss 2053  df-nul 2281  df-pw 2402  df-sn 2412  df-pr 2413  df-op 2416  df-uni 2504  df-br 2620  df-opab 2667  df-id 2835  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