Below are collected some simple results on the theory of free choice sequences [4] or infinitely proceeding sequences (ips) as they are called in [5]. These results are not sufficient to settle the completeness problems for Heyting's predicate calculus [4], as formulated in [12], neither in the strong nor in the weak sense. They are published because they lead to intuitionistically valid versions of completeness proofs which have appeared in the literature, particularly [16], [17], [18], and, with certain reservations, [1].

The problems considered below (except in §8) differ from those of [12] in the following respect: In [12] we were mainly concerned with formulae of Heyting's predicate calculus which were not even classically provable, and showed that the calculus was complete with respect to certain classes of these formulae. The novel feature was that we established this completeness by means of intuitionistically valid methods, in fact methods which can be formalized in Heyting's arithmetic. Here we are primarily concerned with formulae which are classically, but not intuitionistically, provable. As pointed out in [12], the nature of the completeness problem for such formulae is totally different: the class of predicates which provides the required counterexamples must come from a system (with an intuitionistically acceptable interpretation) which, unlike Heyting's arithmetic, is not a subsystem of the corresponding classical system. An example of such a system is an extension FC, given below, of Heyting's formalization of the theory of free choices.

By an algebra is meant an ordered set Γ = 〈V,R1, …, Rn, O1, …, Om〉, where V is a class, Ri (1 ≤ i ≤, n) is a relation on nj elements of V (i.e. Ri ⊆ Vni), and Oj (1 ≤ i ≤ n) is an operation on elements of V such that Oj(x1, … xmj) ∈ V) for all x1, …, xmj ∈ V). A sentence S of the first-order functional calculus is valid in Γ, if it contains just individual variables x1, x2, …, relation variables ϱ1, …,ϱn, where ϱi,- is nj-ary (1 ≤ i ≤ n), and operation variables σ1, …, σm, where σj is mj-ary (1 ≤, j ≤ m), and S holds if the individual variables are interpreted as ranging over V, ϱi is interpreted as Ri, and σi as Oj. If {Γi}i≤α is a (finite or infinite) sequence of algebras Γi, where Γi = 〈Vi, Ri〉 and Ri, is a binary relation, then by the direct productΓ = Πi<αΓi is meant the algebra Γ = 〈V, R〉, where V consists of all (finite or infinite) sequences x = 〈x1, x2, …, xi, …〉 with Xi ∈ Vi and where R is a binary relation such that two elements x and y of V are in the relation R if and only if xi and yi- are in the relation Ri for each i < α.

A “foundational crisis” occurred already in Greek mathematics, brought about by the Pythagorean discovery of incommensurable quantities. It was Eudoxos who provided new foundations, and since then Greek mathematics has been unshakeable. If one reads modern mathematical textbooks, one is normally told that something very similar occurred in modern mathematics. The calculus invented in the seventeenth century had to go through a crisis caused by the use of divergent series. One is told that by the achievements of the nineteenth century from Cauchy to Cantor this crisis has definitely been overcome. It is well known, but it is nevertheless very often not taken seriously into account, that this is an illusion. The so-called ε-δ-definitions of the limit concepts are an admirable achievement, but they are only one step towards the goal of a final foundation of analysis. The nineteenth century solution of the problem of foundations consists of recognizing, in addition to the concept of natural number as the basis of arithmetic, another basic concept for analysis, namely the concept of set. By the inventors of set theory it was strongly held that these sets are self-evident to our intuition; but very soon the belief in their self-evidence was destroyed by the set-theoretic paradoxes. After that, about 1908, the period of axiomatic set theory began. In analogy to geometry there was put forward an uninterpreted system of axioms, a formal system. This, of course, is quite possible. A formal system contains strings of marks; and a special class of these strings, the class of the so-called “theorems”, is inductively defined.

