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

Theorem ac10ct 8406
Description: A proof of the Well ordering theorem weth 8866, an Axiom of Choice equivalent, restricted to sets dominated by some ordinal (in particular finite sets and countable sets), proven in ZF without AC. (Contributed by Mario Carneiro, 5-Jan-2013.)
Assertion
Ref Expression
ac10ct  |-  ( E. y  e.  On  A  ~<_  y  ->  E. x  x  We  A )
Distinct variable group:    x, A, y

Proof of Theorem ac10ct
Dummy variables  f  w  z are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 vex 3111 . . . . . 6  |-  y  e. 
_V
21brdom 7520 . . . . 5  |-  ( A  ~<_  y  <->  E. f  f : A -1-1-> y )
3 f1f 5774 . . . . . . . . . . . 12  |-  ( f : A -1-1-> y  -> 
f : A --> y )
4 frn 5730 . . . . . . . . . . . 12  |-  ( f : A --> y  ->  ran  f  C_  y )
53, 4syl 16 . . . . . . . . . . 11  |-  ( f : A -1-1-> y  ->  ran  f  C_  y )
6 onss 6599 . . . . . . . . . . 11  |-  ( y  e.  On  ->  y  C_  On )
7 sstr2 3506 . . . . . . . . . . 11  |-  ( ran  f  C_  y  ->  ( y  C_  On  ->  ran  f  C_  On )
)
85, 6, 7syl2im 38 . . . . . . . . . 10  |-  ( f : A -1-1-> y  -> 
( y  e.  On  ->  ran  f  C_  On ) )
9 epweon 6592 . . . . . . . . . 10  |-  _E  We  On
10 wess 4861 . . . . . . . . . 10  |-  ( ran  f  C_  On  ->  (  _E  We  On  ->  _E  We  ran  f ) )
118, 9, 10syl6mpi 62 . . . . . . . . 9  |-  ( f : A -1-1-> y  -> 
( y  e.  On  ->  _E  We  ran  f
) )
1211adantl 466 . . . . . . . 8  |-  ( ( A  ~<_  y  /\  f : A -1-1-> y )  -> 
( y  e.  On  ->  _E  We  ran  f
) )
13 f1f1orn 5820 . . . . . . . . . 10  |-  ( f : A -1-1-> y  -> 
f : A -1-1-onto-> ran  f
)
14 eqid 2462 . . . . . . . . . . 11  |-  { <. w ,  z >.  |  ( f `  w )  _E  ( f `  z ) }  =  { <. w ,  z
>.  |  ( f `  w )  _E  (
f `  z ) }
1514f1owe 6230 . . . . . . . . . 10  |-  ( f : A -1-1-onto-> ran  f  ->  (  _E  We  ran  f  ->  { <. w ,  z
>.  |  ( f `  w )  _E  (
f `  z ) }  We  A )
)
1613, 15syl 16 . . . . . . . . 9  |-  ( f : A -1-1-> y  -> 
(  _E  We  ran  f  ->  { <. w ,  z >.  |  ( f `  w )  _E  ( f `  z ) }  We  A ) )
17 weinxp 5061 . . . . . . . . . 10  |-  ( {
<. w ,  z >.  |  ( f `  w )  _E  (
f `  z ) }  We  A  <->  ( { <. w ,  z >.  |  ( f `  w )  _E  (
f `  z ) }  i^i  ( A  X.  A ) )  We  A )
18 reldom 7514 . . . . . . . . . . . 12  |-  Rel  ~<_
1918brrelexi 5034 . . . . . . . . . . 11  |-  ( A  ~<_  y  ->  A  e.  _V )
20 xpexg 6704 . . . . . . . . . . . 12  |-  ( ( A  e.  _V  /\  A  e.  _V )  ->  ( A  X.  A
)  e.  _V )
2120anidms 645 . . . . . . . . . . 11  |-  ( A  e.  _V  ->  ( A  X.  A )  e. 
_V )
22 incom 3686 . . . . . . . . . . . 12  |-  ( ( A  X.  A )  i^i  { <. w ,  z >.  |  ( f `  w )  _E  ( f `  z ) } )  =  ( { <. w ,  z >.  |  ( f `  w )  _E  ( f `  z ) }  i^i  ( A  X.  A
) )
23 inex1g 4585 . . . . . . . . . . . 12  |-  ( ( A  X.  A )  e.  _V  ->  (
( A  X.  A
)  i^i  { <. w ,  z >.  |  ( f `  w )  _E  ( f `  z ) } )  e.  _V )
2422, 23syl5eqelr 2555 . . . . . . . . . . 11  |-  ( ( A  X.  A )  e.  _V  ->  ( { <. w ,  z
>.  |  ( f `  w )  _E  (
f `  z ) }  i^i  ( A  X.  A ) )  e. 
_V )
25 weeq1 4862 . . . . . . . . . . . 12  |-  ( x  =  ( { <. w ,  z >.  |  ( f `  w )  _E  ( f `  z ) }  i^i  ( A  X.  A
) )  ->  (
x  We  A  <->  ( { <. w ,  z >.  |  ( f `  w )  _E  (
f `  z ) }  i^i  ( A  X.  A ) )  We  A ) )
2625spcegv 3194 . . . . . . . . . . 11  |-  ( ( { <. w ,  z
>.  |  ( f `  w )  _E  (
f `  z ) }  i^i  ( A  X.  A ) )  e. 
_V  ->  ( ( {
<. w ,  z >.  |  ( f `  w )  _E  (
f `  z ) }  i^i  ( A  X.  A ) )  We  A  ->  E. x  x  We  A )
)
2719, 21, 24, 264syl 21 . . . . . . . . . 10  |-  ( A  ~<_  y  ->  ( ( { <. w ,  z
>.  |  ( f `  w )  _E  (
f `  z ) }  i^i  ( A  X.  A ) )  We  A  ->  E. x  x  We  A )
)
2817, 27syl5bi 217 . . . . . . . . 9  |-  ( A  ~<_  y  ->  ( { <. w ,  z >.  |  ( f `  w )  _E  (
f `  z ) }  We  A  ->  E. x  x  We  A
) )
2916, 28sylan9r 658 . . . . . . . 8  |-  ( ( A  ~<_  y  /\  f : A -1-1-> y )  -> 
(  _E  We  ran  f  ->  E. x  x  We  A ) )
3012, 29syld 44 . . . . . . 7  |-  ( ( A  ~<_  y  /\  f : A -1-1-> y )  -> 
( y  e.  On  ->  E. x  x  We  A ) )
3130impancom 440 . . . . . 6  |-  ( ( A  ~<_  y  /\  y  e.  On )  ->  (
f : A -1-1-> y  ->  E. x  x  We  A ) )
3231exlimdv 1695 . . . . 5  |-  ( ( A  ~<_  y  /\  y  e.  On )  ->  ( E. f  f : A -1-1-> y  ->  E. x  x  We  A )
)
332, 32syl5bi 217 . . . 4  |-  ( ( A  ~<_  y  /\  y  e.  On )  ->  ( A  ~<_  y  ->  E. x  x  We  A )
)
3433ex 434 . . 3  |-  ( A  ~<_  y  ->  ( y  e.  On  ->  ( A  ~<_  y  ->  E. x  x  We  A ) ) )
3534pm2.43b 50 . 2  |-  ( y  e.  On  ->  ( A  ~<_  y  ->  E. x  x  We  A )
)
3635rexlimiv 2944 1  |-  ( E. y  e.  On  A  ~<_  y  ->  E. x  x  We  A )
Colors of variables: wff setvar class
Syntax hints:    -> wi 4    /\ wa 369   E.wex 1591    e. wcel 1762   E.wrex 2810   _Vcvv 3108    i^i cin 3470    C_ wss 3471   class class class wbr 4442   {copab 4499    _E cep 4784    We wwe 4832   Oncon0 4873    X. cxp 4992   ran crn 4995   -->wf 5577   -1-1->wf1 5578   -1-1-onto->wf1o 5580   ` cfv 5581    ~<_ cdom 7506
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1596  ax-4 1607  ax-5 1675  ax-6 1714  ax-7 1734  ax-8 1764  ax-9 1766  ax-10 1781  ax-11 1786  ax-12 1798  ax-13 1963  ax-ext 2440  ax-rep 4553  ax-sep 4563  ax-nul 4571  ax-pow 4620  ax-pr 4681  ax-un 6569
This theorem depends on definitions:  df-bi 185  df-or 370  df-an 371  df-3or 969  df-3an 970  df-tru 1377  df-ex 1592  df-nf 1595  df-sb 1707  df-eu 2274  df-mo 2275  df-clab 2448  df-cleq 2454  df-clel 2457  df-nfc 2612  df-ne 2659  df-ral 2814  df-rex 2815  df-rab 2818  df-v 3110  df-sbc 3327  df-dif 3474  df-un 3476  df-in 3478  df-ss 3485  df-pss 3487  df-nul 3781  df-if 3935  df-pw 4007  df-sn 4023  df-pr 4025  df-tp 4027  df-op 4029  df-uni 4241  df-br 4443  df-opab 4501  df-tr 4536  df-eprel 4786  df-id 4790  df-po 4795  df-so 4796  df-fr 4833  df-we 4835  df-ord 4876  df-on 4877  df-xp 5000  df-rel 5001  df-cnv 5002  df-co 5003  df-dm 5004  df-rn 5005  df-res 5006  df-ima 5007  df-iota 5544  df-fun 5583  df-fn 5584  df-f 5585  df-f1 5586  df-fo 5587  df-f1o 5588  df-fv 5589  df-isom 5590  df-dom 7510
This theorem is referenced by:  ondomen  8409
  Copyright terms: Public domain W3C validator