MPE Home Metamath Proof Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  MPE Home  >  Th. List  >  tfinds Structured version   Visualization version   GIF version

Theorem tfinds 7905
Description: Principle of Transfinite Induction (inference schema), using implicit substitutions. The first four hypotheses establish the substitutions we need. The last three are the basis, the induction step for successors, and the induction step for limit ordinals. Theorem Schema 4 of [Suppes] p. 197. Theorem 1.19 of [Schloeder] p. 3. (Contributed by NM, 16-Apr-1995.) (Proof shortened by Andrew Salmon, 27-Aug-2011.)
Hypotheses
Ref Expression
tfinds.1 (𝑥 = ∅ → (𝜑 ↔ 𝜓))
tfinds.2 (𝑥 = 𝑦 → (𝜑 ↔ 𝜒))
tfinds.3 (𝑥 = suc 𝑦 → (𝜑 ↔ 𝜃))
tfinds.4 (𝑥 = 𝐴 → (𝜑 ↔ 𝜏))
tfinds.5 𝜓
tfinds.6 (𝑦 ∈ On → (𝜒 → 𝜃))
tfinds.7 (Lim 𝑥 → (∀𝑦 ∈ 𝑥 𝜒 → 𝜑))
Assertion
Ref Expression
tfinds (𝐴 ∈ On → 𝜏)
Distinct variable groups:   𝑥,𝑦   𝑥,𝐴   𝜒,𝑥   𝜏,𝑥   𝜑,𝑦
Allowed substitution hints:   𝜑(𝑥)   𝜓(𝑥, 𝑦)   𝜒(𝑦)   𝜃(𝑥, 𝑦)   𝜏(𝑦)   𝐴(𝑦)

