Theorem bj-bdfindis 15920

Description: Bounded induction (principle of induction for bounded formulas), using implicit substitutions (the biconditional versions of the hypotheses are implicit substitutions, and we have weakened them to implications). Constructive proof (from CZF). See finds 4649 for a proof of full induction in IZF. From this version, it is easy to prove bounded versions of finds 4649, finds2 4650, finds1 4651. (Contributed by BJ, 21-Nov-2019.) (Proof modification is discouraged.)

Hypotheses

Ref	Expression
bj-bdfindis.bd	|- BOUNDED ph
bj-bdfindis.nf0	|- F/ x ps
bj-bdfindis.nf1	|- F/ x ch
bj-bdfindis.nfsuc	|- F/ x th
bj-bdfindis.0	|- ( x = (/) -> ( ps -> ph ) )
bj-bdfindis.1	|- ( x = y -> ( ph -> ch ) )
bj-bdfindis.suc	|- ( x = suc y -> ( th -> ph ) )

Assertion

Ref	Expression
bj-bdfindis	|- ( ( ps /\ A. y e. om ( ch -> th ) ) -> A. x e. om ph )

Distinct variable groups:   x, y   ph, y

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

Proof of Theorem bj-bdfindis

Step	Hyp	Ref	Expression
1		bj-bdfindis.nf0	. . . 4 |- F/ x ps
2		0ex 4172	. . . 4 |- (/) e. _V
3		bj-bdfindis.0	. . . 4 |- ( x = (/) -> ( ps -> ph ) )
4	1, 2, 3	elabf2 15755	. . 3 |- ( ps -> (/) e. { x | ph } )
5		bj-bdfindis.nf1	. . . . . 6 |- F/ x ch
6		bj-bdfindis.1	. . . . . 6 |- ( x = y -> ( ph -> ch ) )
7	5, 6	elabf1 15754	. . . . 5 |- ( y e. { x | ph } -> ch )
8		bj-bdfindis.nfsuc	. . . . . 6 |- F/ x th
9		vex 2775	. . . . . . 7 |- y e. _V
10	9	bj-sucex 15896	. . . . . 6 |- suc y e. _V
11		bj-bdfindis.suc	. . . . . 6 |- ( x = suc y -> ( th -> ph ) )
12	8, 10, 11	elabf2 15755	. . . . 5 |- ( th -> suc y e. { x | ph } )
13	7, 12	imim12i 59	. . . 4 |- ( ( ch -> th ) -> ( y e. { x | ph } -> suc y e. { x | ph } ) )
14	13	ralimi 2569	. . 3 |- ( A. y e. om ( ch -> th ) -> A. y e. om ( y e. { x | ph } -> suc y e. { x | ph } ) )
15		bj-bdfindis.bd	. . . . 5 |- BOUNDED ph
16	15	bdcab 15822	. . . 4 |- BOUNDED { x | ph }
17	16	bdpeano5 15916	. . 3 |- ( ( (/) e. { x | ph } /\ A. y e. om ( y e. { x | ph } -> suc y e. { x | ph } ) ) -> om C_ { x | ph } )
18	4, 14, 17	syl2an 289	. 2 |- ( ( ps /\ A. y e. om ( ch -> th ) ) -> om C_ { x | ph } )
19		ssabral 3264	. 2 |- ( om C_ { x | ph } <-> A. x e. om ph )
20	18, 19	sylib 122	1 |- ( ( ps /\ A. y e. om ( ch -> th ) ) -> A. x e. om ph )

Syntax hints:   -> wi 4   /\ wa 104   = wceq 1373   F/wnf 1483   e. wcel 2176   {cab 2191   A.wral 2484   C_ wss 3166   (/)c0 3460   suc csuc 4413   omcom 4639  BOUNDED wbd 15785

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-ia1 106  ax-ia2 107  ax-ia3 108  ax-in1 615  ax-in2 616  ax-io 711  ax-5 1470  ax-7 1471  ax-gen 1472  ax-ie1 1516  ax-ie2 1517  ax-8 1527  ax-10 1528  ax-11 1529  ax-i12 1530  ax-bndl 1532  ax-4 1533  ax-17 1549  ax-i9 1553  ax-ial 1557  ax-i5r 1558  ax-13 2178  ax-14 2179  ax-ext 2187  ax-nul 4171  ax-pr 4254  ax-un 4481  ax-bd0 15786  ax-bdor 15789  ax-bdex 15792  ax-bdeq 15793  ax-bdel 15794  ax-bdsb 15795  ax-bdsep 15857  ax-infvn 15914

This theorem depends on definitions:  df-bi 117  df-tru 1376  df-nf 1484  df-sb 1786  df-clab 2192  df-cleq 2198  df-clel 2201  df-nfc 2337  df-ral 2489  df-rex 2490  df-rab 2493  df-v 2774  df-dif 3168  df-un 3170  df-in 3172  df-ss 3179  df-nul 3461  df-sn 3639  df-pr 3640  df-uni 3851  df-int 3886  df-suc 4419  df-iom 4640  df-bdc 15814  df-bj-ind 15900

This theorem is referenced by:  bj-bdfindisg  15921  bj-bdfindes  15922  bj-nn0suc0  15923