# Metamath Proof Explorer

## Theorem finds2

Description: Principle of Finite Induction (inference schema), using implicit substitutions. The first three hypotheses establish the substitutions we need. The last two are the basis and the induction step. Theorem Schema 22 of Suppes p. 136. (Contributed by NM, 29-Nov-2002)

Ref Expression
Hypotheses finds2.1 ${⊢}{x}=\varnothing \to \left({\phi }↔{\psi }\right)$
finds2.2 ${⊢}{x}={y}\to \left({\phi }↔{\chi }\right)$
finds2.3 ${⊢}{x}=\mathrm{suc}{y}\to \left({\phi }↔{\theta }\right)$
finds2.4 ${⊢}{\tau }\to {\psi }$
finds2.5 ${⊢}{y}\in \mathrm{\omega }\to \left({\tau }\to \left({\chi }\to {\theta }\right)\right)$
Assertion finds2 ${⊢}{x}\in \mathrm{\omega }\to \left({\tau }\to {\phi }\right)$

### Proof

Step Hyp Ref Expression
1 finds2.1 ${⊢}{x}=\varnothing \to \left({\phi }↔{\psi }\right)$
2 finds2.2 ${⊢}{x}={y}\to \left({\phi }↔{\chi }\right)$
3 finds2.3 ${⊢}{x}=\mathrm{suc}{y}\to \left({\phi }↔{\theta }\right)$
4 finds2.4 ${⊢}{\tau }\to {\psi }$
5 finds2.5 ${⊢}{y}\in \mathrm{\omega }\to \left({\tau }\to \left({\chi }\to {\theta }\right)\right)$
6 0ex ${⊢}\varnothing \in \mathrm{V}$
7 1 imbi2d ${⊢}{x}=\varnothing \to \left(\left({\tau }\to {\phi }\right)↔\left({\tau }\to {\psi }\right)\right)$
8 6 7 elab ${⊢}\varnothing \in \left\{{x}|\left({\tau }\to {\phi }\right)\right\}↔\left({\tau }\to {\psi }\right)$
9 4 8 mpbir ${⊢}\varnothing \in \left\{{x}|\left({\tau }\to {\phi }\right)\right\}$
10 5 a2d ${⊢}{y}\in \mathrm{\omega }\to \left(\left({\tau }\to {\chi }\right)\to \left({\tau }\to {\theta }\right)\right)$
11 vex ${⊢}{y}\in \mathrm{V}$
12 2 imbi2d ${⊢}{x}={y}\to \left(\left({\tau }\to {\phi }\right)↔\left({\tau }\to {\chi }\right)\right)$
13 11 12 elab ${⊢}{y}\in \left\{{x}|\left({\tau }\to {\phi }\right)\right\}↔\left({\tau }\to {\chi }\right)$
14 11 sucex ${⊢}\mathrm{suc}{y}\in \mathrm{V}$
15 3 imbi2d ${⊢}{x}=\mathrm{suc}{y}\to \left(\left({\tau }\to {\phi }\right)↔\left({\tau }\to {\theta }\right)\right)$
16 14 15 elab ${⊢}\mathrm{suc}{y}\in \left\{{x}|\left({\tau }\to {\phi }\right)\right\}↔\left({\tau }\to {\theta }\right)$
17 10 13 16 3imtr4g ${⊢}{y}\in \mathrm{\omega }\to \left({y}\in \left\{{x}|\left({\tau }\to {\phi }\right)\right\}\to \mathrm{suc}{y}\in \left\{{x}|\left({\tau }\to {\phi }\right)\right\}\right)$
18 17 rgen ${⊢}\forall {y}\in \mathrm{\omega }\phantom{\rule{.4em}{0ex}}\left({y}\in \left\{{x}|\left({\tau }\to {\phi }\right)\right\}\to \mathrm{suc}{y}\in \left\{{x}|\left({\tau }\to {\phi }\right)\right\}\right)$
19 peano5 ${⊢}\left(\varnothing \in \left\{{x}|\left({\tau }\to {\phi }\right)\right\}\wedge \forall {y}\in \mathrm{\omega }\phantom{\rule{.4em}{0ex}}\left({y}\in \left\{{x}|\left({\tau }\to {\phi }\right)\right\}\to \mathrm{suc}{y}\in \left\{{x}|\left({\tau }\to {\phi }\right)\right\}\right)\right)\to \mathrm{\omega }\subseteq \left\{{x}|\left({\tau }\to {\phi }\right)\right\}$
20 9 18 19 mp2an ${⊢}\mathrm{\omega }\subseteq \left\{{x}|\left({\tau }\to {\phi }\right)\right\}$
21 20 sseli ${⊢}{x}\in \mathrm{\omega }\to {x}\in \left\{{x}|\left({\tau }\to {\phi }\right)\right\}$
22 abid ${⊢}{x}\in \left\{{x}|\left({\tau }\to {\phi }\right)\right\}↔\left({\tau }\to {\phi }\right)$
23 21 22 sylib ${⊢}{x}\in \mathrm{\omega }\to \left({\tau }\to {\phi }\right)$