Proof of Theorem tfinds
Dummy variable 𝑧 is distinct from all other variables.
StepHypRef Expression
1 tfinds.2 . 2 (𝑥 = 𝑦 → (𝜑 ↔ 𝜒))
2 tfinds.4 . 2 (𝑥 = 𝐴 → (𝜑 ↔ 𝜏))
3 dflim3 7892 . . . . 5 (Lim 𝑥 ↔ (Ord 𝑥 ∧ ¬ (𝑥 = ∅ ∨ ∃𝑦 ∈ On 𝑥 = suc 𝑦)))
43notbii 323 . . . 4 (¬ Lim 𝑥 ↔ ¬ (Ord 𝑥 ∧ ¬ (𝑥 = ∅ ∨ ∃𝑦 ∈ On 𝑥 = suc 𝑦)))
5 iman 407 . . . . 5 ((Ord 𝑥 → (𝑥 = ∅ ∨ ∃𝑦 ∈ On 𝑥 = suc 𝑦)) ↔ ¬ (Ord 𝑥 ∧ ¬ (𝑥 = ∅ ∨ ∃𝑦 ∈ On 𝑥 = suc 𝑦)))
6 eloni 6398 . . . . . . 7 (𝑥 ∈ On → Ord 𝑥)
7 pm2.27 43 . . . . . . 7 (Ord 𝑥 → ((Ord 𝑥 → (𝑥 = ∅ ∨ ∃𝑦 ∈ On 𝑥 = suc 𝑦)) → (𝑥 = ∅ ∨ ∃𝑦 ∈ On 𝑥 = suc 𝑦)))
86, 7syl 18 . . . . . 6 (𝑥 ∈ On → ((Ord 𝑥 → (𝑥 = ∅ ∨ ∃𝑦 ∈ On 𝑥 = suc 𝑦)) → (𝑥 = ∅ ∨ ∃𝑦 ∈ On 𝑥 = suc 𝑦)))
9 tfinds.5 . . . . . . . . 9 𝜓
10 tfinds.1 . . . . . . . . 9 (𝑥 = ∅ → (𝜑 ↔ 𝜓))
119, 10mpbiri 261 . . . . . . . 8 (𝑥 = ∅ → 𝜑)
1211a1d 26 . . . . . . 7 (𝑥 = ∅ → (∀𝑦 ∈ 𝑥 𝜒 → 𝜑))
13 nfra1 3290 . . . . . . . . 9 Ⅎ𝑦∀𝑦 ∈ 𝑥 𝜒
14 nfv 1949 . . . . . . . . 9 Ⅎ𝑦𝜑
1513, 14nfim 1931 . . . . . . . 8 Ⅎ𝑦(∀𝑦 ∈ 𝑥 𝜒 → 𝜑)
16 vex 3458 . . . . . . . . . . . . 13 𝑦 ∈ V
1716sucid 6473 . . . . . . . . . . . 12 𝑦 ∈ suc 𝑦
181rspcv 3576 . . . . . . . . . . . 12 (𝑦 ∈ suc 𝑦 → (∀𝑥 ∈ suc 𝑦𝜑 → 𝜒))
1917, 18ax-mp 5 . . . . . . . . . . 11 (∀𝑥 ∈ suc 𝑦𝜑 → 𝜒)
20 tfinds.6 . . . . . . . . . . 11 (𝑦 ∈ On → (𝜒 → 𝜃))
2119, 20syl5 35 . . . . . . . . . 10 (𝑦 ∈ On → (∀𝑥 ∈ suc 𝑦𝜑 → 𝜃))
22 raleq 3320 . . . . . . . . . . . 12 (𝑥 = suc 𝑦 → (∀𝑧 ∈ 𝑥 [𝑧 / 𝑥]𝜑 ↔ ∀𝑧 ∈ suc 𝑦[𝑧 / 𝑥]𝜑))
23 nfv 1949 . . . . . . . . . . . . . . 15 Ⅎ𝑥𝜒
2423, 1sbiev 2349 . . . . . . . . . . . . . 14 ([𝑦 / 𝑥]𝜑 ↔ 𝜒)
25 sbequ 2122 . . . . . . . . . . . . . 14 (𝑦 = 𝑧 → ([𝑦 / 𝑥]𝜑 ↔ [𝑧 / 𝑥]𝜑))
2624, 25bitr3id 288 . . . . . . . . . . . . 13 (𝑦 = 𝑧 → (𝜒 ↔ [𝑧 / 𝑥]𝜑))
2726cbvralvw 3244 . . . . . . . . . . . 12 (∀𝑦 ∈ 𝑥 𝜒 ↔ ∀𝑧 ∈ 𝑥 [𝑧 / 𝑥]𝜑)
28 cbvralsvw 3317 . . . . . . . . . . . 12 (∀𝑥 ∈ suc 𝑦𝜑 ↔ ∀𝑧 ∈ suc 𝑦[𝑧 / 𝑥]𝜑)
2922, 27, 283bitr4g 317 . . . . . . . . . . 11 (𝑥 = suc 𝑦 → (∀𝑦 ∈ 𝑥 𝜒 ↔ ∀𝑥 ∈ suc 𝑦𝜑))
3029imbi1d 344 . . . . . . . . . 10 (𝑥 = suc 𝑦 → ((∀𝑦 ∈ 𝑥 𝜒 → 𝜃) ↔ (∀𝑥 ∈ suc 𝑦𝜑 → 𝜃)))
3121, 30syl5ibrcom 250 . . . . . . . . 9 (𝑦 ∈ On → (𝑥 = suc 𝑦 → (∀𝑦 ∈ 𝑥 𝜒 → 𝜃)))
32 tfinds.3 . . . . . . . . . . 11 (𝑥 = suc 𝑦 → (𝜑 ↔ 𝜃))
3332biimprd 251 . . . . . . . . . 10 (𝑥 = suc 𝑦 → (𝜃 → 𝜑))
3433a1i 11 . . . . . . . . 9 (𝑦 ∈ On → (𝑥 = suc 𝑦 → (𝜃 → 𝜑)))
3531, 34syldd 73 . . . . . . . 8 (𝑦 ∈ On → (𝑥 = suc 𝑦 → (∀𝑦 ∈ 𝑥 𝜒 → 𝜑)))
3615, 35rexlimi 3266 . . . . . . 7 (∃𝑦 ∈ On 𝑥 = suc 𝑦 → (∀𝑦 ∈ 𝑥 𝜒 → 𝜑))
3712, 36jaoi 871 . . . . . 6 ((𝑥 = ∅ ∨ ∃𝑦 ∈ On 𝑥 = suc 𝑦) → (∀𝑦 ∈ 𝑥 𝜒 → 𝜑))
388, 37syl6 36 . . . . 5 (𝑥 ∈ On → ((Ord 𝑥 → (𝑥 = ∅ ∨ ∃𝑦 ∈ On 𝑥 = suc 𝑦)) → (∀𝑦 ∈ 𝑥 𝜒 → 𝜑)))
395, 38biimtrrid 246 . . . 4 (𝑥 ∈ On → (¬ (Ord 𝑥 ∧ ¬ (𝑥 = ∅ ∨ ∃𝑦 ∈ On 𝑥 = suc 𝑦)) → (∀𝑦 ∈ 𝑥 𝜒 → 𝜑)))
404, 39biimtrid 245 . . 3 (𝑥 ∈ On → (¬ Lim 𝑥 → (∀𝑦 ∈ 𝑥 𝜒 → 𝜑)))
41 tfinds.7 . . 3 (Lim 𝑥 → (∀𝑦 ∈ 𝑥 𝜒 → 𝜑))
4240, 41pm2.61d2 183 . 2 (𝑥 ∈ On → (∀𝑦 ∈ 𝑥 𝜒 → 𝜑))
431, 2, 42tfis3 7903 1 (𝐴 ∈ On → 𝜏)
Colors of variables:    wff setvar class
This proof depends on syntax axioms:  ¬ wn 3   → wi 4   ↔ wb 209   ∧ wa 401   ∨ wo 861   = wceq 1570  [wsb 2101   ∈ wcel 2147  ∀wral 3080  ∃wrex 3090  ∅c0 4281  Ord word 6387  Oncon0 6388  Lim wlim 6389  suc csuc 6390
This proof depends on axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1828  ax-4 1842  ax-5 1945  ax-6 2002  ax-7 2043  ax-8 2149  ax-9 2157  ax-10 2180  ax-11 2197  ax-12 2216  ax-ext 2735  ax-sep 5255  ax-nul 5266  ax-pr 5398  ax-un 7783
This proof depends on definitions:  df-bi 210  df-an 402  df-or 862  df-3or 1104  df-3an 1105  df-tru 1573  df-fal 1583  df-ex 1813  df-nf 1817  df-sb 2102  df-clab 2742  df-cleq 2755  df-clel 2839  df-nfc 2913  df-ne 2960  df-ral 3081  df-rex 3091  df-rab 3417  df-v 3456  df-ss 3901  df-pss 4017  df-dif 4050  df-in 4094  df-un 4154  df-nul 4282  df-if 4486  df-pw 4562  df-sn 4589  df-pr 4591  df-op 4841  df-uni 4873  df-br 5109  df-opab 5174  df-tr 5219  df-eprel 5558  df-po 5566  df-so 5567  df-fr 5611  df-we 5613  df-ord 6391  df-on 6392  df-lim 6393  df-suc 6394
This theorem is used by:  tfindsg  7906  tfindes  7908  tfinds3  7910  oa0r  8584  om0r  8585  om1r  8589  oe1m  8591  oeoalem  8643  r1sdom  9818  r1tr  9820  alephon  10187  alephcard  10188  alephordi  10192  constrsscn  34483  constr01  34485  constrmon  34487  constrconj  34488  rdgprc  36771
  Copyright terms: Public domain W3C validator