On Tuesday, October 20, 2020 at 5:54:13 PM UTC-4, Dan Christensen wrote:
> On Monday, October 19, 2020 at 11:05:26 AM UTC-4, Dan Christensen wrote:
>
> > PROOF BY INDUCTION FOR 2 VARIABLES
> >
> > Suppose you want to prove that, for all m, n in N, we have P(m, n) being true.
> >
> > It will be sufficient to prove:
> >
> > 1. P(0,0)
> >
> > 2. For all k in N, we have: P(0, k) => P(0, k+1)
> >
> > 3. For all j, k in N, we have: P(j, k) => P(j+1, k)
> >
> >
>
> And now...
>
> Proof by Induction with *** THREE *** Variables
>
>
> Suppose you want to prove that P(x, y, z) is true for all x, y, z in N. It will suffice to prove each of the following?
>
> 1. P(0, 0, 0)
>
> 2. For all k in N:[P(0, 0, k) => P(0, 0, k+1)]
>
> 3. For all j, k in N:[P(0, j, k) => P(0, j+1, k)]
>
> 4. For all i, j, k in N:[P(i,j,k) => P(i+1,j ,k)
>
>
I used sets of ordered triples instead of logical predicates in the following proof (205 lines).
THEOREM
ALL(a):[Set''(a) & ALL(b):ALL(c):ALL(d):[(b,c,d) in a => b in n & c in n & d in n]
=> [(0,0,0) in a
& ALL(d):[d in n => [(0,0,d) in a => (0,0,s(d)) in a]]
& ALL(c):ALL(d):[c in n & d in n => [(0,c,d) in a => (0,s(c),d) in a]]
& ALL(b):ALL(c):ALL(d):[b in n & c in n & d in n => [(b,c,d) in a => (s(b),c,d) in a]]
=> ALL(b):ALL(c):ALL(d):[b in n & c in n & d in n => (b,c,d) in a]]]
PEANO'S AXIOMS
1 Set(n)
Axiom
2 0 in n
Axiom
3 ALL(a):[a in n => s(a) in n]
Axiom
Not used here:
4 ALL(a):ALL(b):[a in n & b in n => [s(a)=s(b) => a=b]]
Axiom
Not used here:
5 ALL(a):[a in n => ~s(a)=0]
Axiom
6 ALL(a):[Set(a) & ALL(b):[b in a => b in n]
=> [0 in a & ALL(b):[b in a => s(b) in a]
=> ALL(b):[b in n => b in a]]]
Axiom
Suppose...
7 Set''(p) & ALL(b):ALL(c):ALL(d):[(b,c,d) in p => b in n & c in n & d in n]
Premise
Suppose...
8 (0,0,0) in p
& ALL(d):[d in n => [(0,0,d) in p => (0,0,s(d)) in p]]
& ALL(c):ALL(d):[c in n & d in n => [(0,c,d) in p => (0,s(c),d) in p]]
& ALL(b):ALL(c):ALL(d):[b in n & c in n & d in n => [(b,c,d) in p => (s(b),c,d) in p]]
Premise
9 (0,0,0) in p
Split, 8
10 ALL(d):[d in n => [(0,0,d) in p => (0,0,s(d)) in p]]
Split, 8
11 ALL(c):ALL(d):[c in n & d in n => [(0,c,d) in p => (0,s(c),d) in p]]
Split, 8
12 ALL(b):ALL(c):ALL(d):[b in n & c in n & d in n => [(b,c,d) in p => (s(b),c,d) in p]]
Split, 8
Construct subset p1 of n
13 EXIST(a):[Set(a) & ALL(b):[b in a <=> b in n & (0,0,b) in p]]
Subset, 1
14 Set(p1) & ALL(b):[b in p1 <=> b in n & (0,0,b) in p]
E Spec, 13
Define: p1
15 Set(p1)
Split, 14
16 ALL(b):[b in p1 <=> b in n & (0,0,b) in p]
Split, 14
Apply PMI
17 Set(p1) & ALL(b):[b in p1 => b in n]
=> [0 in p1 & ALL(b):[b in p1 => s(b) in p1]
=> ALL(b):[b in n => b in p1]]
U Spec, 6
Prove: ALL(b):[b in p1 => b in n]
Suppose...
18 x in p1
Premise
19 x in p1 <=> x in n & (0,0,x) in p
U Spec, 16
20 [x in p1 => x in n & (0,0,x) in p]
& [x in n & (0,0,x) in p => x in p1]
Iff-And, 19
21 x in p1 => x in n & (0,0,x) in p
Split, 20
22 x in n & (0,0,x) in p => x in p1
Split, 20
23 x in n & (0,0,x) in p
Detach, 21, 18
24 x in n
Split, 23
As Required:
25 ALL(b):[b in p1 => b in n]
Conclusion, 18
26 Set(p1) & ALL(b):[b in p1 => b in n]
Join, 15, 25
Sufficient: For ALL(b):[b in n => b in p1]
27 0 in p1 & ALL(b):[b in p1 => s(b) in p1]
=> ALL(b):[b in n => b in p1]
Detach, 17, 26
BASE CASE
28 0 in p1 <=> 0 in n & (0,0,0) in p
U Spec, 16
29 [0 in p1 => 0 in n & (0,0,0) in p]
& [0 in n & (0,0,0) in p => 0 in p1]
Iff-And, 28
30 0 in p1 => 0 in n & (0,0,0) in p
Split, 29
31 0 in n & (0,0,0) in p => 0 in p1
Split, 29
32 0 in n & (0,0,0) in p
Join, 2, 9
As Required:
33 0 in p1
Detach, 31, 32
INDUCTIVE STEP
Prove: ALL(b):[b in p1 => s(b) in p1]
Suppose...
34 x in p1
Premise
35 x in p1 <=> x in n & (0,0,x) in p
U Spec, 16
36 [x in p1 => x in n & (0,0,x) in p]
& [x in n & (0,0,x) in p => x in p1]
Iff-And, 35
37 x in p1 => x in n & (0,0,x) in p
Split, 36
38 x in n & (0,0,x) in p => x in p1
Split, 36
39 x in n & (0,0,x) in p
Detach, 37, 34
40 x in n
Split, 39
41 (0,0,x) in p
Split, 39
42 x in n => s(x) in n
U Spec, 3
43 s(x) in n
Detach, 42, 40
44 s(x) in p1 <=> s(x) in n & (0,0,s(x)) in p
U Spec, 16, 43
45 [s(x) in p1 => s(x) in n & (0,0,s(x)) in p]
& [s(x) in n & (0,0,s(x)) in p => s(x) in p1]
Iff-And, 44
46 s(x) in p1 => s(x) in n & (0,0,s(x)) in p
Split, 45
Sufficient: For s(x) in p1
47 s(x) in n & (0,0,s(x)) in p => s(x) in p1
Split, 45
48 x in n => [(0,0,x) in p => (0,0,s(x)) in p]
U Spec, 10
49 (0,0,x) in p => (0,0,s(x)) in p
Detach, 48, 40
50 (0,0,s(x)) in p
Detach, 49, 41
51 s(x) in n & (0,0,s(x)) in p
Join, 43, 50
52 s(x) in p1
Detach, 47, 51
As Required:
53 ALL(b):[b in p1 => s(b) in p1]
Conclusion, 34
54 0 in p1 & ALL(b):[b in p1 => s(b) in p1]
Join, 33, 53
As Required:
55 ALL(b):[b in n => b in p1]
Detach, 27, 54
Prove: ALL(c):[c in n => (0,0,c) in p]
Suppose...
56 x in n
Premise
57 x in n => x in p1
U Spec, 55
58 x in p1
Detach, 57, 56
59 x in p1 <=> x in n & (0,0,x) in p
U Spec, 16
60 [x in p1 => x in n & (0,0,x) in p]
& [x in n & (0,0,x) in p => x in p1]
Iff-And, 59
61 x in p1 => x in n & (0,0,x) in p
Split, 60
62 x in n & (0,0,x) in p => x in p1
Split, 60
63 x in n & (0,0,x) in p
Detach, 61, 58
64 x in n
Split, 63
65 (0,0,x) in p
Split, 63
As Required:
66 ALL(c):[c in n => (0,0,c) in p]
Conclusion, 56
Suppose...
67 z in n
Premise
Construct subset p2 of n
68 EXIST(a):[Set(a) & ALL(b):[b in a <=> b in n & (0,b,z) in p]]
Subset, 1
69 Set(p2) & ALL(b):[b in p2 <=> b in n & (0,b,z) in p]
E Spec, 68
Define: p2
70 Set(p2)
Split, 69
71 ALL(b):[b in p2 <=> b in n & (0,b,z) in p]
Split, 69
Apply PMI
72 Set(p2) & ALL(b):[b in p2 => b in n]
=> [0 in p2 & ALL(b):[b in p2 => s(b) in p2]
=> ALL(b):[b in n => b in p2]]
U Spec, 6
Prove: ALL(b):[b in p2 => b in n]
Suppose...
73 x in p2
Premise
74 x in p2 <=> x in n & (0,x,z) in p
U Spec, 71
75 [x in p2 => x in n & (0,x,z) in p]
& [x in n & (0,x,z) in p => x in p2]
Iff-And, 74
76 x in p2 => x in n & (0,x,z) in p
Split, 75
77 x in n & (0,x,z) in p => x in p2
Split, 75
78 x in n & (0,x,z) in p
Detach, 76, 73
79 x in n
Split, 78
As Required:
80 ALL(b):[b in p2 => b in n]
Conclusion, 73
81 Set(p2) & ALL(b):[b in p2 => b in n]
Join, 70, 80
Sufficient: For ALL(b):[b in n => b in p2]
82 0 in p2 & ALL(b):[b in p2 => s(b) in p2]
=> ALL(b):[b in n => b in p2]
Detach, 72, 81
BASE CASE
83 0 in p2 <=> 0 in n & (0,0,z) in p
U Spec, 71
84 [0 in p2 => 0 in n & (0,0,z) in p]
& [0 in n & (0,0,z) in p => 0 in p2]
Iff-And, 83
85 0 in p2 => 0 in n & (0,0,z) in p
Split, 84
Sufficient: For 0 in p2
86 0 in n & (0,0,z) in p => 0 in p2
Split, 84
87 z in n => (0,0,z) in p
U Spec, 66
88 (0,0,z) in p
Detach, 87, 67
89 0 in n & (0,0,z) in p
Join, 2, 88
As Required:
90 0 in p2
Detach, 86, 89
INDUCTIVE STEP
Suppose...
91 y in p2
Premise
92 y in p2 <=> y in n & (0,y,z) in p
U Spec, 71
93 [y in p2 => y in n & (0,y,z) in p]
& [y in n & (0,y,z) in p => y in p2]
Iff-And, 92
94 y in p2 => y in n & (0,y,z) in p
Split, 93
95 y in n & (0,y,z) in p => y in p2
Split, 93
96 y in n & (0,y,z) in p
Detach, 94, 91
97 y in n
Split, 96
98 (0,y,z) in p
Split, 96
99 y in n => s(y) in n
U Spec, 3
100 s(y) in n
Detach, 99, 97
101 s(y) in p2 <=> s(y) in n & (0,s(y),z) in p
U Spec, 71, 100
102 [s(y) in p2 => s(y) in n & (0,s(y),z) in p]
& [s(y) in n & (0,s(y),z) in p => s(y) in p2]
Iff-And, 101
103 s(y) in p2 => s(y) in n & (0,s(y),z) in p
Split, 102
104 s(y) in n & (0,s(y),z) in p => s(y) in p2
Split, 102
105 ALL(d):[y in n & d in n => [(0,y,d) in p => (0,s(y),d) in p]]
U Spec, 11
106 y in n & z in n => [(0,y,z) in p => (0,s(y),z) in p]
U Spec, 105
107 y in n & z in n
Join, 97, 67
108 (0,y,z) in p => (0,s(y),z) in p
Detach, 106, 107
109 (0,s(y),z) in p
Detach, 108, 98
110 s(y) in n & (0,s(y),z) in p
Join, 100, 109
111 s(y) in p2
Detach, 104, 110
As Required:
112 ALL(b):[b in p2 => s(b) in p2]
Conclusion, 91
113 0 in p2 & ALL(b):[b in p2 => s(b) in p2]
Join, 90, 112
As Required:
114 ALL(b):[b in n => b in p2]
Detach, 82, 113
Prove: ALL(b):[b in n => (0,b,z) in p]
Suppose...
115 y in n
Premise
116 y in n => y in p2
U Spec, 114
117 y in p2
Detach, 116, 115
118 y in p2 <=> y in n & (0,y,z) in p
U Spec, 71
119 [y in p2 => y in n & (0,y,z) in p]
& [y in n & (0,y,z) in p => y in p2]
Iff-And, 118
120 y in p2 => y in n & (0,y,z) in p
Split, 119
121 y in n & (0,y,z) in p => y in p2
Split, 119
122 y in n & (0,y,z) in p
Detach, 120, 117
123 y in n
Split, 122
124 (0,y,z) in p
Split, 122
As Required:
125 ALL(b):[b in n => (0,b,z) in p]
Conclusion, 115
As Required:
126 ALL(c):[c in n => ALL(b):[b in n => (0,b,c) in p]]
Conclusion, 67
Prove: ALL(b):ALL(c):[b in n & c in n => ALL(a):[a in n => (a,b,c) in p]]
Suppose...
127 y in n & z in n
Premise
128 y in n
Split, 127
129 z in n
Split, 127
130 EXIST(a):[Set(a) & ALL(b):[b in a <=> b in n & (b,y,z) in p]]
Subset, 1
131 Set(p3) & ALL(b):[b in p3 <=> b in n & (b,y,z) in p]
E Spec, 130
Define: p3
132 Set(p3)
Split, 131
133 ALL(b):[b in p3 <=> b in n & (b,y,z) in p]
Split, 131
Apply PMI
134 Set(p3) & ALL(b):[b in p3 => b in n]
=> [0 in p3 & ALL(b):[b in p3 => s(b) in p3]
=> ALL(b):[b in n => b in p3]]
U Spec, 6
Prove: ALL(b):[b in p3 => b in n]
Suppose...
135 x in p3
Premise
136 x in p3 <=> x in n & (x,y,z) in p
U Spec, 133
137 [x in p3 => x in n & (x,y,z) in p]
& [x in n & (x,y,z) in p => x in p3]
Iff-And, 136
138 x in p3 => x in n & (x,y,z) in p
Split, 137
139 x in n & (x,y,z) in p => x in p3
Split, 137
140 x in n & (x,y,z) in p
Detach, 138, 135
141 x in n
Split, 140
As Required:
142 ALL(b):[b in p3 => b in n]
Conclusion, 135
143 Set(p3) & ALL(b):[b in p3 => b in n]
Join, 132, 142
Sufficient: For ALL(b):[b in n => b in p3]
144 0 in p3 & ALL(b):[b in p3 => s(b) in p3]
=> ALL(b):[b in n => b in p3]
Detach, 134, 143
BASE CASE
145 0 in p3 <=> 0 in n & (0,y,z) in p
U Spec, 133
146 [0 in p3 => 0 in n & (0,y,z) in p]
& [0 in n & (0,y,z) in p => 0 in p3]
Iff-And, 145
147 0 in p3 => 0 in n & (0,y,z) in p
Split, 146
148 0 in n & (0,y,z) in p => 0 in p3
Split, 146
149 z in n => ALL(b):[b in n => (0,b,z) in p]
U Spec, 126
150 ALL(b):[b in n => (0,b,z) in p]
Detach, 149, 129
151 y in n => (0,y,z) in p
U Spec, 150
152 (0,y,z) in p
Detach, 151, 128
153 0 in n & (0,y,z) in p
Join, 2, 152
As Required:
154 0 in p3
Detach, 148, 153
INDUCTIVE STEP
Prove: ALL(a):[a in p3 => s(a) in p3]
Suppose...
155 x in p3
Premise
156 x in p3 <=> x in n & (x,y,z) in p
U Spec, 133
157 [x in p3 => x in n & (x,y,z) in p]
& [x in n & (x,y,z) in p => x in p3]
Iff-And, 156
158 x in p3 => x in n & (x,y,z) in p
Split, 157
159 x in n & (x,y,z) in p => x in p3
Split, 157
160 x in n & (x,y,z) in p
Detach, 158, 155
161 x in n
Split, 160
162 (x,y,z) in p
Split, 160
163 x in n => s(x) in n
U Spec, 3
164 s(x) in n
Detach, 163, 161
165 s(x) in p3 <=> s(x) in n & (s(x),y,z) in p
U Spec, 133, 164
166 [s(x) in p3 => s(x) in n & (s(x),y,z) in p]
& [s(x) in n & (s(x),y,z) in p => s(x) in p3]
Iff-And, 165
167 s(x) in p3 => s(x) in n & (s(x),y,z) in p
Split, 166
168 s(x) in n & (s(x),y,z) in p => s(x) in p3
Split, 166
169 ALL(c):ALL(d):[x in n & c in n & d in n => [(x,c,d) in p => (s(x),c,d) in p]]
U Spec, 12
170 ALL(d):[x in n & y in n & d in n => [(x,y,d) in p => (s(x),y,d) in p]]
U Spec, 169
171 x in n & y in n & z in n => [(x,y,z) in p => (s(x),y,z) in p]
U Spec, 170
172 x in n & y in n
Join, 161, 128
173 x in n & y in n & z in n
Join, 172, 129
174 (x,y,z) in p => (s(x),y,z) in p
Detach, 171, 173
175 (s(x),y,z) in p
Detach, 174, 162
176 s(x) in n & (s(x),y,z) in p
Join, 164, 175
177 s(x) in p3
Detach, 168, 176
As Required:
178 ALL(a):[a in p3 => s(a) in p3]
Conclusion, 155
179 0 in p3 & ALL(a):[a in p3 => s(a) in p3]
Join, 154, 178
180 ALL(b):[b in n => b in p3]
Detach, 144, 179
Prove: ALL(a):[a in n => (a,y,z) in p]
Suppose...
181 x in n
Premise
182 x in n => x in p3
U Spec, 180
183 x in p3
Detach, 182, 181
184 x in p3 <=> x in n & (x,y,z) in p
U Spec, 133
185 [x in p3 => x in n & (x,y,z) in p]
& [x in n & (x,y,z) in p => x in p3]
Iff-And, 184
186 x in p3 => x in n & (x,y,z) in p
Split, 185
187 x in n & (x,y,z) in p => x in p3
Split, 185
188 x in n & (x,y,z) in p
Detach, 186, 183
189 x in n
Split, 188
190 (x,y,z) in p
Split, 188
As Required:
191 ALL(a):[a in n => (a,y,z) in p]
Conclusion, 181
As Required:
192 ALL(b):ALL(c):[b in n & c in n => ALL(a):[a in n => (a,b,c) in p]]
Conclusion, 127
Prove: ALL(a):ALL(b):ALL(c):[a in n & b in n & c in n => (a,b,c) in p]
Suppose...
193 x in n & y in n & z in n
Premise
194 x in n
Split, 193
195 y in n
Split, 193
196 z in n
Split, 193
197 ALL(c):[y in n & c in n => ALL(a):[a in n => (a,y,c) in p]]
U Spec, 192
198 y in n & z in n => ALL(a):[a in n => (a,y,z) in p]
U Spec, 197
199 y in n & z in n
Join, 195, 196
200 ALL(a):[a in n => (a,y,z) in p]
Detach, 198, 199
201 x in n => (x,y,z) in p
U Spec, 200
202 (x,y,z) in p
Detach, 201, 194
As Required:
203 ALL(a):ALL(b):ALL(c):[a in n & b in n & c in n => (a,b,c) in p]
Conclusion, 193
As Required:
204 (0,0,0) in p
& ALL(d):[d in n => [(0,0,d) in p => (0,0,s(d)) in p]]
& ALL(c):ALL(d):[c in n & d in n => [(0,c,d) in p => (0,s(c),d) in p]]
& ALL(b):ALL(c):ALL(d):[b in n & c in n & d in n => [(b,c,d) in p => (s(b),c,d) in p]]
=> ALL(a):ALL(b):ALL(c):[a in n & b in n & c in n => (a,b,c) in p]
Conclusion, 8
As Required:
205 ALL(p):[Set''(p) & ALL(b):ALL(c):ALL(d):[(b,c,d) in p => b in n & c in n & d in n]
=> [(0,0,0) in p
& ALL(d):[d in n => [(0,0,d) in p => (0,0,s(d)) in p]]
& ALL(c):ALL(d):[c in n & d in n => [(0,c,d) in p => (0,s(c),d) in p]]
& ALL(b):ALL(c):ALL(d):[b in n & c in n & d in n => [(b,c,d) in p => (s(b),c,d) in p]]
=> ALL(a):ALL(b):ALL(c):[a in n & b in n & c in n => (a,b,c) in p]]]
Conclusion, 7