Step | Hyp | Ref
| Expression |
1 | | ctinfom.f |
. . . 4
β’ (π β πΉ:Οβontoβπ΄) |
2 | | ctinfom.n |
. . . . . . 7
β’ π = frec((π₯ β β€ β¦ (π₯ + 1)), 0) |
3 | 2 | frechashgf1o 10427 |
. . . . . 6
β’ π:Οβ1-1-ontoββ0 |
4 | | f1ocnv 5474 |
. . . . . 6
β’ (π:Οβ1-1-ontoββ0 β β‘π:β0β1-1-ontoβΟ) |
5 | 3, 4 | ax-mp 5 |
. . . . 5
β’ β‘π:β0β1-1-ontoβΟ |
6 | | f1ofo 5468 |
. . . . 5
β’ (β‘π:β0β1-1-ontoβΟ β β‘π:β0βontoβΟ) |
7 | 5, 6 | ax-mp 5 |
. . . 4
β’ β‘π:β0βontoβΟ |
8 | | foco 5448 |
. . . 4
β’ ((πΉ:Οβontoβπ΄ β§ β‘π:β0βontoβΟ) β (πΉ β β‘π):β0βontoβπ΄) |
9 | 1, 7, 8 | sylancl 413 |
. . 3
β’ (π β (πΉ β β‘π):β0βontoβπ΄) |
10 | | ctinfom.g |
. . . 4
β’ πΊ = (πΉ β β‘π) |
11 | | foeq1 5434 |
. . . 4
β’ (πΊ = (πΉ β β‘π) β (πΊ:β0βontoβπ΄ β (πΉ β β‘π):β0βontoβπ΄)) |
12 | 10, 11 | ax-mp 5 |
. . 3
β’ (πΊ:β0βontoβπ΄ β (πΉ β β‘π):β0βontoβπ΄) |
13 | 9, 12 | sylibr 134 |
. 2
β’ (π β πΊ:β0βontoβπ΄) |
14 | | imaeq2 4966 |
. . . . . . . 8
β’ (π = suc (β‘πβπ) β (πΉ β π) = (πΉ β suc (β‘πβπ))) |
15 | 14 | eleq2d 2247 |
. . . . . . 7
β’ (π = suc (β‘πβπ) β ((πΉβπ) β (πΉ β π) β (πΉβπ) β (πΉ β suc (β‘πβπ)))) |
16 | 15 | notbid 667 |
. . . . . 6
β’ (π = suc (β‘πβπ) β (Β¬ (πΉβπ) β (πΉ β π) β Β¬ (πΉβπ) β (πΉ β suc (β‘πβπ)))) |
17 | 16 | rexbidv 2478 |
. . . . 5
β’ (π = suc (β‘πβπ) β (βπ β Ο Β¬ (πΉβπ) β (πΉ β π) β βπ β Ο Β¬ (πΉβπ) β (πΉ β suc (β‘πβπ)))) |
18 | | ctinfom.inf |
. . . . . 6
β’ (π β βπ β Ο βπ β Ο Β¬ (πΉβπ) β (πΉ β π)) |
19 | 18 | adantr 276 |
. . . . 5
β’ ((π β§ π β β0) β
βπ β Ο
βπ β Ο
Β¬ (πΉβπ) β (πΉ β π)) |
20 | | f1of 5461 |
. . . . . . . . 9
β’ (β‘π:β0β1-1-ontoβΟ β β‘π:β0βΆΟ) |
21 | 5, 20 | ax-mp 5 |
. . . . . . . 8
β’ β‘π:β0βΆΟ |
22 | 21 | a1i 9 |
. . . . . . 7
β’ ((π β§ π β β0) β β‘π:β0βΆΟ) |
23 | | simpr 110 |
. . . . . . 7
β’ ((π β§ π β β0) β π β
β0) |
24 | 22, 23 | ffvelcdmd 5652 |
. . . . . 6
β’ ((π β§ π β β0) β (β‘πβπ) β Ο) |
25 | | peano2 4594 |
. . . . . 6
β’ ((β‘πβπ) β Ο β suc (β‘πβπ) β Ο) |
26 | 24, 25 | syl 14 |
. . . . 5
β’ ((π β§ π β β0) β suc
(β‘πβπ) β Ο) |
27 | 17, 19, 26 | rspcdva 2846 |
. . . 4
β’ ((π β§ π β β0) β
βπ β Ο
Β¬ (πΉβπ) β (πΉ β suc (β‘πβπ))) |
28 | | f1of 5461 |
. . . . . . . 8
β’ (π:Οβ1-1-ontoββ0 β π:ΟβΆβ0) |
29 | 3, 28 | ax-mp 5 |
. . . . . . 7
β’ π:ΟβΆβ0 |
30 | 29 | a1i 9 |
. . . . . 6
β’ (((π β§ π β β0) β§ (π β Ο β§ Β¬
(πΉβπ) β (πΉ β suc (β‘πβπ)))) β π:ΟβΆβ0) |
31 | | simprl 529 |
. . . . . 6
β’ (((π β§ π β β0) β§ (π β Ο β§ Β¬
(πΉβπ) β (πΉ β suc (β‘πβπ)))) β π β Ο) |
32 | 30, 31 | ffvelcdmd 5652 |
. . . . 5
β’ (((π β§ π β β0) β§ (π β Ο β§ Β¬
(πΉβπ) β (πΉ β suc (β‘πβπ)))) β (πβπ) β
β0) |
33 | 10 | fveq1i 5516 |
. . . . . . . . . . 11
β’ (πΊβ(πβπ)) = ((πΉ β β‘π)β(πβπ)) |
34 | 32 | adantr 276 |
. . . . . . . . . . . 12
β’ ((((π β§ π β β0) β§ (π β Ο β§ Β¬
(πΉβπ) β (πΉ β suc (β‘πβπ)))) β§ π β (0...π)) β (πβπ) β
β0) |
35 | | fvco3 5587 |
. . . . . . . . . . . 12
β’ ((β‘π:β0βΆΟ β§
(πβπ) β β0) β ((πΉ β β‘π)β(πβπ)) = (πΉβ(β‘πβ(πβπ)))) |
36 | 21, 34, 35 | sylancr 414 |
. . . . . . . . . . 11
β’ ((((π β§ π β β0) β§ (π β Ο β§ Β¬
(πΉβπ) β (πΉ β suc (β‘πβπ)))) β§ π β (0...π)) β ((πΉ β β‘π)β(πβπ)) = (πΉβ(β‘πβ(πβπ)))) |
37 | 33, 36 | eqtrid 2222 |
. . . . . . . . . 10
β’ ((((π β§ π β β0) β§ (π β Ο β§ Β¬
(πΉβπ) β (πΉ β suc (β‘πβπ)))) β§ π β (0...π)) β (πΊβ(πβπ)) = (πΉβ(β‘πβ(πβπ)))) |
38 | 31 | adantr 276 |
. . . . . . . . . . 11
β’ ((((π β§ π β β0) β§ (π β Ο β§ Β¬
(πΉβπ) β (πΉ β suc (β‘πβπ)))) β§ π β (0...π)) β π β Ο) |
39 | | f1ocnvfv1 5777 |
. . . . . . . . . . . . 13
β’ ((π:Οβ1-1-ontoββ0 β§ π β Ο) β (β‘πβ(πβπ)) = π) |
40 | 3, 39 | mpan 424 |
. . . . . . . . . . . 12
β’ (π β Ο β (β‘πβ(πβπ)) = π) |
41 | 40 | fveq2d 5519 |
. . . . . . . . . . 11
β’ (π β Ο β (πΉβ(β‘πβ(πβπ))) = (πΉβπ)) |
42 | 38, 41 | syl 14 |
. . . . . . . . . 10
β’ ((((π β§ π β β0) β§ (π β Ο β§ Β¬
(πΉβπ) β (πΉ β suc (β‘πβπ)))) β§ π β (0...π)) β (πΉβ(β‘πβ(πβπ))) = (πΉβπ)) |
43 | 37, 42 | eqtrd 2210 |
. . . . . . . . 9
β’ ((((π β§ π β β0) β§ (π β Ο β§ Β¬
(πΉβπ) β (πΉ β suc (β‘πβπ)))) β§ π β (0...π)) β (πΊβ(πβπ)) = (πΉβπ)) |
44 | | simplrr 536 |
. . . . . . . . 9
β’ ((((π β§ π β β0) β§ (π β Ο β§ Β¬
(πΉβπ) β (πΉ β suc (β‘πβπ)))) β§ π β (0...π)) β Β¬ (πΉβπ) β (πΉ β suc (β‘πβπ))) |
45 | 43, 44 | eqneltrd 2273 |
. . . . . . . 8
β’ ((((π β§ π β β0) β§ (π β Ο β§ Β¬
(πΉβπ) β (πΉ β suc (β‘πβπ)))) β§ π β (0...π)) β Β¬ (πΊβ(πβπ)) β (πΉ β suc (β‘πβπ))) |
46 | | simpr 110 |
. . . . . . . . 9
β’
(((((π β§ π β β0)
β§ (π β Ο
β§ Β¬ (πΉβπ) β (πΉ β suc (β‘πβπ)))) β§ π β (0...π)) β§ (πΊβ(πβπ)) = (πΊβπ)) β (πΊβ(πβπ)) = (πΊβπ)) |
47 | 10 | fveq1i 5516 |
. . . . . . . . . . . 12
β’ (πΊβπ) = ((πΉ β β‘π)βπ) |
48 | | elfznn0 10113 |
. . . . . . . . . . . . . 14
β’ (π β (0...π) β π β β0) |
49 | 48 | adantl 277 |
. . . . . . . . . . . . 13
β’ ((((π β§ π β β0) β§ (π β Ο β§ Β¬
(πΉβπ) β (πΉ β suc (β‘πβπ)))) β§ π β (0...π)) β π β β0) |
50 | | fvco3 5587 |
. . . . . . . . . . . . 13
β’ ((β‘π:β0βΆΟ β§
π β
β0) β ((πΉ β β‘π)βπ) = (πΉβ(β‘πβπ))) |
51 | 21, 49, 50 | sylancr 414 |
. . . . . . . . . . . 12
β’ ((((π β§ π β β0) β§ (π β Ο β§ Β¬
(πΉβπ) β (πΉ β suc (β‘πβπ)))) β§ π β (0...π)) β ((πΉ β β‘π)βπ) = (πΉβ(β‘πβπ))) |
52 | 47, 51 | eqtrid 2222 |
. . . . . . . . . . 11
β’ ((((π β§ π β β0) β§ (π β Ο β§ Β¬
(πΉβπ) β (πΉ β suc (β‘πβπ)))) β§ π β (0...π)) β (πΊβπ) = (πΉβ(β‘πβπ))) |
53 | | elfzle2 10027 |
. . . . . . . . . . . . . . 15
β’ (π β (0...π) β π β€ π) |
54 | 53 | adantl 277 |
. . . . . . . . . . . . . 14
β’ ((((π β§ π β β0) β§ (π β Ο β§ Β¬
(πΉβπ) β (πΉ β suc (β‘πβπ)))) β§ π β (0...π)) β π β€ π) |
55 | | 0zd 9264 |
. . . . . . . . . . . . . . . 16
β’ ((((π β§ π β β0) β§ (π β Ο β§ Β¬
(πΉβπ) β (πΉ β suc (β‘πβπ)))) β§ π β (0...π)) β 0 β β€) |
56 | 21 | a1i 9 |
. . . . . . . . . . . . . . . . 17
β’ ((((π β§ π β β0) β§ (π β Ο β§ Β¬
(πΉβπ) β (πΉ β suc (β‘πβπ)))) β§ π β (0...π)) β β‘π:β0βΆΟ) |
57 | 56, 49 | ffvelcdmd 5652 |
. . . . . . . . . . . . . . . 16
β’ ((((π β§ π β β0) β§ (π β Ο β§ Β¬
(πΉβπ) β (πΉ β suc (β‘πβπ)))) β§ π β (0...π)) β (β‘πβπ) β Ο) |
58 | 24 | ad2antrr 488 |
. . . . . . . . . . . . . . . 16
β’ ((((π β§ π β β0) β§ (π β Ο β§ Β¬
(πΉβπ) β (πΉ β suc (β‘πβπ)))) β§ π β (0...π)) β (β‘πβπ) β Ο) |
59 | 55, 2, 57, 58 | frec2uzled 10428 |
. . . . . . . . . . . . . . 15
β’ ((((π β§ π β β0) β§ (π β Ο β§ Β¬
(πΉβπ) β (πΉ β suc (β‘πβπ)))) β§ π β (0...π)) β ((β‘πβπ) β (β‘πβπ) β (πβ(β‘πβπ)) β€ (πβ(β‘πβπ)))) |
60 | | f1ocnvfv2 5778 |
. . . . . . . . . . . . . . . . 17
β’ ((π:Οβ1-1-ontoββ0 β§ π β β0) β (πβ(β‘πβπ)) = π) |
61 | 3, 49, 60 | sylancr 414 |
. . . . . . . . . . . . . . . 16
β’ ((((π β§ π β β0) β§ (π β Ο β§ Β¬
(πΉβπ) β (πΉ β suc (β‘πβπ)))) β§ π β (0...π)) β (πβ(β‘πβπ)) = π) |
62 | 23 | ad2antrr 488 |
. . . . . . . . . . . . . . . . 17
β’ ((((π β§ π β β0) β§ (π β Ο β§ Β¬
(πΉβπ) β (πΉ β suc (β‘πβπ)))) β§ π β (0...π)) β π β β0) |
63 | | f1ocnvfv2 5778 |
. . . . . . . . . . . . . . . . 17
β’ ((π:Οβ1-1-ontoββ0 β§ π β β0) β (πβ(β‘πβπ)) = π) |
64 | 3, 62, 63 | sylancr 414 |
. . . . . . . . . . . . . . . 16
β’ ((((π β§ π β β0) β§ (π β Ο β§ Β¬
(πΉβπ) β (πΉ β suc (β‘πβπ)))) β§ π β (0...π)) β (πβ(β‘πβπ)) = π) |
65 | 61, 64 | breq12d 4016 |
. . . . . . . . . . . . . . 15
β’ ((((π β§ π β β0) β§ (π β Ο β§ Β¬
(πΉβπ) β (πΉ β suc (β‘πβπ)))) β§ π β (0...π)) β ((πβ(β‘πβπ)) β€ (πβ(β‘πβπ)) β π β€ π)) |
66 | 59, 65 | bitrd 188 |
. . . . . . . . . . . . . 14
β’ ((((π β§ π β β0) β§ (π β Ο β§ Β¬
(πΉβπ) β (πΉ β suc (β‘πβπ)))) β§ π β (0...π)) β ((β‘πβπ) β (β‘πβπ) β π β€ π)) |
67 | 54, 66 | mpbird 167 |
. . . . . . . . . . . . 13
β’ ((((π β§ π β β0) β§ (π β Ο β§ Β¬
(πΉβπ) β (πΉ β suc (β‘πβπ)))) β§ π β (0...π)) β (β‘πβπ) β (β‘πβπ)) |
68 | | nnsssuc 6502 |
. . . . . . . . . . . . . 14
β’ (((β‘πβπ) β Ο β§ (β‘πβπ) β Ο) β ((β‘πβπ) β (β‘πβπ) β (β‘πβπ) β suc (β‘πβπ))) |
69 | 57, 58, 68 | syl2anc 411 |
. . . . . . . . . . . . 13
β’ ((((π β§ π β β0) β§ (π β Ο β§ Β¬
(πΉβπ) β (πΉ β suc (β‘πβπ)))) β§ π β (0...π)) β ((β‘πβπ) β (β‘πβπ) β (β‘πβπ) β suc (β‘πβπ))) |
70 | 67, 69 | mpbid 147 |
. . . . . . . . . . . 12
β’ ((((π β§ π β β0) β§ (π β Ο β§ Β¬
(πΉβπ) β (πΉ β suc (β‘πβπ)))) β§ π β (0...π)) β (β‘πβπ) β suc (β‘πβπ)) |
71 | 1 | ad3antrrr 492 |
. . . . . . . . . . . . . . 15
β’ ((((π β§ π β β0) β§ (π β Ο β§ Β¬
(πΉβπ) β (πΉ β suc (β‘πβπ)))) β§ π β (0...π)) β πΉ:Οβontoβπ΄) |
72 | | fof 5438 |
. . . . . . . . . . . . . . 15
β’ (πΉ:Οβontoβπ΄ β πΉ:ΟβΆπ΄) |
73 | 71, 72 | syl 14 |
. . . . . . . . . . . . . 14
β’ ((((π β§ π β β0) β§ (π β Ο β§ Β¬
(πΉβπ) β (πΉ β suc (β‘πβπ)))) β§ π β (0...π)) β πΉ:ΟβΆπ΄) |
74 | 73 | ffund 5369 |
. . . . . . . . . . . . 13
β’ ((((π β§ π β β0) β§ (π β Ο β§ Β¬
(πΉβπ) β (πΉ β suc (β‘πβπ)))) β§ π β (0...π)) β Fun πΉ) |
75 | 73 | fdmd 5372 |
. . . . . . . . . . . . . 14
β’ ((((π β§ π β β0) β§ (π β Ο β§ Β¬
(πΉβπ) β (πΉ β suc (β‘πβπ)))) β§ π β (0...π)) β dom πΉ = Ο) |
76 | 57, 75 | eleqtrrd 2257 |
. . . . . . . . . . . . 13
β’ ((((π β§ π β β0) β§ (π β Ο β§ Β¬
(πΉβπ) β (πΉ β suc (β‘πβπ)))) β§ π β (0...π)) β (β‘πβπ) β dom πΉ) |
77 | | funfvima 5748 |
. . . . . . . . . . . . 13
β’ ((Fun
πΉ β§ (β‘πβπ) β dom πΉ) β ((β‘πβπ) β suc (β‘πβπ) β (πΉβ(β‘πβπ)) β (πΉ β suc (β‘πβπ)))) |
78 | 74, 76, 77 | syl2anc 411 |
. . . . . . . . . . . 12
β’ ((((π β§ π β β0) β§ (π β Ο β§ Β¬
(πΉβπ) β (πΉ β suc (β‘πβπ)))) β§ π β (0...π)) β ((β‘πβπ) β suc (β‘πβπ) β (πΉβ(β‘πβπ)) β (πΉ β suc (β‘πβπ)))) |
79 | 70, 78 | mpd 13 |
. . . . . . . . . . 11
β’ ((((π β§ π β β0) β§ (π β Ο β§ Β¬
(πΉβπ) β (πΉ β suc (β‘πβπ)))) β§ π β (0...π)) β (πΉβ(β‘πβπ)) β (πΉ β suc (β‘πβπ))) |
80 | 52, 79 | eqeltrd 2254 |
. . . . . . . . . 10
β’ ((((π β§ π β β0) β§ (π β Ο β§ Β¬
(πΉβπ) β (πΉ β suc (β‘πβπ)))) β§ π β (0...π)) β (πΊβπ) β (πΉ β suc (β‘πβπ))) |
81 | 80 | adantr 276 |
. . . . . . . . 9
β’
(((((π β§ π β β0)
β§ (π β Ο
β§ Β¬ (πΉβπ) β (πΉ β suc (β‘πβπ)))) β§ π β (0...π)) β§ (πΊβ(πβπ)) = (πΊβπ)) β (πΊβπ) β (πΉ β suc (β‘πβπ))) |
82 | 46, 81 | eqeltrd 2254 |
. . . . . . . 8
β’
(((((π β§ π β β0)
β§ (π β Ο
β§ Β¬ (πΉβπ) β (πΉ β suc (β‘πβπ)))) β§ π β (0...π)) β§ (πΊβ(πβπ)) = (πΊβπ)) β (πΊβ(πβπ)) β (πΉ β suc (β‘πβπ))) |
83 | 45, 82 | mtand 665 |
. . . . . . 7
β’ ((((π β§ π β β0) β§ (π β Ο β§ Β¬
(πΉβπ) β (πΉ β suc (β‘πβπ)))) β§ π β (0...π)) β Β¬ (πΊβ(πβπ)) = (πΊβπ)) |
84 | 83 | neqned 2354 |
. . . . . 6
β’ ((((π β§ π β β0) β§ (π β Ο β§ Β¬
(πΉβπ) β (πΉ β suc (β‘πβπ)))) β§ π β (0...π)) β (πΊβ(πβπ)) β (πΊβπ)) |
85 | 84 | ralrimiva 2550 |
. . . . 5
β’ (((π β§ π β β0) β§ (π β Ο β§ Β¬
(πΉβπ) β (πΉ β suc (β‘πβπ)))) β βπ β (0...π)(πΊβ(πβπ)) β (πΊβπ)) |
86 | | fveq2 5515 |
. . . . . . . 8
β’ (π = (πβπ) β (πΊβπ) = (πΊβ(πβπ))) |
87 | 86 | neeq1d 2365 |
. . . . . . 7
β’ (π = (πβπ) β ((πΊβπ) β (πΊβπ) β (πΊβ(πβπ)) β (πΊβπ))) |
88 | 87 | ralbidv 2477 |
. . . . . 6
β’ (π = (πβπ) β (βπ β (0...π)(πΊβπ) β (πΊβπ) β βπ β (0...π)(πΊβ(πβπ)) β (πΊβπ))) |
89 | 88 | rspcev 2841 |
. . . . 5
β’ (((πβπ) β β0 β§
βπ β (0...π)(πΊβ(πβπ)) β (πΊβπ)) β βπ β β0 βπ β (0...π)(πΊβπ) β (πΊβπ)) |
90 | 32, 85, 89 | syl2anc 411 |
. . . 4
β’ (((π β§ π β β0) β§ (π β Ο β§ Β¬
(πΉβπ) β (πΉ β suc (β‘πβπ)))) β βπ β β0 βπ β (0...π)(πΊβπ) β (πΊβπ)) |
91 | 27, 90 | rexlimddv 2599 |
. . 3
β’ ((π β§ π β β0) β
βπ β
β0 βπ β (0...π)(πΊβπ) β (πΊβπ)) |
92 | 91 | ralrimiva 2550 |
. 2
β’ (π β βπ β β0 βπ β β0
βπ β (0...π)(πΊβπ) β (πΊβπ)) |
93 | 13, 92 | jca 306 |
1
β’ (π β (πΊ:β0βontoβπ΄ β§ βπ β β0 βπ β β0
βπ β (0...π)(πΊβπ) β (πΊβπ))) |