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

Theorem tfinds 7882
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 7869 . . . . 5 (Lim 𝑥 ↔ (Ord 𝑥 ∧ ¬ (𝑥 = ∅ ∨ ∃𝑦 ∈ On 𝑥 = suc 𝑦)))
43notbii 320 . . . 4 (¬ Lim 𝑥 ↔ ¬ (Ord 𝑥 ∧ ¬ (𝑥 = ∅ ∨ ∃𝑦 ∈ On 𝑥 = suc 𝑦)))
5 iman 401 . . . . 5 ((Ord 𝑥 → (𝑥 = ∅ ∨ ∃𝑦 ∈ On 𝑥 = suc 𝑦)) ↔ ¬ (Ord 𝑥 ∧ ¬ (𝑥 = ∅ ∨ ∃𝑦 ∈ On 𝑥 = suc 𝑦)))
6 eloni 6393 . . . . . . 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 258 . . . . . . . 8 (𝑥 = ∅ → 𝜑)
1211a1d 25 . . . . . . 7 (𝑥 = ∅ → (∀𝑦𝑥 𝜒𝜑))
13 nfra1 3283 . . . . . . . . 9 𝑦𝑦𝑥 𝜒
14 nfv 1913 . . . . . . . . 9 𝑦𝜑
1513, 14nfim 1895 . . . . . . . 8 𝑦(∀𝑦𝑥 𝜒𝜑)
16 vex 3483 . . . . . . . . . . . . 13 𝑦 ∈ V
1716sucid 6465 . . . . . . . . . . . 12 𝑦 ∈ suc 𝑦
181rspcv 3617 . . . . . . . . . . . 12 (𝑦 ∈ suc 𝑦 → (∀𝑥 ∈ suc 𝑦𝜑𝜒))
1917, 18ax-mp 5 . . . . . . . . . . 11 (∀𝑥 ∈ suc 𝑦𝜑𝜒)
20 tfinds.6 . . . . . . . . . . 11 (𝑦 ∈ On → (𝜒𝜃))
2119, 20syl5 34 . . . . . . . . . 10 (𝑦 ∈ On → (∀𝑥 ∈ suc 𝑦𝜑𝜃))
22 raleq 3322 . . . . . . . . . . . 12 (𝑥 = suc 𝑦 → (∀𝑧𝑥 [𝑧 / 𝑥]𝜑 ↔ ∀𝑧 ∈ suc 𝑦[𝑧 / 𝑥]𝜑))
23 nfv 1913 . . . . . . . . . . . . . . 15 𝑥𝜒
2423, 1sbiev 2313 . . . . . . . . . . . . . 14 ([𝑦 / 𝑥]𝜑𝜒)
25 sbequ 2082 . . . . . . . . . . . . . 14 (𝑦 = 𝑧 → ([𝑦 / 𝑥]𝜑 ↔ [𝑧 / 𝑥]𝜑))
2624, 25bitr3id 285 . . . . . . . . . . . . 13 (𝑦 = 𝑧 → (𝜒 ↔ [𝑧 / 𝑥]𝜑))
2726cbvralvw 3236 . . . . . . . . . . . 12 (∀𝑦𝑥 𝜒 ↔ ∀𝑧𝑥 [𝑧 / 𝑥]𝜑)
28 cbvralsvw 3316 . . . . . . . . . . . 12 (∀𝑥 ∈ suc 𝑦𝜑 ↔ ∀𝑧 ∈ suc 𝑦[𝑧 / 𝑥]𝜑)
2922, 27, 283bitr4g 314 . . . . . . . . . . 11 (𝑥 = suc 𝑦 → (∀𝑦𝑥 𝜒 ↔ ∀𝑥 ∈ suc 𝑦𝜑))
3029imbi1d 341 . . . . . . . . . 10 (𝑥 = suc 𝑦 → ((∀𝑦𝑥 𝜒𝜃) ↔ (∀𝑥 ∈ suc 𝑦𝜑𝜃)))
3121, 30syl5ibrcom 247 . . . . . . . . 9 (𝑦 ∈ On → (𝑥 = suc 𝑦 → (∀𝑦𝑥 𝜒𝜃)))
32 tfinds.3 . . . . . . . . . . 11 (𝑥 = suc 𝑦 → (𝜑𝜃))
3332biimprd 248 . . . . . . . . . 10 (𝑥 = suc 𝑦 → (𝜃𝜑))
3433a1i 11 . . . . . . . . 9 (𝑦 ∈ On → (𝑥 = suc 𝑦 → (𝜃𝜑)))
3531, 34syldd 72 . . . . . . . 8 (𝑦 ∈ On → (𝑥 = suc 𝑦 → (∀𝑦𝑥 𝜒𝜑)))
3615, 35rexlimi 3258 . . . . . . 7 (∃𝑦 ∈ On 𝑥 = suc 𝑦 → (∀𝑦𝑥 𝜒𝜑))
3712, 36jaoi 857 . . . . . 6 ((𝑥 = ∅ ∨ ∃𝑦 ∈ On 𝑥 = suc 𝑦) → (∀𝑦𝑥 𝜒𝜑))
388, 37syl6 35 . . . . 5 (𝑥 ∈ On → ((Ord 𝑥 → (𝑥 = ∅ ∨ ∃𝑦 ∈ On 𝑥 = suc 𝑦)) → (∀𝑦𝑥 𝜒𝜑)))
395, 38biimtrrid 243 . . . 4 (𝑥 ∈ On → (¬ (Ord 𝑥 ∧ ¬ (𝑥 = ∅ ∨ ∃𝑦 ∈ On 𝑥 = suc 𝑦)) → (∀𝑦𝑥 𝜒𝜑)))
404, 39biimtrid 242 . . 3 (𝑥 ∈ On → (¬ Lim 𝑥 → (∀𝑦𝑥 𝜒𝜑)))
41 tfinds.7 . . 3 (Lim 𝑥 → (∀𝑦𝑥 𝜒𝜑))
4240, 41pm2.61d2 181 . 2 (𝑥 ∈ On → (∀𝑦𝑥 𝜒𝜑))
431, 2, 42tfis3 7880 1 (𝐴 ∈ On → 𝜏)
Colors of variables: wff setvar class
Syntax hints:  ¬ wn 3  wi 4  wb 206  wa 395  wo 847   = wceq 1539  [wsb 2063  wcel 2107  wral 3060  wrex 3069  c0 4332  Ord word 6382  Oncon0 6383  Lim wlim 6384  suc csuc 6385
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1794  ax-4 1808  ax-5 1909  ax-6 1966  ax-7 2006  ax-8 2109  ax-9 2117  ax-10 2140  ax-11 2156  ax-12 2176  ax-ext 2707  ax-sep 5295  ax-nul 5305  ax-pr 5431  ax-un 7756
This theorem depends on definitions:  df-bi 207  df-an 396  df-or 848  df-3or 1087  df-3an 1088  df-tru 1542  df-fal 1552  df-ex 1779  df-nf 1783  df-sb 2064  df-clab 2714  df-cleq 2728  df-clel 2815  df-nfc 2891  df-ne 2940  df-ral 3061  df-rex 3070  df-rab 3436  df-v 3481  df-dif 3953  df-un 3955  df-in 3957  df-ss 3967  df-pss 3970  df-nul 4333  df-if 4525  df-pw 4601  df-sn 4626  df-pr 4628  df-op 4632  df-uni 4907  df-br 5143  df-opab 5205  df-tr 5259  df-eprel 5583  df-po 5591  df-so 5592  df-fr 5636  df-we 5638  df-ord 6386  df-on 6387  df-lim 6388  df-suc 6389
This theorem is referenced by:  tfindsg  7883  tfindes  7885  tfinds3  7887  oa0r  8577  om0r  8578  om1r  8582  oe1m  8584  oeoalem  8635  r1sdom  9815  r1tr  9817  alephon  10110  alephcard  10111  alephordi  10115  constrsscn  33782  constr01  33784  constrmon  33786  constrconj  33787  rdgprc  35796
  Copyright terms: Public domain W3C validator