Users' Mathboxes Mathbox for BJ < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  ILE Home  >  Th. List  >   Mathboxes  >  bj-bdfindis GIF version

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 𝜑
bj-bdfindis.nf0 𝑥𝜓
bj-bdfindis.nf1 𝑥𝜒
bj-bdfindis.nfsuc 𝑥𝜃
bj-bdfindis.0 (𝑥 = ∅ → (𝜓𝜑))
bj-bdfindis.1 (𝑥 = 𝑦 → (𝜑𝜒))
bj-bdfindis.suc (𝑥 = suc 𝑦 → (𝜃𝜑))
Assertion
Ref Expression
bj-bdfindis ((𝜓 ∧ ∀𝑦 ∈ ω (𝜒𝜃)) → ∀𝑥 ∈ ω 𝜑)
Distinct variable groups:   𝑥,𝑦   𝜑,𝑦
Allowed substitution hints:   𝜑(𝑥)   𝜓(𝑥,𝑦)   𝜒(𝑥,𝑦)   𝜃(𝑥,𝑦)

Proof of Theorem bj-bdfindis
StepHypRef Expression
1 bj-bdfindis.nf0 . . . 4 𝑥𝜓
2 0ex 3884 . . . 4 ∅ ∈ V
3 bj-bdfindis.0 . . . 4 (𝑥 = ∅ → (𝜓𝜑))
41, 2, 3elabf2 9921 . . 3 (𝜓 → ∅ ∈ {𝑥𝜑})
5 bj-bdfindis.nf1 . . . . . 6 𝑥𝜒
6 bj-bdfindis.1 . . . . . 6 (𝑥 = 𝑦 → (𝜑𝜒))
75, 6elabf1 9920 . . . . 5 (𝑦 ∈ {𝑥𝜑} → 𝜒)
8 bj-bdfindis.nfsuc . . . . . 6 𝑥𝜃
9 vex 2560 . . . . . . 7 𝑦 ∈ V
109bj-sucex 10043 . . . . . 6 suc 𝑦 ∈ V
11 bj-bdfindis.suc . . . . . 6 (𝑥 = suc 𝑦 → (𝜃𝜑))
128, 10, 11elabf2 9921 . . . . 5 (𝜃 → suc 𝑦 ∈ {𝑥𝜑})
137, 12imim12i 53 . . . 4 ((𝜒𝜃) → (𝑦 ∈ {𝑥𝜑} → suc 𝑦 ∈ {𝑥𝜑}))
1413ralimi 2384 . . 3 (∀𝑦 ∈ ω (𝜒𝜃) → ∀𝑦 ∈ ω (𝑦 ∈ {𝑥𝜑} → suc 𝑦 ∈ {𝑥𝜑}))
15 bj-bdfindis.bd . . . . 5 BOUNDED 𝜑
1615bdcab 9969 . . . 4 BOUNDED {𝑥𝜑}
1716bdpeano5 10068 . . 3 ((∅ ∈ {𝑥𝜑} ∧ ∀𝑦 ∈ ω (𝑦 ∈ {𝑥𝜑} → suc 𝑦 ∈ {𝑥𝜑})) → ω ⊆ {𝑥𝜑})
184, 14, 17syl2an 273 . 2 ((𝜓 ∧ ∀𝑦 ∈ ω (𝜒𝜃)) → ω ⊆ {𝑥𝜑})
19 ssabral 3011 . 2 (ω ⊆ {𝑥𝜑} ↔ ∀𝑥 ∈ ω 𝜑)
2018, 19sylib 127 1 ((𝜓 ∧ ∀𝑦 ∈ ω (𝜒𝜃)) → ∀𝑥 ∈ ω 𝜑)
Colors of variables: wff set class
Syntax hints:  wi 4  wa 97   = wceq 1243  wnf 1349  wcel 1393  {cab 2026  wral 2306  wss 2917  c0 3224  suc csuc 4102  ωcom 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
  Copyright terms: Public domain W3C validator