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

Theorem findsg 4683
Description: Principle of Finite Induction (inference schema), using implicit substitutions. The first four hypotheses establish the substitutions we need. The last two are the basis and the induction hypothesis. The basis of this version is an arbitrary natural number  B instead of zero. (Contributed by NM, 16-Sep-1995.)
Hypotheses
Ref Expression
findsg.1  |-  ( x  =  B  ->  ( ph 
<->  ps ) )
findsg.2  |-  ( x  =  y  ->  ( ph 
<->  ch ) )
findsg.3  |-  ( x  =  suc  y  -> 
( ph  <->  th ) )
findsg.4  |-  ( x  =  A  ->  ( ph 
<->  ta ) )
findsg.5  |-  ( B  e.  om  ->  ps )
findsg.6  |-  ( ( ( y  e.  om  /\  B  e.  om )  /\  B  C_  y )  ->  ( ch  ->  th ) )
Assertion
Ref Expression
findsg  |-  ( ( ( A  e.  om  /\  B  e.  om )  /\  B  C_  A )  ->  ta )
Distinct variable groups:    x, A    x, y, B    ps, x    ch, x    th, x    ta, x    ph, y
Allowed substitution hints:    ph( x)    ps( y)    ch( y)    th( y)    ta( y)    A( y)

Proof of Theorem findsg
StepHypRef Expression
1 sseq2 3200 . . . . . . 7  |-  ( x  =  (/)  ->  ( B 
C_  x  <->  B  C_  (/) ) )
21adantl 452 . . . . . 6  |-  ( ( B  =  (/)  /\  x  =  (/) )  ->  ( B  C_  x  <->  B  C_  (/) ) )
3 eqeq2 2292 . . . . . . . 8  |-  ( B  =  (/)  ->  ( x  =  B  <->  x  =  (/) ) )
4 findsg.1 . . . . . . . 8  |-  ( x  =  B  ->  ( ph 
<->  ps ) )
53, 4syl6bir 220 . . . . . . 7  |-  ( B  =  (/)  ->  ( x  =  (/)  ->  ( ph  <->  ps ) ) )
65imp 418 . . . . . 6  |-  ( ( B  =  (/)  /\  x  =  (/) )  ->  ( ph 
<->  ps ) )
72, 6imbi12d 311 . . . . 5  |-  ( ( B  =  (/)  /\  x  =  (/) )  ->  (
( B  C_  x  ->  ph )  <->  ( B  C_  (/)  ->  ps ) ) )
81imbi1d 308 . . . . . 6  |-  ( x  =  (/)  ->  ( ( B  C_  x  ->  ph )  <->  ( B  C_  (/) 
->  ph ) ) )
9 ss0 3485 . . . . . . . . 9  |-  ( B 
C_  (/)  ->  B  =  (/) )
109con3i 127 . . . . . . . 8  |-  ( -.  B  =  (/)  ->  -.  B  C_  (/) )
1110pm2.21d 98 . . . . . . 7  |-  ( -.  B  =  (/)  ->  ( B  C_  (/)  ->  ( ph  <->  ps ) ) )
1211pm5.74d 238 . . . . . 6  |-  ( -.  B  =  (/)  ->  (
( B  C_  (/)  ->  ph )  <->  ( B  C_  (/)  ->  ps ) ) )
138, 12sylan9bbr 681 . . . . 5  |-  ( ( -.  B  =  (/)  /\  x  =  (/) )  -> 
( ( B  C_  x  ->  ph )  <->  ( B  C_  (/)  ->  ps ) ) )
147, 13pm2.61ian 765 . . . 4  |-  ( x  =  (/)  ->  ( ( B  C_  x  ->  ph )  <->  ( B  C_  (/) 
->  ps ) ) )
1514imbi2d 307 . . 3  |-  ( x  =  (/)  ->  ( ( B  e.  om  ->  ( B  C_  x  ->  ph ) )  <->  ( B  e.  om  ->  ( B  C_  (/)  ->  ps ) ) ) )
16 sseq2 3200 . . . . 5  |-  ( x  =  y  ->  ( B  C_  x  <->  B  C_  y
) )
17 findsg.2 . . . . 5  |-  ( x  =  y  ->  ( ph 
<->  ch ) )
1816, 17imbi12d 311 . . . 4  |-  ( x  =  y  ->  (
( B  C_  x  ->  ph )  <->  ( B  C_  y  ->  ch )
) )
1918imbi2d 307 . . 3  |-  ( x  =  y  ->  (
( B  e.  om  ->  ( B  C_  x  ->  ph ) )  <->  ( B  e.  om  ->  ( B  C_  y  ->  ch )
) ) )
20 sseq2 3200 . . . . 5  |-  ( x  =  suc  y  -> 
( B  C_  x  <->  B 
C_  suc  y )
)
21 findsg.3 . . . . 5  |-  ( x  =  suc  y  -> 
( ph  <->  th ) )
2220, 21imbi12d 311 . . . 4  |-  ( x  =  suc  y  -> 
( ( B  C_  x  ->  ph )  <->  ( B  C_ 
suc  y  ->  th )
) )
2322imbi2d 307 . . 3  |-  ( x  =  suc  y  -> 
( ( B  e. 
om  ->  ( B  C_  x  ->  ph ) )  <->  ( B  e.  om  ->  ( B  C_ 
suc  y  ->  th )
) ) )
24 sseq2 3200 . . . . 5  |-  ( x  =  A  ->  ( B  C_  x  <->  B  C_  A
) )
25 findsg.4 . . . . 5  |-  ( x  =  A  ->  ( ph 
<->  ta ) )
2624, 25imbi12d 311 . . . 4  |-  ( x  =  A  ->  (
( B  C_  x  ->  ph )  <->  ( B  C_  A  ->  ta )
) )
2726imbi2d 307 . . 3  |-  ( x  =  A  ->  (
( B  e.  om  ->  ( B  C_  x  ->  ph ) )  <->  ( B  e.  om  ->  ( B  C_  A  ->  ta )
) ) )
28 findsg.5 . . . 4  |-  ( B  e.  om  ->  ps )
2928a1d 22 . . 3  |-  ( B  e.  om  ->  ( B  C_  (/)  ->  ps )
)
30 vex 2791 . . . . . . . . . . . . . 14  |-  y  e. 
_V
3130sucex 4602 . . . . . . . . . . . . 13  |-  suc  y  e.  _V
3231eqvinc 2895 . . . . . . . . . . . 12  |-  ( suc  y  =  B  <->  E. x
( x  =  suc  y  /\  x  =  B ) )
3328, 4syl5ibr 212 . . . . . . . . . . . . . 14  |-  ( x  =  B  ->  ( B  e.  om  ->  ph ) )
3421biimpd 198 . . . . . . . . . . . . . 14  |-  ( x  =  suc  y  -> 
( ph  ->  th )
)
3533, 34sylan9r 639 . . . . . . . . . . . . 13  |-  ( ( x  =  suc  y  /\  x  =  B
)  ->  ( B  e.  om  ->  th )
)
3635exlimiv 1666 . . . . . . . . . . . 12  |-  ( E. x ( x  =  suc  y  /\  x  =  B )  ->  ( B  e.  om  ->  th ) )
3732, 36sylbi 187 . . . . . . . . . . 11  |-  ( suc  y  =  B  -> 
( B  e.  om  ->  th ) )
3837eqcoms 2286 . . . . . . . . . 10  |-  ( B  =  suc  y  -> 
( B  e.  om  ->  th ) )
3938imim2i 13 . . . . . . . . 9  |-  ( ( B  C_  suc  y  ->  B  =  suc  y )  ->  ( B  C_  suc  y  ->  ( B  e.  om  ->  th )
) )
4039a1d 22 . . . . . . . 8  |-  ( ( B  C_  suc  y  ->  B  =  suc  y )  ->  ( ( B 
C_  y  ->  ch )  ->  ( B  C_  suc  y  ->  ( B  e.  om  ->  th )
) ) )
4140com4r 80 . . . . . . 7  |-  ( B  e.  om  ->  (
( B  C_  suc  y  ->  B  =  suc  y )  ->  (
( B  C_  y  ->  ch )  ->  ( B  C_  suc  y  ->  th ) ) ) )
4241adantl 452 . . . . . 6  |-  ( ( y  e.  om  /\  B  e.  om )  ->  ( ( B  C_  suc  y  ->  B  =  suc  y )  -> 
( ( B  C_  y  ->  ch )  -> 
( B  C_  suc  y  ->  th ) ) ) )
43 df-ne 2448 . . . . . . . . 9  |-  ( B  =/=  suc  y  <->  -.  B  =  suc  y )
4443anbi2i 675 . . . . . . . 8  |-  ( ( B  C_  suc  y  /\  B  =/=  suc  y )  <->  ( B  C_  suc  y  /\  -.  B  =  suc  y ) )
45 annim 414 . . . . . . . 8  |-  ( ( B  C_  suc  y  /\  -.  B  =  suc  y )  <->  -.  ( B  C_  suc  y  ->  B  =  suc  y ) )
4644, 45bitri 240 . . . . . . 7  |-  ( ( B  C_  suc  y  /\  B  =/=  suc  y )  <->  -.  ( B  C_  suc  y  ->  B  =  suc  y ) )
47 nnon 4662 . . . . . . . . 9  |-  ( B  e.  om  ->  B  e.  On )
48 nnon 4662 . . . . . . . . 9  |-  ( y  e.  om  ->  y  e.  On )
49 onsssuc 4480 . . . . . . . . . 10  |-  ( ( B  e.  On  /\  y  e.  On )  ->  ( B  C_  y  <->  B  e.  suc  y ) )
50 suceloni 4604 . . . . . . . . . . 11  |-  ( y  e.  On  ->  suc  y  e.  On )
51 onelpss 4432 . . . . . . . . . . 11  |-  ( ( B  e.  On  /\  suc  y  e.  On )  ->  ( B  e. 
suc  y  <->  ( B  C_ 
suc  y  /\  B  =/=  suc  y ) ) )
5250, 51sylan2 460 . . . . . . . . . 10  |-  ( ( B  e.  On  /\  y  e.  On )  ->  ( B  e.  suc  y 
<->  ( B  C_  suc  y  /\  B  =/=  suc  y ) ) )
5349, 52bitrd 244 . . . . . . . . 9  |-  ( ( B  e.  On  /\  y  e.  On )  ->  ( B  C_  y  <->  ( B  C_  suc  y  /\  B  =/=  suc  y )
) )
5447, 48, 53syl2anr 464 . . . . . . . 8  |-  ( ( y  e.  om  /\  B  e.  om )  ->  ( B  C_  y  <->  ( B  C_  suc  y  /\  B  =/=  suc  y )
) )
55 findsg.6 . . . . . . . . . . . 12  |-  ( ( ( y  e.  om  /\  B  e.  om )  /\  B  C_  y )  ->  ( ch  ->  th ) )
5655ex 423 . . . . . . . . . . 11  |-  ( ( y  e.  om  /\  B  e.  om )  ->  ( B  C_  y  ->  ( ch  ->  th )
) )
57 ax-1 5 . . . . . . . . . . 11  |-  ( th 
->  ( B  C_  suc  y  ->  th ) )
5856, 57syl8 65 . . . . . . . . . 10  |-  ( ( y  e.  om  /\  B  e.  om )  ->  ( B  C_  y  ->  ( ch  ->  ( B  C_  suc  y  ->  th ) ) ) )
5958a2d 23 . . . . . . . . 9  |-  ( ( y  e.  om  /\  B  e.  om )  ->  ( ( B  C_  y  ->  ch )  -> 
( B  C_  y  ->  ( B  C_  suc  y  ->  th ) ) ) )
6059com23 72 . . . . . . . 8  |-  ( ( y  e.  om  /\  B  e.  om )  ->  ( B  C_  y  ->  ( ( B  C_  y  ->  ch )  -> 
( B  C_  suc  y  ->  th ) ) ) )
6154, 60sylbird 226 . . . . . . 7  |-  ( ( y  e.  om  /\  B  e.  om )  ->  ( ( B  C_  suc  y  /\  B  =/= 
suc  y )  -> 
( ( B  C_  y  ->  ch )  -> 
( B  C_  suc  y  ->  th ) ) ) )
6246, 61syl5bir 209 . . . . . 6  |-  ( ( y  e.  om  /\  B  e.  om )  ->  ( -.  ( B 
C_  suc  y  ->  B  =  suc  y )  ->  ( ( B 
C_  y  ->  ch )  ->  ( B  C_  suc  y  ->  th )
) ) )
6342, 62pm2.61d 150 . . . . 5  |-  ( ( y  e.  om  /\  B  e.  om )  ->  ( ( B  C_  y  ->  ch )  -> 
( B  C_  suc  y  ->  th ) ) )
6463ex 423 . . . 4  |-  ( y  e.  om  ->  ( B  e.  om  ->  ( ( B  C_  y  ->  ch )  ->  ( B  C_  suc  y  ->  th ) ) ) )
6564a2d 23 . . 3  |-  ( y  e.  om  ->  (
( B  e.  om  ->  ( B  C_  y  ->  ch ) )  -> 
( B  e.  om  ->  ( B  C_  suc  y  ->  th ) ) ) )
6615, 19, 23, 27, 29, 65finds 4682 . 2  |-  ( A  e.  om  ->  ( B  e.  om  ->  ( B  C_  A  ->  ta ) ) )
6766imp31 421 1  |-  ( ( ( A  e.  om  /\  B  e.  om )  /\  B  C_  A )  ->  ta )
Colors of variables: wff set class
Syntax hints:   -. wn 3    -> wi 4    <-> wb 176    /\ wa 358   E.wex 1528    = wceq 1623    e. wcel 1684    =/= wne 2446    C_ wss 3152   (/)c0 3455   Oncon0 4392   suc csuc 4394   omcom 4656
This theorem is referenced by:  nnaordi  6616  inf3lem5  7333  ackbij2lem4  7868  sornom  7903  fin23lem15  7960  fin23lem36  7974  isf32lem1  7979  isf32lem2  7980  wunex2  8360  indpi  8531
This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-3 7  ax-mp 8  ax-gen 1533  ax-5 1544  ax-17 1603  ax-9 1635  ax-8 1643  ax-13 1686  ax-14 1688  ax-6 1703  ax-7 1708  ax-11 1715  ax-12 1866  ax-ext 2264  ax-sep 4141  ax-nul 4149  ax-pr 4214  ax-un 4512
This theorem depends on definitions:  df-bi 177  df-or 359  df-an 360  df-3or 935  df-3an 936  df-tru 1310  df-ex 1529  df-nf 1532  df-sb 1630  df-eu 2147  df-mo 2148  df-clab 2270  df-cleq 2276  df-clel 2279  df-nfc 2408  df-ne 2448  df-ral 2548  df-rex 2549  df-rab 2552  df-v 2790  df-sbc 2992  df-dif 3155  df-un 3157  df-in 3159  df-ss 3166  df-pss 3168  df-nul 3456  df-if 3566  df-pw 3627  df-sn 3646  df-pr 3647  df-tp 3648  df-op 3649  df-uni 3828  df-br 4024  df-opab 4078  df-tr 4114  df-eprel 4305  df-po 4314  df-so 4315  df-fr 4352  df-we 4354  df-ord 4395  df-on 4396  df-lim 4397  df-suc 4398  df-om 4657
  Copyright terms: Public domain W3C validator