It is a scientific platitude that there can be neither precise control nor prediction of phenomena without measurement. Disciplines are diverse as cosmology and social psychology provide evidence that it is nearly useless to have an exactly formulated quantitative theory if empirically feasible methods of measurement cannot be developed for a substantial portion of the quantitative concepts of the theory. Given a physical concept like that of mass or a psychological concept like that of habit strength, the point of a theory of measurement is to lay bare the structure of a collection of empirical relations which may be used to measure the characteristic of empirical phenomena corresponding to the concept. Why a collection of relations? From an abstract standpoint a set of empirical data consists of a collection of relations between specified objects. For example, data on the relative weights of a set of physical objects are easily represented by an ordering relation on the set; additional data, and a fortiori an additional relation, are needed to yield a satisfactory quantitative measurement of the masses of the objects.

The major source of difficulty in providing an adequate theory of measurement is to construct relations which have an exact and reasonable numerical interpretation and yet also have a technically practical empirical interpretation. The classical analyses of the measurement of mass, for instance, have the embarrassing consequence that the basic set of objects measured must be infinite. Here the relations postulated have acceptable numerical interpretations, but are utterly unsuitable empirically. Conversely, as we shall see in the last section of this paper, the structure of relations which have a sound empirical meaning often cannot be succinctly characterized so as to guarantee a desired numerical interpretation.

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.

In this paper we answer some of the questions left open in [2]. We use the terminology of [2]. In particular, a theory will be a formal system formulated within the first-order calculus with identity. A theory is identified with the set of Gödel numbers of the theorems of the theory. Thus Craig's theorem [1] asserts that a theory is axiomatizable if and only if it is recursively enumerable.

In [2], Feferman showed that if A is any recursively enumerable set, then there is an axiomatizable theory T having the same degree of unsolvability as A. (This result was proved independently by D. B. Mumford.) We show in Theorem 2 that if A is not recursive, then T may be chosen essentially undecidable. This depends on Theorem 1, which is a result on recursively enumerable sets of some independent interest.

Our second result, given in Theorem 3, gives sufficient conditions for a theory to be creative. These conditions are more general than those given by Feferman. In particular, they show that the system of Kreisel described in [2] is creative.

We offer a simple alternative proof of Theorem II, Kleene [1]:

Theorem. For certain primitive recursive -predicates R and S,

We separate the definitions of < o and O:

Definition 1. (1) 1 <o2; (2) for all y, if 1 <oy, then y <o 2v; (3) for all e, if (n)(Ey)T(e, no, y) and (n)(e(no) <oe((n+1)o)), then (n)(e(no) <o 3·5e); (4) for all x, y, z, if x <oy, y <oz, then x <oz; (5) a <ob only as required by (1)–(4).

Definition 2. a ϵ O if and only if 1 <o 2α.

If we write α(2a·3b) = O for a <ob in Conditions (1) to (4) of Definition 1 and take their conjunction, we get an arithmetic predicate P(α). By the Frege-Dedekind device for handling inductive definitions,

Hence, by Theorem 1 (Part 2) of [2], we have a primitive recursive S such that a <o b ≡ (α)(Ey)S(a, b, α, y). By Definition 2,

The classical use of the function quantifier (α) in the above proof is conspicuous. It is not clear that the constructive or intuitionistic content of Kleene's proof (cf. [1] Footnote 40) can be obtained by this method.

Plutarch berichtet, Chrysipp habe gesagt, “daß die Konjunktionen aus 10 Aussagen zahlenmäßig 1.000.000 übertreffen, ohne daß er das zuvor selbst genau untersucht hat oder von Fachleuten die Wahrheit erkundet hat …. Den Chrysipp widerlegen alle Arithmetiker, unter ihnen Hipparch, der beweist, daß ihm (Chrysipp) ein sehr großer Rechenfehler unterlaufen ist insofern, als nämlich das Bejahende 103.049 Konjunktionen ausmache, das Verneinende 310.952.”

