New Foundations Explorer |
< Previous
Next >
Nearby theorems |
||
Mirrors > Home > NFE Home > Th. List > findsd | GIF version |
Description: Principle of finite induction over the finite cardinals, using implicit substitutions. The first hypothesis ensures stratification of φ, the next four set up the substitutions, and the last two set up the base case and induction hypothesis. This version allows for an extra deduction clause that may make proving stratification simpler. Compare Theorem X.1.13 of [Rosser] p. 277. (Contributed by SF, 31-Jul-2019.) |
Ref | Expression |
---|---|
findsd.1 | ⊢ (η → {x ∣ φ} ∈ V) |
findsd.2 | ⊢ (x = 0c → (φ ↔ ψ)) |
findsd.3 | ⊢ (x = y → (φ ↔ χ)) |
findsd.4 | ⊢ (x = (y +c 1c) → (φ ↔ θ)) |
findsd.5 | ⊢ (x = A → (φ ↔ τ)) |
findsd.6 | ⊢ (η → ψ) |
findsd.7 | ⊢ ((y ∈ Nn ∧ η) → (χ → θ)) |
Ref | Expression |
---|---|
findsd | ⊢ ((A ∈ Nn ∧ η) → τ) |
Step | Hyp | Ref | Expression |
---|---|---|---|
1 | findsd.1 | . . . . 5 ⊢ (η → {x ∣ φ} ∈ V) | |
2 | findsd.6 | . . . . . 6 ⊢ (η → ψ) | |
3 | 0cex 4392 | . . . . . . 7 ⊢ 0c ∈ V | |
4 | findsd.2 | . . . . . . 7 ⊢ (x = 0c → (φ ↔ ψ)) | |
5 | 3, 4 | elab 2985 | . . . . . 6 ⊢ (0c ∈ {x ∣ φ} ↔ ψ) |
6 | 2, 5 | sylibr 203 | . . . . 5 ⊢ (η → 0c ∈ {x ∣ φ}) |
7 | findsd.7 | . . . . . . . 8 ⊢ ((y ∈ Nn ∧ η) → (χ → θ)) | |
8 | vex 2862 | . . . . . . . . 9 ⊢ y ∈ V | |
9 | findsd.3 | . . . . . . . . 9 ⊢ (x = y → (φ ↔ χ)) | |
10 | 8, 9 | elab 2985 | . . . . . . . 8 ⊢ (y ∈ {x ∣ φ} ↔ χ) |
11 | 1cex 4142 | . . . . . . . . . 10 ⊢ 1c ∈ V | |
12 | 8, 11 | addcex 4394 | . . . . . . . . 9 ⊢ (y +c 1c) ∈ V |
13 | findsd.4 | . . . . . . . . 9 ⊢ (x = (y +c 1c) → (φ ↔ θ)) | |
14 | 12, 13 | elab 2985 | . . . . . . . 8 ⊢ ((y +c 1c) ∈ {x ∣ φ} ↔ θ) |
15 | 7, 10, 14 | 3imtr4g 261 | . . . . . . 7 ⊢ ((y ∈ Nn ∧ η) → (y ∈ {x ∣ φ} → (y +c 1c) ∈ {x ∣ φ})) |
16 | 15 | ancoms 439 | . . . . . 6 ⊢ ((η ∧ y ∈ Nn ) → (y ∈ {x ∣ φ} → (y +c 1c) ∈ {x ∣ φ})) |
17 | 16 | ralrimiva 2697 | . . . . 5 ⊢ (η → ∀y ∈ Nn (y ∈ {x ∣ φ} → (y +c 1c) ∈ {x ∣ φ})) |
18 | peano5 4409 | . . . . 5 ⊢ (({x ∣ φ} ∈ V ∧ 0c ∈ {x ∣ φ} ∧ ∀y ∈ Nn (y ∈ {x ∣ φ} → (y +c 1c) ∈ {x ∣ φ})) → Nn ⊆ {x ∣ φ}) | |
19 | 1, 6, 17, 18 | syl3anc 1182 | . . . 4 ⊢ (η → Nn ⊆ {x ∣ φ}) |
20 | 19 | sseld 3272 | . . 3 ⊢ (η → (A ∈ Nn → A ∈ {x ∣ φ})) |
21 | 20 | impcom 419 | . 2 ⊢ ((A ∈ Nn ∧ η) → A ∈ {x ∣ φ}) |
22 | findsd.5 | . . . 4 ⊢ (x = A → (φ ↔ τ)) | |
23 | 22 | elabg 2986 | . . 3 ⊢ (A ∈ Nn → (A ∈ {x ∣ φ} ↔ τ)) |
24 | 23 | adantr 451 | . 2 ⊢ ((A ∈ Nn ∧ η) → (A ∈ {x ∣ φ} ↔ τ)) |
25 | 21, 24 | mpbid 201 | 1 ⊢ ((A ∈ Nn ∧ η) → τ) |
Colors of variables: wff setvar class |
Syntax hints: → wi 4 ↔ wb 176 ∧ wa 358 = wceq 1642 ∈ wcel 1710 {cab 2339 ∀wral 2614 ⊆ wss 3257 1cc1c 4134 Nn cnnc 4373 0cc0c 4374 +c cplc 4375 |
This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1546 ax-5 1557 ax-17 1616 ax-9 1654 ax-8 1675 ax-6 1729 ax-7 1734 ax-11 1746 ax-12 1925 ax-ext 2334 ax-nin 4078 ax-xp 4079 ax-cnv 4080 ax-1c 4081 ax-sset 4082 ax-si 4083 ax-ins2 4084 ax-ins3 4085 ax-typlower 4086 ax-sn 4087 |
This theorem depends on definitions: df-bi 177 df-or 359 df-an 360 df-3an 936 df-nan 1288 df-tru 1319 df-ex 1542 df-nf 1545 df-sb 1649 df-clab 2340 df-cleq 2346 df-clel 2349 df-nfc 2478 df-ne 2518 df-ral 2619 df-rex 2620 df-v 2861 df-sbc 3047 df-nin 3211 df-compl 3212 df-in 3213 df-un 3214 df-dif 3215 df-symdif 3216 df-ss 3259 df-nul 3551 df-if 3663 df-pw 3724 df-sn 3741 df-pr 3742 df-uni 3892 df-int 3927 df-opk 4058 df-1c 4136 df-pw1 4137 df-uni1 4138 df-xpk 4185 df-cnvk 4186 df-ins2k 4187 df-ins3k 4188 df-imak 4189 df-cok 4190 df-p6 4191 df-sik 4192 df-ssetk 4193 df-imagek 4194 df-0c 4377 df-addc 4378 df-nnc 4379 |
This theorem is referenced by: finds 4411 preaddccan2 4455 addccan2nc 6265 fnfrec 6320 |
Copyright terms: Public domain | W3C validator |