1. Introduction
Main Results
Let us remind that accordingly to naive set theory, any definable collection is a set. Let R be the set of all sets that are not members of themselves. If R qualifies as a member of itself, it would contradict its own definition as a set containing all sets that are not members of themselves. On the other hand, if such a set is not a member of itself, it would qualify as a member of itself by the same definition. This contradiction is Russell’s paradox. In 1908, two ways of avoiding the paradox were proposed, Russell’s type theory and Zermelo set theory, the first constructed axiomatic set theory. Zermelo’s axioms went well beyond Frege’s axioms of extensionality and unlimited set abstraction, and evolved into the now-canonical Zermelo-Fraenkel set theory ZFC. “But how do we know that ZFC is a consistent theory, free of contradictions? The short answer is that we don’t; it is a matter of faith (or of skepticism)”—E. Nelson wrote in his paper [1] . However, it is deemed unlikely that even ZFC2 which is significantly stronger than ZFC harbors an unsuspected contradiction; it is widely believed that if ZFC and ZFC2 were consistent, that fact would have been uncovered by now. This much is certain—ZFC and ZFC2 are immune to the classic paradoxes of naive set theory: Russell’s paradox, the Burali-Forti paradox, and Cantor’s paradox.
Remark 1.1.1. The inconsistency of the second-order set theory ZFC2082 originally have been uncovered in [2] and officially announced in [3] , see also ref. [4] [5] [6] .
Remark 1.1.2. In order to derive a contradiction in second-order set theory ZFC2 with the Henkin semantics [7] , we remind the definition given in P. Cohen handbook [8] (see [8] Ch. III, sec. 1, p. 87). P. Cohen wrote: “A set which can be obtained as the result of a transfinite sequence of predicative definitions Godel called ‘constructible’”. His result then is that the constructible sets are a model for ZF and that in this model GCH and AC hold. The notion of a predicative construction must be made more precise, of course, but there is essentially only one way to proceed. Another way to explain constructibility is to remark that the constructible sets are those sets which just occur in any model in which one admits all ordinals. The definition we now give is the one used in [9] .
Definition 1.1.1. [8] . Let X be a set. The set
is defined as the union of X and the set Y of all sets y for which there is a formula
in ZF such that if
denotes A with all bound variables restricted to X, then for some
, in X,
(1)
Observe
,
if X is infinite (and we assume AC). It should be clear to the reader that the definition of
, as we have given it, can be done entirely within ZF and that
is a single formula
in ZF. In general, one’s intuition is that all normal definitions can be expressed in ZF, except possibly those which involve discussing the truth or falsity of an infinite sequence of statements. Since this is a very important point we shall give a rigorous proof in a later section that the construction of
is expressible in ZF.”
Remark 1.1.3. We will say that a set y is definable by the formula
relative to a given set X.
Remark 1.1.4. Note that a simple generalisation of the notion of the definability which has been by Definition 1.1.1 immediately gives Russell’s paradox in second order set theory ZFC2 with the Henkin semantics [7] .
Definition 1.1.2. [6] . i) We will say that a set y is definable relative to a given set X iff there is a formula
in ZFC then for some
, in X there exists a set z such that the condition
is satisfied and
or symbolically
(2)
It should be clear to the reader that the definition of
, as we have given it, can be done entirely within second order set theory ZFC2 with the Henkin semantics [7] denoted by
and that
is a single formula
in
.
ii) We will denote the set Y of all sets y definable relative to a given set X by
.
Definition 1.1.3. Let
be a set of the all sets definable relative to a given set X by the first order 1-place open wff’s and such that
(3)
Remark 1.1.5. (a) Note that
since
is a set definable by the first order 1-place open wff
:
(4)
Theorem 1.1.1. [6] . Set theory
is inconsistent.
Proof. From (3) and Remark 1.1.2 one obtains
(5)
From (5) one obtains a contradiction
(6)
Remark 1.1.6. Note that in paper [6] we dealing by using following definability condition: a set y is definable if there is a formula
in ZFC such that
(7)
Obviously in this case a set
is a countable set.
Definition 1.1.4. Let
be the countable set of the all sets definable by the first order 1-place open wff’s and such that
(8)
Remark 1.1.7. (a) Note that
since
is a set definable by the first order 1-place open wff
:
(9)
one obtains a contradiction
.
In this paper we dealing by using following definability condition.
Definition 1.1.5. i) Let
be a standard model of ZFC. We will say that a set y is definable relative to a given standard model
of ZFC if there is a formula
in ZFC such that if
denotes A with all bound variables restricted to
, then for some
, in
there exists a set z such that the condition
is satisfied and
or symbolically
(10)
It should be clear to the reader that the definition of
, as we have given it, can be done entirely within second order set theory ZFC2 with the Henkin semantics.
ii) In this paper we assume for simplicity but without loss of generality that
(11)
Remark 1.1.8. Note that in this paper we view i) the first order set theory ZFC under the canonical first order semantics ii) the second order set theory ZFC2 under the Henkin semantics [7] and iii) the second order set theory ZFC2 under the full second-order semantics [8] [9] [10] [11] [12] but also with a proof theory based on formal Urlogic [13] .
Remark 1.1.9. Second-order logic essentially differs from the usual first-order predicate calculus in that it has variables and quantifiers not only for individuals but also for subsets of the universe and variables for n-ary relations as well [7] - [13] . The deductive calculus
of second order logic is based on rules and axioms which guarantee that the quantifiers range at least over definable subsets [7] . As to the semantics, there are two types of models: i) Suppose
is an ordinary first-order structure and
is a set of subsets of the domain A of
. The main idea is that the set-variables range over
, i.e.
.
We call
a Henkin model, if
satisfies the axioms of
and truth in
is preserved by the rules of
. We call this semantics of second-order logic the Henkin semantics and second-order logic with the Henkin semantics the Henkin second-order logic. There is a special class of Henkin models, namely those
where
is the set of all subsets of A.
We call these full models. We call this semantics of second-order logic the full semantics and second-order logic with the full semantics the full second-order logic.
Remark 1.1.10. We emphasize that the following facts are the main features of second-order logic:
1) The Completeness Theorem: A sentence is provable in
if and only if it holds in all Henkin models [7] - [13] .
2) The Löwenheim-Skolem Theorem: A sentence with an infinite Henkin model has a countable Henkin model.
3) The Compactness Theorem: A set of sentences, every finite subset of which has a Henkin model, has itself a Henkin model.
4) The Incompleteness Theorem: Neither
nor any other effectively given deductive calculus is complete for full models, that is, there are always sentences which are true in all full models but which are unprovable.
5) Failure of the Compactness Theorem for full models.
6) Failure of the Löwenheim-Skolem Theorem for full models.
7) There is a finite second-order axiom system
such that the semiring
of natural numbers is the only full model of
up to isomorphism.
8) There is a finite second-order axiom system RCF2 such that the field
of the real numbers is the only full model of RCF2 up to isomorphism.
Remark 1.1.11. For let second-order ZFC be, as usual, the theory that results obtained from ZFC when the axiom schema of replacement is replaced by its second-order universal closure, i.e.
(12)
where X is a second-order variable, and where
abbreviates “X is a functional relation”, see [12] .
Thus we interpret the wff’s of ZFC2 language with the full second-order semantics as required in [12] [13] but also with a proof theory based on formal urlogic [13] .
Designation 1.1.1. We will denote: i) by
set theory
with the Henkin semantics,
ii) by
set theory
with the full second-order semantics,
iii) by
set theory
and
iv) by
set theory
, where
is a standard model of the theory
.
Remark 1.1.12. There is no completeness theorem for second-order logic with the full second-order semantics. Nor do the axioms of
imply a reflection principle which ensures that if a sentence Z of second-order set theory is true, then it is true in some model
of
[11] .
Let Z be the conjunction of all the axioms of
. We assume now that: Z is true, i.e.
. It is known that the existence of a model for Z requires the existence of strongly inaccessible cardinals, i.e. under ZFC it can be shown that
is a strongly inaccessible if and only if
is a model of
. Thus
(13)
In this paper we prove that:
i)
ii)
and iii)
is inconsistent, where
is a standard model of the theory
.
Axiom
[8] . There is a set
and a binary relation
which makes
a model for ZFC.
Remark 1.1.13. i) We emphasize that it is well known that axiom
a single statement in ZFC see [8] , Ch. II, Section 7. We denote this statement thought all this paper by symbol
. The completeness theorem says that
.
ii) Obviously there exists a single statement in
such that
.
We denote this statement through all this paper by symbol
and there exists a single statement
in
. We denote this statement through all this paper by symbol
.
Axiom
[8] . There is a set
such that if R is
then
is a model for ZFC under the relation R.
Definition 1.1.6. [8] . The model
is called a standard model since the relation
used is merely the standard
-relation.
Remark 1.1.14. Note that axiom
doesn’t imply axiom
, see ref. [8] .
Remark 1.1.15. We remind that in Henkin semantics, each sort of second-order variable has a particular domain of its own to range over, which may be a proper subset of all sets or functions of that sort. Leon Henkin (1950) defined these semantics and proved that Gödel’s completeness theorem and compactness theorem, which hold for first-order logic, carry over to second-order logic with Henkin semantics. This is because Henkin semantics are almost identical to many-sorted first-order semantics, where additional sorts of variables are added to simulate the new variables of second-order logic. Second-order logic with Henkin semantics is not more expressive than first-order logic. Henkin semantics are commonly used in the study of second-order arithmetic. Väänänen [13] argued that the choice between Henkin models and full models for second-order logic is analogous to the choice between ZFC and
(
is von Neumann universe), as a basis for set theory: “As with second-order logic, we cannot really choose whether we axiomatize mathematics using
or ZFC. The result is the same in both cases, as ZFC is the best attempt so far to use
as an axiomatization of mathematics”.
Remark 1.1.16. Note that in order to deduce: i)
from
,
ii)
from
, by using Gödel encoding, one needs something more than the consistency of
, e.g., that
has an omega-model
or an standard model
i.e., a model in which the integers are the standard integers and the all wff of
, ZFC, etc. represented by standard objects. To put it another way, why should we believe a statement just because there’s a
-proof of it? It’s clear that if
is inconsistent, then we won’t believe
-proofs. What’s slightly more subtle is that the mere consistency of
isn’t quite enough to get us to believe arithmetical theorems of
; we must also believe that these arithmetical theorems are asserting something about the standard naturals. It is “conceivable” that
might be consistent but that the only nonstandard models
it has are those in which the integers are nonstandard, in which case we might not “believe” an arithmetical statement such as “
is inconsistent” even if there is a
-proof of it.
Remark 1.1.17. Note that assumption
is not necessary if nonstandard model
is a transitive or has a standard part
, see [14] [15] .
Remark 1.1.18. Remind that if M is a transitive model, then
is the standard
. This implies that the natural numbers, integers, and rational numbers of the model are also the same as their standard counterparts. Each real number in a transitive model is a standard real number, although not all standard reals need be included in a particular transitive model. Note that in any nonstandard model
of the second-order arithmetic
the terms
comprise the initial segment isomorphic to
. This initial segment is called the standard cut of the
. The order type of any nonstandard model of
is equal to
, see ref. [16] , for some linear order A.
Thus one can choose Gödel encoding inside the standard model
.
Remark 1.1.19. However there is no any problem as mentioned above in second order set theory
with the full second-order semantics because corresponding second order arithmetic
is categorical.
Remark 1.1.20. Note if we view second-order arithmetic
as a theory in first-order predicate calculus. Thus a model
of the language of second-order arithmetic
consists of a set M (which forms the range of individual variables) together with a constant 0 (an element of M), a function S from M to M, two binary operations + and × on M, a binary relation < on M, and a collection D of subsets of M, which is the range of the set variables. When D is the full power set of M, the model
is called a full model. The use of full second-order semantics is equivalent to limiting the models of second-order arithmetic to the full models. In fact, the axioms of second-order arithmetic have only one full model. This follows from the fact that the axioms of Peano arithmetic with the second-order induction axiom have only one model under second-order semantics, i.e.
, with the full semantics, is categorical by Dedekind’s argument, so has only one model up to isomorphism. When M is the usual set of natural numbers with its usual operations,
is called an ω-model. In this case we may identify the model with D, its collection of sets of naturals, because this set is enough to completely determine an ω-model. The unique full omega-model
, which is the usual set of natural numbers with its usual structure and all its subsets, is called the intended or standard model of second-order arithmetic.
2. Generalized Löb’s Theorem. Remarks on the Tarski’s Undefinability Theorem
2.1. Remarks on the Tarski’s Undefinability Theorem
Remark 2.1.1. In paper [2] under the following assumption
(14)
it has been proved that there exists countable Russell’s set
such that the following statement is satisfied:
(15)
From (15) it immediately follows a contradiction
(16)
From (16) and (14) by reductio and absurdum it follows
(17)
Theorem 2.1.1. [17] [18] [19] . (Tarski’s undefinability theorem). Let
be first order theory with formal language
, which includes negation and has a Gödel numbering
such that for every
-formula
there is a formula B such that
holds. Assume that
has a standard model
and
where
(18)
Let
be the set of Gödel numbers of
-sentences true in
. Then there is no
-formula
(truth predicate) which defines
. That is, there is no
-formula
such that for every
-formula A,
(19)
where the abbreviation
means that A holds in standard model
, i.e.
. Therefore
implies that
(20)
Thus Tarski’s undefinability theorem reads
(21)
Remark 2.1.2. i) By the other hand the Theorem 2.1.1 says that given some really consistent formal theory
that contains formal arithmetic, the concept of truth in that formal theory
is not definable using the expressive means that that arithmetic affords. This implies a major limitation on the scope of “self-representation”. It is possible to define a formula
, but only by drawing on a metalanguage whose expressive power goes beyond that of
. To define a truth predicate for the metalanguage would require a still higher metametalanguage, and so on.
ii) However if formal theory
is inconsistent this is not surprising if we define a formula
by drawing only on a language
.
iii) Note that if under assumption
we define a formula
by drawing only on a language
by reductio ad absurdum it follows
(22)
Remark 2.1.3. i) Let
be a theory
. In this paper under assumption
we define a formula
by drawing only on a language
by using Generalized Löb’s theorem [4] [5] . Thus by reductio ad absurdum it follows
(23)
ii) However note that in this case we obtain
by using approach that completely different in comparison with approach based on derivation of the countable Russell’s set
with conditions (15).
2.2. Generalized Löb’s Theorem
Definition 2.2.1. Let
be first order theory and
. A theory
is complete if, for every formula A in the theory’s language
, that formula A or its negation
is provable in
, i.e., for any wff A, always
or
.
Definition 2.2.2. Let
be first order theory and
. We will say that a theory
is completion of the theory
if i)
, ii) a theory
is complete.
Theorem 2.2.1. [4] [5] . Assume that:
, where
. Then there exists completion
of the theory
such that the following conditions hold:
i) For every formula A in the language of ZFC that formula
or formula
is provable in
i.e., for any wff A, always
or
.
ii)
, where for any m a theory
is finite extension of the theory
.
iii) Let
be recursive relation such that: y is a Gödel number of a proof of the wff of the theory
and x is a Gödel number of this wff. Then the relation
is expressible in the theory
by canonical Gödel encoding and really asserts provability in
.
iv) Let
be relation such that: y is a Gödel number of a proof of the wff of the theory
and x is a Gödel number of this wff. Then the relation
is expressible in the theory
by the following formula
(24)
v) The predicate
really asserts provability in the set theory
.
Remark 2.2.1. Note that the relation
is expressible in the theory
since a theory
is a finite extension of the recursively axiomatizable theory ZFC and therefore the predicate
exists since any theory
is recursively axiomatizable.
Remark 2.2.2. Note that a theory
obviously is not recursively axiomatizable nevertheless Gödel encoding holds by Remark 2.2.1.
Theorem 2.2.2. Assume that:
, where
. Then truth predicate
is expressible by using only first order language by the following formula
(25)
Proof. Assume that:
(26)
It follows from (26) there exists
such that
and therefore by (24) we obtain
(27)
From (24) immediately by definitions one obtains (25).
Remark 2.2.3. Note that Theorem 2.1.1 in this case reads
(28)
Theorem 2.2.3.
.
Proof. Assume that:
. From (25) and (28) one obtains a contradiction
(see Remark 2.1.3) and therefore by reductio ad absurdum it follows
.
Theorem 2.2.4. [4] [5] . Let
be a nonstandard model of ZFC and let
be a standard model of PA.
We assume now that
and denote such nonstandard model of the set theory ZFC by
. Let
be the theory
. Assume that:
, where
. Then there exists completion
of the theory
such that the following conditions hold:
i) For every formula A in the language of ZFC that formula
or formula
is provable in
i.e., for any wff A, always
or
.
ii)
, where for any m a theory
is finite extension of the theory
.
iii) Let
be recursive relation such that: y is a Gödel number of a proof of the wff of the theory
and x is a Gödel number of this wff. Then the relation
is expressible in the theory
by canonical Gödel encoding and really asserts provability in
.
iv) Let
be relation such that: y is a Gödel number of a proof of the wff of the theory
and x is a Gödel number of this wff. Then the relation
is expressible in the theory
by the following formula
(29)
v) The predicate
really asserts provability in the set theory
.
Remark 2.2.4. Note that the relation
is expressible in the theory
since a theory
is a finite extension of the recursively axiomatizable theory ZFC and therefore the predicate
exists since any theory
is recursively axiomatizable.
Remark 2.2.5. Note that a theory
obviously is not recursively axiomatizable nevertheless Gödel encoding holds by Remark 2.2.1.
Theorem 2.2.5. Assume that:
, where
,
.
Then truth predicate
is expressible by using first order language by the following formula
(30)
Proof. Assume that:
(31)
It follows from (29) there exists
such that
and therefore by (31) we obtain
(32)
From (32) immediately by definitions one obtains (30).
Remark 2.2.6. Note that Theorem 2.1.1 in this case reads
(33)
Theorem 2.2.6.
.
Proof. Assume that:
. From (30) and (33) one obtains a contradiction
and therefore by reductio ad absurdum it follows
.
Theorem 2.2.7. Assume that:
, where
. Then there exists completion
of the theory
such that the following conditions hold:
i) For every first order wff formula A (wff1 A) in the language of
that formula
or formula
is provable in
i.e., for any wff1 A, always
or
.
ii)
, where for any m a theory
is finite extension of the theory
.
iii) Let
be recursive relation such that: y is a Gödel number of a proof of the wff1 of the theory
and x is a Gödel number of this wff1. Then the relation
is expressible in the theory
by canonical Gödel encoding and really asserts provability in
.
iv) Let
be relation such that: y is a Gödel number of a proof of the wff of the set theory
and x is a Gödel number of this wff1. Then the relation
is expressible in the set theory
by the following formula
(34)
v) The predicate
really asserts provability in the set theory
.
Remark 2.2.7. Note that the relation
is expressible in the theory
since a theory
is a finite extension of the finite axiomatizable theory
and therefore the predicate
exists since any theory
is recursively axiomatizable.
Remark 2.2.8. Note that a theory
obviously is not recursively axiomatizable nevertheless Gödel encoding holds by Remark 2.2.1.
Theorem 2.2.8. Assume that:
, where
.
Then truth predicate
is expressible by using first order language by the following formula
(35)
where A is wff1.
Proof. Assume that:
(36)
It follows from (34) there exists
such that
and therefore by (36) we obtain
(37)
From (37) immediately by definitions one obtains (35).
Remark 2.2.9. Note that in considered case Tarski’s undefinability theorem (2.1.1) reads
(38)
where A is wff1.
Theorem 2.2.9.
.
Proof. Assume that:
. From (35) and (38) one obtains a contradiction
and therefore by reductio ad absurdum it follows
.
3. Derivation of the Inconsistent Provably Definable Set in Set Theory
,
and
3.1. Derivation of the Inconsistent Provably Definable Set in Set Theory
Definition 3.1.1. i) Let
be a wff of
. We will say that
is a first order n-place open wff if
contains free occurrences of the first order individual variables
and quantifiers only over any first order individual variables
.
ii) Let
be the countable set of the all first order provable definable sets X, i.e. sets such that
, where
is a first order 1-place open wff that contains only first order variables (we will denote such wff for short by wff1), with all bound variables restricted to standard model
, i.e.
(39)
or in a short notation
(40)
Notation 3.1.1. In this subsection we often write for short
instead
but this should not lead to a confusion.
Assumption 3.1.1. We assume now for simplicity but without loss of generality that
(41)
and therefore by definition of model
one obtains
.
Let
be a predicate such that
. Let
be the countable set of the all sets such that
(42)
From (42) one obtains
(43)
But obviously (43) immediately gives a contradiction
(44)
Remark 3.1.1. Note that a contradiction (44) in fact is a contradiction inside
for the reason that predicate
is expressible by first order
language as predicate of
(see subsection 1.2, Theorem 1.2.8 (ii)-(iii)) and therefore countable sets
and
are sets in the sense of the set theory
.
Remark 3.1.2. Note that by using Gödel encoding the above stated contradiction can be shipped in special completion
of
, see subsection 1.2, Theorem 1.2.8.
Remark 3.1.3. i) Note that Tarski’s undefinability theorem cannot block the equivalence (43) since this theorem is no longer holds by Proposition 2.2.1. (Generalized Löbs Theorem).
ii) In additional note that: since Tarski’s undefinability theorem has been proved under the same assumption
by reductio ad absurdum it follows again
, see Theorem 1.2.10.
Remark 3.1.4. More formally we can to explain the gist of the contradictions derived in this paper (see Section 4) as follows.
Let M be Henkin model of
. Let
be the set of the all sets of M provably definable in
, and let
where
means “sentence A derivable in
”, or some appropriate modification thereof. We replace now formula (39) by the following formula
(45)
and we replace formula (42) by the following formula
(46)
Definition 3.1.2. We rewrite now (45) in the following equivalent form
(47)
where the countable set
is defined by the following formula
(48)
Definition 3.1.3. Let
be the countable set of the all sets such that
(49)
Remark 3.1.5. Note that
since
is a set definable by the first order 1-place open wff1:
(50)
From (49) and Remark 3.1.4 one obtains
(51)
But (51) immediately gives a contradiction
(52)
Remark 3.1.6. Note that contradiction (52) is a contradiction inside
for the reason that the countable set
is a set in the sense of the set theory
.
In order to obtain a contradiction inside
without any reference to Assumption 3.1.1 we introduce the following definitions.
Definition 3.1.4. We define now the countable set
by the following formula
(53)
Definition 3.1.5. We choose now
in the following form
(54)
Here
is a canonical Gödel formula which says to us that there exists proof in
of the formula A with Gödel number
.
Remark 3.1.7. Note that the Definition 3.1.5 holds as definition of predicate really asserting provability of the first order sentence A in
.
Definition 3.1.6. Using Definition 3.1.5, we replace now formula (48) by the following formula
(55)
Definition 3.1.7. Using Definition 3.1.5, we replace now formula (49) by the following formula
(56)
Definition 3.1.8. Using Proposition 2.1.1 and Remark 2.1.10 [6] , we replace now formula (53) by the following formula
(57)
Definition 3.1.9. Using Definitions 3.1.4-3.1.6, we define now the countable set
by formula
(58)
Remark 3.1.8. Note that from the second order axiom schema of replacement (12) it follows directly that
is a set in the sense of the set theory
.
Definition 3.1.10. Using Definition 3.1.8 we replace now formula (56) by the following formula
(59)
Remark 3.1.9. Notice that the expression (60)
(60)
obviously is a well formed formula of
and therefore a set
is a set in the sense of
.
Remark 3.1.10. Note that
since
is a set definable by 1-place open wff
(61)
Theorem 3.1.1. Set theory
is inconsistent.
Proof. From (59) we obtain
(62)
a) Assume now that:
(63)
Then from (62) we obtain
and
,
therefore
and so
(64)
From (63)-(64) we obtain
and thus
.
b) Assume now that
(65)
Then from (65) we obtain
. From (65) and (62) we obtain
, so
,
which immediately gives us a contradiction
.
Definition 3.1.11. We choose now
in the following form
(66)
or in the following equivalent form
(67)
similar to (46). Here
is a Gödel formula which really asserts provability in
of the formula A with Gödel number
.
Remark 3.1.11. Notice that the Definition 3.1.12 with formula (66) holds as definition of predicate really asserting provability in
.
Definition 3.1.12. Using Definition 3.1.11 with formula (66), we replace now formula (48) by the following formula
(68)
Definition 3.1.13. Using Definition 3.1.11 with formula (66), we replace now formula (49) by the following formula
(69)
Definition 3.1.14. Using Definition 3.1.11 with formula (66), we replace now formula (53) by the following formula
(70)
Definition 3.1.15. Using Definitions 3.1.12-3.1.16, we define now the countable set
by formula
(71)
Remark 3.1.12. Note that from the axiom schema of replacement (12) it follows directly that
is a set in the sense of the set theory
.
Definition 3.1.16. Using Definition 3.1.15 we replace now formula (69) by the following formula
(72)
Remark 3.1.13. Notice that the expressions (73)
(73)
obviously are a well formed formula of
and therefore collection
is a set in the sense of
.
Remark 3.1.14. Note that
since
is a set definable by 1-place open wff1
(74)
Theorem 3.1.2. Set theory
is inconsistent.
Proof. From (72) we obtain
(75)
a) Assume now that:
(76)
Then from (75) we obtain
and therefore
, thus we obtain
(77)
From (76)-(77) we obtain
and
, thus
and finally we obtain
.
b) Assume now that
(78)
Then from (78) we obtain
. From (78) and (75) we obtain
, thus
and
which immediately gives us a contradiction
.
3.2. Derivation of the Inconsistent Provably Definable Set in Set Theory ZFCst
Let
be the countable set of all sets X such that
, where
is a 1-place open wff of ZFC i.e.,
(79)
Let
be a predicate such that
. Let
be the countable set of the all sets such that
(80)
From (80) one obtains
(81)
But (81) immediately gives a contradiction
(82)
Remark 3.2.1. Note that a contradiction (82) is a contradiction inside
for the reason that predicate
is expressible by using first order
language as predicate of
(see subsection 4.1) and therefore countable sets
and
are sets in the sense of the set theory
.
Remark 3.2.2. Note that by using Gödel encoding the above stated contradiction can be shipped in special completion
of
, see subsection 1.2, Theorem 1.2.2 (i).
Designation 3.2.1. i) Let
be a standard model of ZFC and
ii) let
be the theory
,
iii) let
be the set of the all sets of
provably definable in
, and let
, where
means: “sentence A derivable in
”, or some appropriate modification thereof.
We replace now (79) by formula
(83)
and we replace (80) by formula
(84)
Assume that
. Then, we have that:
iff
, which immediately gives us
iff
. But this is a contradiction, i.e.,
. We choose now
in the following form
(85)
Here
is a canonical Gödel formula which says to us that there exists proof in
of the formula A with Gödel number
.
Remark 3.2.3. Notice that Definition 3.2.6 holds as definition of predicate really asserting provability in
.
Definition 3.2.1. We rewrite now (83) in the following equivalent form
(86)
where the countable collection
is defined by the following formula
(87)
Definition 3.2.2. Let
be the countable collection of the all sets such that
(88)
Remark 3.2.4. Note that
since
is a collection definable by 1-place open wff
(89)
Definition 3.2.3. By using formula (85) we rewrite now (86) in the following equivalent form
(90)
where the countable collection
is defined by the following formula
(91)
Definition 3.2.4. Using formula (85), we replace now formula (88) by the following formula
(92)
Definition 3.2.5. Using Proposition 2.1.1 and Remark 2.2.2 [6] , we replace now formula (89) by the following formula
(93)
Definition 3.2.6. Using Definitions 3.2.3-3.2.5, we define now the countable set
by formula
(94)
Remark 3.2.5. Note that from the axiom schema of replacement it follows directly that
is a set in the sense of the set theory
.
Definition 3.2.7. Using Definition 3.2.6 we replace now formula (92) by the following formula
(95)
Remark 3.2.6. Notice that the expression (96)
(96)
obviously is a well formed formula of
and therefore collection
is a set in the sense of
.
Remark 3.2.7. Note that
since
is a collection definable by 1-place open wff
(97)
Theorem 3.2.1. Set theory
is inconsistent.
Proof. From (95) we obtain
(98)
a) Assume now that:
(99)
Then from (98) we obtain
and
, therefore
and so
(100)
From (99)-(100) we obtain
and therefore
.
b) Assume now that
(101)
Then from (101) we obtain
. From (101) and (98) we obtain
, so
which immediately gives us a contradiction
.
3.3. Derivation of the Inconsistent Provably Definable Set in ZFCNst
Designation 3.3.1. i) Let
be a first order theory which contain usual postulates of Peano arithmetic [8] and recursive defining equations for every primitive recursive function as desired.
ii) Let
be a nonstandard model of ZFC and let
be a standard model of
. We assume now that
and denote such nonstandard model of ZFC by
.
iii) Let
be the theory
.
iv) Let
be the set of the all sets of
provably definable in
, and let
where
means “sentence A derivable in
”, or some appropriate modification thereof. We replace now (45) by formula
(102)
and we replace (46) by formula
(103)
Assume that
. Then, we have that:
iff
, which immediately gives us
iff
. But this is a contradiction, i.e.,
. We choose now
in the following form
(104)
Here
is a canonical Gödel formula which says to us that there exists proof in
of the formula A with Gödel number
.
Remark 3.3.1. Notice that definition (104) holds as definition of predicate really asserting provability in
.
Designation 3.3.2. i) Let
be a Gödel number of given an expression u of
.
ii) Let
be the relation: y is the Gödel number of a wff of
that contains free occurrences of the variable with Gödel number v [6] [10] .
iii) Let
be a Gödel number of the following wff:
, where
,
,
.
iv) Let
be a predicate asserting provability in
.
Remark 3.3.2. Let
be the countable collection of all sets X such that
, where
is a 1-place open wff i.e.,
(105)
We rewrite now (105) in the following form
(106)
Designation 3.3.3. Let
be a Gödel number of the following wff:
, where
.
Remark 3.3.3. Let
above by formula (103), i.e.,
(107)
We rewrite now (107) in the following form
(108)
Theorem 3.3.1.
.
3.4. Generalized Tarski’s Undefinability Lemma
Remark 3.4.1. Remind that: i) if
is a theory, let
be the set of Godel numbers of theorems of
[10] , ii) the property
is said to be is expressible in
by wff
if the following properties are satisfied [10] :
a) if
then
, b) if
then
.
Remark 3.4.2. Notice it follows from (a)
(b) that
.
Theorem 3.4.1. (Tarski’s undefinability Lemma) [10] . Let
be a consistent theory with equality in the language
in which the diagonal function D is representable and let
be a Gödel number of given an expression u of
. Then the property
is not expressible in
.
Proof. By the diagonalization lemma applied to
there is a sentence
such that: c)
, where q is the Godel number of
, i.e.
.
Case 1. Suppose that
, then
. By (a),
. But, from
and (c), by biconditional elimination, one obtains
. Hence
is inconsistent, contradicting our hypothesis.
Case 2. Suppose that
, then
. By (b),
. Hence, by (c) and biconditional elimination,
. Thus, in either case a contradiction is reached.
Definition 3.4.1. If
is a theory, let
be the set of Godel numbers of theorems of
and let
be a Gödel number of given an expression u of
. The property
is said to be is a strongly expressible in
by wff
if the following properties are satisfied:
a) if
then
,
b) if
then
.
Theorem 3.4.2. (Generalized Tarski’s undefinability Lemma). Let
be a consistent theory with equality in the language
in which the diagonal function D is representable and let
be a Gödel number of given an expression u of
. Then the property
is not strongly expressible in
.
Proof. By the diagonalization lemma applied to
there is a sentence
such that: c)
, where q is the Godel number of
, i.e.
.
Case 1. Suppose that
, then
. By (a),
. But, from
and (c), by biconditional elimination, one obtains
. Hence
is inconsistent, contradicting our hypothesis.
Case 2. Suppose that
, then
. By (b),
. Hence, by (c) and biconditional elimination,
. Thus, in either case a contradiction is reached.
Remark 3.4.3. Notice that Tarski’s undefinability theorem cannot blocking the biconditionals
(109)
see Subsection 2.2.
3.5. Generalized Tarski’s Undefinability Theorem
Remark 3.5.1. I) Let
be the theory
.
In addition under assumption
, we establish a countable sequence of the consistent extensions of the theory
such that:
i)
, where
ii)
is a finite consistent extension of
,
iii)
,
iv)
proves the all sentences of
, which is valid in M, i.e.,
, see see Subsection 4.1, Proposition 4.1.1.
II) Let
be
.
In addition under assumption
, we establish a countable sequence of the consistent extensions of the theory
such that:
i)
, where
ii)
is a finite consistent extension of
,
iii)
,
iv)
proves the all sentences of
, which valid in
, i.e.,
, see Subsection 4.1, Proposition 4.1.1.
III) Let
be
.
In addition under assumption
, we establish a countable sequence of the consistent extensions of the theory
such that:
i)
, where
ii)
is a finite consistent extension of
,
iii)
iv)
proves the all sentences of
, which valid in
, i.e.,
, see Subsection 4.1, Proposition 4.1.1.
Remark 3.5.2. I) Let
be the set of the all sets of M provably definable in
,
(110)
and let
where
means sentence A derivable in
. Then we have that
iff
, which immediately gives us
iff
. We choose now
in the following form
(111)
Here
is a canonical Gödel formulae which says to us that there exists proof in
of the formula A with Gödel number
.
II) Let
be the set of the all sets of
provably definable in
,
(112)
and let
where
means sentence A derivable in
.
Then we have that
iff
, which immediately gives us
iff
. We choose now
in the following form
(113)
Here
is a canonical Gödel formulae which says to us that there exists proof in
of the formula A with Gödel number
.
III) Let
be the set of the all sets of
provably definable in
,
(114)
and let
where
means sentence A derivable in
. Then we have that
iff
, which immediately gives us
iff
.
We choose now
in the following form
(115)
Here
is a canonical Gödel formulae which says to us that there exists proof in
of the formula A with Gödel number
.
Remark 3.5.3. Notice that definitions (111), (113) and (115) hold as definitions of predicates really asserting provability in
and
correspondingly.
Remark 3.5.4. Of course the all theories
are inconsistent, see subsection 4.1.
Remark 3.5.5. I) Let
be the set of the all sets of M provably definable in
,
(116)
and let
, where
means “sentence A derivable in
”. Then, we have that
iff
, which immediately gives us
iff
. We choose now
in the following form
(117)
II) Let
be the set of the all sets of
provably definable in
,
(118)
and let
be the set
, where
means “sentence A derivable in
”. Then, we have that
iff
, which immediately gives us
iff
. We choose now
in the following form
(119)
III) Let
be the set of the all sets of
provably definable in
,
(120)
and let
be the set
where
means “sentence A derivable in
”. Then, we have that
iff
, which immediately gives us
iff
. We choose now
in the following form
(121)
Remark 3.5.6. Notice that definitions (117), (119) and (121) hold as definitions of a predicate really asserting provability in
and
correspondingly.
Remark 3.5.7. Of course all the theories
and
are inconsistent, see subsection 4.1.
Remark 3.5.8. Notice that under naive consideration the set
and
can be defined directly using a truth predicate, which of course is not available in the language of
(but iff
is consistent) by well-known Tarski’s undefinability theorem [10] .
Theorem 3.5.1. Tarski’s undefinability theorem: I) Let
be first order theory with formal language
, which includes negation and has a Gödel numbering
such that for every
-formula
there is a formula B such that
holds. Assume that
has a standard model
and
where
(122)
Let
be the set of Gödel numbers of
-sentences true in
. Then there is no
-formula
(truth predicate) which defines
. That is, there is no
-formula
such that for every
-formula A,
(123)
holds.
II) Let
be second order theory with Henkin semantics and formal language
, which includes negation and has a Gödel numbering
such that for every
-formula
there is a formula B such that
holds.
Assume that
has a standard model
and
, where
(124)
Let
be the set of Gödel numbers of the all
-sentences true in M. Then there is no
-formula
(truth predicate) which defines
. That is, there is no
-formula
such that for every
-formula A,
(125)
holds.
Remark 3.5.9. Notice that the proof of Tarski’s undefinability theorem in this form is again by simple reductio ad absurdum. Suppose that an
-formula True(n) defines
. In particular, if A is a sentence of
then
holds in
iff A is true in
. Hence for all A, the Tarski T-sentence
is true in
. But the diagonal lemma yields a counterexample to this equivalence, by giving a “Liar” sentence S such that
holds in
. Thus no
-formula
can define
.
Remark 3.5.10. Notice that the formal machinery of this proof is wholly elementary except for the diagonalization that the diagonal lemma requires. The proof of the diagonal lemma is likewise surprisingly simple; for example, it does not invoke recursive functions in any way. The proof does assume that every
-formula has a Gödel number, but the specifics of a coding method are not required.
Remark 3.5.11. The undefinability theorem does not prevent truth in one consistent theory from being defined in a stronger theory. For example, the set of (codes for) formulas of first-order Peano arithmetic that are true in
is definable by a formula in second order arithmetic. Similarly, the set of true formulas of the standard model of second order arithmetic (or n-th order arithmetic for any n) can be defined by a formula in first-order ZFC.
Remark1.3.5.12. Notice that Tarski’s undefinability theorem cannot blocking the biconditionals
(126)
see Remark 3.5.14 below.
Remark 3.5.13. I) We define again the set
but now by using generalized truth predicate
such that
(127)
holds.
II) We define the set
using generalized truth predicate
such that
(128)
holds. Thus in contrast with naive definition of the sets
and
there is no any problem which arises from Tarski’s undefinability theorem.
III) We define a set
using generalized truth predicate
such that
(129)
holds. Thus in contrast with naive definition of the sets
and
there is no any problem which arises from Tarski’s undefinability theorem.
Remark 3.5.14. In order to prove that set theory
is inconsistent without any reference to the set
, notice that by the properties of the extension
it follows that definition given by formula (127) is correct, i.e., for every
-formula
such that
the following equivalence
holds.
Theorem 3.5.2. (Generalized Tarski’s undefinability theorem) (see subsection 4.2, Proposition 4.2.1). Let
be a first order theory or the second order theory with Henkin semantics and with formal language
, which includes negation and has a Gödel encoding
such that for every
-formula
there is a formula B such that the equivalence
holds. Assume that
has a standard Model
. Then there is no
-formula
, such that for every
-formula A such that
, the following equivalence holds
(130)
Theorem 3.5.3. i) Set theory
is inconsistent;
ii) Set theory
is inconsistent; iii) Set theory
is inconsistent; (see subsection 4.2, Proposition 4.2.2).
Proof. i) Notice that by the properties of the extension
of the theory
it follows that
(131)
Therefore formula (127) gives generalized “truth predicate” for the set theory
. By Theorem 3.5.2 one obtains a contradiction.
ii) Notice that by the properties of the extension
of the theory
it follows that
(132)
Therefore formula (128) gives generalized “truth predicate” for the set theory
. By Theorem 3.5.2 one obtains a contradiction.
iii) Notice that by the properties of the extension
of the theory
it follows that
(133)
Therefore (129) gives generalized “truth predicate” for the set theory
. By Theorem 3.5.2 one obtains a contradiction.
3.6. Avoiding the Contradictions from Set Theory
,
and Set Theory
Using Quinean Approach
In order to avoid difficulties mentioned above we use well known Quinean approach [19] .
3.6.1. Quinean Set Theory NF
Remind that the primitive predicates of Russellian unramified typed set theory (TST), a streamlined version of the theory of types, are equality = and membership
. TST has a linear hierarchy of types: type 0 consists of individuals otherwise undescribed. For each (meta-) natural number n, type
objects are sets of type n objects; sets of type n have members of type
. Objects connected by identity must have the same type. The following two atomic formulas succinctly describe the typing rules:
and
.
The axioms of TST are:
Extensionality: sets of the same (positive) type with the same members are equal;
Axiom schema of comprehension:
If
is a formula, then the set
exists i.e., given any formula
, the formula
(134)
is an axiom where
represents the set
and is not free in
.
Quinean set theory. (New Foundations) seeks to eliminate the need for such superscripts.
New Foundations has a universal set, so it is a non-well founded set theory. That is to say, it is a logical theory that allows infinite descending chains of membership such as
. It avoids Russell’s paradox by only allowing stratifiable formulas in the axiom of comprehension. For instance
is a stratifiable formula, but
is not (for details of how this works see below).
Definition 3.6.1. In New Foundations (NF) and related set theories, a formula
in the language of first-order logic with equality and membership is said to be stratified iff there is a function 3c3 which sends each variable appearing in
[considered as an item of syntax] to a natural number (this works equally well if all integers are used) in such a way that any atomic formula
appearing in
satisfies
and any atomic formula
appearing in
satisfies
.
Quinean Set Theory NF
Axioms and stratification are:
The well-formed formulas of New Foundations (NF) are the same as the well-formed formulas of TST, but with the type annotations erased. The axioms of NF are [19] .
Extensionality: Two objects with the same elements are the same object.
A comprehension schema: All instances of TST Comprehension but with type indices dropped (and without introducing new identifications between variables).
By convention, NF’s Comprehension schema is stated using the concept of stratified formula and making no direct reference to types. Comprehension then becomes.
Stratified Axiom schema of comprehension:
exists for each stratified formula
.
Even the indirect reference to types implicit in the notion of stratification can be eliminated. Theodore Hailperin showed in 1944 that Comprehension is equivalent to a finite conjunction of its instances, so that NF can be finitely axiomatized without any reference to the notion of type [20] . Comprehension may seem to run afoul of problems similar to those in naive set theory, but this is not the case. For example, the existence of the impossible Russell class
is not an axiom of NF, because
cannot be stratified.
3.6.2. SET Theory
,
and Set Theory
with Stratified Axiom Schema of Replacement
The stratified axiom schema of replacement asserts that the image of a set under any function definable by stratified formula of the theory
will also fall inside a set.
Stratified Axiom schema of replacement:
Let
be any stratified formula in the language of
whose free variables are among
, so that in particular B is not free in
. Then
(135)
i.e., if the relation
represents a definable function f, A represents its domain, and
is a set for every
, then the range of f is a subset of some set B.
Stratified Axiom schema of separation:
Let
be any stratified formula in the language of
whose free variables are among
, so that in particular B is not free in
. Then
(136)
Remark 3.6.1. Notice that the stratified axiom schema of separation follows from the stratified axiom schema of replacement together with the axiom of empty set.
Remark 3.6.2. Notice that the stratified axiom schema of replacement (separation) obviously violated any contradictions (82), (126), etc. mentioned above. The existence of the countable Russell sets
and
is impossible, because
cannot be stratified.
4. Generalized Löbs Theorem
4.1. Generalized Löbs Theorem. Second-Order Theories with Henkin Semantics
Remark 4.1.1. In this section we use second-order arithmetic
with Henkin semantics. Notice that any standard model
of second-order arithmetic
consisting of a set
of unusual natural numbers (which forms the range of individual variables) together with a constant 0 (an element of
), a function S from
to
, two binary operations + and
on
, a binary relation < on
, and a collection
of subsets of
, which is the range of the set variables. Omitting D produces a model of the first order Peano arithmetic.
When
is the full power set of
, the model
is called a full model. The use of full second-order semantics is equivalent to limiting the models of second-order arithmetic to the full models. In fact, the axioms of second-order arithmetic
have only one full model. This follows from the fact that the axioms of Peano arithmetic with the second-order induction axiom have only one model under second-order semantics, see Section 3.
Let
be some fixed, but unspecified, consistent formal theory. For later convenience, we assume that the encoding is done in some fixed formal second order theory
and that
contains
. We assume throughout this paper that formal second order theory
has an ω-model
. The sense in which
is contained in
is better exemplified than explained: if
is a formal system of a second order arithmetic
and
is, say,
, then
contains
in the sense that there is a well-known embedding, or interpretation, of S in
. Since encoding is to take place in
, it will have to have a large supply of constants and closed terms to be used as codes (e.g. in formal arithmetic, one has
).
will also have certain function symbols to be described shortly. To each formula,
, of the language of
is assigned a closed term,
, called the code of
[19] . We note that if
is a formula with free variable x, then
is a closed term encoding the formula
with x viewed as a syntactic object and not as a parameter. Corresponding to the logical connectives and quantifiers are the function symbols,
,
, etc., such that for all first order formulae
,
etc. Of particular importance is the substitution operator, represented by the function symbol
. For formulae
, terms t with codes
:
(137)
It well known that one can also encode derivations and have a binary relation
(read “x proves y” or “x is a proof of y”) such that for closed
iff
is the code of a derivation in
of the formula with code
. It follows that
(138)
for some closed term t. Thus we can define
(139)
and therefore we obtain a predicate asserting provability.
Remark 4.1.2. I) We note that it is not always the case that:
(140)
unless
is fairly sound, e.g. this is the case when
and
replaced by
and
correspondingly (see Designation 4.1.1 below).
II) Notice that it is always the case that:
(141)
i.e. that is the case when predicate
:
(142)
really asserting provability.
It well known that the above encoding can be carried out in such a way that the following important conditions
and
are meeting for all sentences:
(143)
Conditions
and
are called the Derivability Conditions.
Remark 4.1.3. From (141)-(142) it follows that
(144)
Conditions
and
are called a Strong Derivability Conditions.
Definition 4.1.1. Let
be well formed formula (wff) of
. Then wff
is called
-sentence iff it has no free variables.
Designation 4.1.1 i) Assume that a theory
has an ω-model
and
is a
-sentence, then:
(we will write
instead
)
is a
-sentence
with all quantifiers relativized to ω-model
[11] and
is a theory
relativized to model
, i.e., any
-sentence has the form
for some
-sentence
.
ii) Assume that a theory
has a standard model
and
is a
-sentence, then:
(we will write
instead
) is a
-sentence with
all quantifiers relativized to a standard model
, and
is a theory
relativized to model
, i.e., any
-sentence has a form
for some
-sentence
.
iii) Assume that a theory
has a non-standard model
and
is a
-sentence, then:
(we will write
instead
) is a
-sentence with
all quantifiers relativized to non-standard model
, and
is a theory
relativized to model
, i.e., any
-sentence has a form
for some
-sentence
.
iv) Assume that a theory
has a model
and
is a
-sentence, then:
is a
-sentence with all quantifiers relativized to model
, and
is a theory
relativized to model
, i.e. any
-sentence has a form
for some
-sentence
.
Designation 4.1.2. i) Assume that a theory
with a language
has an ω-model
and there exists
-sentence
such that: a)
expressible by language
and
b)
asserts that
has a model
; we denote such
-sentence
by
.
ii) Assume that a theory
with a language
has a non-standard model
and there exists
-sentence
such that: a)
expressible by language
and
b)
asserts that
has a non-standard model
; we denote such
-sentence
by
.
iii) Assume that a theory
with a language
has an model
and there exists
-sentence
such that: a)
expressible by language
and
b)
asserts that
has a model
; we denote such
-sentence
by
.
Remark 4.1.4. We emphasize that: i) it is well known that there exists a ZFC-sentence
[8] ,
ii) obviously there exists a
-sentence
and there exists a
-sentence
.
Designation 4.1.3. Assume that
. Let
be the formula:
(145)
and where
is a closed term.
Lemma 4.1.1. I) Assume that: i) a theory
is recursively axiomatizable.
ii)
,
iii)
and
iv)
, where
is a closed formula.
Then
.
II) Assume that: i) a theory
is recursively axiomatizable.
ii)
iii)
and
iv)
, where
is a closed formula.
Then
.
Proof. I) Let
be the formula:
(146)
where
is a closed term. From (i)-(ii) it follows that theory
is consistent. We note that
for any closed
. Suppose that
, then (iii) gives
(147)
From (139) and (147) we obtain
(148)
But the formula (146) contradicts the formula (148). Therefore
.
Remark 4.1.5. In additional note that under the following conditions:
i) a theory
is recursively axiomatizable,
ii)
, and
iii)
predicate
really asserts provability, one obtains
(149)
and therefore by reductio ad absurdum again one obtains
.
II) Let
be the formula:
(150)
This case is trivial because formula
by the Strong Derivability Condition
, see formulae (144), really asserts provability of the
-sentence
. But this is a contradiction.
Lemma 4.1.2. I) Assume that: i) a theory
is recursively axiomatizable.
ii)
,
iii)
and
iv)
, where
is a closed formula. Then
,
II) Assume that: i) a theory
is recursively axiomatizable.
ii)
iii)
and
iv)
,
where
is a closed formula. Then
.
Proof. Similarly as Lemma 4.1.1 above.
Example 4.1.1. i) Let
be Peano arithmetic and
.
Assume that: i)
ii)
where
is a model of
.
Then obviously
since
and therefore by Lemma 4.1.1
.
ii) Let
and let
be a theory
and
. Then obviously
(151)
and therefore
(152)
and
(153)
However by Löbs theorem
(154)
iii) Let
and
. Then obviously
since
and therefore by Lemma 4.1.1 we obtain.