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

Theorem bj-bdfindis 11842
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 4415 for a proof of full induction in IZF. From this version, it is easy to prove bounded versions of finds 4415, finds2 4416, finds1 4417. (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 3966 . . . 4 ∅ ∈ V
3 bj-bdfindis.0 . . . 4 (𝑥 = ∅ → (𝜓𝜑))
41, 2, 3elabf2 11682 . . 3 (𝜓 → ∅ ∈ {𝑥𝜑})
5 bj-bdfindis.nf1 . . . . . 6 𝑥𝜒
6 bj-bdfindis.1 . . . . . 6 (𝑥 = 𝑦 → (𝜑𝜒))
75, 6elabf1 11681 . . . . 5 (𝑦 ∈ {𝑥𝜑} → 𝜒)
8 bj-bdfindis.nfsuc . . . . . 6 𝑥𝜃
9 vex 2622 . . . . . . 7 𝑦 ∈ V
109bj-sucex 11814 . . . . . 6 suc 𝑦 ∈ V
11 bj-bdfindis.suc . . . . . 6 (𝑥 = suc 𝑦 → (𝜃𝜑))
128, 10, 11elabf2 11682 . . . . 5 (𝜃 → suc 𝑦 ∈ {𝑥𝜑})
137, 12imim12i 58 . . . 4 ((𝜒𝜃) → (𝑦 ∈ {𝑥𝜑} → suc 𝑦 ∈ {𝑥𝜑}))
1413ralimi 2438 . . 3 (∀𝑦 ∈ ω (𝜒𝜃) → ∀𝑦 ∈ ω (𝑦 ∈ {𝑥𝜑} → suc 𝑦 ∈ {𝑥𝜑}))
15 bj-bdfindis.bd . . . . 5 BOUNDED 𝜑
1615bdcab 11740 . . . 4 BOUNDED {𝑥𝜑}
1716bdpeano5 11838 . . 3 ((∅ ∈ {𝑥𝜑} ∧ ∀𝑦 ∈ ω (𝑦 ∈ {𝑥𝜑} → suc 𝑦 ∈ {𝑥𝜑})) → ω ⊆ {𝑥𝜑})
184, 14, 17syl2an 283 . 2 ((𝜓 ∧ ∀𝑦 ∈ ω (𝜒𝜃)) → ω ⊆ {𝑥𝜑})
19 ssabral 3092 . 2 (ω ⊆ {𝑥𝜑} ↔ ∀𝑥 ∈ ω 𝜑)
2018, 19sylib 120 1 ((𝜓 ∧ ∀𝑦 ∈ ω (𝜒𝜃)) → ∀𝑥 ∈ ω 𝜑)
Colors of variables: wff set class
Syntax hints:  wi 4  wa 102   = wceq 1289  wnf 1394  wcel 1438  {cab 2074  wral 2359  wss 2999  c0 3286  suc csuc 4192  ωcom 4405  BOUNDED wbd 11703
This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-mp 7  ax-ia1 104  ax-ia2 105  ax-ia3 106  ax-in1 579  ax-in2 580  ax-io 665  ax-5 1381  ax-7 1382  ax-gen 1383  ax-ie1 1427  ax-ie2 1428  ax-8 1440  ax-10 1441  ax-11 1442  ax-i12 1443  ax-bndl 1444  ax-4 1445  ax-13 1449  ax-14 1450  ax-17 1464  ax-i9 1468  ax-ial 1472  ax-i5r 1473  ax-ext 2070  ax-nul 3965  ax-pr 4036  ax-un 4260  ax-bd0 11704  ax-bdor 11707  ax-bdex 11710  ax-bdeq 11711  ax-bdel 11712  ax-bdsb 11713  ax-bdsep 11775  ax-infvn 11836
This theorem depends on definitions:  df-bi 115  df-tru 1292  df-nf 1395  df-sb 1693  df-clab 2075  df-cleq 2081  df-clel 2084  df-nfc 2217  df-ral 2364  df-rex 2365  df-rab 2368  df-v 2621  df-dif 3001  df-un 3003  df-in 3005  df-ss 3012  df-nul 3287  df-sn 3452  df-pr 3453  df-uni 3654  df-int 3689  df-suc 4198  df-iom 4406  df-bdc 11732  df-bj-ind 11822
This theorem is referenced by:  bj-bdfindisg  11843  bj-bdfindes  11844  bj-nn0suc0  11845
  Copyright terms: Public domain W3C validator