Hostname: page-component-78c5997874-4rdpn Total loading time: 0 Render date: 2024-11-16T18:24:05.274Z Has data issue: false hasContentIssue false
  • English
  • Français

A generalization of the concept of ω-completeness1

Published online by Cambridge University Press:  12 March 2014

Leon Henkin
Leon Henkin*
Affiliation:
University of California, Berkeley
Get access Rights & Permissions [Opens in a new window]

Extract

The concepts of ω-consistency and ω-completeness are closely related. The former concept has been generalized to notions of Γ-consistency and strong Γ-consistency, which are applicable not only to formal systems of number theory, but to all functional calculi containing individual constants; and in this general setting the semantical significance of these concepts has been studied. In the present work we carry out an analogous generalization for the concept of ω-completeness.

Suppose, then, that F is an applied functional calculus, and that Γ is a non-empty set of individual constants of F. We say that F is Γ-complete if, whenever B(x) is a formula (containing the single free individual variable x) such that ⊦ B(α) for every α in Γ, then also ⊦ (x)B(x). In the paper “Γ-con” a sequence of increasingly strong concepts, Γ-consistency, n = 1,2, 3,…, was introduced; and it is possible in a formal way to define corresponding concepts of Γn-completeness, as follows. We say that F is Γn-complete if, whenever B(x1,…, xn) is a formula (containing exactly n distinct free variables, namely x1…, xn) such that ⊦ B(α1,…,αn) for all α1,…,αn in Γ, then also ⊦ (X1)…(xn)B(x1,…,xn). However, unlike the situation encountered in the paper “Γ-con”, these definitions are not of interest – for the simple reason that F is Γn-complete if and only if it is Γ-complete, as one easily sees.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 22 , Issue 1 , March 1957 , pp. 1 - 14
Copyright
Copyright © Association for Symbolic Logic 1957

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

The research and writing of this paper have been supported in part by grants from the U.S. National Science Foundation. Under the title “Γ-completeness” the material contained in Theorems 1–3 was presented at the International Mathematical Congress held in Amsterdam in September, 1954. However, the abstract appearing in the published Proceedings of the Congress is in error; it should be corrected by replacing the last occurrence of “Γ” by an occurrence of .

References

2 For an early study of these concepts see Tarski, A., Einige Betrachtungen über die Begriffe der ω-Widerspruchsfreiheit und ω-Vollständigkeit, Monatshefte für Mathematik und Physik, vol. 40 (1933), pp. 97–112CrossRefGoogle Scholar.

3 See Henkin, L., A generalization of the concept of ω-consistency, this Journal, vol. 19 (1954), pp. 183–196Google Scholar. We shall refer to this paper hereafter as “Γ-con.” Although we shall employ some of its results here, the present paper can be read independently.

4 The symbol “⊦” stands for “the following formula is a formal theorem of F”. The formula B(α) is obtained from B(x) by replacing all free occurrences of x by occurrences of a.

5 The completeness of first-order functional calculi was established by Gödel, K., Die Vollständigkeit der Axiome des logischen Funktionenkalküls, Monatshefte für Mathematik und Physik, vol. 37 (1930), pp. 349–360CrossRefGoogle Scholar. For the case of higher-order calculi the completeness property only holds in general if we admit a wide class of models in which the range of the predicate variables is not uniquely determined by the range of the individual variables: see Henkin, L., Completeness in the theory of types, this Journal, vol. 15 (1950), pp. 81–91Google Scholar. However, in the special case here considered, where ⊦ (x)(x = α1 ∨ x = α2 ∨ … ∨ x = αn), it can easily be shown that all models in this wider sense are actually models in the classical sense, with the range of the predicate variables uniquely determined by that of the individual variables.

6 Since F is consistent and Γ-complete, we easily see that it is Γ-consistent, and indeed Γ∞-consistent; yet there is no model which Γ-satisfies F, We thus obtain a very simple example for proving Theorems 3 and 6 of the paper “Γ-con”. For another simple proof (but one using much heavier machinery), see the review of “Γ-con” by Kreisel, G. in Mathematical reviews, vol. 16 (1955), p. 103Google Scholar.

7 See, for instance, Quine, W. V., Mathematical Logic, Cambridge (Harvard University Press), revised edition, 1951Google Scholar; especially§ 18.

8 At this point we desist from listing the axioms of F which are used in justifying the equivalences, since almost all axioms are required in each of the remaining cases.

9 We assume that in each application of Σ1 suitable changes of bound variable are first made so as to permit these substitutions.

10 Of course there must be such a symbol since MA Γ-satisfies F and (∃x)B(x) is true of MA.

11 The concept of strong Γ-consistency is defined on p. 194 of the paper “Γ-con”. From that definition it is easy to see that the consistency of Δ in F ∼ A is equivalent to the strong Γ-consistency of F ∼ A.