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 2813 . . . . . . . . 9  |-  F/ y A. y  e.  x  ch
14 nfv 1754 . . . . . . . . 9  |-  F/ y
ph
1513, 14nfim 1978 . . . . . . . 8  |-  F/ y ( A. y  e.  x  ch  ->  ph )
16 vex 3090 . . . . . . . . . . . . 13  |-  y  e. 
_V
1716sucid 5521 . . . . . . . . . . . 12  |-  y  e. 
suc  y
181rspcv 3184 . . . . . . . . . . . 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 3032 . . . . . . . . . . . 12  |-  ( x  =  suc  y  -> 
( A. z  e.  x  [ z  /  x ] ph  <->  A. z  e.  suc  y [ z  /  x ] ph ) )
23 nfv 1754 . . . . . . . . . . . . . . 15  |-  F/ x ch
2423, 1sbie 2203 . . . . . . . . . . . . . 14  |-  ( [ y  /  x ] ph 
<->  ch )
25 sbequ 2171 . . . . . . . . . . . . . 14  |-  ( y  =  z  ->  ( [ y  /  x ] ph  <->  [ z  /  x ] ph ) )
2624, 25syl5bbr 262 . . . . . . . . . . . . 13  |-  ( y  =  z  ->  ( ch 
<->  [ z  /  x ] ph ) )
2726cbvralv 3062 . . . . . . . . . . . 12  |-  ( A. y  e.  x  ch  <->  A. z  e.  x  [
z  /  x ] ph )
28 cbvralsv 3073 . . . . . . . . . . . 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 2914 . . . . . . 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 1789    e. wcel 1870   A.wral 2782   E.wrex 2783   (/)c0 3767   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 1665  ax-4 1678  ax-5 1751  ax-6 1797  ax-7 1841  ax-8 1872  ax-9 1874  ax-10 1889  ax-11 1894  ax-12 1907  ax-13 2055  ax-ext 2407  ax-sep 4548  ax-nul 4556  ax-pr 4661  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 1660  df-nf 1664  df-sb 1790  df-eu 2270  df-mo 2271  df-clab 2415  df-cleq 2421  df-clel 2424  df-nfc 2579  df-ne 2627  df-ral 2787  df-rex 2788  df-rab 2791  df-v 3089  df-sbc 3306  df-dif 3445  df-un 3447  df-in 3449  df-ss 3456  df-pss 3458  df-nul 3768  df-if 3916  df-pw 3987  df-sn 4003  df-pr 4005  df-tp 4007  df-op 4009  df-uni 4223  df-br 4427  df-opab 4485  df-tr 4521  df-eprel 4765  df-po 4775  df-so 4776  df-fr 4813  df-we 4815  df-ord 5445  df-on 5446  df-lim 5447  df-suc 5448
This theorem is referenced by:  tfindsg  6701  tfindes  6703  tfinds3  6705  oa0r  7248  om0r  7249  om1r  7252  oe1m  7254  oeoalem  7305  r1sdom  8244  r1tr  8246  alephon  8498  alephcard  8499  alephordi  8503  rdgprc  30228
  Copyright terms: Public domain W3C validator