Hostname: page-component-78c5997874-g7gxr Total loading time: 0 Render date: 2024-11-17T16:57:57.583Z Has data issue: false hasContentIssue false

Open sentences and the induction axiom1

Published online by Cambridge University Press:  12 March 2014

J. R. Shoenfield*
Affiliation:
Institute for Advanced Study

Extract

The purpose of this paper is to give a partial answer to the question: How much is the induction axiom weakened if it is applied only to sentences with no bound variables? It is well known that for the full Peano arithmetic this is a weakening ([1] p. 90). We consider Peano arithmetic without multiplication, and give a full answer to the question. It turns out that only four new theorems can be proved from the weakened induction axiom; i.e., all further consequences of this axiom are derivable from these four.

We consider a system T formulated within the first-order predicate calculus with equality. The system contains the constant 0 and the three function symbols S (successor), P (predecessor), and +. The non-logical axioms are:

A sentence is open if it contains no bound variables. We obtain the system TI from T by adding the rule of inference:

(I) If A(x) is an open sentence, infer A(x) from A(0) and A(x) ⊃ A(Sx).

The following open sentences are easily proved in TI:

The system formed by adding (B1) - (B4) to T is called T′.

We abbreviate SS … Sx, where S occurs n times, to Snx. Similarly, we abbreviate (… (x+x)+ …) + x, where x occurs n times, to nx. A term of the form n1x1 + … + nkXk + Sp0 is called simple. An equation between simple terms is called a simple equation.

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1958

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

1

Presented to the Association for Symbolic Logic, December 27, 1956. This research was supported by the National Science Foundation. The author would like to thank G. Kreisel for suggestions and advice.

References

REFERENCES

[1]Hilbert, D. and Bernays, P., Grundlagen der Mathematik, vol. 2, Berlin (Julius Springer), 1939.Google Scholar
[2]Skolem, T., Peano's axioms and models of arithmetic, Mathematical interpretations of formal systems, Amsterdam (North Holland), 1955, pp. 114.Google Scholar
[3]Skolem, T., Diophantische Gleichungen, Ergebnisse der Mathematik und ihrer Grenzgebiete, Berlin, 1938.Google Scholar
[4]Weyl, H., Elementary proof of a minimax theorem due to von Neumann, Contributions to the theory of games I, Annals of Mathematics Studies No. 24 (1950). pp. 1925.Google Scholar