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

Theorem tfinds 6700
Description: Principle of Transfinite Induction (inference schema), using implicit substitutions. The first four hypotheses establish the substitutions we need. The last three are the basis, the induction step for successors, and the induction step for limit ordinals. Theorem Schema 4 of [Suppes] p. 197. (Contributed by NM, 16-Apr-1995.) (Proof shortened by Andrew Salmon, 27-Aug-2011.)
Hypotheses
Ref Expression
tfinds.1  |-  ( x  =  (/)  ->  ( ph  <->  ps ) )
tfinds.2  |-  ( x  =  y  ->  ( ph 
<->  ch ) )
tfinds.3  |-  ( x  =  suc  y  -> 
( ph  <->  th ) )
tfinds.4  |-  ( x  =  A  ->  ( ph 
<->  ta ) )
tfinds.5  |-  ps
tfinds.6  |-  ( y  e.  On  ->  ( ch  ->  th ) )
tfinds.7  |-  ( Lim  x  ->  ( A. y  e.  x  ch  ->  ph ) )
Assertion
Ref Expression
tfinds  |-  ( A  e.  On  ->  ta )
Distinct variable groups:    x, y    x, A    ch, x    ta, x    ph, y
Allowed substitution hints:    ph( x)    ps( x, y)    ch( y)    th( x, y)    ta( y)    A( y)

