33:
284:
in this case it is not possible to give finitary proofs of reasonably strong theories. On the other hand, Gödel himself suggested the possibility of giving finitary consistency proofs using finitary methods that cannot be formalized in Peano arithmetic, so he seems to have had a more liberal view of what finitary methods might be allowed. A few years later,
146:
set of axioms which is capable of expressing arithmetic can never be complete: it is possible to construct a statement that can be shown to be true, but that cannot be derived from the formal rules of the system. In his second theorem, he showed that such a system could not prove its own consistency,
283:
The question of whether there are finitary consistency proofs of strong theories is difficult to answer, mainly because there is no generally accepted definition of a "finitary proof". Most mathematicians in proof theory seem to regard finitary mathematics as being contained in Peano arithmetic, and
200:
showed that most of the goals of
Hilbert's program were impossible to achieve, at least if interpreted in the most obvious way. Gödel's second incompleteness theorem shows that any consistent theory powerful enough to encode addition and multiplication of integers cannot prove its own consistency.
267:
Although it is not possible to prove completeness for systems that can express at least the Peano arithmetic (or, more generally, that have a computable set of axioms), it is possible to prove forms of completeness for many other interesting systems. An example of a non-trivial theory for which
147:
so it certainly cannot be used to prove the consistency of anything stronger with certainty. This refuted
Hilbert's assumption that a finitistic system could be used to prove the consistency of itself, and therefore could not prove everything else.
248:, can be viewed as natural continuations of Hilbert's original program. Much of it can be salvaged by changing its goals slightly (Zach 2005), and with the following modifications some of it was successfully completed:
314:
and others, and one can again debate about exactly how finitary or constructive these proofs are. (The theories that have been proved consistent by these methods are quite strong, and include most "ordinary"
220:
A theory such as Peano arithmetic cannot even prove its own consistency, so a restricted "finitistic" subset of it certainly cannot prove the consistency of more powerful theories such as set theory.
169:
Consistency: a proof that no contradiction can be obtained in the formalism of mathematics. This consistency proof should preferably use only "finitistic" reasoning about finite mathematical objects.
318:
Although there is no algorithm for deciding the truth of statements in Peano arithmetic, there are many interesting and non-trivial theories for which such algorithms have been found. For example,
209:
mathematical true statements within a formal system, as any attempt at such a formalism will omit some true mathematical statements. There is no complete, consistent extension of even
306:. If this transfinite induction is accepted as a finitary method, then one can assert that there is a finitary proof of the consistency of Peano arithmetic. More powerful subsets of
223:
There is no algorithm to decide the truth (or provability) of statements in any consistent extension of Peano arithmetic. Strictly speaking, this negative solution to the
142:, published in 1931, showed that Hilbert's program was unattainable for key areas of mathematics. In his first theorem, Gödel showed that any consistent system with a
192:
139:
54:
468:
353:
116:
were found to suffer from paradoxes and inconsistencies. As a solution, Hilbert proposed to ground all existing theories to a finite,
109:
76:
257:
155:
The main goal of
Hilbert's program was to provide secure foundations for all mathematics. In particular, this should include:
496:
289:
413:
104:485–94. Translated by W. Ewald as 'The
Grounding of Elementary Number Theory', pp. 266–273 in Mancosu (ed., 1998)
132:, could be proven in terms of simpler systems. Ultimately, the consistency of all of mathematics could be reduced to basic
420:
227:
appeared a few years after Gödel's theorem, because at the time the notion of an algorithm had not been precisely defined.
486:
47:
41:
273:
172:
Conservation: a proof that any result about "real objects" obtained using reasoning about "ideal objects" (such as
113:
331:
429:
348:
58:
277:
307:
159:
A formulation of all mathematics; in other words all mathematical statements should be written in a precise
256:
mathematics, it is possible to formalize essentially all the mathematics that anyone uses. In particular
491:
398:
293:
214:
374:
224:
179:
117:
245:
335:
237:
424:
182:: there should be an algorithm for deciding the truth or falsity of any mathematical statement.
327:
323:
292:
for Peano arithmetic. The only part of this proof that was not clearly finitary was a certain
261:
264:, gives a satisfactory and generally accepted formalism for almost all current mathematics.
166:
Completeness: a proof that all true mathematical statements can be proved in the formalism.
463:
285:
269:
160:
334:, this algorithm can be regarded as an algorithm to decide the truth of any statement in
338:. This is substantial as few people would consider Euclidean geometry a trivial theory.
300:
297:
459:
17:
480:
319:
311:
197:
129:
105:
436:
241:
210:
415:
From
Brouwer to Hilbert: The debate on the foundations of mathematics in the 1920s
173:
93:
143:
133:
125:
128:. Hilbert proposed that the consistency of more complicated systems, such as
396:
89:
Attempt to formalize all of mathematics, based on a finite set of axioms
101:
444:
381:(Spring 2023 ed.), Metaphysics Research Lab, Stanford University
121:
322:
found an algorithm that can decide the truth of any statement in
402:
112:493–565. Translated as 'The consistency of arithmetic', in
373:
Zach, Richard (2023), Zalta, Edward N.; Nodelman, Uri (eds.),
26:
409:
D. Hilbert. 'Die
Grundlegung der elementaren Zahlenlehre'.
108:in the early 1920s, was a proposed solution to the
163:, and manipulated according to well defined rules.
201:This presents a challenge to Hilbert's program:
176:sets) can be proved without using ideal objects.
425:Partial realizations of Hilbert's program (pdf)
326:(more precisely, he proved that the theory of
124:, and provide a proof that these axioms were
8:
252:Although it is not possible to formalize
77:Learn how and when to remove this message
439:, 2006. Hilbert's Program Then and Now.
40:This article includes a list of general
404:The collected papers of Gerhard Gentzen
379:The Stanford Encyclopedia of Philosophy
365:
186:
310:have been given consistency proofs by
112:, when early attempts to clarify the
7:
417:, Oxford University Press. New York.
469:Stanford Encyclopedia of Philosophy
231:
354:Foundational crisis of mathematics
236:Many current lines of research in
110:foundational crisis of mathematics
46:it lacks sufficient corresponding
25:
272:has been proved is the theory of
205:It is not possible to formalize
31:
193:Gödel's incompleteness theorems
187:Gödel's incompleteness theorems
140:Gödel's incompleteness theorems
151:Statement of Hilbert's program
1:
232:Hilbert's program after Gödel
274:algebraically closed fields
258:Zermelo–Fraenkel set theory
513:
406:, M. E. Szabo (ed.), 1969.
190:
114:foundations of mathematics
430:Journal of Symbolic Logic
349:Grundlagen der Mathematik
330:is decidable). Given the
308:second-order arithmetic
150:
61:more precise citations.
18:Hilbert's Program
411:Mathematische Annalen
399:Mathematische Annalen
332:Cantor–Dedekind axiom
294:transfinite induction
215:computably enumerable
225:Entscheidungsproblem
460:"Hilbert's Program"
441:Philosophy of Logic
375:"Hilbert's Program"
246:reverse mathematics
497:Hilbert's problems
487:Mathematical logic
445:arXiv:math/0508572
336:Euclidean geometry
328:real closed fields
238:mathematical logic
324:analytic geometry
290:consistency proof
262:first-order logic
98:Hilbert's program
87:
86:
79:
16:(Redirected from
504:
473:
464:Zalta, Edward N.
389:
388:
387:
386:
370:
260:, combined with
211:Peano arithmetic
100:, formulated by
82:
75:
71:
68:
62:
57:this article by
48:inline citations
35:
34:
27:
21:
512:
511:
507:
506:
505:
503:
502:
501:
477:
476:
457:
454:
393:
392:
384:
382:
372:
371:
367:
362:
345:
304:
234:
195:
189:
161:formal language
153:
90:
83:
72:
66:
63:
53:Please help to
52:
36:
32:
23:
22:
15:
12:
11:
5:
510:
508:
500:
499:
494:
489:
479:
478:
475:
474:
458:Richard Zach.
453:
452:External links
450:
449:
448:
434:
418:
407:
391:
390:
364:
363:
361:
358:
357:
356:
351:
344:
341:
340:
339:
316:
302:
281:
278:characteristic
265:
233:
230:
229:
228:
221:
218:
217:set of axioms.
191:Main article:
188:
185:
184:
183:
177:
170:
167:
164:
152:
149:
104:mathematician
88:
85:
84:
39:
37:
30:
24:
14:
13:
10:
9:
6:
4:
3:
2:
509:
498:
495:
493:
490:
488:
485:
484:
482:
471:
470:
465:
461:
456:
455:
451:
446:
442:
438:
435:
432:
431:
426:
422:
419:
416:
412:
408:
405:
401:
400:
395:
394:
380:
376:
369:
366:
359:
355:
352:
350:
347:
346:
342:
337:
333:
329:
325:
321:
317:
315:mathematics.)
313:
312:Gaisi Takeuti
309:
305:
299:
295:
291:
287:
282:
279:
275:
271:
266:
263:
259:
255:
251:
250:
249:
247:
243:
239:
226:
222:
219:
216:
212:
208:
204:
203:
202:
199:
194:
181:
178:
175:
171:
168:
165:
162:
158:
157:
156:
148:
145:
141:
137:
135:
131:
130:real analysis
127:
123:
119:
115:
111:
107:
106:David Hilbert
103:
99:
95:
81:
78:
70:
60:
56:
50:
49:
43:
38:
29:
28:
19:
492:Proof theory
467:
440:
428:
421:S.G. Simpson
414:
410:
403:
397:
383:, retrieved
378:
368:
270:completeness
253:
242:proof theory
235:
206:
196:
180:Decidability
154:
138:
97:
91:
73:
64:
45:
443:5:411–447,
433:53:349–363.
213:based on a
174:uncountable
94:mathematics
59:introducing
481:Categories
385:2023-07-05
360:References
296:up to the
240:, such as
198:Kurt Gödel
144:computable
134:arithmetic
126:consistent
67:April 2023
42:references
276:of given
423:, 1988.
343:See also
118:complete
466:(ed.).
437:R. Zach
298:ordinal
288:gave a
286:Gentzen
120:set of
55:improve
320:Tarski
122:axioms
102:German
44:, but
462:. In
244:and
254:all
207:all
92:In
483::
427:.
377:,
136:.
96:,
472:.
447:.
303:0
301:ε
280:.
80:)
74:(
69:)
65:(
51:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.