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

Theorem sbth 7230
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 7220 through sbthlem10 7229; this final piece mainly changes bound variables to eliminate the hypotheses of sbthlem10 7229. 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. (Contributed by NM, 8-Jun-1998.)
Assertion
Ref Expression
sbth  |-  ( ( A  ~<_  B  /\  B  ~<_  A )  ->  A  ~~  B )

Proof of Theorem sbth
Dummy variables  x  y  z  w  f 
g are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 reldom 7118 . . . 4  |-  Rel  ~<_
21brrelexi 4921 . . 3  |-  ( A  ~<_  B  ->  A  e.  _V )
31brrelexi 4921 . . 3  |-  ( B  ~<_  A  ->  B  e.  _V )
4 breq1 4218 . . . . . 6  |-  ( z  =  A  ->  (
z  ~<_  w  <->  A  ~<_  w ) )
5 breq2 4219 . . . . . 6  |-  ( z  =  A  ->  (
w  ~<_  z  <->  w  ~<_  A ) )
64, 5anbi12d 693 . . . . 5  |-  ( z  =  A  ->  (
( z  ~<_  w  /\  w  ~<_  z )  <->  ( A  ~<_  w  /\  w  ~<_  A ) ) )
7 breq1 4218 . . . . 5  |-  ( z  =  A  ->  (
z  ~~  w  <->  A  ~~  w ) )
86, 7imbi12d 313 . . . 4  |-  ( z  =  A  ->  (
( ( z  ~<_  w  /\  w  ~<_  z )  ->  z  ~~  w
)  <->  ( ( A  ~<_  w  /\  w  ~<_  A )  ->  A  ~~  w ) ) )
9 breq2 4219 . . . . . 6  |-  ( w  =  B  ->  ( A  ~<_  w  <->  A  ~<_  B ) )
10 breq1 4218 . . . . . 6  |-  ( w  =  B  ->  (
w  ~<_  A  <->  B  ~<_  A ) )
119, 10anbi12d 693 . . . . 5  |-  ( w  =  B  ->  (
( A  ~<_  w  /\  w  ~<_  A )  <->  ( A  ~<_  B  /\  B  ~<_  A ) ) )
12 breq2 4219 . . . . 5  |-  ( w  =  B  ->  ( A  ~~  w  <->  A  ~~  B ) )
1311, 12imbi12d 313 . . . 4  |-  ( w  =  B  ->  (
( ( A  ~<_  w  /\  w  ~<_  A )  ->  A  ~~  w
)  <->  ( ( A  ~<_  B  /\  B  ~<_  A )  ->  A  ~~  B ) ) )
14 vex 2961 . . . . 5  |-  z  e. 
_V
15 sseq1 3371 . . . . . . 7  |-  ( y  =  x  ->  (
y  C_  z  <->  x  C_  z
) )
16 imaeq2 5202 . . . . . . . . . 10  |-  ( y  =  x  ->  (
f " y )  =  ( f "
x ) )
1716difeq2d 3467 . . . . . . . . 9  |-  ( y  =  x  ->  (
w  \  ( f " y ) )  =  ( w  \ 
( f " x
) ) )
1817imaeq2d 5206 . . . . . . . 8  |-  ( y  =  x  ->  (
g " ( w 
\  ( f "
y ) ) )  =  ( g "
( w  \  (
f " x ) ) ) )
19 difeq2 3461 . . . . . . . 8  |-  ( y  =  x  ->  (
z  \  y )  =  ( z  \  x ) )
2018, 19sseq12d 3379 . . . . . . 7  |-  ( y  =  x  ->  (
( g " (
w  \  ( f " y ) ) )  C_  ( z  \  y )  <->  ( g " ( w  \ 
( f " x
) ) )  C_  ( z  \  x
) ) )
2115, 20anbi12d 693 . . . . . 6  |-  ( y  =  x  ->  (
( y  C_  z  /\  ( g " (
w  \  ( f " y ) ) )  C_  ( z  \  y ) )  <-> 
( x  C_  z  /\  ( g " (
w  \  ( f " x ) ) )  C_  ( z  \  x ) ) ) )
2221cbvabv 2557 . . . . 5  |-  { y  |  ( y  C_  z  /\  ( g "
( w  \  (
f " y ) ) )  C_  (
z  \  y )
) }  =  {
x  |  ( x 
C_  z  /\  (
g " ( w 
\  ( f "
x ) ) ) 
C_  ( z  \  x ) ) }
23 eqid 2438 . . . . 5  |-  ( ( f  |`  U. { y  |  ( y  C_  z  /\  ( g "
( w  \  (
f " y ) ) )  C_  (
z  \  y )
) } )  u.  ( `' g  |`  ( z  \  U. { y  |  ( y  C_  z  /\  ( g " (
w  \  ( f " y ) ) )  C_  ( z  \  y ) ) } ) ) )  =  ( ( f  |`  U. { y  |  ( y  C_  z  /\  ( g " (
w  \  ( f " y ) ) )  C_  ( z  \  y ) ) } )  u.  ( `' g  |`  ( z 
\  U. { y  |  ( y  C_  z  /\  ( g " (
w  \  ( f " y ) ) )  C_  ( z  \  y ) ) } ) ) )
24 vex 2961 . . . . 5  |-  w  e. 
_V
2514, 22, 23, 24sbthlem10 7229 . . . 4  |-  ( ( z  ~<_  w  /\  w  ~<_  z )  ->  z  ~~  w )
268, 13, 25vtocl2g 3017 . . 3  |-  ( ( A  e.  _V  /\  B  e.  _V )  ->  ( ( A  ~<_  B  /\  B  ~<_  A )  ->  A  ~~  B
) )
272, 3, 26syl2an 465 . 2  |-  ( ( A  ~<_  B  /\  B  ~<_  A )  ->  (
( A  ~<_  B  /\  B  ~<_  A )  ->  A  ~~  B ) )
2827pm2.43i 46 1  |-  ( ( A  ~<_  B  /\  B  ~<_  A )  ->  A  ~~  B )
Colors of variables: wff set class
Syntax hints:    -> wi 4    /\ wa 360    = wceq 1653    e. wcel 1726   {cab 2424   _Vcvv 2958    \ cdif 3319    u. cun 3320    C_ wss 3322   U.cuni 4017   class class class wbr 4215   `'ccnv 4880    |` cres 4883   "cima 4884    ~~ cen 7109    ~<_ cdom 7110
This theorem is referenced by:  sbthb  7231  sdomnsym  7235  domtriord  7256  xpen  7273  limenpsi  7285  php  7294  onomeneq  7299  unbnn  7366  infxpenlem  7900  fseqen  7913  infpwfien  7948  inffien  7949  alephdom  7967  mappwen  7998  infcdaabs  8091  infunabs  8092  infcda  8093  infdif  8094  infxpabs  8097  infmap2  8103  gchaleph  8551  gchhar  8559  inttsk  8654  inar1  8655  xpnnenOLD  12814  znnen  12817  qnnen  12818  rpnnen  12831  rexpen  12832  mreexfidimd  13880  acsinfdimd  14613  fislw  15264  opnreen  18867  ovolctb2  19393  vitali  19510  aannenlem3  20252  basellem4  20871  lgsqrlem4  21133  umgraex  21363  pellexlem4  26909  pellexlem5  26910  idomsubgmo  27505
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1556  ax-5 1567  ax-17 1627  ax-9 1667  ax-8 1688  ax-13 1728  ax-14 1730  ax-6 1745  ax-7 1750  ax-11 1762  ax-12 1951  ax-ext 2419  ax-sep 4333  ax-nul 4341  ax-pow 4380  ax-pr 4406  ax-un 4704
This theorem depends on definitions:  df-bi 179  df-or 361  df-an 362  df-3an 939  df-tru 1329  df-ex 1552  df-nf 1555  df-sb 1660  df-eu 2287  df-mo 2288  df-clab 2425  df-cleq 2431  df-clel 2434  df-nfc 2563  df-ne 2603  df-ral 2712  df-rex 2713  df-rab 2716  df-v 2960  df-dif 3325  df-un 3327  df-in 3329  df-ss 3336  df-nul 3631  df-if 3742  df-pw 3803  df-sn 3822  df-pr 3823  df-op 3825  df-uni 4018  df-br 4216  df-opab 4270  df-id 4501  df-xp 4887  df-rel 4888  df-cnv 4889  df-co 4890  df-dm 4891  df-rn 4892  df-res 4893  df-ima 4894  df-fun 5459  df-fn 5460  df-f 5461  df-f1 5462  df-fo 5463  df-f1o 5464  df-en 7113  df-dom 7114
  Copyright terms: Public domain W3C validator