Intuitionistic Logic Explorer < Previous   Next > Nearby theorems Mirrors  >  Home  >  ILE Home  >  Th. List  >  findes GIF version

Theorem findes 4524
 Description: Finite induction with explicit substitution. The first hypothesis is the basis and the second is the induction step. Theorem Schema 22 of [Suppes] p. 136. This is an alternative for Metamath 100 proof #74. (Contributed by Raph Levien, 9-Jul-2003.)
Hypotheses
Ref Expression
findes.1 [∅ / 𝑥]𝜑
findes.2 (𝑥 ∈ ω → (𝜑[suc 𝑥 / 𝑥]𝜑))
Assertion
Ref Expression
findes (𝑥 ∈ ω → 𝜑)

Proof of Theorem findes
Dummy variables 𝑦 𝑧 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 dfsbcq2 2915 . 2 (𝑧 = ∅ → ([𝑧 / 𝑥]𝜑[∅ / 𝑥]𝜑))
2 sbequ 1813 . 2 (𝑧 = 𝑦 → ([𝑧 / 𝑥]𝜑 ↔ [𝑦 / 𝑥]𝜑))
3 dfsbcq2 2915 . 2 (𝑧 = suc 𝑦 → ([𝑧 / 𝑥]𝜑[suc 𝑦 / 𝑥]𝜑))
4 sbequ12r 1746 . 2 (𝑧 = 𝑥 → ([𝑧 / 𝑥]𝜑𝜑))
5 findes.1 . 2 [∅ / 𝑥]𝜑
6 nfv 1509 . . . 4 𝑥 𝑦 ∈ ω
7 nfs1v 1913 . . . . 5 𝑥[𝑦 / 𝑥]𝜑
8 nfsbc1v 2930 . . . . 5 𝑥[suc 𝑦 / 𝑥]𝜑
97, 8nfim 1552 . . . 4 𝑥([𝑦 / 𝑥]𝜑[suc 𝑦 / 𝑥]𝜑)
106, 9nfim 1552 . . 3 𝑥(𝑦 ∈ ω → ([𝑦 / 𝑥]𝜑[suc 𝑦 / 𝑥]𝜑))
11 eleq1 2203 . . . 4 (𝑥 = 𝑦 → (𝑥 ∈ ω ↔ 𝑦 ∈ ω))
12 sbequ12 1745 . . . . 5 (𝑥 = 𝑦 → (𝜑 ↔ [𝑦 / 𝑥]𝜑))
13 suceq 4331 . . . . . 6 (𝑥 = 𝑦 → suc 𝑥 = suc 𝑦)
14 dfsbcq 2914 . . . . . 6 (suc 𝑥 = suc 𝑦 → ([suc 𝑥 / 𝑥]𝜑[suc 𝑦 / 𝑥]𝜑))
1513, 14syl 14 . . . . 5 (𝑥 = 𝑦 → ([suc 𝑥 / 𝑥]𝜑[suc 𝑦 / 𝑥]𝜑))
1612, 15imbi12d 233 . . . 4 (𝑥 = 𝑦 → ((𝜑[suc 𝑥 / 𝑥]𝜑) ↔ ([𝑦 / 𝑥]𝜑[suc 𝑦 / 𝑥]𝜑)))
1711, 16imbi12d 233 . . 3 (𝑥 = 𝑦 → ((𝑥 ∈ ω → (𝜑[suc 𝑥 / 𝑥]𝜑)) ↔ (𝑦 ∈ ω → ([𝑦 / 𝑥]𝜑[suc 𝑦 / 𝑥]𝜑))))
18 findes.2 . . 3 (𝑥 ∈ ω → (𝜑[suc 𝑥 / 𝑥]𝜑))
1910, 17, 18chvar 1731 . 2 (𝑦 ∈ ω → ([𝑦 / 𝑥]𝜑[suc 𝑦 / 𝑥]𝜑))
201, 2, 3, 4, 5, 19finds 4521 1 (𝑥 ∈ ω → 𝜑)
 Colors of variables: wff set class Syntax hints:   → wi 4   ↔ wb 104   = wceq 1332   ∈ wcel 1481  [wsb 1736  [wsbc 2912  ∅c0 3367  suc csuc 4294  ωcom 4511 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 1424  ax-7 1425  ax-gen 1426  ax-ie1 1470  ax-ie2 1471  ax-8 1483  ax-10 1484  ax-11 1485  ax-i12 1486  ax-bndl 1487  ax-4 1488  ax-13 1492  ax-14 1493  ax-17 1507  ax-i9 1511  ax-ial 1515  ax-i5r 1516  ax-ext 2122  ax-sep 4053  ax-nul 4061  ax-pow 4105  ax-pr 4138  ax-un 4362  ax-iinf 4509 This theorem depends on definitions:  df-bi 116  df-3an 965  df-tru 1335  df-nf 1438  df-sb 1737  df-clab 2127  df-cleq 2133  df-clel 2136  df-nfc 2271  df-ral 2422  df-rex 2423  df-v 2691  df-sbc 2913  df-dif 3077  df-un 3079  df-in 3081  df-ss 3088  df-nul 3368  df-pw 3516  df-sn 3537  df-pr 3538  df-uni 3744  df-int 3779  df-suc 4300  df-iom 4512 This theorem is referenced by: (None)
 Copyright terms: Public domain W3C validator