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

Theorem tfinds 7292
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. (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 7280 . . . . 5 (Lim 𝑥 ↔ (Ord 𝑥 ∧ ¬ (𝑥 = ∅ ∨ ∃𝑦 ∈ On 𝑥 = suc 𝑦)))
43notbii 311 . . . 4 (¬ Lim 𝑥 ↔ ¬ (Ord 𝑥 ∧ ¬ (𝑥 = ∅ ∨ ∃𝑦 ∈ On 𝑥 = suc 𝑦)))
5 iman 390 . . . . 5 ((Ord 𝑥 → (𝑥 = ∅ ∨ ∃𝑦 ∈ On 𝑥 = suc 𝑦)) ↔ ¬ (Ord 𝑥 ∧ ¬ (𝑥 = ∅ ∨ ∃𝑦 ∈ On 𝑥 = suc 𝑦)))
6 eloni 5953 . . . . . . 7 (𝑥 ∈ On → Ord 𝑥)
7 pm2.27 42 . . . . . . 7 (Ord 𝑥 → ((Ord 𝑥 → (𝑥 = ∅ ∨ ∃𝑦 ∈ On 𝑥 = suc 𝑦)) → (𝑥 = ∅ ∨ ∃𝑦 ∈ On 𝑥 = suc 𝑦)))
86, 7syl 17 . . . . . 6 (𝑥 ∈ On → ((Ord 𝑥 → (𝑥 = ∅ ∨ ∃𝑦 ∈ On 𝑥 = suc 𝑦)) → (𝑥 = ∅ ∨ ∃𝑦 ∈ On 𝑥 = suc 𝑦)))
9 tfinds.5 . . . . . . . . 9 𝜓
10 tfinds.1 . . . . . . . . 9 (𝑥 = ∅ → (𝜑𝜓))
119, 10mpbiri 249 . . . . . . . 8 (𝑥 = ∅ → 𝜑)
1211a1d 25 . . . . . . 7 (𝑥 = ∅ → (∀𝑦𝑥 𝜒𝜑))
13 nfra1 3136 . . . . . . . . 9 𝑦𝑦𝑥 𝜒
14 nfv 2005 . . . . . . . . 9 𝑦𝜑
1513, 14nfim 1987 . . . . . . . 8 𝑦(∀𝑦𝑥 𝜒𝜑)
16 vex 3401 . . . . . . . . . . . . 13 𝑦 ∈ V
1716sucid 6023 . . . . . . . . . . . 12 𝑦 ∈ suc 𝑦
181rspcv 3505 . . . . . . . . . . . 12 (𝑦 ∈ suc 𝑦 → (∀𝑥 ∈ suc 𝑦𝜑𝜒))
1917, 18ax-mp 5 . . . . . . . . . . 11 (∀𝑥 ∈ suc 𝑦𝜑𝜒)
20 tfinds.6 . . . . . . . . . . 11 (𝑦 ∈ On → (𝜒𝜃))
2119, 20syl5 34 . . . . . . . . . 10 (𝑦 ∈ On → (∀𝑥 ∈ suc 𝑦𝜑𝜃))
22 raleq 3334 . . . . . . . . . . . 12 (𝑥 = suc 𝑦 → (∀𝑧𝑥 [𝑧 / 𝑥]𝜑 ↔ ∀𝑧 ∈ suc 𝑦[𝑧 / 𝑥]𝜑))
23 nfv 2005 . . . . . . . . . . . . . . 15 𝑥𝜒
2423, 1sbie 2569 . . . . . . . . . . . . . 14 ([𝑦 / 𝑥]𝜑𝜒)
25 sbequ 2537 . . . . . . . . . . . . . 14 (𝑦 = 𝑧 → ([𝑦 / 𝑥]𝜑 ↔ [𝑧 / 𝑥]𝜑))
2624, 25syl5bbr 276 . . . . . . . . . . . . 13 (𝑦 = 𝑧 → (𝜒 ↔ [𝑧 / 𝑥]𝜑))
2726cbvralv 3367 . . . . . . . . . . . 12 (∀𝑦𝑥 𝜒 ↔ ∀𝑧𝑥 [𝑧 / 𝑥]𝜑)
28 cbvralsv 3378 . . . . . . . . . . . 12 (∀𝑥 ∈ suc 𝑦𝜑 ↔ ∀𝑧 ∈ suc 𝑦[𝑧 / 𝑥]𝜑)
2922, 27, 283bitr4g 305 . . . . . . . . . . 11 (𝑥 = suc 𝑦 → (∀𝑦𝑥 𝜒 ↔ ∀𝑥 ∈ suc 𝑦𝜑))
3029imbi1d 332 . . . . . . . . . 10 (𝑥 = suc 𝑦 → ((∀𝑦𝑥 𝜒𝜃) ↔ (∀𝑥 ∈ suc 𝑦𝜑𝜃)))
3121, 30syl5ibrcom 238 . . . . . . . . 9 (𝑦 ∈ On → (𝑥 = suc 𝑦 → (∀𝑦𝑥 𝜒𝜃)))
32 tfinds.3 . . . . . . . . . . 11 (𝑥 = suc 𝑦 → (𝜑𝜃))
3332biimprd 239 . . . . . . . . . 10 (𝑥 = suc 𝑦 → (𝜃𝜑))
3433a1i 11 . . . . . . . . 9 (𝑦 ∈ On → (𝑥 = suc 𝑦 → (𝜃𝜑)))
3531, 34syldd 72 . . . . . . . 8 (𝑦 ∈ On → (𝑥 = suc 𝑦 → (∀𝑦𝑥 𝜒𝜑)))
3615, 35rexlimi 3219 . . . . . . 7 (∃𝑦 ∈ On 𝑥 = suc 𝑦 → (∀𝑦𝑥 𝜒𝜑))
3712, 36jaoi 875 . . . . . 6 ((𝑥 = ∅ ∨ ∃𝑦 ∈ On 𝑥 = suc 𝑦) → (∀𝑦𝑥 𝜒𝜑))
388, 37syl6 35 . . . . 5 (𝑥 ∈ On → ((Ord 𝑥 → (𝑥 = ∅ ∨ ∃𝑦 ∈ On 𝑥 = suc 𝑦)) → (∀𝑦𝑥 𝜒𝜑)))
395, 38syl5bir 234 . . . 4 (𝑥 ∈ On → (¬ (Ord 𝑥 ∧ ¬ (𝑥 = ∅ ∨ ∃𝑦 ∈ On 𝑥 = suc 𝑦)) → (∀𝑦𝑥 𝜒𝜑)))
404, 39syl5bi 233 . . 3 (𝑥 ∈ On → (¬ Lim 𝑥 → (∀𝑦𝑥 𝜒𝜑)))
41 tfinds.7 . . 3 (Lim 𝑥 → (∀𝑦𝑥 𝜒𝜑))
4240, 41pm2.61d2 173 . 2 (𝑥 ∈ On → (∀𝑦𝑥 𝜒𝜑))
431, 2, 42tfis3 7290 1 (𝐴 ∈ On → 𝜏)
Colors of variables: wff setvar class
Syntax hints:  ¬ wn 3  wi 4  wb 197  wa 384  wo 865   = wceq 1637  [wsb 2061  wcel 2157  wral 3103  wrex 3104  c0 4123  Ord word 5942  Oncon0 5943  Lim wlim 5944  suc csuc 5945
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1877  ax-4 1894  ax-5 2001  ax-6 2069  ax-7 2105  ax-8 2159  ax-9 2166  ax-10 2186  ax-11 2202  ax-12 2215  ax-13 2422  ax-ext 2791  ax-sep 4982  ax-nul 4990  ax-pr 5103  ax-un 7182
This theorem depends on definitions:  df-bi 198  df-an 385  df-or 866  df-3or 1101  df-3an 1102  df-tru 1641  df-ex 1860  df-nf 1864  df-sb 2062  df-mo 2635  df-eu 2638  df-clab 2800  df-cleq 2806  df-clel 2809  df-nfc 2944  df-ne 2986  df-ral 3108  df-rex 3109  df-rab 3112  df-v 3400  df-sbc 3641  df-dif 3779  df-un 3781  df-in 3783  df-ss 3790  df-pss 3792  df-nul 4124  df-if 4287  df-pw 4360  df-sn 4378  df-pr 4380  df-tp 4382  df-op 4384  df-uni 4638  df-br 4852  df-opab 4914  df-tr 4954  df-eprel 5231  df-po 5239  df-so 5240  df-fr 5277  df-we 5279  df-ord 5946  df-on 5947  df-lim 5948  df-suc 5949
This theorem is referenced by:  tfindsg  7293  tfindes  7295  tfinds3  7297  oa0r  7858  om0r  7859  om1r  7863  oe1m  7865  oeoalem  7916  r1sdom  8887  r1tr  8889  alephon  9178  alephcard  9179  alephordi  9183  rdgprc  32025
  Copyright terms: Public domain W3C validator