Ohne Zweifel liegt hier eine der frühesten uns bekannten Aufgaben aus dem Gebiete der Kombinatorik, − neben der Berechnung der Zahl der Silben durch Xenokrates, die sich aus der Zusammenstellung von Buchstaben ergeben −, vor. Außerdem handelt es sich um die erste Anwendung der Kombinatorik in der Logik, bei der Werte auftreten, die nicht durch einfaches Abzählen gewonnen sein können.

Es ist bisher weder eine befriedigende Deutung der von Plutarch gegebenen Zahlenwerte noch, von der Interpretation ausgehend, eine Wiederherstellung der von den Alten benutzten Formeln gelungen.

If a contradiction is deduced by using only the defining formula of a set, it is called a contradiction of Russell's type, and the set is called inconsistent. A set is called consistent, if no contradiction can be deduced from the defining formula of the set.

The object of this note is to determine some conditions for some sets to be consistent or inconsistent.

In §1 notations and terms are defined. In §2 main results are stated. In §3, the proof in UL of a contradiction is simplified for a special kind of sets, so that a simplified definition of the proof of a contradiction is given for the kind of sets, and some properties of a proof in UL are stated concerning the simplified definition. This definition and the properties of a proof are the basis of the proof of the results given in §§5–10. Thus, this Part (V), except §3, is written independently of other Parts as far as possible. However, it depends essentially on Parts (I) and (II). In §4 some examples are given.

Adam of Balsham (Parvipontanus) writing his Ars Disserendi in 1132 A.D. reaches the notion of a set A equinumerous with a set B containing A as a proper sub-set. References by page and line are to [Minio-Paluello].

It can be asked, says Adam (92,13) whether this one is something, and whether that one is something, and these are two askables (interrogabilia), and again whether a third is something, and similarly of anything whatever. He thinks, then, of the totality of ‘objects’ (92,12) as numbered. But this question can be put not only about those which are not askables; of any askable too it can be asked whether it is something. Whether the questions be actually put or not, makes no difference; even when they are not put, the points remain askable. Thus the totality of askables is seen to be equinumerous with the totality of objects, which last comprises both the objects which are not askables and those which are. And so the same set is more numerous than itself.

Conscious that this paradoxical situation may be ascribed to his novel terminology and methods, Adam points out that a similar puzzle arises over things enunciated. Even if you do not want to term them ‘enunciables,’ still they are generally said to be true or false. Take the true ones, and compare them as to number with the totality of objects of which enunciations can be made. There he leaves this second version, but it is easy to see how the same result as before can be reached.

The argument lightly paraphrased in the last paragraph but one concludes with the words ‘which is impossible’ (92,21). Instead, however, of rejecting some of his premisses, Adam lets everything stand, and breaks off the discussion on the ground that his purpose is to expound a finite process of achievement (artis viam finitam) rather than what infinitely exceeds our capability to construct − or perhaps, the infinitely extending realm of possibility (possibilitatis excessum infinitum, 93,3–5).

The system K′ of “extended basic logic” lacks a principle of extensionality. In this paper a system KE′ will be presented which is like K′ in many respects but which does possess a fairly strong principle of extensionality by way of rule 6.37 below. It will be shown that KE′ is free from contradiction. KE′ is especially well suited for formalizing the theory of numbers presented in my paper, On natural numbers, integers, and rationals. The methods used there can be applied even more directly here because of the freedom of KE′ from type restrictions, but the details of such a derivation of a portion of mathematics will not be presented in this paper. It is evident, moreover, that KE′ contains at least as much of mathematical analysis as does K′, and perhaps considerably more. The method of carrying out proofs in KE′ is closely similar to that used in my book Symbolic logic, and could be expressed in similar notation.

In this note we show how Carnap's theory of degree of confirmation (inductive logic) may be constructed upon a very simple and restricted semantical basis. The semantical meta-languages here may either be based upon a relation of multiple denotation or may even be non-translational. To these meta-languages a suitable metric for sentences may be appended. Axioms for such meta-languages are suggested, so that an especially simple formalization of Carnap's inductive logic is in effect presented in outline.

