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

Theorem hta 8393
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 1786 and weth 8950, using scottexs 8383 to establish the existence of 
A.

For a version of this theorem scheme using class (meta)variables instead of wff (meta)variables, see htalem 8392. (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 1945 . . 3  |-  ( ph  ->  E. x ph )
2 scott0s 8384 . . . 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 2699 . . . 4  |-  ( A  =/=  (/)  <->  { x  |  (
ph  /\  A. y
( [. y  /  x ]. ph  ->  ( rank `  x )  C_  ( rank `  y ) ) ) }  =/=  (/) )
52, 4bitr4i 260 . . 3  |-  ( E. x ph  <->  A  =/=  (/) )
61, 5sylib 201 . 2  |-  ( ph  ->  A  =/=  (/) )
7 scottexs 8383 . . . . 5  |-  { x  |  ( ph  /\  A. y ( [. y  /  x ]. ph  ->  (
rank `  x )  C_  ( rank `  y
) ) ) }  e.  _V
83, 7eqeltri 2535 . . . 4  |-  A  e. 
_V
9 hta.2 . . . 4  |-  B  =  ( iota_ z  e.  A  A. w  e.  A  -.  w R z )
108, 9htalem 8392 . . 3  |-  ( ( R  We  A  /\  A  =/=  (/) )  ->  B  e.  A )
1110ex 440 . 2  |-  ( R  We  A  ->  ( A  =/=  (/)  ->  B  e.  A ) )
12 simpl 463 . . . . . 6  |-  ( (
ph  /\  A. y
( [. y  /  x ]. ph  ->  ( rank `  x )  C_  ( rank `  y ) ) )  ->  ph )
1312ss2abi 3512 . . . . 5  |-  { x  |  ( ph  /\  A. y ( [. y  /  x ]. ph  ->  (
rank `  x )  C_  ( rank `  y
) ) ) } 
C_  { x  | 
ph }
143, 13eqsstri 3473 . . . 4  |-  A  C_  { x  |  ph }
1514sseli 3439 . . 3  |-  ( B  e.  A  ->  B  e.  { x  |  ph } )
16 df-sbc 3279 . . 3  |-  ( [. B  /  x ]. ph  <->  B  e.  { x  |  ph }
)
1715, 16sylibr 217 . 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 375   A.wal 1452    = wceq 1454   E.wex 1673    e. wcel 1897   {cab 2447    =/= wne 2632   A.wral 2748   _Vcvv 3056   [.wsbc 3278    C_ wss 3415   (/)c0 3742   class class class wbr 4415    We wwe 4810   ` cfv 5600   iota_crio 6275   rankcrnk 8259
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1679  ax-4 1692  ax-5 1768  ax-6 1815  ax-7 1861  ax-8 1899  ax-9 1906  ax-10 1925  ax-11 1930  ax-12 1943  ax-13 2101  ax-ext 2441  ax-rep 4528  ax-sep 4538  ax-nul 4547  ax-pow 4594  ax-pr 4652  ax-un 6609  ax-reg 8132  ax-inf2 8171
This theorem depends on definitions:  df-bi 190  df-or 376  df-an 377  df-3or 992  df-3an 993  df-tru 1457  df-ex 1674  df-nf 1678  df-sb 1808  df-eu 2313  df-mo 2314  df-clab 2448  df-cleq 2454  df-clel 2457  df-nfc 2591  df-ne 2634  df-ral 2753  df-rex 2754  df-reu 2755  df-rmo 2756  df-rab 2757  df-v 3058  df-sbc 3279  df-csb 3375  df-dif 3418  df-un 3420  df-in 3422  df-ss 3429  df-pss 3431  df-nul 3743  df-if 3893  df-pw 3964  df-sn 3980  df-pr 3982  df-tp 3984  df-op 3986  df-uni 4212  df-int 4248  df-iun 4293  df-iin 4294  df-br 4416  df-opab 4475  df-mpt 4476  df-tr 4511  df-eprel 4763  df-id 4767  df-po 4773  df-so 4774  df-fr 4811  df-we 4813  df-xp 4858  df-rel 4859  df-cnv 4860  df-co 4861  df-dm 4862  df-rn 4863  df-res 4864  df-ima 4865  df-pred 5398  df-ord 5444  df-on 5445  df-lim 5446  df-suc 5447  df-iota 5564  df-fun 5602  df-fn 5603  df-f 5604  df-f1 5605  df-fo 5606  df-f1o 5607  df-fv 5608  df-riota 6276  df-om 6719  df-wrecs 7053  df-recs 7115  df-rdg 7153  df-r1 8260  df-rank 8261
This theorem is referenced by: (None)
  Copyright terms: Public domain W3C validator