Theorem finds 4571

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 step. Theorem Schema 22 of [Suppes] p. 136. This is Metamath 100 proof #74. (Contributed by NM, 14-Apr-1995.)

Hypotheses

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

Assertion

Ref	Expression
finds	|- ( A e. om -> ta )

Distinct variable groups:   x, y   x, A   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 finds

Step	Hyp	Ref	Expression
1		finds.5	. . . . 5 |- ps
2		0ex 4103	. . . . . 6 |- (/) e. _V
3		finds.1	. . . . . 6 |- ( x = (/) -> ( ph <-> ps ) )
4	2, 3	elab 2865	. . . . 5 |- ( (/) e. { x | ph } <-> ps )
5	1, 4	mpbir 145	. . . 4 |- (/) e. { x | ph }
6		finds.6	. . . . . 6 |- ( y e. om -> ( ch -> th ) )
7		vex 2724	. . . . . . 7 |- y e. _V
8		finds.2	. . . . . . 7 |- ( x = y -> ( ph <-> ch ) )
9	7, 8	elab 2865	. . . . . 6 |- ( y e. { x | ph } <-> ch )
10	7	sucex 4470	. . . . . . 7 |- suc y e. _V
11		finds.3	. . . . . . 7 |- ( x = suc y -> ( ph <-> th ) )
12	10, 11	elab 2865	. . . . . 6 |- ( suc y e. { x | ph } <-> th )
13	6, 9, 12	3imtr4g 204	. . . . 5 |- ( y e. om -> ( y e. { x | ph } -> suc y e. { x | ph } ) )
14	13	rgen 2517	. . . 4 |- A. y e. om ( y e. { x | ph } -> suc y e. { x | ph } )
15		peano5 4569	. . . 4 |- ( ( (/) e. { x | ph } /\ A. y e. om ( y e. { x | ph } -> suc y e. { x | ph } ) ) -> om C_ { x | ph } )
16	5, 14, 15	mp2an 423	. . 3 |- om C_ { x | ph }
17	16	sseli 3133	. 2 |- ( A e. om -> A e. { x | ph } )
18		finds.4	. . 3 |- ( x = A -> ( ph <-> ta ) )
19	18	elabg 2867	. 2 |- ( A e. om -> ( A e. { x | ph } <-> ta ) )
20	17, 19	mpbid 146	1 |- ( A e. om -> ta )

Syntax hints:   -> wi 4   <-> wb 104   = wceq 1342   e. wcel 2135   {cab 2150   A.wral 2442   C_ wss 3111   (/)c0 3404   suc csuc 4337   omcom 4561

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-ia1 105  ax-ia2 106  ax-ia3 107  ax-in1 604  ax-in2 605  ax-io 699  ax-5 1434  ax-7 1435  ax-gen 1436  ax-ie1 1480  ax-ie2 1481  ax-8 1491  ax-10 1492  ax-11 1493  ax-i12 1494  ax-bndl 1496  ax-4 1497  ax-17 1513  ax-i9 1517  ax-ial 1521  ax-i5r 1522  ax-13 2137  ax-14 2138  ax-ext 2146  ax-sep 4094  ax-nul 4102  ax-pow 4147  ax-pr 4181  ax-un 4405  ax-iinf 4559

This theorem depends on definitions:  df-bi 116  df-3an 969  df-tru 1345  df-nf 1448  df-sb 1750  df-clab 2151  df-cleq 2157  df-clel 2160  df-nfc 2295  df-ral 2447  df-rex 2448  df-v 2723  df-dif 3113  df-un 3115  df-in 3117  df-ss 3124  df-nul 3405  df-pw 3555  df-sn 3576  df-pr 3577  df-uni 3784  df-int 3819  df-suc 4343  df-iom 4562

This theorem is referenced by:  findes  4574  nn0suc  4575  elomssom  4576  ordom  4578  nndceq0  4589  0elnn  4590  omsinds  4593  nna0r  6437  nnm0r  6438  nnsucelsuc  6450  nneneq  6814  php5  6815  php5dom  6820  fidcenumlemrk  6910  fidcenumlemr  6911  nnnninfeq  7083  nnnninfeq2  7084  frec2uzltd  10328  frecuzrdgg  10341  seq3val  10383  seqvalcd  10384  omgadd  10704  zfz1iso  10740  ennnfonelemhom  12285  nninfsellemdc  13724