Theorem finds2 4444

Description: Principle of Finite Induction (inference schema), using implicit substitutions. The first three hypotheses establish the substitutions we need. The last two are the basis and the induction step. Theorem Schema 22 of [Suppes] p. 136. (Contributed by NM, 29-Nov-2002.)

Hypotheses

Ref	Expression
finds2.1	|- ( x = (/) -> ( ph <-> ps ) )
finds2.2	|- ( x = y -> ( ph <-> ch ) )
finds2.3	|- ( x = suc y -> ( ph <-> th ) )
finds2.4	|- ( ta -> ps )
finds2.5	|- ( y e. om -> ( ta -> ( ch -> th ) ) )

Assertion

Ref	Expression
finds2	|- ( x e. om -> ( ta -> ph ) )

Distinct variable groups:   x, y, ta   ps, x   ch, x   th, x   ph, y

Allowed substitution hints:   ph( x)   ps( y)   ch( y)   th( y)

Proof of Theorem finds2

Step	Hyp	Ref	Expression
1		finds2.4	. . . . 5 |- ( ta -> ps )
2		0ex 3987	. . . . . 6 |- (/) e. _V
3		finds2.1	. . . . . . 7 |- ( x = (/) -> ( ph <-> ps ) )
4	3	imbi2d 229	. . . . . 6 |- ( x = (/) -> ( ( ta -> ph ) <-> ( ta -> ps ) ) )
5	2, 4	elab 2774	. . . . 5 |- ( (/) e. { x | ( ta -> ph ) } <-> ( ta -> ps ) )
6	1, 5	mpbir 145	. . . 4 |- (/) e. { x | ( ta -> ph ) }
7		finds2.5	. . . . . . 7 |- ( y e. om -> ( ta -> ( ch -> th ) ) )
8	7	a2d 26	. . . . . 6 |- ( y e. om -> ( ( ta -> ch ) -> ( ta -> th ) ) )
9		vex 2636	. . . . . . 7 |- y e. _V
10		finds2.2	. . . . . . . 8 |- ( x = y -> ( ph <-> ch ) )
11	10	imbi2d 229	. . . . . . 7 |- ( x = y -> ( ( ta -> ph ) <-> ( ta -> ch ) ) )
12	9, 11	elab 2774	. . . . . 6 |- ( y e. { x | ( ta -> ph ) } <-> ( ta -> ch ) )
13	9	sucex 4344	. . . . . . 7 |- suc y e. _V
14		finds2.3	. . . . . . . 8 |- ( x = suc y -> ( ph <-> th ) )
15	14	imbi2d 229	. . . . . . 7 |- ( x = suc y -> ( ( ta -> ph ) <-> ( ta -> th ) ) )
16	13, 15	elab 2774	. . . . . 6 |- ( suc y e. { x | ( ta -> ph ) } <-> ( ta -> th ) )
17	8, 12, 16	3imtr4g 204	. . . . 5 |- ( y e. om -> ( y e. { x | ( ta -> ph ) } -> suc y e. { x | ( ta -> ph ) } ) )
18	17	rgen 2439	. . . 4 |- A. y e. om ( y e. { x | ( ta -> ph ) } -> suc y e. { x | ( ta -> ph ) } )
19		peano5 4441	. . . 4 |- ( ( (/) e. { x | ( ta -> ph ) } /\ A. y e. om ( y e. { x | ( ta -> ph ) } -> suc y e. { x | ( ta -> ph ) } ) ) -> om C_ { x | ( ta -> ph ) } )
20	6, 18, 19	mp2an 418	. . 3 |- om C_ { x | ( ta -> ph ) }
21	20	sseli 3035	. 2 |- ( x e. om -> x e. { x | ( ta -> ph ) } )
22		abid 2083	. 2 |- ( x e. { x | ( ta -> ph ) } <-> ( ta -> ph ) )
23	21, 22	sylib 121	1 |- ( x e. om -> ( ta -> ph ) )

Syntax hints:   -> wi 4   <-> wb 104   = wceq 1296   e. wcel 1445   {cab 2081   A.wral 2370   C_ wss 3013   (/)c0 3302   suc csuc 4216   omcom 4433

This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-mp 7  ax-ia1 105  ax-ia2 106  ax-ia3 107  ax-in1 582  ax-in2 583  ax-io 668  ax-5 1388  ax-7 1389  ax-gen 1390  ax-ie1 1434  ax-ie2 1435  ax-8 1447  ax-10 1448  ax-11 1449  ax-i12 1450  ax-bndl 1451  ax-4 1452  ax-13 1456  ax-14 1457  ax-17 1471  ax-i9 1475  ax-ial 1479  ax-i5r 1480  ax-ext 2077  ax-sep 3978  ax-nul 3986  ax-pow 4030  ax-pr 4060  ax-un 4284  ax-iinf 4431

This theorem depends on definitions:  df-bi 116  df-3an 929  df-tru 1299  df-nf 1402  df-sb 1700  df-clab 2082  df-cleq 2088  df-clel 2091  df-nfc 2224  df-ral 2375  df-rex 2376  df-v 2635  df-dif 3015  df-un 3017  df-in 3019  df-ss 3026  df-nul 3303  df-pw 3451  df-sn 3472  df-pr 3473  df-uni 3676  df-int 3711  df-suc 4222  df-iom 4434

This theorem is referenced by:  finds1  4445  frecrdg  6211  nnacl  6281  nnmcl  6282  nnacom  6285  nnaass  6286  nndi  6287  nnmass  6288  nnmsucr  6289  nnmcom  6290  nnsucsssuc  6293  nntri3or  6294  nnaordi  6307  nnaword  6310  nnmordi  6315  nnaordex  6326  fiintim  6719  prarloclem3  7153  frec2uzuzd  9958  frec2uzrdg  9965