80:
The statement has a short proof in a more powerful system: in fact the proof given in the previous paragraph is a proof in the system of Peano arithmetic plus the statement "Peano arithmetic is consistent" (which, per the incompleteness theorem, cannot be proved in Peano arithmetic).
77:. But simply enumerating all strings of length up to a googolplex and checking that each such string is not a proof (in PA) of the statement, yields a proof of the statement (which is necessarily longer than a googolplex symbols).
84:
In this argument, Peano arithmetic can be replaced by any more powerful consistent system, and a googolplex can be replaced by any number that can be described concisely in the system.
90:
found some explicit natural examples of this phenomenon, giving some explicit statements in Peano arithmetic and other formal systems whose shortest proofs are ridiculously long (
49:
showed how to find explicit examples of statements in formal systems that are provable in that system but whose shortest proof is unimaginably long. For example, the statement:
371:
73:, then it cannot prove the statement in fewer than a googolplex symbols, because the existence of such a proof would itself be a theorem of PA, a
65:
is provable in Peano arithmetic (PA) but the shortest proof has at least a googolplex symbols, by an argument similar to the proof of
66:
282:
269:(1995), "On Gödel's theorems on lengths of proofs. II. Lower bounds for recognizing k symbol provability", in Clote, Peter;
319:
184:
of the statement above, one obtains an inconsistent theory whose shortest known contradiction is equivalently long.
376:
193:
214:(1994), "On Gödel's theorems on lengths of proofs. I. Number of lines and speedup for arithmetics",
174:
277:, Progr. Comput. Sci. Appl. Logic, vol. 13, Boston, MA: Birkhäuser Boston, pp. 57–90,
74:
303:
366:
350:
292:
251:
170:
8:
198:
255:
239:
315:
278:
270:
231:
338:
223:
54:
16:
There are theorems whose proofs can be shortened in more powerful axiomatic systems
259:
346:
288:
247:
146:
87:
360:
235:
43:
can be drastically shortened by working in more powerful axiomatic systems.
299:
153:
is provable in Peano arithmetic, but the shortest proof has length at least
46:
28:
143:
40:
266:
211:
106:
70:
20:
324:, Reprinted with English translation in volume 1 of his collected works.
342:
243:
58:
227:
181:
99:
36:
329:
Smoryński, C. (1982), "The varieties of arboreal experience",
142: + 10 vertices, then some tree can be
358:
180:If one takes Peano arithmetic together with the
169:+1) = 2. The statement is a special case of
308:Ergebnisse Eines Mathematischen Kolloquiums
275:Feasible mathematics, II (Ithaca, NY, 1992)
372:Theorems in the foundations of mathematics
328:
91:
359:
298:
32:
265:
210:
105:such that if there is a sequence of
67:Gödel's first incompleteness theorem
53:"This statement cannot be proved in
13:
14:
388:
94:). For example, the statement
1:
304:"Über die Länge von Beweisen"
216:The Journal of Symbolic Logic
204:
7:
187:
10:
393:
173:and has a short proof in
35:), shows that there are
25:Gödel's speed-up theorem
175:second order arithmetic
194:Blum's speedup theorem
377:Works by Kurt Gödel
331:Math. Intelligencer
199:List of long proofs
343:10.1007/bf03023553
284:978-0-8176-3675-3
171:Kruskal's theorem
384:
353:
325:
295:
262:
144:homeomorphically
57:in fewer than a
55:Peano arithmetic
392:
391:
387:
386:
385:
383:
382:
381:
357:
356:
322:
285:
271:Remmel, Jeffrey
267:Buss, Samuel R.
228:10.2307/2275906
212:Buss, Samuel R.
207:
190:
149:in a later one"
136:
130:
121:
114:
88:Harvey Friedman
17:
12:
11:
5:
390:
380:
379:
374:
369:
355:
354:
337:(4): 182–189,
326:
320:
296:
283:
263:
222:(3): 737–756,
206:
203:
202:
201:
196:
189:
186:
157:(1000), where
151:
150:
134:
126:
119:
112:
92:Smoryński 1982
63:
62:
15:
9:
6:
4:
3:
2:
389:
378:
375:
373:
370:
368:
365:
364:
362:
352:
348:
344:
340:
336:
332:
327:
323:
321:9780195039641
317:
313:
310:(in German),
309:
305:
301:
297:
294:
290:
286:
280:
276:
272:
268:
264:
261:
257:
253:
249:
245:
241:
237:
233:
229:
225:
221:
217:
213:
209:
208:
200:
197:
195:
192:
191:
185:
183:
178:
176:
172:
168:
164:
160:
156:
148:
145:
141:
137:
129:
125:
118:
111:
108:
104:
101:
98:"there is an
97:
96:
95:
93:
89:
85:
82:
78:
76:
75:contradiction
72:
68:
60:
56:
52:
51:
50:
48:
44:
42:
38:
34:
30:
26:
22:
367:Proof theory
334:
330:
311:
307:
274:
219:
215:
179:
166:
162:
161:(0) = 1 and
158:
154:
152:
139:
138:has at most
132:
127:
123:
116:
109:
107:rooted trees
102:
86:
83:
79:
64:
45:
27:, proved by
24:
18:
300:Gödel, Kurt
69:: If PA is
21:mathematics
361:Categories
205:References
131:such that
71:consistent
59:googolplex
47:Kurt Gödel
314:: 23–24,
236:0022-4812
302:(1936),
273:(eds.),
188:See also
182:negation
147:embedded
61:symbols"
37:theorems
351:0685558
293:1322274
252:1295967
244:2275906
122:, ...,
100:integer
31: (
349:
318:
291:
281:
260:914043
258:
250:
242:
234:
41:proofs
39:whose
256:S2CID
240:JSTOR
29:Gödel
316:ISBN
279:ISBN
232:ISSN
33:1936
339:doi
224:doi
19:In
363::
347:MR
345:,
333:,
306:,
289:MR
287:,
254:,
248:MR
246:,
238:,
230:,
220:59
218:,
177:.
115:,
23:,
341::
335:4
312:7
226::
167:n
165:(
163:A
159:A
155:A
140:k
135:k
133:T
128:n
124:T
120:2
117:T
113:1
110:T
103:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.