Theorem bj-bdfindis 10072

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 4323 for a proof of full induction in IZF. From this version, it is easy to prove bounded versions of finds 4323, finds2 4324, finds1 4325. (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 3884	. . . 4 |- (/) e. _V
3		bj-bdfindis.0	. . . 4 |- ( x = (/) -> ( ps -> ph ) )
4	1, 2, 3	elabf2 9921	. . 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 9920	. . . . 5 |- ( y e. { x | ph } -> ch )
8		bj-bdfindis.nfsuc	. . . . . 6 |- F/ x th
9		vex 2560	. . . . . . 7 |- y e. _V
10	9	bj-sucex 10043	. . . . . 6 |- suc y e. _V
11		bj-bdfindis.suc	. . . . . 6 |- ( x = suc y -> ( th -> ph ) )
12	8, 10, 11	elabf2 9921	. . . . 5 |- ( th -> suc y e. { x | ph } )
13	7, 12	imim12i 53	. . . 4 |- ( ( ch -> th ) -> ( y e. { x | ph } -> suc y e. { x | ph } ) )
14	13	ralimi 2384	. . 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 9969	. . . 4 |- BOUNDED { x | ph }
17	16	bdpeano5 10068	. . 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 273	. 2 |- ( ( ps /\ A. y e. om ( ch -> th ) ) -> om C_ { x | ph } )
19		ssabral 3011	. 2 |- ( om C_ { x | ph } <-> A. x e. om ph )
20	18, 19	sylib 127	1 |- ( ( ps /\ A. y e. om ( ch -> th ) ) -> A. x e. om ph )

Syntax hints:   -> wi 4   /\ wa 97   = wceq 1243   F/wnf 1349   e. wcel 1393   {cab 2026   A.wral 2306   C_ wss 2917   (/)c0 3224   suc csuc 4102   omcom 4313  BOUNDED wbd 9932

This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-mp 7  ax-ia1 99  ax-ia2 100  ax-ia3 101  ax-in1 544  ax-in2 545  ax-io 630  ax-5 1336  ax-7 1337  ax-gen 1338  ax-ie1 1382  ax-ie2 1383  ax-8 1395  ax-10 1396  ax-11 1397  ax-i12 1398  ax-bndl 1399  ax-4 1400  ax-13 1404  ax-14 1405  ax-17 1419  ax-i9 1423  ax-ial 1427  ax-i5r 1428  ax-ext 2022  ax-nul 3883  ax-pr 3944  ax-un 4170  ax-bd0 9933  ax-bdor 9936  ax-bdex 9939  ax-bdeq 9940  ax-bdel 9941  ax-bdsb 9942  ax-bdsep 10004  ax-infvn 10066

This theorem depends on definitions:  df-bi 110  df-tru 1246  df-nf 1350  df-sb 1646  df-clab 2027  df-cleq 2033  df-clel 2036  df-nfc 2167  df-ral 2311  df-rex 2312  df-rab 2315  df-v 2559  df-dif 2920  df-un 2922  df-in 2924  df-ss 2931  df-nul 3225  df-sn 3381  df-pr 3382  df-uni 3581  df-int 3616  df-suc 4108  df-iom 4314  df-bdc 9961  df-bj-ind 10051

This theorem is referenced by:  bj-bdfindisg  10073  bj-bdfindes  10074  bj-nn0suc0  10075