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

Theorem hartogs 7549
Description: Given any set, the Hartogs number of the set is the least ordinal not dominated by that set. This theorem proves that there is always an ordinal which satisfies this. (This theorem can be proven trivially using the AC - see theorem ondomon 8476- but this proof works in ZF.) (Contributed by Jeff Hankins, 22-Oct-2009.) (Revised by Mario Carneiro, 15-May-2015.)
Assertion
Ref Expression
hartogs  |-  ( A  e.  V  ->  { x  e.  On  |  x  ~<_  A }  e.  On )
Distinct variable group:    x, A
Allowed substitution hint:    V( x)

Proof of Theorem hartogs
Dummy variables  g 
r  s  t  w  y  z are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 onelon 4641 . . . . . . . . . . . 12  |-  ( ( z  e.  On  /\  y  e.  z )  ->  y  e.  On )
2 vex 2968 . . . . . . . . . . . . 13  |-  z  e. 
_V
3 onelss 4658 . . . . . . . . . . . . . 14  |-  ( z  e.  On  ->  (
y  e.  z  -> 
y  C_  z )
)
43imp 420 . . . . . . . . . . . . 13  |-  ( ( z  e.  On  /\  y  e.  z )  ->  y  C_  z )
5 ssdomg 7189 . . . . . . . . . . . . 13  |-  ( z  e.  _V  ->  (
y  C_  z  ->  y  ~<_  z ) )
62, 4, 5mpsyl 62 . . . . . . . . . . . 12  |-  ( ( z  e.  On  /\  y  e.  z )  ->  y  ~<_  z )
71, 6jca 520 . . . . . . . . . . 11  |-  ( ( z  e.  On  /\  y  e.  z )  ->  ( y  e.  On  /\  y  ~<_  z ) )
8 domtr 7196 . . . . . . . . . . . . 13  |-  ( ( y  ~<_  z  /\  z  ~<_  A )  ->  y  ~<_  A )
98anim2i 554 . . . . . . . . . . . 12  |-  ( ( y  e.  On  /\  ( y  ~<_  z  /\  z  ~<_  A ) )  ->  ( y  e.  On  /\  y  ~<_  A ) )
109anassrs 631 . . . . . . . . . . 11  |-  ( ( ( y  e.  On  /\  y  ~<_  z )  /\  z  ~<_  A )  -> 
( y  e.  On  /\  y  ~<_  A ) )
117, 10sylan 459 . . . . . . . . . 10  |-  ( ( ( z  e.  On  /\  y  e.  z )  /\  z  ~<_  A )  ->  ( y  e.  On  /\  y  ~<_  A ) )
1211exp31 589 . . . . . . . . 9  |-  ( z  e.  On  ->  (
y  e.  z  -> 
( z  ~<_  A  -> 
( y  e.  On  /\  y  ~<_  A ) ) ) )
1312com12 30 . . . . . . . 8  |-  ( y  e.  z  ->  (
z  e.  On  ->  ( z  ~<_  A  ->  (
y  e.  On  /\  y  ~<_  A ) ) ) )
1413imp3a 422 . . . . . . 7  |-  ( y  e.  z  ->  (
( z  e.  On  /\  z  ~<_  A )  -> 
( y  e.  On  /\  y  ~<_  A ) ) )
15 breq1 4246 . . . . . . . 8  |-  ( x  =  z  ->  (
x  ~<_  A  <->  z  ~<_  A ) )
1615elrab 3101 . . . . . . 7  |-  ( z  e.  { x  e.  On  |  x  ~<_  A }  <->  ( z  e.  On  /\  z  ~<_  A ) )
17 breq1 4246 . . . . . . . 8  |-  ( x  =  y  ->  (
x  ~<_  A  <->  y  ~<_  A ) )
1817elrab 3101 . . . . . . 7  |-  ( y  e.  { x  e.  On  |  x  ~<_  A }  <->  ( y  e.  On  /\  y  ~<_  A ) )
1914, 16, 183imtr4g 263 . . . . . 6  |-  ( y  e.  z  ->  (
z  e.  { x  e.  On  |  x  ~<_  A }  ->  y  e.  { x  e.  On  |  x  ~<_  A } ) )
2019imp 420 . . . . 5  |-  ( ( y  e.  z  /\  z  e.  { x  e.  On  |  x  ~<_  A } )  ->  y  e.  { x  e.  On  |  x  ~<_  A }
)
2120gen2 1557 . . . 4  |-  A. y A. z ( ( y  e.  z  /\  z  e.  { x  e.  On  |  x  ~<_  A }
)  ->  y  e.  { x  e.  On  |  x  ~<_  A } )
22 dftr2 4335 . . . 4  |-  ( Tr 
{ x  e.  On  |  x  ~<_  A }  <->  A. y A. z ( ( y  e.  z  /\  z  e.  {
x  e.  On  |  x  ~<_  A } )  ->  y  e.  {
x  e.  On  |  x  ~<_  A } ) )
2321, 22mpbir 202 . . 3  |-  Tr  {
x  e.  On  |  x  ~<_  A }
24 ssrab2 3417 . . 3  |-  { x  e.  On  |  x  ~<_  A }  C_  On
25 ordon 4798 . . 3  |-  Ord  On
26 trssord 4633 . . 3  |-  ( ( Tr  { x  e.  On  |  x  ~<_  A }  /\  { x  e.  On  |  x  ~<_  A }  C_  On  /\  Ord  On )  ->  Ord  { x  e.  On  |  x  ~<_  A } )
2723, 24, 25, 26mp3an 1280 . 2  |-  Ord  {
x  e.  On  |  x  ~<_  A }
28 eqid 2443 . . . 4  |-  { <. r ,  y >.  |  ( ( ( dom  r  C_  A  /\  (  _I  |`  dom  r )  C_  r  /\  r  C_  ( dom  r  X.  dom  r
) )  /\  (
r  \  _I  )  We  dom  r )  /\  y  =  dom OrdIso ( ( r  \  _I  ) ,  dom  r ) ) }  =  { <. r ,  y >.  |  ( ( ( dom  r  C_  A  /\  (  _I  |`  dom  r )  C_  r  /\  r  C_  ( dom  r  X.  dom  r
) )  /\  (
r  \  _I  )  We  dom  r )  /\  y  =  dom OrdIso ( ( r  \  _I  ) ,  dom  r ) ) }
29 eqid 2443 . . . 4  |-  { <. s ,  t >.  |  E. w  e.  y  E. z  e.  y  (
( s  =  ( g `  w )  /\  t  =  ( g `  z ) )  /\  w  _E  z ) }  =  { <. s ,  t
>.  |  E. w  e.  y  E. z  e.  y  ( (
s  =  ( g `
 w )  /\  t  =  ( g `  z ) )  /\  w  _E  z ) }