Proof of Theorem tfinds
Dummy variable  z is distinct from all other variables.
StepHypRef Expression
1 tfinds.2 . 2  |-  ( x  =  y  ->  ( ph 
<->  ch ) )
2 tfinds.4 . 2  |-  ( x  =  A  ->  ( ph 
<->  ta ) )
3 dflim3 6688 . . . . 5  |-  ( Lim  x  <->  ( Ord  x  /\  -.  ( x  =  (/)  \/  E. y  e.  On  x  =  suc  y ) ) )
43notbii 297 . . . 4  |-  ( -. 
Lim  x  <->  -.  ( Ord  x  /\  -.  (
x  =  (/)  \/  E. y  e.  On  x  =  suc  y ) ) )
5 iman 425 . . . . 5  |-  ( ( Ord  x  ->  (
x  =  (/)  \/  E. y  e.  On  x  =  suc  y ) )  <->  -.  ( Ord  x  /\  -.  ( x  =  (/)  \/ 
E. y  e.  On  x  =  suc  y ) ) )
6 eloni 5452 . . . . . . 7  |-  ( x  e.  On  ->  Ord  x )
7 pm2.27 40 . . . . . . 7  |-  ( Ord  x  ->  ( ( Ord  x  ->  ( x  =  (/)  \/  E. y  e.  On  x  =  suc  y ) )  -> 
( x  =  (/)  \/ 
E. y  e.  On  x  =  suc  y ) ) )
86, 7syl 17 . . . . . 6  |-  ( x  e.  On  ->  (
( Ord  x  ->  ( x  =  (/)  \/  E. y  e.  On  x  =  suc  y ) )  ->  ( x  =  (/)  \/  E. y  e.  On  x  =  suc  y ) ) )
9 tfinds.5 . . . . . . . . 9  |-  ps
10 tfinds.1 . . . . . . . . 9  |-  ( x  =  (/)  ->  ( ph  <->  ps ) )
119, 10mpbiri 236 . . . . . . . 8  |-  ( x  =  (/)  ->  ph )
1211a1d 26 . . . . . . 7  |-  ( x  =  (/)  ->  ( A. y  e.  x  ch  ->  ph ) )
13 nfra1 2803 . . . . . . . . 9  |-  F/ y A. y  e.  x  ch
14 nfv 1755 . . . . . . . . 9  |-  F/ y
ph
1513, 14nfim 1980 . . . . . . . 8  |-  F/ y ( A. y  e.  x  ch  ->  ph )
16 vex 3083 . . . . . . . . . . . . 13  |-  y  e. 
_V
1716sucid 5521 . . . . . . . . . . . 12  |-  y  e. 
suc  y
181rspcv 3178 . . . . . . . . . . . 12  |-  ( y  e.  suc  y  -> 
( A. x  e. 
suc  y ph  ->  ch ) )
1917, 18ax-mp 5 . . . . . . . . . . 11  |-  ( A. x  e.  suc  y ph  ->  ch )
20 tfinds.6 . . . . . . . . . . 11  |-  ( y  e.  On  ->  ( ch  ->  th ) )
2119, 20syl5 33 . . . . . . . . . 10  |-  ( y  e.  On  ->  ( A. x  e.  suc  y ph  ->  th )
)
22 raleq 3022 . . . . . . . . . . . 12  |-  ( x  =  suc  y  -> 
( A. z  e.  x  [ z  /  x ] ph  <->  A. z  e.  suc  y [ z  /  x ] ph ) )
23 nfv 1755 . . . . . . . . . . . . . . 15  |-  F/ x ch
2423, 1sbie 2206 . . . . . . . . . . . . . 14  |-  ( [ y  /  x ] ph 
<->  ch )
25 sbequ 2174 . . . . . . . . . . . . . 14  |-  ( y  =  z  ->  ( [ y  /  x ] ph  <->  [ z  /  x ] ph ) )
2624, 25syl5bbr 262 . . . . . . . . . . . . 13  |-  ( y  =  z  ->  ( ch 
<->  [ z  /  x ] ph ) )
2726cbvralv 3054 . . . . . . . . . . . 12  |-  ( A. y  e.  x  ch  <->  A. z  e.  x  [
z  /  x ] ph )
28 cbvralsv 3065 . . . . . . . . . . . 12  |-  ( A. x  e.  suc  y ph  <->  A. z  e.  suc  y [ z  /  x ] ph )
2922, 27, 283bitr4g 291 . . . . . . . . . . 11  |-  ( x  =  suc  y  -> 
( A. y  e.  x  ch  <->  A. x  e.  suc  y ph )
)
3029imbi1d 318 . . . . . . . . . 10  |-  ( x  =  suc  y  -> 
( ( A. y  e.  x  ch  ->  th )  <->  ( A. x  e.  suc  y ph  ->  th ) ) )
3121, 30syl5ibrcom 225 . . . . . . . . 9  |-  ( y  e.  On  ->  (
x  =  suc  y  ->  ( A. y  e.  x  ch  ->  th )
) )
32 tfinds.3 . . . . . . . . . . 11  |-  ( x  =  suc  y  -> 
( ph  <->  th ) )
3332biimprd 226 . . . . . . . . . 10  |-  ( x  =  suc  y  -> 
( th  ->  ph )
)
3433a1i 11 . . . . . . . . 9  |-  ( y  e.  On  ->  (
x  =  suc  y  ->  ( th  ->  ph )
) )
3531, 34syldd 68 . . . . . . . 8  |-  ( y  e.  On  ->  (
x  =  suc  y  ->  ( A. y  e.  x  ch  ->  ph )
) )
3615, 35rexlimi 2904 . . . . . . 7  |-  ( E. y  e.  On  x  =  suc  y  ->  ( A. y  e.  x  ch  ->  ph ) )
3712, 36jaoi 380 . . . . . 6  |-  ( ( x  =  (/)  \/  E. y  e.  On  x  =  suc  y )  -> 
( A. y  e.  x  ch  ->  ph )
)
388, 37syl6 34 . . . . 5  |-  ( x  e.  On  ->  (
( Ord  x  ->  ( x  =  (/)  \/  E. y  e.  On  x  =  suc  y ) )  ->  ( A. y  e.  x  ch  ->  ph ) ) )
395, 38syl5bir 221 . . . 4  |-  ( x  e.  On  ->  ( -.  ( Ord  x  /\  -.  ( x  =  (/)  \/ 
E. y  e.  On  x  =  suc  y ) )  ->  ( A. y  e.  x  ch  ->  ph ) ) )
404, 39syl5bi 220 . . 3  |-  ( x  e.  On  ->  ( -.  Lim  x  ->  ( A. y  e.  x  ch  ->  ph ) ) )
41 tfinds.7 . . 3  |-  ( Lim  x  ->  ( A. y  e.  x  ch  ->  ph ) )
4240, 41pm2.61d2 163 . 2  |-  ( x  e.  On  ->  ( A. y  e.  x  ch  ->  ph ) )
431, 2, 42tfis3 6698 1  |-  ( A  e.  On  ->  ta )
Colors of variables: wff setvar class
Syntax hints:   -. wn 3    -> wi 4    <-> wb 187    \/ wo 369    /\ wa 370    = wceq 1437   [wsb 1790    e. wcel 1872   A.wral 2771   E.wrex 2772   (/)c0 3761   Ord word 5441   Oncon0 5442   Lim wlim 5443   suc csuc 5444
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 2057  ax-ext 2401  ax-sep 4546  ax-nul 4555  ax-pr 4660  ax-un 6597
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 2273  df-mo 2274  df-clab 2408  df-cleq 2414  df-clel 2417  df-nfc 2568  df-ne 2616  df-ral 2776  df-rex 2777  df-rab 2780  df-v 3082  df-sbc 3300  df-dif 3439  df-un 3441  df-in 3443  df-ss 3450  df-pss 3452  df-nul 3762  df-if 3912  df-pw 3983  df-sn 3999  df-pr 4001  df-tp 4003  df-op 4005  df-uni 4220  df-br 4424  df-opab 4483  df-tr 4519  df-eprel 4764  df-po 4774  df-so 4775  df-fr 4812  df-we 4814  df-ord 5445  df-on 5446  df-lim 5447  df-suc 5448
This theorem is referenced by:  tfindsg  6701  tfindes  6703  tfinds3  6705  oa0r  7251  om0r  7252  om1r  7255  oe1m  7257  oeoalem  7308  r1sdom  8253  r1tr  8255  alephon  8507  alephcard  8508  alephordi  8512  rdgprc  30448
  Copyright terms: Public domain W3C validator