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

Theorem hta 8313
Description: A ZFC emulation of Hilbert's transfinite axiom. The set  B has the properties of Hilbert's epsilon, except that it also depends on a well-ordering  R. This theorem arose from discussions with Raph Levien on 5-Mar-2004 about translating the HOL proof language, which uses Hilbert's epsilon. See http://us.metamath.org/downloads/choice.txt (copy of obsolete link http://ghilbert.org/choice.txt) and http://us.metamath.org/downloads/megillaward2005he.pdf.

Hilbert's epsilon is described at http://plato.stanford.edu/entries/epsilon-calculus/. This theorem differs from Hilbert's transfinite axiom described on that page in that it requires  R  We  A as an antecedent. Class  A collects the sets of the least rank for which  ph ( x ) is true. Class  B, which emulates the epsilon, is the minimum element in a well-ordering  R on  A.

If a well-ordering  R on  A can be expressed in a closed form, as might be the case if we are working with say natural numbers, we can eliminate the antecedent with modus ponens, giving us the exact equivalent of Hilbert's transfinite axiom. Otherwise, we replace  R with a dummy setvar variable, say  w, and attach  w  We  A as an antecedent in each step of the ZFC version of the HOL proof until the epsilon is eliminated. At that point,  B (which will have  w as a free variable) will no longer be present, and we can eliminate  w  We  A by applying exlimiv 1770 and weth 8869, using scottexs 8303 to establish the existence of 
A.

For a version of this theorem scheme using class (meta)variables instead of wff (meta)variables, see htalem 8312. (Contributed by NM, 11-Mar-2004.) (Revised by Mario Carneiro, 25-Jun-2015.)

Hypotheses
Ref Expression
hta.1  |-  A  =  { x  |  (
ph  /\  A. y
( [. y  /  x ]. ph  ->  ( rank `  x )  C_  ( rank `  y ) ) ) }
hta.2  |-  B  =  ( iota_ z  e.  A  A. w  e.  A  -.  w R z )
Assertion
Ref Expression
hta  |-  ( R  We  A  ->  ( ph  ->  [. B  /  x ]. ph ) )
Distinct variable groups:    x, y    z, w, A    ph, y    w, R, z
Allowed substitution hints:    ph( x, z, w)    A( x, y)    B( x, y, z, w)    R( x, y)

Proof of Theorem hta
StepHypRef Expression
1 19.8a 1912 . . 3  |-  ( ph  ->  E. x ph )
2 scott0s 8304 . . . 4  |-  ( E. x ph  <->  { x  |  ( ph  /\  A. y ( [. y  /  x ]. ph  ->  (
rank `  x )  C_  ( rank `  y
) ) ) }  =/=  (/) )
3 hta.1 . . . . 5  |-  A  =  { x  |  (
ph  /\  A. y
( [. y  /  x ]. ph  ->  ( rank `  x )  C_  ( rank `  y ) ) ) }
43neeq1i 2659 . . . 4  |-  ( A  =/=  (/)  <->  { x  |  (
ph  /\  A. y
( [. y  /  x ]. ph  ->  ( rank `  x )  C_  ( rank `  y ) ) ) }  =/=  (/) )
52, 4bitr4i 255 . . 3  |-  ( E. x ph  <->  A  =/=  (/) )
61, 5sylib 199 . 2  |-  ( ph  ->  A  =/=  (/) )
7 scottexs 8303 . . . . 5  |-  { x  |  ( ph  /\  A. y ( [. y  /  x ]. ph  ->  (
rank `  x )  C_  ( rank `  y
) ) ) }  e.  _V
83, 7eqeltri 2496 . . . 4  |-  A  e. 
_V
9 hta.2 . . . 4  |-  B  =  ( iota_ z  e.  A  A. w  e.  A  -.  w R z )
108, 9htalem 8312 . . 3  |-  ( ( R  We  A  /\  A  =/=  (/) )  ->  B  e.  A )
1110ex 435 . 2  |-  ( R  We  A  ->  ( A  =/=  (/)  ->  B  e.  A ) )
12 simpl 458 . . . . . 6  |-  ( (
ph  /\  A. y
( [. y  /  x ]. ph  ->  ( rank `  x )  C_  ( rank `  y ) ) )  ->  ph )
1312ss2abi 3469 . . . . 5  |-  { x  |  ( ph  /\  A. y ( [. y  /  x ]. ph  ->  (
rank `  x )  C_  ( rank `  y
) ) ) } 
C_  { x  | 
ph }
143, 13eqsstri 3430 . . . 4  |-  A  C_  { x  |  ph }
1514sseli 3396 . . 3  |-  ( B  e.  A  ->  B  e.  { x  |  ph } )
16 df-sbc 3236 . . 3  |-  ( [. B  /  x ]. ph  <->  B  e.  { x  |  ph }
)
1715, 16sylibr 215 . 2  |-  ( B  e.  A  ->  [. B  /  x ]. ph )
186, 11, 17syl56 35 1  |-  ( R  We  A  ->  ( ph  ->  [. B  /  x ]. ph ) )
Colors of variables: wff setvar class
Syntax hints:   -. wn 3    -> wi 4    /\ wa 370   A.wal 1435    = wceq 1437   E.wex 1657    e. wcel 1872   {cab 2408    =/= wne 2593   A.wral 2708   _Vcvv 3016   [.wsbc 3235    C_ wss 3372   (/)c0 3697   class class class wbr 4359    We wwe 4747   ` cfv 5537   iota_crio 6203   rankcrnk 8179
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1663  ax-4 1676  ax-5 1752  ax-6 1798  ax-7 1843  ax-8 1874  ax-9 1876  ax-10 1891  ax-11 1896  ax-12 1909  ax-13 2058  ax-ext 2402  ax-rep 4472  ax-sep 4482  ax-nul 4491  ax-pow 4538  ax-pr 4596  ax-un 6534  ax-reg 8053  ax-inf2 8092
This theorem depends on definitions:  df-bi 188  df-or 371  df-an 372  df-3or 983  df-3an 984  df-tru 1440  df-ex 1658  df-nf 1662  df-sb 1791  df-eu 2274  df-mo 2275  df-clab 2409  df-cleq 2415  df-clel 2418  df-nfc 2552  df-ne 2595  df-ral 2713  df-rex 2714  df-reu 2715  df-rmo 2716  df-rab 2717  df-v 3018  df-sbc 3236  df-csb 3332  df-dif 3375  df-un 3377  df-in 3379  df-ss 3386  df-pss 3388  df-nul 3698  df-if 3848  df-pw 3919  df-sn 3935  df-pr 3937  df-tp 3939  df-op 3941  df-uni 4156  df-int 4192  df-iun 4237  df-iin 4238  df-br 4360  df-opab 4419  df-mpt 4420  df-tr 4455  df-eprel 4700  df-id 4704  df-po 4710  df-so 4711  df-fr 4748  df-we 4750  df-xp 4795  df-rel 4796  df-cnv 4797  df-co 4798  df-dm 4799  df-rn 4800  df-res 4801  df-ima 4802  df-pred 5335  df-ord 5381  df-on 5382  df-lim 5383  df-suc 5384  df-iota 5501  df-fun 5539  df-fn 5540  df-f 5541  df-f1 5542  df-fo 5543  df-f1o 5544  df-fv 5545  df-riota 6204  df-om 6644  df-wrecs 6976  df-recs 7038  df-rdg 7076  df-r1 8180  df-rank 8181
This theorem is referenced by: (None)
  Copyright terms: Public domain W3C validator