3028, 29hartogslem2 7548 . . 3  |-  ( A  e.  V  ->  { x  e.  On  |  x  ~<_  A }  e.  _V )
31 elong 4624 . . 3  |-  ( { x  e.  On  |  x  ~<_  A }  e.  _V  ->  ( { x  e.  On  |  x  ~<_  A }  e.  On  <->  Ord  { x  e.  On  |  x  ~<_  A } ) )
3230, 31syl 16 . 2  |-  ( A  e.  V  ->  ( { x  e.  On  |  x  ~<_  A }  e.  On  <->  Ord  { x  e.  On  |  x  ~<_  A } ) )
3327, 32mpbiri 226 1  |-  ( A  e.  V  ->  { x  e.  On  |  x  ~<_  A }  e.  On )
Colors of variables: wff set class
Syntax hints:    -> wi 4    <-> wb 178    /\ wa 360    /\ w3a 937   A.wal 1550    = wceq 1654    e. wcel 1728   E.wrex 2713   {crab 2716   _Vcvv 2965    \ cdif 3306    C_ wss 3309   class class class wbr 4243   {copab 4296   Tr wtr 4333    _E cep 4527    _I cid 4528    We wwe 4575   Ord word 4615   Oncon0 4616    X. cxp 4911   dom cdm 4913    |` cres 4915   ` cfv 5489    ~<_ cdom 7143  OrdIsocoi 7514
This theorem is referenced by:  card2on  7558  harf  7564  harval  7566
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 1628  ax-9 1669  ax-8 1690  ax-13 1730  ax-14 1732  ax-6 1747  ax-7 1752  ax-11 1764  ax-12 1954  ax-ext 2424  ax-rep 4351  ax-sep 4361  ax-nul 4369  ax-pow 4412  ax-pr 4438  ax-un 4736
This theorem depends on definitions:  df-bi 179  df-or 361  df-an 362  df-3or 938  df-3an 939  df-tru 1329  df-ex 1552  df-nf 1555  df-sb 1661  df-eu 2292  df-mo 2293  df-clab 2430  df-cleq 2436  df-clel 2439  df-nfc 2568  df-ne 2608  df-ral 2717  df-rex 2718  df-reu 2719  df-rmo 2720  df-rab 2721  df-v 2967  df-sbc 3171  df-csb 3271  df-dif 3312  df-un 3314  df-in 3316  df-ss 3323  df-pss 3325  df-nul 3617  df-if 3768  df-pw 3830  df-sn 3849  df-pr 3850  df-tp 3851  df-op 3852  df-uni 4045  df-iun 4124  df-br 4244  df-opab 4298  df-mpt 4299  df-tr 4334  df-eprel 4529  df-id 4533  df-po 4538  df-so 4539  df-fr 4576  df-se 4577  df-we 4578  df-ord 4619  df-on 4620  df-lim 4621  df-suc 4622  df-xp 4919  df-rel 4920  df-cnv 4921  df-co 4922  df-dm 4923  df-rn 4924  df-res 4925  df-ima 4926  df-iota 5453  df-fun 5491  df-fn 5492  df-f 5493  df-f1 5494  df-fo 5495  df-f1o 5496  df-fv 5497  df-isom 5498  df-riota 6585  df-recs 6669  df-en 7146  df-dom 7147  df-oi 7515
  Copyright terms: Public domain W3C validator