![]() |
Mathbox for BJ |
< Previous
Next >
Nearby theorems |
|
Mirrors > Home > ILE Home > Th. List > Mathboxes > bj-bdfindis | GIF version |
Description: Bounded induction (principle of induction for bounded formulas), using implicit substitutions (the biconditional versions of the hypotheses are implicit substitutions, and we have weakened them to implications). Constructive proof (from CZF). See finds 4599 for a proof of full induction in IZF. From this version, it is easy to prove bounded versions of finds 4599, finds2 4600, finds1 4601. (Contributed by BJ, 21-Nov-2019.) (Proof modification is discouraged.) |
Ref | Expression |
---|---|
bj-bdfindis.bd | ⊢ BOUNDED 𝜑 |
bj-bdfindis.nf0 | ⊢ Ⅎ𝑥𝜓 |
bj-bdfindis.nf1 | ⊢ Ⅎ𝑥𝜒 |
bj-bdfindis.nfsuc | ⊢ Ⅎ𝑥𝜃 |
bj-bdfindis.0 | ⊢ (𝑥 = ∅ → (𝜓 → 𝜑)) |
bj-bdfindis.1 | ⊢ (𝑥 = 𝑦 → (𝜑 → 𝜒)) |
bj-bdfindis.suc | ⊢ (𝑥 = suc 𝑦 → (𝜃 → 𝜑)) |
Ref | Expression |
---|---|
bj-bdfindis | ⊢ ((𝜓 ∧ ∀𝑦 ∈ ω (𝜒 → 𝜃)) → ∀𝑥 ∈ ω 𝜑) |
Step | Hyp | Ref | Expression |
---|---|---|---|
1 | bj-bdfindis.nf0 | . . . 4 ⊢ Ⅎ𝑥𝜓 | |
2 | 0ex 4130 | . . . 4 ⊢ ∅ ∈ V | |
3 | bj-bdfindis.0 | . . . 4 ⊢ (𝑥 = ∅ → (𝜓 → 𝜑)) | |
4 | 1, 2, 3 | elabf2 14416 | . . 3 ⊢ (𝜓 → ∅ ∈ {𝑥 ∣ 𝜑}) |
5 | bj-bdfindis.nf1 | . . . . . 6 ⊢ Ⅎ𝑥𝜒 | |
6 | bj-bdfindis.1 | . . . . . 6 ⊢ (𝑥 = 𝑦 → (𝜑 → 𝜒)) | |
7 | 5, 6 | elabf1 14415 | . . . . 5 ⊢ (𝑦 ∈ {𝑥 ∣ 𝜑} → 𝜒) |
8 | bj-bdfindis.nfsuc | . . . . . 6 ⊢ Ⅎ𝑥𝜃 | |
9 | vex 2740 | . . . . . . 7 ⊢ 𝑦 ∈ V | |
10 | 9 | bj-sucex 14557 | . . . . . 6 ⊢ suc 𝑦 ∈ V |
11 | bj-bdfindis.suc | . . . . . 6 ⊢ (𝑥 = suc 𝑦 → (𝜃 → 𝜑)) | |
12 | 8, 10, 11 | elabf2 14416 | . . . . 5 ⊢ (𝜃 → suc 𝑦 ∈ {𝑥 ∣ 𝜑}) |
13 | 7, 12 | imim12i 59 | . . . 4 ⊢ ((𝜒 → 𝜃) → (𝑦 ∈ {𝑥 ∣ 𝜑} → suc 𝑦 ∈ {𝑥 ∣ 𝜑})) |
14 | 13 | ralimi 2540 | . . 3 ⊢ (∀𝑦 ∈ ω (𝜒 → 𝜃) → ∀𝑦 ∈ ω (𝑦 ∈ {𝑥 ∣ 𝜑} → suc 𝑦 ∈ {𝑥 ∣ 𝜑})) |
15 | bj-bdfindis.bd | . . . . 5 ⊢ BOUNDED 𝜑 | |
16 | 15 | bdcab 14483 | . . . 4 ⊢ BOUNDED {𝑥 ∣ 𝜑} |
17 | 16 | bdpeano5 14577 | . . 3 ⊢ ((∅ ∈ {𝑥 ∣ 𝜑} ∧ ∀𝑦 ∈ ω (𝑦 ∈ {𝑥 ∣ 𝜑} → suc 𝑦 ∈ {𝑥 ∣ 𝜑})) → ω ⊆ {𝑥 ∣ 𝜑}) |
18 | 4, 14, 17 | syl2an 289 | . 2 ⊢ ((𝜓 ∧ ∀𝑦 ∈ ω (𝜒 → 𝜃)) → ω ⊆ {𝑥 ∣ 𝜑}) |
19 | ssabral 3226 | . 2 ⊢ (ω ⊆ {𝑥 ∣ 𝜑} ↔ ∀𝑥 ∈ ω 𝜑) | |
20 | 18, 19 | sylib 122 | 1 ⊢ ((𝜓 ∧ ∀𝑦 ∈ ω (𝜒 → 𝜃)) → ∀𝑥 ∈ ω 𝜑) |
Colors of variables: wff set class |
Syntax hints: → wi 4 ∧ wa 104 = wceq 1353 Ⅎwnf 1460 ∈ wcel 2148 {cab 2163 ∀wral 2455 ⊆ wss 3129 ∅c0 3422 suc csuc 4365 ωcom 4589 BOUNDED wbd 14446 |
This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-ia1 106 ax-ia2 107 ax-ia3 108 ax-in1 614 ax-in2 615 ax-io 709 ax-5 1447 ax-7 1448 ax-gen 1449 ax-ie1 1493 ax-ie2 1494 ax-8 1504 ax-10 1505 ax-11 1506 ax-i12 1507 ax-bndl 1509 ax-4 1510 ax-17 1526 ax-i9 1530 ax-ial 1534 ax-i5r 1535 ax-13 2150 ax-14 2151 ax-ext 2159 ax-nul 4129 ax-pr 4209 ax-un 4433 ax-bd0 14447 ax-bdor 14450 ax-bdex 14453 ax-bdeq 14454 ax-bdel 14455 ax-bdsb 14456 ax-bdsep 14518 ax-infvn 14575 |
This theorem depends on definitions: df-bi 117 df-tru 1356 df-nf 1461 df-sb 1763 df-clab 2164 df-cleq 2170 df-clel 2173 df-nfc 2308 df-ral 2460 df-rex 2461 df-rab 2464 df-v 2739 df-dif 3131 df-un 3133 df-in 3135 df-ss 3142 df-nul 3423 df-sn 3598 df-pr 3599 df-uni 3810 df-int 3845 df-suc 4371 df-iom 4590 df-bdc 14475 df-bj-ind 14561 |
This theorem is referenced by: bj-bdfindisg 14582 bj-bdfindes 14583 bj-nn0suc0 14584 |
Copyright terms: Public domain | W3C validator |