For Carnap, inductive logic consists, roughly speaking, of a semantics augmented by a metric. More specifically, for a finite object-language the semantics consists of a theory of designation for , and to this are added numerical functions on sentences of taking real numbers as values. (, it will be recalled, contains just N distinct individual constants as primitive, where ‘N’ is a constant standing for some fixed finite number. contains a denumerable infinity of distinct individual constants as primitive, and will be discussed in a moment.) Were we to formalize this theory we should have, then, a translation of (or just itself), a syntax for , a primitive relation of designation, real numbers, and several different kinds of class and relational variables. The character of the underlying syntax is not clear from Carnap's account, but this can easily be supplied by a suitable adaptation of Tarski's method. For this, variables for classes of and relations between the expressions of the object-language are needed. Also in Carnap's theory of designation, variables over relations between expressions and objects are needed fundamentally. Real numbers may be handled in various ways. To simplify, let us suppose these are introduced by having a special kind of variable to range over them. Then suitable axioms for real numbers may be given, e.g., one of the axiom sets of Tarski.

A (binary) relation is a collection of ordered couples. Two relations are isomorphic if there is a 1–1 correspondence between their fields which preserves the ordered couples. Isomorphism between relations is itself an equivalence relation, and a structure is an isomorphism class of binary relations.

Carnap ([1], p. 124) asks certain questions concerning (both the exact and) the asymptotic value of the relative frequency that a relation on p objects satisfies certain properties. Among the most interesting special cases are the asymptotic value of the relative frequency that a binary relation on p objects be (a) symmetric, (b) reflexive, (c) transitive irreflexive anti-symmetric, and (d) symmetric irreflexive. These results already appear either in, or almost in, the literature, in various disguises. The object of this expository note is to bring them to light, especially since some of the references may not be generally known to logicians.

Carnap ([1], p. 124) points out explicitly the correspondence between binary relations and linear graphs. Davis [2] and Harary [4] obtains precise results for the number of structures with certain properties using the language of relations and graphs respectively; but these do not supply the asymptotic values directly. The asymptotic results which are most useful here are either contained in, or are straight-forward extensions of, the formulas presented in Ford and Uhlenbeck [3], which in turn are based on unpublished work of G. Pólya. In addition, we utilize a result of L. Moser on transitive relations, which appears in Wine and Freund [5].

In this note we shall prove a certain relative recursiveness lemma concerning countable models of set theory (Lemma 5). From this lemma will follow two results about special types of such models.

Kreisel [5] and Mostowski [6] have shown that certain (finitely axiomatized) systems of set theory, formulated by means of the ϵ relation and certain additional non-logical constants, do not possess recursive models. Their purpose in doing this was to construct consistent sentences without recursive models. As a first corollary of Lemma 5, we obtain a very simple proof, not involving any formal constructions within the system of the notions of truth and satisfiability, of an extension of the Kreisel-Mostowski theorems. Namely, set theory with the single non-logical constant ϵ does not possess any recursively enumerable model. Thus we get, as a side product, an easy example of a consistent sentence containing a single binary relation which does not possess any recursively enumerable model; this sentence being the conjunction of the (finitely many) axioms of set theory.

In 1885 Peirce axiomatised the propositional calculus on the basis of five ‘icons’ or axioms, which with Cpq for ‘If p then q’ and o for a false proposition, and with the source in Peirce's [2] beside each, may be represented as follows: 1. Cpp (3.376); 2. CCpCqrCqCpr (3.377); 3. CCpqCCqrCpr (3.379); 4. Cop (3.381); 5. CCCpqpp (3.384). From these Peirce proves, among other things, 6. CpCCpqq (3.377), 7. CpCqp (3.378), and with Np (Not p) for Cpo, 8. CNNpp (3.384).

