![]() |
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 4522 for a proof of full induction in IZF. From this version, it is easy to prove bounded versions of finds 4522, finds2 4523, finds1 4524. (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 4063 | . . . 4 ⊢ ∅ ∈ V | |
3 | bj-bdfindis.0 | . . . 4 ⊢ (𝑥 = ∅ → (𝜓 → 𝜑)) | |
4 | 1, 2, 3 | elabf2 13160 | . . 3 ⊢ (𝜓 → ∅ ∈ {𝑥 ∣ 𝜑}) |
5 | bj-bdfindis.nf1 | . . . . . 6 ⊢ Ⅎ𝑥𝜒 | |
6 | bj-bdfindis.1 | . . . . . 6 ⊢ (𝑥 = 𝑦 → (𝜑 → 𝜒)) | |
7 | 5, 6 | elabf1 13159 | . . . . 5 ⊢ (𝑦 ∈ {𝑥 ∣ 𝜑} → 𝜒) |
8 | bj-bdfindis.nfsuc | . . . . . 6 ⊢ Ⅎ𝑥𝜃 | |
9 | vex 2692 | . . . . . . 7 ⊢ 𝑦 ∈ V | |
10 | 9 | bj-sucex 13292 | . . . . . 6 ⊢ suc 𝑦 ∈ V |
11 | bj-bdfindis.suc | . . . . . 6 ⊢ (𝑥 = suc 𝑦 → (𝜃 → 𝜑)) | |
12 | 8, 10, 11 | elabf2 13160 | . . . . 5 ⊢ (𝜃 → suc 𝑦 ∈ {𝑥 ∣ 𝜑}) |
13 | 7, 12 | imim12i 59 | . . . 4 ⊢ ((𝜒 → 𝜃) → (𝑦 ∈ {𝑥 ∣ 𝜑} → suc 𝑦 ∈ {𝑥 ∣ 𝜑})) |
14 | 13 | ralimi 2498 | . . 3 ⊢ (∀𝑦 ∈ ω (𝜒 → 𝜃) → ∀𝑦 ∈ ω (𝑦 ∈ {𝑥 ∣ 𝜑} → suc 𝑦 ∈ {𝑥 ∣ 𝜑})) |
15 | bj-bdfindis.bd | . . . . 5 ⊢ BOUNDED 𝜑 | |
16 | 15 | bdcab 13218 | . . . 4 ⊢ BOUNDED {𝑥 ∣ 𝜑} |
17 | 16 | bdpeano5 13312 | . . 3 ⊢ ((∅ ∈ {𝑥 ∣ 𝜑} ∧ ∀𝑦 ∈ ω (𝑦 ∈ {𝑥 ∣ 𝜑} → suc 𝑦 ∈ {𝑥 ∣ 𝜑})) → ω ⊆ {𝑥 ∣ 𝜑}) |
18 | 4, 14, 17 | syl2an 287 | . 2 ⊢ ((𝜓 ∧ ∀𝑦 ∈ ω (𝜒 → 𝜃)) → ω ⊆ {𝑥 ∣ 𝜑}) |
19 | ssabral 3173 | . 2 ⊢ (ω ⊆ {𝑥 ∣ 𝜑} ↔ ∀𝑥 ∈ ω 𝜑) | |
20 | 18, 19 | sylib 121 | 1 ⊢ ((𝜓 ∧ ∀𝑦 ∈ ω (𝜒 → 𝜃)) → ∀𝑥 ∈ ω 𝜑) |
Colors of variables: wff set class |
Syntax hints: → wi 4 ∧ wa 103 = wceq 1332 Ⅎwnf 1437 ∈ wcel 1481 {cab 2126 ∀wral 2417 ⊆ wss 3076 ∅c0 3368 suc csuc 4295 ωcom 4512 BOUNDED wbd 13181 |
This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-ia1 105 ax-ia2 106 ax-ia3 107 ax-in1 604 ax-in2 605 ax-io 699 ax-5 1424 ax-7 1425 ax-gen 1426 ax-ie1 1470 ax-ie2 1471 ax-8 1483 ax-10 1484 ax-11 1485 ax-i12 1486 ax-bndl 1487 ax-4 1488 ax-13 1492 ax-14 1493 ax-17 1507 ax-i9 1511 ax-ial 1515 ax-i5r 1516 ax-ext 2122 ax-nul 4062 ax-pr 4139 ax-un 4363 ax-bd0 13182 ax-bdor 13185 ax-bdex 13188 ax-bdeq 13189 ax-bdel 13190 ax-bdsb 13191 ax-bdsep 13253 ax-infvn 13310 |
This theorem depends on definitions: df-bi 116 df-tru 1335 df-nf 1438 df-sb 1737 df-clab 2127 df-cleq 2133 df-clel 2136 df-nfc 2271 df-ral 2422 df-rex 2423 df-rab 2426 df-v 2691 df-dif 3078 df-un 3080 df-in 3082 df-ss 3089 df-nul 3369 df-sn 3538 df-pr 3539 df-uni 3745 df-int 3780 df-suc 4301 df-iom 4513 df-bdc 13210 df-bj-ind 13296 |
This theorem is referenced by: bj-bdfindisg 13317 bj-bdfindes 13318 bj-nn0suc0 13319 |
Copyright terms: Public domain | W3C validator |