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

Theorem tfindes 6716
Description: Transfinite Induction with explicit substitution. The first hypothesis is the basis, the second is the induction step for successors, and the third is the induction step for limit ordinals. Theorem Schema 4 of [Suppes] p. 197. (Contributed by NM, 5-Mar-2004.)
Hypotheses
Ref Expression
tfindes.1  |-  [. (/)  /  x ]. ph
tfindes.2  |-  ( x  e.  On  ->  ( ph  ->  [. suc  x  /  x ]. ph ) )
tfindes.3  |-  ( Lim  y  ->  ( A. x  e.  y  ph  ->  [. y  /  x ]. ph ) )
Assertion
Ref Expression
tfindes  |-  ( x  e.  On  ->  ph )
Distinct variable groups:    x, y    ph, y
Allowed substitution hint:    ph( x)

Proof of Theorem tfindes
Dummy variable  z is distinct from all other variables.
StepHypRef Expression
1 dfsbcq 3281 . 2  |-  ( y  =  (/)  ->  ( [. y  /  x ]. ph  <->  [. (/)  /  x ]. ph ) )
2 dfsbcq 3281 . 2  |-  ( y  =  z  ->  ( [. y  /  x ]. ph  <->  [. z  /  x ]. ph ) )
3 dfsbcq 3281 . 2  |-  ( y  =  suc  z  -> 
( [. y  /  x ]. ph  <->  [. suc  z  /  x ]. ph ) )
4 sbceq2a 3291 . 2  |-  ( y  =  x  ->  ( [. y  /  x ]. ph  <->  ph ) )
5 tfindes.1 . 2  |-  [. (/)  /  x ]. ph
6 nfv 1772 . . . 4  |-  F/ x  z  e.  On
7 nfsbc1v 3299 . . . . 5  |-  F/ x [. z  /  x ]. ph
8 nfsbc1v 3299 . . . . 5  |-  F/ x [. suc  z  /  x ]. ph
97, 8nfim 2014 . . . 4  |-  F/ x
( [. z  /  x ]. ph  ->  [. suc  z  /  x ]. ph )
106, 9nfim 2014 . . 3  |-  F/ x
( z  e.  On  ->  ( [. z  /  x ]. ph  ->  [. suc  z  /  x ]. ph )
)
11 eleq1 2528 . . . 4  |-  ( x  =  z  ->  (
x  e.  On  <->  z  e.  On ) )
12 sbceq1a 3290 . . . . 5  |-  ( x  =  z  ->  ( ph 
<-> 
[. z  /  x ]. ph ) )
13 suceq 5507 . . . . . 6  |-  ( x  =  z  ->  suc  x  =  suc  z )
1413sbceq1d 3284 . . . . 5  |-  ( x  =  z  ->  ( [. suc  x  /  x ]. ph  <->  [. suc  z  /  x ]. ph ) )
1512, 14imbi12d 326 . . . 4  |-  ( x  =  z  ->  (
( ph  ->  [. suc  x  /  x ]. ph )  <->  (
[. z  /  x ]. ph  ->  [. suc  z  /  x ]. ph )
) )
1611, 15imbi12d 326 . . 3  |-  ( x  =  z  ->  (
( x  e.  On  ->  ( ph  ->  [. suc  x  /  x ]. ph )
)  <->  ( z  e.  On  ->  ( [. z  /  x ]. ph  ->  [.
suc  z  /  x ]. ph ) ) ) )
17 tfindes.2 . . 3  |-  ( x  e.  On  ->  ( ph  ->  [. suc  x  /  x ]. ph ) )
1810, 16, 17chvar 2117 . 2  |-  ( z  e.  On  ->  ( [. z  /  x ]. ph  ->  [. suc  z  /  x ]. ph )
)
19 cbvralsv 3042 . . . 4  |-  ( A. x  e.  y  ph  <->  A. z  e.  y  [
z  /  x ] ph )
20 sbsbc 3283 . . . . 5  |-  ( [ z  /  x ] ph 
<-> 
[. z  /  x ]. ph )
2120ralbii 2831 . . . 4  |-  ( A. z  e.  y  [
z  /  x ] ph 
<-> 
A. z  e.  y 
[. z  /  x ]. ph )
2219, 21bitri 257 . . 3  |-  ( A. x  e.  y  ph  <->  A. z  e.  y  [. z  /  x ]. ph )
23 tfindes.3 . . 3  |-  ( Lim  y  ->  ( A. x  e.  y  ph  ->  [. y  /  x ]. ph ) )
2422, 23syl5bir 226 . 2  |-  ( Lim  y  ->  ( A. z  e.  y  [. z  /  x ]. ph  ->  [. y  /  x ]. ph ) )
251, 2, 3, 4, 5, 18, 24tfinds 6713 1  |-  ( x  e.  On  ->  ph )
Colors of variables: wff setvar class
Syntax hints:    -> wi 4   [wsb 1808    e. wcel 1898   A.wral 2749   [.wsbc 3279   (/)c0 3743   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 1680  ax-4 1693  ax-5 1769  ax-6 1816  ax-7 1862  ax-8 1900  ax-9 1907  ax-10 1926  ax-11 1931  ax-12 1944  ax-13 2102  ax-ext 2442  ax-sep 4539  ax-nul 4548  ax-pr 4653  ax-un 6610
This theorem depends on definitions:  df-bi 190  df-or 376  df-an 377  df-3or 992  df-3an 993  df-tru 1458  df-ex 1675  df-nf 1679  df-sb 1809  df-eu 2314  df-mo 2315  df-clab 2449  df-cleq 2455  df-clel 2458  df-nfc 2592  df-ne 2635  df-ral 2754  df-rex 2755  df-rab 2758  df-v 3059  df-sbc 3280  df-dif 3419  df-un 3421  df-in 3423  df-ss 3430  df-pss 3432  df-nul 3744  df-if 3894  df-pw 3965  df-sn 3981  df-pr 3983  df-tp 3985  df-op 3987  df-uni 4213  df-br 4417  df-opab 4476  df-tr 4512  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:  tfinds2  6717
  Copyright terms: Public domain W3C validator