By a well-known result of Wajsberg's II. 93, the entire two-valued propositional calculus is derivable by substitution and detachment from 3, 4, 5, and 7 (with Df. N). In Berry [1] this is taken to show the completeness of Peirce's basis; but this proof will not do as it stands. For Peirce's proof of 7 consists in first passing from 1 to CqCpp by the argument that ‘to say that (x ⥽ x) is generally true is to say that it is so in every state of things, say in that in which y is true’; and then from CqCpp to 7 by 2. This procedure clearly involves, formally, the use not only of substitution and detachment but of a rule to infer ⊦ Cqα. from ⊦α. Peirce's basis is sufficient with substitution and detachment nevertheless; for by a less well-known result of Wajsberg's II. 93, 3, 4, 5, and 6 are sufficient in this sense, and Peirce does prove 6 by substitution and detachment from 1 and 2.

Mr. L. J. Cohen's interesting example of a logical truth of indirect discourse appears to be capable of a simple formalisation and proof in a variant of first order predicate calculus. His example has the form:

If A says that anything which B says is false, and B says that something which A says is true, then something which A says is false and something which B says is true.

Let ‘A says x’ be formalised by ‘A(x)’ and let assertions of truth and falsehood be formalised as in the following table.

We treat both variables x and predicates A (x) as sentences and add to the familiar axioms and inference rules of predicate logic a rule permitting the inference of A(p) from (x)A(x), where p is a closed sentence.

We have to prove that from

In attempting to reconstruct Rose's proof of Lemma 3.2 of [1], the present authors found what is apparently a different and simpler method, which moreover leads to a far stronger conclusion.

We are operating in the Heyting prepositional calculus as formulated on p. 3 of [1] or on pp. 82 and 101 of [2], and shall make use of relevant theorems on pp. 90, 113–119 of [2]. We shall use a, b, c, w, x, y, z as propositional variables.

We say that a conjunction is simple if each factor has one of the forms: (i) a, (ii) ¬a, (iii) a⊃b, (iv) a⊃(b∨c), (v) (a&b)⊃c, (vi) (a⊃b)⊃c.

What I am offering here is a reconsideration, and in the end a solution, of the ancient paradox of the Epimenides. What has provoked this new assault on so old a stronghold is L. Jonathan Cohen's [2], in which it is rightly pointed out that the Epimenidean as contrasted with the Eubulidean version of the Liar paradox is the one that threatens logicians who attempt to formalise the use of indirect rather than direct discourse. Among these he includes myself, referring to the system sketched on pp. 130–131 of my [4], and suggesting that I ought to have shown how a person interpreting this system in the obvious way can avoid semantic antinomies. Here too he is right, and my main purpose now is not to criticise his paper, but to fill in this lacuna in my own work to which he has drawn attention. I do want, however, to make one small criticism at the start, namely that Cohen fails to notice what it is that is really paradoxical about the Epimenides, and in consequence fails to perceive the same paradoxical character in a proposition which he is himself quite happy to accept as a ‘logical truth.’

The point about the Epimenides, as was noted by Church in [1], is not that when we examine the truth value of a Cretan's assertion that nothing true is ever asserted by a Cretan we are led to contradictory conclusions, for we are not; the paradox is rather that such examination makes it seem possible to settle an empirical question on logical grounds. If we treat the Cretan's assertion as true, and so assume that nothing true is ever asserted by a Cretan, it follows immediately that the Cretan's assertion is false. If, however, we treat it as false, there is no way of deducing from this assumption that it is true. We can, therefore, consistently suppose it to be false, and this is all that we can consistently suppose. But to suppose it false (considering what the assertion actually is) is to suppose that something asserted by a Cretan is true; and this of course can only be some other assertion than the one mentioned. We thus reach the peculiar conclusion that if any Cretan does assert that nothing asserted by a Cretan is true, then this cannot possibly be the only assertion made by a Cretan — there must also be, beside this false Cretan assertion, some true one.