Back
 APM  Vol.9 No.9 , September 2019
There Is No Standard Model of ZFC and ZFC2 with Henkin Semantics
Abstract: In this article we proved so-called strong reflection principles corresponding to formal theories Th which has omega-models or nonstandard model with standard part. A possible generalization of Löb’s theorem is considered. Main results are: 1) , 2) , 3) , 4) , 5) let k be inaccessible cardinal then .

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 X is defined as the union of X and the set Y of all sets y for which there is a formula A ( z , t 1 , , t k ) in ZF such that if A X denotes A with all bound variables restricted to X, then for some t ¯ i , i = 1 , , k , in X,

y = { z X | A X ( z , t ¯ 1 , , t ¯ k ) } . (1)

Observe X P ( x ) X , X ¯ ¯ = X ¯ ¯ if X is infinite (and we assume AC). It should be clear to the reader that the definition of X , as we have given it, can be done entirely within ZF and that Y = X is a single formula A ( X , Y ) 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 X is expressible in ZF.”

Remark 1.1.3. We will say that a set y is definable by the formula A ( z , t 1 , , t k ) 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 A ( z , t 1 , , t k ) in ZFC then for some t ¯ i X , i = 1 , , k , in X there exists a set z such that the condition A ( z , t ¯ 1 , , t ¯ k ) is satisfied and y = z or symbolically

z [ A ( z , t ¯ 1 , , t ¯ k ) y = z ] . (2)

It should be clear to the reader that the definition of X , as we have given it, can be done entirely within second order set theory ZFC2 with the Henkin semantics [7] denoted by Z F C 2 H s and that Y = X is a single formula A ( X , Y ) in Z F C 2 H s .

ii) We will denote the set Y of all sets y definable relative to a given set X by Y 2 H s .

Definition 1.1.3. Let 2 H s 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

x ( x 2 H s ) [ x 2 H s x x ] . (3)

Remark 1.1.5. (a) Note that 2 H s 2 H s since 2 H s is a set definable by the first order 1-place open wff Ψ ( Z , 2 H s ) :

Ψ ( Z , 2 H s ) x ( x 2 H s ) [ x Z x x ] , (4)

Theorem 1.1.1. [6] . Set theory Z F C 2 H s is inconsistent.

Proof. From (3) and Remark 1.1.2 one obtains

2 H s 2 H s 2 H s 2 H s . (5)

From (5) one obtains a contradiction

( 2 H s 2 H s ) ( 2 H s 2 H s ) . (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 A ( z ) in ZFC such that

z [ A ( z ) y = z ] . (7)

Obviously in this case a set Y = 2 H s is a countable set.

Definition 1.1.4. Let 2 H s be the countable set of the all sets definable by the first order 1-place open wff’s and such that

x ( x 2 H s ) [ x 2 H s x x ] . (8)

Remark 1.1.7. (a) Note that 2 H s 2 H s since 2 H s is a set definable by the first order 1-place open wff Ψ ( Z , 2 H s ) :

Ψ ( Z , 2 H s ) x ( x 2 H s ) [ x Z x x ] , (9)

one obtains a contradiction ( 2 H s 2 H s ) ( 2 H s 2 H s ) .

In this paper we dealing by using following definability condition.

Definition 1.1.5. i) Let M s t = M s t Z F C be a standard model of ZFC. We will say that a set y is definable relative to a given standard model M s t of ZFC if there is a formula A ( z , t 1 , , t k ) in ZFC such that if A M s t denotes A with all bound variables restricted to M s t , then for some t ¯ i M s t , i = 1 , , k , in M s t there exists a set z such that the condition A M s t ( z , t ¯ 1 , , t ¯ k ) is satisfied and y = z or symbolically

z [ A M s t ( z , t ¯ 1 , , t ¯ k ) y = z ] . (10)

It should be clear to the reader that the definition of M s t , 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

A M s t ( z , t ¯ 1 , , t ¯ k ) = A M s t ( z ) . (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 D E D 2 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 U is an ordinary first-order structure and S is a set of subsets of the domain A of U . The main idea is that the set-variables range over S , i.e.

U , S X Φ ( X ) S ( S S ) [ U , S Φ ( S ) ] .

We call U , S a Henkin model, if U , S satisfies the axioms of D E D 2 and truth in U , S is preserved by the rules of D E D 2 . 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 U , S where S 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 D E D 2 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 D E D 2 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 2 such that the semiring of natural numbers is the only full model of 2 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.

X [ F u n c ( X ) u ν r [ r ν s ( s u ( s , r ) X ) ] ] , (12)

where X is a second-order variable, and where F u n c ( X ) 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 Z F C 2 H s set theory Z F C 2 with the Henkin semantics,

ii) by Z F C 2 f s s set theory Z F C 2 with the full second-order semantics,

iii) by Z F C ¯ 2 H s set theory Z F C 2 H s + M s t Z F C 2 H s and

iv) by Z F C s t set theory Z F C + M s t Z F C , where M s t T h is a standard model of the theory T h .

Remark 1.1.12. There is no completeness theorem for second-order logic with the full second-order semantics. Nor do the axioms of Z F C 2 f s s 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 M Z F C 2 f s s of Z F C 2 f s s [11] .

Let Z be the conjunction of all the axioms of Z F C 2 f s s . We assume now that: Z is true, i.e. C o n ( Z F C 2 f s s ) . 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 ( H κ , ) is a model of Z F C 2 f s s . Thus

¬ C o n ( Z F C 2 f s s ) ¬ C o n ( Z F C + κ ) . (13)

In this paper we prove that:

i) Z F C s t Z F C + M s t Z F C ii) Z F C ¯ 2 H s Z F C 2 H s + M s t Z F C 2 H s and iii) Z F C 2 f s s is inconsistent, where M s t T h is a standard model of the theory T h .

Axiom M Z F C [8] . There is a set M Z F C and a binary relation ε M Z F C × M Z F C which makes M Z F C a model for ZFC.

Remark 1.1.13. i) We emphasize that it is well known that axiom M Z F C a single statement in ZFC see [8] , Ch. II, Section 7. We denote this statement thought all this paper by symbol C o n ( Z F C ; M Z F C ) . The completeness theorem says that M Z F C C o n ( Z F C ) .

ii) Obviously there exists a single statement in Z F C 2 H s such that M Z F C 2 H s C o n ( Z F C 2 H s ) .

We denote this statement through all this paper by symbol C o n ( Z F C 2 H s ; M Z F C 2 H s ) and there exists a single statement M Z 2 H s in Z 2 H s . We denote this statement through all this paper by symbol C o n ( Z 2 H s ; M Z 2 H s ) .

Axiom M s t Z F C [8] . There is a set M s t Z F C such that if R is { x , y | x y x M s t Z F C y M s t Z F C } then M s t Z F C is a model for ZFC under the relation R.

Definition 1.1.6. [8] . The model M s t Z F C is called a standard model since the relation used is merely the standard -relation.

Remark 1.1.14. Note that axiom M Z F C doesn’t imply axiom M s t Z F C , 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 V ( V is von Neumann universe), as a basis for set theory: “As with second-order logic, we cannot really choose whether we axiomatize mathematics using V or ZFC. The result is the same in both cases, as ZFC is the best attempt so far to use V as an axiomatization of mathematics”.

Remark 1.1.16. Note that in order to deduce: i) ~ C o n ( Z F C 2 H s ) from C o n ( Z F C 2 H s ) ,

ii) ~ C o n ( Z F C ) from C o n ( Z F C ) , by using Gödel encoding, one needs something more than the consistency of Z F C 2 H s , e.g., that Z F C 2 H s has an omega-model M ω Z F C 2 H s or an standard model M s t Z F C 2 H s i.e., a model in which the integers are the standard integers and the all wff of Z F C 2 H s , ZFC, etc. represented by standard objects. To put it another way, why should we believe a statement just because there’s a Z F C 2 H s -proof of it? It’s clear that if Z F C 2 H s is inconsistent, then we won’t believe Z F C 2 H s -proofs. What’s slightly more subtle is that the mere consistency of Z F C 2 isn’t quite enough to get us to believe arithmetical theorems of Z F C 2 H s ; we must also believe that these arithmetical theorems are asserting something about the standard naturals. It is “conceivable” that Z F C 2 H s might be consistent but that the only nonstandard models M N s t Z F C 2 H s it has are those in which the integers are nonstandard, in which case we might not “believe” an arithmetical statement such as “ Z F C 2 H s is inconsistent” even if there is a Z F C 2 H s -proof of it.

Remark 1.1.17. Note that assumption M s t Z F C 2 H s is not necessary if nonstandard model M N s t Z F C 2 H s is a transitive or has a standard part M s t Z 2 H s M N s t Z 2 H s , see [14] [15] .

Remark 1.1.18. Remind that if M is a transitive model, then ω M 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 M N s t Z 2 H s of the second-order arithmetic Z 2 H s the terms 0 ¯ , S 0 ¯ = 1 ¯ , S S 0 ¯ = 2 ¯ , comprise the initial segment isomorphic to M s t Z 2 H s M N s t Z 2 H s . This initial segment is called the standard cut of the M N s t Z 2 H s . The order type of any nonstandard model of M N s t Z 2 H s is equal to + A × , see ref. [16] , for some linear order A.

Thus one can choose Gödel encoding inside the standard model M s t Z 2 H s .

Remark 1.1.19. However there is no any problem as mentioned above in second order set theory Z F C 2 with the full second-order semantics because corresponding second order arithmetic Z 2 f s s is categorical.

Remark 1.1.20. Note if we view second-order arithmetic Z 2 as a theory in first-order predicate calculus. Thus a model M Z 2 of the language of second-order arithmetic Z 2 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 M Z 2 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. Z 2 , 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, M Z 2 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 M ω Z 2 f s s , 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

C o n ( Z F C + M s t Z F C ) (14)

it has been proved that there exists countable Russell’s set ω such that the following statement is satisfied:

Z F C + M s t Z F C ω ( ω M s t Z F C ) ( c a r d ( ω ) = 0 ) [ M s t Z F C x ( x ω x x ) ] . (15)

From (15) it immediately follows a contradiction

M s t Z F C ( ω ω ) ( ω ω ) . (16)

From (16) and (14) by reductio and absurdum it follows

¬ C o n ( Z F C + M s t Z F C ) (17)

Theorem 2.1.1. [17] [18] [19] . (Tarski’s undefinability theorem). Let T h L be first order theory with formal language L , which includes negation and has a Gödel numbering g ( ) such that for every L -formula A ( x ) there is a formula B such that B A ( g ( B ) ) holds. Assume that T h L has a standard model M s t T h L and C o n ( T h L , s t ) where

T h L , s t T h L + M s t T h L . (18)

Let T be the set of Gödel numbers of L -sentences true in M s t T h L . Then there is no L -formula T r u e ( n ) (truth predicate) which defines T . That is, there is no L -formula T r u e ( n ) such that for every L -formula A,

T r u e ( g ( A ) ) [ A ] M s t T h L , (19)

where the abbreviation [ A ] M s t T h L means that A holds in standard model M s t T h L , i.e. [ A ] M s t T h L M s t T h L A . Therefore C o n ( T h L , s t ) implies that

¬ T r u e ( x ) ( T r u e ( g ( A ) ) [ A ] M s t T h L ) (20)

Thus Tarski’s undefinability theorem reads

C o n ( T h L , s t ) ¬ T r u e ( x ) ( T r u e ( g ( A ) ) [ A ] M s t T h L ) . (21)

Remark 2.1.2. i) By the other hand the Theorem 2.1.1 says that given some really consistent formal theory T h L , s t that contains formal arithmetic, the concept of truth in that formal theory T h L , s t 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 T r u e ( n ) , but only by drawing on a metalanguage whose expressive power goes beyond that of L . To define a truth predicate for the metalanguage would require a still higher metametalanguage, and so on.

ii) However if formal theory T h L , s t is inconsistent this is not surprising if we define a formula T r u e ( n ) = T r u e ( n ; T h L , s t ) by drawing only on a language L .

iii) Note that if under assumption C o n ( T h L , s t ) we define a formula T r u e ( n ; T h L , s t ) by drawing only on a language L by reductio ad absurdum it follows

¬ C o n ( T h L , s t ) . (22)

Remark 2.1.3. i) Let Z F C s t be a theory Z F C s t Z F C + M s t Z F C . In this paper under assumption C o n ( Z F C s t ) we define a formula T r u e ( n ; Z F C s t ) by drawing only on a language L Z F C s t by using Generalized Löb’s theorem [4] [5] . Thus by reductio ad absurdum it follows

¬ C o n ( Z F C + M s t Z F C ) . (23)

ii) However note that in this case we obtain ¬ C o n ( Z F C s t ) 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 T h L # be first order theory and C o n ( T h # ) . A theory T h L # is complete if, for every formula A in the theory’s language L , that formula A or its negation ¬ A is provable in T h L # , i.e., for any wff A, always T h L # A or T h L # ¬ A .

Definition 2.2.2. Let T h L be first order theory and C o n ( T h L ) . We will say that a theory T h L # is completion of the theory T h L if i) T h L T h L # , ii) a theory T h L # is complete.

Theorem 2.2.1. [4] [5] . Assume that: C o n ( Z F C s t ) , where Z F C s t Z F C + M s t Z F C . Then there exists completion Z F C s t # of the theory Z F C s t such that the following conditions hold:

i) For every formula A in the language of ZFC that formula [ A ] M s t Z F C or formula [ ¬ A ] M s t Z F C is provable in Z F C s t # i.e., for any wff A, always Z F C s t # [ A ] M s t Z F C or Z F C s t # [ ¬ A ] M s t Z F C .

ii) Z F C s t # = m T h m , where for any m a theory T h m + 1 is finite extension of the theory T h m .

iii) Let Pr m s t ( y , x ) be recursive relation such that: y is a Gödel number of a proof of the wff of the theory T h m and x is a Gödel number of this wff. Then the relation Pr m s t ( y , x ) is expressible in the theory T h m by canonical Gödel encoding and really asserts provability in T h m .

iv) Let Pr s t # ( y , x ) be relation such that: y is a Gödel number of a proof of the wff of the theory Z F C s t # and x is a Gödel number of this wff. Then the relation Pr s t # ( y , x ) is expressible in the theory Z F C s t # by the following formula

Pr s t # ( y , x ) m ( m ) Pr m s t ( y , x ) (24)

v) The predicate Pr s t # ( y , x ) really asserts provability in the set theory Z F C s t # .

Remark 2.2.1. Note that the relation Pr m s t ( y , x ) is expressible in the theory T h m since a theory T h m is a finite extension of the recursively axiomatizable theory ZFC and therefore the predicate Pr m s t ( y , x ) exists since any theory T h m is recursively axiomatizable.

Remark 2.2.2. Note that a theory Z F C s t # obviously is not recursively axiomatizable nevertheless Gödel encoding holds by Remark 2.2.1.

Theorem 2.2.2. Assume that: C o n ( Z F C s t ) , where Z F C s t Z F C + M s t Z F C . Then truth predicate T r u e ( n ) is expressible by using only first order language by the following formula

T r u e ( g ( A ) ) y ( y ) m ( m ) Pr m s t ( y , g ( A ) ) . (25)

Proof. Assume that:

Z F C s t # [ A ] M s t Z F C . (26)

It follows from (26) there exists m = m ( g ( A ) ) such that T h m [ A ] M s t Z F C and therefore by (24) we obtain

Pr s t # ( y , g ( A ) ) Pr m s t ( y , g ( A ) ) . (27)

From (24) immediately by definitions one obtains (25).

Remark 2.2.3. Note that Theorem 2.1.1 in this case reads

C o n ( Z F C s t ) ¬ T r u e ( x ) ( T r u e ( g ( A ) ) [ A ] M s t Z F C ) . (28)

Theorem 2.2.3. ¬ C o n ( Z F C s t ) .

Proof. Assume that: C o n ( Z F C s t ) . From (25) and (28) one obtains a contradiction C o n ( Z F C s t ) ¬ C o n ( Z F C s t ) (see Remark 2.1.3) and therefore by reductio ad absurdum it follows ¬ C o n ( Z F C s t ) .

Theorem 2.2.4. [4] [5] . Let M N s t Z F C be a nonstandard model of ZFC and let M s t P A be a standard model of PA.

We assume now that M s t P A M N s t Z F C and denote such nonstandard model of the set theory ZFC by M N s t Z F C = M N s t Z F C [ P A ] . Let Z F C N s t be the theory Z F C N s t = Z F C + M N s t Z F C [ P A ] . Assume that: C o n ( Z F C N s t ) , where Z F C s t Z F C + M N s t Z F C . Then there exists completion Z F C N s t # of the theory Z F C N s t such that the following conditions hold:

i) For every formula A in the language of ZFC that formula [ A ] M N s t Z F C or formula [ ¬ A ] M N s t Z F C is provable in Z F C N s t # i.e., for any wff A, always Z F C N s t # [ A ] M N s t Z F C or Z F C N s t # [ ¬ A ] M N s t Z F C .

ii) Z F C N s t # = m T h m , where for any m a theory T h m + 1 is finite extension of the theory T h m .

iii) Let Pr m N s t ( y , x ) be recursive relation such that: y is a Gödel number of a proof of the wff of the theory T h m and x is a Gödel number of this wff. Then the relation Pr m N s t ( y , x ) is expressible in the theory T h m by canonical Gödel encoding and really asserts provability in T h m .

iv) Let Pr N s t # ( y , x ) be relation such that: y is a Gödel number of a proof of the wff of the theory Z F C N s t # and x is a Gödel number of this wff. Then the relation Pr N s t # ( y , x ) is expressible in the theory Z F C N s t # by the following formula

Pr N s t # ( y , x ) m ( m M s t P A ) Pr m N s t ( y , x ) (29)

v) The predicate Pr N s t # ( y , x ) really asserts provability in the set theory Z F C N s t # .

Remark 2.2.4. Note that the relation Pr m N s t ( y , x ) is expressible in the theory T h m since a theory T h m is a finite extension of the recursively axiomatizable theory ZFC and therefore the predicate Pr m N s t ( y , x ) exists since any theory T h m is recursively axiomatizable.

Remark 2.2.5. Note that a theory Z F C N s t # obviously is not recursively axiomatizable nevertheless Gödel encoding holds by Remark 2.2.1.

Theorem 2.2.5. Assume that: C o n ( Z F C N s t ) , where Z F C N s t Z F C + M N s t Z F C , M s t P A M N s t Z F C .

Then truth predicate T r u e ( n ) is expressible by using first order language by the following formula

T r u e ( g ( A ) ) y ( y M s t P A ) m ( m M s t P A ) Pr m N s t ( y , g ( A ) ) . (30)

Proof. Assume that:

Z F C N s t # [ A ] M N s t Z F C . (31)

It follows from (29) there exists m = m ( g ( A ) ) such that T h m [ A ] M N s t Z F C and therefore by (31) we obtain

Pr N s t # ( y , g ( A ) ) Pr m N s t ( y , g ( A ) ) . (32)

From (32) immediately by definitions one obtains (30).

Remark 2.2.6. Note that Theorem 2.1.1 in this case reads

C o n ( Z F C N s t ) ¬ T r u e ( x ) ( T r u e ( g ( A ) ) [ A ] M N s t Z F C ) . (33)

Theorem 2.2.6. ¬ C o n ( Z F C N s t ) .

Proof. Assume that: C o n ( Z F C N s t ) . From (30) and (33) one obtains a contradiction C o n ( Z F C N s t ) ¬ C o n ( Z F C N s t ) and therefore by reductio ad absurdum it follows ¬ C o n ( Z F C N s t ) .

Theorem 2.2.7. Assume that: C o n ( Z F C ¯ 2 H s ) , where Z F C ¯ 2 H s Z F C 2 H s + M s t Z F C 2 H s . Then there exists completion Z F C ¯ 2 H s # of the theory Z F C ¯ 2 H s such that the following conditions hold:

i) For every first order wff formula A (wff1 A) in the language of Z F C 2 H s that formula [ A ] M s t Z F C 2 H s or formula [ ¬ A ] M s t Z F C 2 H s is provable in Z F C ¯ 2 H s # i.e., for any wff1 A, always Z F C ¯ 2 H s # [ A ] M s t Z F C 2 H s or Z F C ¯ 2 H s # [ ¬ A ] M s t Z F C 2 H s .

ii) Z F C ¯ 2 H s # = m T h m , where for any m a theory T h m + 1 is finite extension of the theory T h m .

iii) Let Pr m s t ( y , x ) be recursive relation such that: y is a Gödel number of a proof of the wff1 of the theory T h m and x is a Gödel number of this wff1. Then the relation Pr m s t ( y , x ) is expressible in the theory T h m by canonical Gödel encoding and really asserts provability in T h m .

iv) Let Pr s t # ( y , x ) be relation such that: y is a Gödel number of a proof of the wff of the set theory Z F C ¯ 2 H s # and x is a Gödel number of this wff1. Then the relation Pr s t # ( y , x ) is expressible in the set theory Z F C ¯ 2 H s # by the following formula

Pr s t # ( y , x ) m ( m ) Pr m s t ( y , x ) (34)

v) The predicate Pr s t # ( y , x ) really asserts provability in the set theory Z F C ¯ 2 H s # .

Remark 2.2.7. Note that the relation Pr m s t ( y , x ) is expressible in the theory T h m since a theory T h m is a finite extension of the finite axiomatizable theory Z F C 2 H s and therefore the predicate Pr m N s t ( y , x ) exists since any theory T h m is recursively axiomatizable.

Remark 2.2.8. Note that a theory Z F C N s t # obviously is not recursively axiomatizable nevertheless Gödel encoding holds by Remark 2.2.1.

Theorem 2.2.8. Assume that: C o n ( Z F C ¯ 2 H s ) , where

Z F C ¯ 2 H s Z F C 2 H s + M s t Z F C 2 H s .

Then truth predicate T r u e ( n ) is expressible by using first order language by the following formula

T r u e ( g ( A ) ) y ( y ) m ( m ) Pr m s t ( y , g ( A ) ) , (35)

where A is wff1.

Proof. Assume that:

Z F C ¯ 2 H s # [ A ] M s t Z F C 2 H s . (36)

It follows from (34) there exists m = m ( g ( A ) ) such that T h m [ A ] M s t Z F C 2 H s and therefore by (36) we obtain

Pr s t # ( y , g ( A ) ) Pr m s t ( y , g ( A ) ) . (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

C o n ( Z F C ¯ 2 H s # ) ¬ T r u e ( x ) ( T r u e ( g ( A ) ) [ A ] M s t Z F C 2 H s ) , (38)

where A is wff1.

Theorem 2.2.9. ¬ C o n ( Z F C ¯ 2 H s # ) .

Proof. Assume that: C o n ( Z F C ¯ 2 H s # ) . From (35) and (38) one obtains a contradiction C o n ( Z F C ¯ 2 H s # ) ¬ C o n ( Z F C ¯ 2 H s # ) and therefore by reductio ad absurdum it follows ¬ C o n ( Z F C ¯ 2 H s # ) .

3. Derivation of the Inconsistent Provably Definable Set in Set Theory Z F C ¯ 2 H s , Z F C s t and Z F C N s t

3.1. Derivation of the Inconsistent Provably Definable Set in Set Theory Z F C ¯ 2 H s

Definition 3.1.1. i) Let Φ be a wff of Z F C ¯ 2 H s . We will say that Φ is a first order n-place open wff if Φ contains free occurrences of the first order individual variables X 1 , , X n and quantifiers only over any first order individual variables Y 1 , , Y m .

ii) Let ˜ 2 H s be the countable set of the all first order provable definable sets X, i.e. sets such that Z F C ¯ 2 H s ! X Ψ ( X ) , where Ψ ( X ) = Ψ M s t ( X ) 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 M s t = M s t Z F C 2 H s , i.e.

Y { Y ˜ 2 H s Z F C ¯ 2 H s Ψ M s t ( X ) [ ( [ Ψ M s t ( X ) ] Γ X , M s t H s / X ) [ ! X [ Ψ M s t ( X ) Y = X ] ] ] } , (39)

or in a short notation

Y { Y ˜ 2 H s Z F C ¯ 2 H s Ψ ( X ) [ ( [ Ψ ( X ) ] Γ X H s / X ) [ ! X [ Ψ ( X ) Y = X ] ] ] } . (40)

Notation 3.1.1. In this subsection we often write for short Ψ ( X ) , F X H s , Γ X H s instead Ψ M s t ( X ) , F X , M s t H s , Γ X , M s t H s but this should not lead to a confusion.

Assumption 3.1.1. We assume now for simplicity but without loss of generality that

F X , M s t H s M s t (41)

and therefore by definition of model M s t = M s t Z F C 2 H s one obtains Γ X , M s t H s M s t Z F C 2 H s .

Let X Z F C ¯ 2 H s Y be a predicate such that X Z F C ¯ 2 H s Y Z F C ¯ 2 H s X Y . Let ˜ 2 H s be the countable set of the all sets such that

X ( X ˜ 2 H s ) [ X ˜ 2 H s X Z F C ¯ 2 H s X ] . (42)

From (42) one obtains

˜ 2 H s ˜ 2 H s ˜ 2 H s Z F C ¯ 2 H s ˜ 2 H s . (43)

But obviously (43) immediately gives a contradiction

( ˜ 2 H s ˜ 2 H s ) ( ˜ 2 H s Z F C ¯ 2 H s ˜ 2 H s ) . (44)

Remark 3.1.1. Note that a contradiction (44) in fact is a contradiction inside Z F C ¯ 2 H s for the reason that predicate X Z F C ¯ 2 H s Y is expressible by first order

language as predicate of Z F C ¯ 2 H s (see subsection 1.2, Theorem 1.2.8 (ii)-(iii)) and therefore countable sets ˜ 2 H s and ˜ 2 H s are sets in the sense of the set theory Z F C ¯ 2 H s .

Remark 3.1.2. Note that by using Gödel encoding the above stated contradiction can be shipped in special completion Z F C ¯ 2 H s # of Z F C ¯ 2 H s , 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 M s t Z F C 2 H s by reductio ad absurdum it follows again ¬ C o n ( Z F C N s t ) , 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 Z F C 2 H s . Let ˜ 2 H s be the set of the all sets of M provably definable in Z F C ¯ 2 H s , and let ˜ 2 H s = { x ˜ 2 H s : ( x x ) } where A means “sentence A derivable in Z F C ¯ 2 H s ”, or some appropriate modification thereof. We replace now formula (39) by the following formula

Y { Y ˜ 2 H s Ψ ( X ) [ ( [ Ψ ( X ) ] Γ X H s / X ) ! X [ Ψ ( X ) Y = X ] ] } . (45)

and we replace formula (42) by the following formula

X ( X ˜ 2 H s ) [ X ˜ 2 H s ( X X ) ] . (46)

Definition 3.1.2. We rewrite now (45) in the following equivalent form

Y { Y ˜ 2 H s Ψ ( X ) [ ( [ Ψ ( X ) ] H s Γ X H s / X ) ( Y = X ) ] } , (47)

where the countable set Γ X H s / X is defined by the following formula

Ψ ( X ) { [ Ψ ( X ) ] Γ X H s / X [ ( [ Ψ ( X ) ] H s Γ X H s / X ) ! X Ψ ( X ) ] } (48)

Definition 3.1.3. Let ˜ 2 H s be the countable set of the all sets such that

X ( X ˜ 2 H s ) [ X ˜ 2 H s X X ] . (49)

Remark 3.1.5. Note that ˜ 2 H s ˜ 2 H s since ˜ 2 H s is a set definable by the first order 1-place open wff1:

Ψ ( Z , ˜ 2 H s ) X ( X ˜ 2 H s ) [ X Z ( X X ) ] . (50)

From (49) and Remark 3.1.4 one obtains

˜ 2 H s ˜ 2 H s ( ˜ 2 H s ˜ 2 H s ) . (51)

But (51) immediately gives a contradiction

Z F C ¯ 2 H s ( ˜ 2 H s ˜ 2 H s ) ( ˜ 2 H s ˜ 2 H s ) . (52)

Remark 3.1.6. Note that contradiction (52) is a contradiction inside Z F C ¯ 2 H s for the reason that the countable set ˜ 2 H s is a set in the sense of the set theory Z F C ¯ 2 H s .

In order to obtain a contradiction inside Z F C ¯ 2 H s without any reference to Assumption 3.1.1 we introduce the following definitions.

Definition 3.1.4. We define now the countable set Γ ν H s / ν by the following formula

[ y ] H s Γ ν H s / ν ( [ y ] H s Γ ν H s / ν ) F r ^ 2 H s ( y , v ) [ ! X Ψ y , ν ( X ) ] (53)

Definition 3.1.5. We choose now A in the following form

A B e w Z F C ¯ 2 H s ( # A ) [ B e w Z F C ¯ 2 H s ( # A ) A ] . (54)

Here B e w Z F C ¯ 2 H s ( # A ) is a canonical Gödel formula which says to us that there exists proof in Z F C ¯ 2 H s of the formula A with Gödel number # A .

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 Z F C ¯ 2 H s .

Definition 3.1.6. Using Definition 3.1.5, we replace now formula (48) by the following formula

Ψ ( X ) { [ Ψ ( X ) ] Γ X H s / X Ψ ( X ) ( [ Ψ ( X ) ] Γ X H s / X ) [ B e w Z F C ¯ 2 H s ( # ( ! X [ Ψ ( X ) Y = X ] ) ) ] [ B e w Z F C ¯ 2 H s ( # ( ! X [ Ψ ( X ) Y = X ] ) ) ! X [ Ψ ( X ) Y = X ] ] } . (55)

Definition 3.1.7. Using Definition 3.1.5, we replace now formula (49) by the following formula

X ( X ˜ 2 H s ) [ X ˜ 2 H s [ B e w Z F C ¯ 2 H s ( # ( X X ) ) ] [ B e w Z F C ¯ 2 H s ( # ( X X ) ) X X ] . (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

y { [ y ] H s Γ ν H s / ν ( [ y ] H s Γ ν H s / ν ) F r 2 H s ^ ( y , v ) [ B e w Z F C ¯ 2 H s ( # ! X [ Ψ y , ν ( X ) Y = X ] ) ] [ B e w Z F C ¯ 2 H s ( # ! X [ Ψ y , ν ( X ) Y = X ] ) ! X [ Ψ y , ν ( X ) Y = X ] ] } . (57)

Definition 3.1.9. Using Definitions 3.1.4-3.1.6, we define now the countable set ˜ 2 H s by formula

Y { Y ˜ 2 H s y [ ( [ y ] Γ ν H s / ν ) ( g Z F C ¯ 2 H s ( X ) = ν ) ] } . (58)

Remark 3.1.8. Note that from the second order axiom schema of replacement (12) it follows directly that ˜ 2 H s is a set in the sense of the set theory Z F C ¯ 2 H s .

Definition 3.1.10. Using Definition 3.1.8 we replace now formula (56) by the following formula

X ( X ˜ 2 H s ) [ X ˜ 2 H s [ B e w Z F C ¯ 2 H s ( # ( X X ) ) ] [ B e w Z F C ¯ 2 H s ( # ( X X ) ) X X ] ] . (59)

Remark 3.1.9. Notice that the expression (60)

[ B e w Z F C ¯ 2 H s ( # ( X X ) ) ] [ B e w Z F C ¯ 2 H s ( # ( X X ) ) X X ] (60)

obviously is a well formed formula of Z F C ¯ 2 H s and therefore a set ˜ 2 H s is a set in the sense of Z F C ¯ 2 H s .

Remark 3.1.10. Note that ˜ 2 H s ˜ 2 H s since ˜ 2 H s is a set definable by 1-place open wff

Ψ ( Z , ˜ 2 H s ) X ( X ˜ 2 H s ) [ X Z [ B e w Z F C ¯ 2 H s ( # ( X X ) ) ] [ B e w Z F C ¯ 2 H s ( # ( X X ) ) X X ] ] . (61)

Theorem 3.1.1. Set theory Z F C ¯ 2 H s Z F C 2 H s + M s t Z F C 2 H s is inconsistent.

Proof. From (59) we obtain

˜ 2 H s ˜ 2 H s [ B e w Z F C ¯ 2 H s ( # ( ˜ 2 H s ˜ 2 H s ) ) ] [ B e w Z F C ¯ 2 H s ( # ( ˜ 2 H s ˜ 2 H s ) ) ˜ 2 H s ˜ 2 H s ] . (62)

a) Assume now that:

˜ 2 H s ˜ 2 H s . (63)

Then from (62) we obtain Z F C ¯ 2 H s B e w Z F C ¯ 2 H s ( # ( ˜ 2 H s ˜ 2 H s ) ) and

Z F C ¯ 2 H s B e w Z F C ¯ 2 H s ( # ( ˜ 2 H s ˜ 2 H s ) ) ˜ 2 H s ˜ 2 H s ,

therefore Z F C ¯ 2 H s ˜ 2 H s ˜ 2 H s and so

Z F C ¯ 2 H s ˜ 2 H s ˜ 2 H s ˜ 2 H s ˜ 2 H s . (64)

From (63)-(64) we obtain

˜ 2 H s ˜ 2 H s , ˜ 2 H s ˜ 2 H s ˜ 2 H s ˜ 2 H s ˜ 2 H s ˜ 2 H s

and thus Z F C ¯ 2 H s ( ˜ 2 H s ˜ 2 H s ) ( ˜ 2 H s ˜ 2 H s ) .

b) Assume now that

[ B e w Z F C ¯ 2 H s ( # ( ˜ 2 H s ˜ 2 H s ) ) ] [ B e w Z F C ¯ 2 H s ( # ( ˜ 2 H s ˜ 2 H s ) ) ˜ 2 H s ˜ 2 H s ] . (65)

Then from (65) we obtain ˜ 2 H s ˜ 2 H s . From (65) and (62) we obtain Z F C ¯ 2 H s ˜ 2 H s ˜ 2 H s , so Z F C ¯ 2 H s ˜ 2 H s ˜ 2 H s , ˜ 2 H s ˜ 2 H s which immediately gives us a contradiction Z F C ¯ 2 H s ( ˜ 2 H s ˜ 2 H s ) ( ˜ 2 H s ˜ 2 H s ) .

Definition 3.1.11. We choose now A in the following form

A B e w ¯ Z F C ¯ 2 H s ( # A ) , (66)

or in the following equivalent form

A B e w ¯ Z F C ¯ 2 H s ( # A ) [ B e w ¯ Z F C ¯ 2 H s ( # A ) A ] (67)

similar to (46). Here B e w ¯ Z F C ¯ 2 H s ( # A ) is a Gödel formula which really asserts provability in Z F C ¯ 2 H s of the formula A with Gödel number # A .

Remark 3.1.11. Notice that the Definition 3.1.12 with formula (66) holds as definition of predicate really asserting provability in Z F C ¯ 2 H s .

Definition 3.1.12. Using Definition 3.1.11 with formula (66), we replace now formula (48) by the following formula

Ψ ( X ) { [ Ψ ( X ) ] Γ ¯ X H s / X Ψ ( X ) ( [ Ψ ( X ) ] Γ X H s / X ) [ B e w ¯ Z F C ¯ 2 H s ( # ( ! X [ Ψ ( X ) Y = X ] ) ) ] } . (68)

Definition 3.1.13. Using Definition 3.1.11 with formula (66), we replace now formula (49) by the following formula

X ( X ˜ 2 H s ) [ X ˜ 2 H s [ B e w ¯ Z F C ¯ 2 H s ( # ( X X ) ) ] ] (69)

Definition 3.1.14. Using Definition 3.1.11 with formula (66), we replace now formula (53) by the following formula

y { [ y ] H s Γ ν H s / ν ( [ y ] H s Γ ν H s / ν ) F r ^ 2 H s ( y , v ) [ B e w ¯ Z F C ¯ 2 H s ( # ! X [ Ψ y , ν ( X ) Y = X ] ) ] } . (70)

Definition 3.1.15. Using Definitions 3.1.12-3.1.16, we define now the countable set ˜ 2 H s by formula

Y { Y ˜ 2 H s y [ ( [ y ] Γ ν H s / ν ) ( g Z F C ¯ 2 H s ( X ) = ν ) ] } . (71)

Remark 3.1.12. Note that from the axiom schema of replacement (12) it follows directly that ˜ 2 H s is a set in the sense of the set theory Z F C ¯ 2 H s .

Definition 3.1.16. Using Definition 3.1.15 we replace now formula (69) by the following formula

X ( X ˜ 2 H s ) [ X ˜ 2 H s [ B e w ¯ Z F C ¯ 2 H s ( # ( X X ) ) ] ] . (72)

Remark 3.1.13. Notice that the expressions (73)

[ B e w ¯ Z F C ¯ 2 H s ( # ( X X ) ) ] and [ B e w ¯ Z F C ¯ 2 H s ( # ( X X ) ) ] [ B e w ¯ Z F C ¯ 2 H s ( # ( X X ) ) X X ] (73)

obviously are a well formed formula of Z F C ¯ 2 H s and therefore collection ˜ 2 H s is a set in the sense of Z F C ¯ 2 H s .

Remark 3.1.14. Note that ˜ 2 H s ˜ 2 H s since ˜ 2 H s is a set definable by 1-place open wff1

Ψ ( Z , ˜ 2 H s ) X ( X ˜ 2 H s ) [ X Z B e w ¯ Z F C ¯ 2 H s ( # ( X X ) ) ] . (74)

Theorem 3.1.2. Set theory Z F C ¯ 2 H s Z F C 2 H s + M s t Z F C 2 H s is inconsistent.

Proof. From (72) we obtain

˜ 2 H s ˜ 2 H s [ B e w ¯ Z F C ¯ 2 H s ( # ( ˜ 2 H s ˜ 2 H s ) ) ] . (75)

a) Assume now that:

˜ 2 H s ˜ 2 H s . (76)

Then from (75) we obtain Z F C ¯ 2 H s B e w ¯ Z F C ¯ 2 H s ( # ( ˜ 2 H s ˜ 2 H s ) ) and therefore Z F C ¯ 2 H s ˜ 2 H s ˜ 2 H s , thus we obtain

Z F C ¯ 2 H s ˜ 2 H s ˜ 2 H s ˜ 2 H s ˜ 2 H s . (77)

From (76)-(77) we obtain ˜ 2 H s ˜ 2 H s and ˜ 2 H s ˜ 2 H s ˜ 2 H s ˜ 2 H s , thus Z F C ¯ 2 H s ˜ 2 H s ˜ 2 H s and finally we obtain Z F C ¯ 2 H s ( ˜ 2 H s ˜ 2 H s ) ( ˜ 2 H s ˜ 2 H s ) .

b) Assume now that

[ B e w Z F C ¯ 2 H s ( # ( ˜ 2 H s ˜ 2 H s ) ) ] . (78)

Then from (78) we obtain Z F C ¯ 2 H s ˜ 2 H s ˜ 2 H s . From (78) and (75) we obtain Z F C ¯ 2 H s ˜ 2 H s ˜ 2 H s , thus Z F C ¯ 2 H s ˜ 2 H s ˜ 2 H s and Z F C ¯ 2 H s ˜ 2 H s ˜ 2 H s which immediately gives us a contradiction Z F C ¯ 2 H s ( ˜ 2 H s ˜ 2 H s ) ( ˜ 2 H s ˜ 2 H s ) .

3.2. Derivation of the Inconsistent Provably Definable Set in Set Theory ZFCst

Let s t be the countable set of all sets X such that Z F C s t ! X Ψ ( X ) , where Ψ ( X ) is a 1-place open wff of ZFC i.e.,

Y { Y s t Z F C s t Ψ ( X ) [ ( [ Ψ ( X ) ] Γ X s t / X ) ! X [ Ψ ( X ) Y = X ] ] } . (79)

Let X Z F C s t Y be a predicate such that X Z F C s t Y Z F C s t X Y . Let be the countable set of the all sets such that

X [ X s t ( X s t ) ( X Z F C s t X ) ] . (80)

From (80) one obtains

s t s t s t Z F C s t s t . (81)

But (81) immediately gives a contradiction

( s t s t ) ( s t s t ) . (82)

Remark 3.2.1. Note that a contradiction (82) is a contradiction inside Z F C s t

for the reason that predicate X Z F C s t Y is expressible by using first order

language as predicate of Z F C s t (see subsection 4.1) and therefore countable sets s t and s t are sets in the sense of the set theory Z F C s t .

Remark 3.2.2. Note that by using Gödel encoding the above stated contradiction can be shipped in special completion Z F C s t # of Z F C s t , see subsection 1.2, Theorem 1.2.2 (i).

Designation 3.2.1. i) Let M s t Z F C be a standard model of ZFC and

ii) let Z F C s t be the theory Z F C s t = Z F C + M s t Z F C ,

iii) let s t be the set of the all sets of M s t Z F C provably definable in Z F C s t , and let s t = { X s t : s t ( X X ) } , where s t A means: “sentence A derivable in Z F C s t ”, or some appropriate modification thereof.

We replace now (79) by formula

Y { Y s t s t [ Ψ ( ) ! X [ Ψ ( X ) Y = X ] ] } , (83)

and we replace (80) by formula

X [ X s t ( X s t ) s t ( X X ) ] . (84)

Assume that Z F C s t s t s t . Then, we have that: s t s t iff s t ( s t s t ) , which immediately gives us s t s t iff s t s t . But this is a contradiction, i.e., Z F C s t ( s t s t ) ( s t s t ) . We choose now s t A in the following form

s t A B e w Z F C s t ( # A ) [ B e w Z F C s t ( # A ) A ] . (85)

Here B e w Z F C s t ( # A ) is a canonical Gödel formula which says to us that there exists proof in Z F C s t of the formula A with Gödel number # A M s t P A .

Remark 3.2.3. Notice that Definition 3.2.6 holds as definition of predicate really asserting provability in Z F C s t .

Definition 3.2.1. We rewrite now (83) in the following equivalent form

Y { Y ˜ s t Ψ ( X ) [ ( [ Ψ ( X ) ] s t Γ X s t / X ) ( Y = X ) ] } , (86)

where the countable collection Γ X H s / X is defined by the following formula

Ψ ( X ) { [ Ψ ( X ) ] s t Γ X s t / X [ ( [ Ψ ( X ) ] s t Γ X s t / X ) s t ! X Ψ ( X ) ] } (87)

Definition 3.2.2. Let ˜ s t be the countable collection of the all sets such that

X ( X ˜ s t ) [ X ˜ s t s t ( X X ) ] . (88)

Remark 3.2.4. Note that ˜ 2 H s ˜ 2 H s since ˜ 2 H s is a collection definable by 1-place open wff

Ψ ( Z , ˜ s t ) X ( X ˜ s t ) [ X Z s t ( X X ) ] . (89)

Definition 3.2.3. By using formula (85) we rewrite now (86) in the following equivalent form

Y { Y ˜ s t Ψ ( X ) [ ( [ Ψ ( X ) ] s t Γ X s t / X ) ( Y = X ) ] } , (90)

where the countable collection Γ X H s / X is defined by the following formula

Ψ ( X ) { [ Ψ ( X ) ] s t Γ X s t / X [ ( [ Ψ ( X ) ] s t Γ X s t / X ) B e w Z F C s t ( # ! X Ψ ( X ) ) ] [ B e w Z F C s t ( # ! X Ψ ( X ) ) ! X Ψ ( X ) ] } (91)

Definition 3.2.4. Using formula (85), we replace now formula (88) by the following formula

X ( X ˜ s t ) [ X ˜ s t [ B e w Z F C s t ( # ( X X ) ) ] [ B e w Z F C s t ( # ( X X ) ) ] . (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

y { [ y ] s t Γ ν s t / ν ( [ y ] s t Γ ν s t / ν ) F r ^ s t ( y , v ) [ B e w Z F C s t ( # ! X [ Ψ y , ν ( X ) Y = X ] ) ] [ B e w Z F C s t ( # ! X [ Ψ y , ν ( X ) Y = X ] ) ! X [ Ψ y , ν ( X ) Y = X ] ] } . (93)

Definition 3.2.6. Using Definitions 3.2.3-3.2.5, we define now the countable set ˜ s t by formula

Y { Y ˜ s t y [ ( [ y ] s t Γ ν s t / ν ) ( g Z F C s t ( X ) = ν ) ] } . (94)

Remark 3.2.5. Note that from the axiom schema of replacement it follows directly that ˜ s t is a set in the sense of the set theory Z F C s t .

Definition 3.2.7. Using Definition 3.2.6 we replace now formula (92) by the following formula

X ( X ˜ s t ) [ X ˜ s t [ B e w Z F C s t ( # ( X X ) ) ] [ B e w Z F C ¯ s t ( # ( X X ) ) X X ] ] . (95)

Remark 3.2.6. Notice that the expression (96)

[ B e w Z F C s t ( # ( X X ) ) ] [ B e w Z F C s t ( # ( X X ) ) X X ] (96)

obviously is a well formed formula of Z F C s t and therefore collection ˜ s t is a set in the sense of Z F C ¯ 2 H s .

Remark 3.2.7. Note that ˜ s t ˜ s t since ˜ s t is a collection definable by 1-place open wff

Ψ ( Z , ˜ s t ) X ( X ˜ s t ) [ X Z [ B e w Z F C s t ( # ( X X ) ) ] [ B e w Z F C s t ( # ( X X ) ) X X ] ] . (97)

Theorem 3.2.1. Set theory Z F C s t Z F C + M s t Z F C is inconsistent.

Proof. From (95) we obtain

˜ s t ˜ s t [ B e w Z F C s t ( # ( ˜ s t ˜ s t ) ) ] [ B e w Z F C s t ( # ( ˜ s t ˜ s t ) ) ˜ s t ˜ s t ] . (98)

a) Assume now that:

˜ s t ˜ s t . (99)

Then from (98) we obtain B e w Z F C s t ( # ( ˜ s t ˜ s t ) ) and B e w Z F C s t ( # ( ˜ s t ˜ s t ) ) ˜ s t ˜ s t , therefore ˜ s t ˜ s t and so

Z F C s t ˜ s t ˜ s t ˜ s t ˜ s t . (100)

From (99)-(100) we obtain ˜ s t ˜ s t , ˜ s t ˜ s t ˜ s t ˜ s t ˜ s t ˜ s t and therefore Z F C s t ( ˜ s t ˜ s t ) ( ˜ s t ˜ s t ) .

b) Assume now that

[ B e w Z F C s t ( # ( ˜ s t ˜ s t ) ) ] [ B e w Z F C s t ( # ( ˜ s t ˜ s t ) ) ˜ s t ˜ s t ] . (101)

Then from (101) we obtain ˜ 2 H s ˜ 2 H s . From (101) and (98) we obtain Z F C ¯ 2 H s ˜ 2 H s ˜ 2 H s , so Z F C ¯ 2 H s ˜ 2 H s ˜ 2 H s , ˜ 2 H s ˜ 2 H s which immediately gives us a contradiction Z F C ¯ 2 H s ( ˜ 2 H s ˜ 2 H s ) ( ˜ 2 H s ˜ 2 H s ) .

3.3. Derivation of the Inconsistent Provably Definable Set in ZFCNst

Designation 3.3.1. i) Let P A ¯ 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 M N s t Z F C be a nonstandard model of ZFC and let M s t P A ¯ be a standard model of P A ¯ . We assume now that M s t P A ¯ M N s t Z F C and denote such nonstandard model of ZFC by M N s t Z F C [ P A ¯ ] .

iii) Let Z F C N s t be the theory Z F C N s t = Z F C + M N s t Z F C [ P A ¯ ] .

iv) Let N s t be the set of the all sets of M s t Z F C [ P A ¯ ] provably definable in Z F C N s t , and let N s t = { X N s t : N s t ( X X ) } where N s t A means “sentence A derivable in Z F C N s t ”, or some appropriate modification thereof. We replace now (45) by formula

Y { Y N s t N s t [ Ψ ( ) ! X [ Ψ ( X ) Y = X ] ] } , (102)

and we replace (46) by formula

X [ X N s t ( X N s t ) N s t ( X X ) ] . (103)

Assume that Z F C N s t N s t N s t . Then, we have that: N s t N s t iff N s t ( N s t N s t ) , which immediately gives us N s t N s t iff N s t N s t . But this is a contradiction, i.e., Z F C N s t ( N s t N s t ) ( N s t N s t ) . We choose now N s t A in the following form

N s t A B e w Z F C N s t ( # A ) [ B e w Z F C N s t ( # A ) A ] . (104)

Here B e w Z F C N s t ( # A ) is a canonical Gödel formula which says to us that there exists proof in Z F C N s t of the formula A with Gödel number # A M s t P A .

Remark 3.3.1. Notice that definition (104) holds as definition of predicate really asserting provability in Z F C N s t .

Designation 3.3.2. i) Let g Z F C N s t ( u ) be a Gödel number of given an expression u of Z F C N s t .

ii) Let F r N s t ( y , v ) be the relation: y is the Gödel number of a wff of Z F C N s t that contains free occurrences of the variable with Gödel number v [6] [10] .

iii) Let N s t ( y , v , ν 1 ) be a Gödel number of the following wff: ! X [ Ψ ( X ) Y = X ] , where g Z F C N s t ( Ψ ( X ) ) = y , g Z F C N s t ( X ) = ν , g Z F C N s t ( Y ) = ν 1 .

iv) Let Pr Z F C N s t ( z ) be a predicate asserting provability in Z F C N s t .

Remark 3.3.2. Let N s t be the countable collection of all sets X such that Z F C N s t ! X Ψ ( X ) , where Ψ ( X ) is a 1-place open wff i.e.,

Y { Y N s t Z F C N s t Ψ ( X ) ! X [ Ψ ( X ) Y = X ] } . (105)

We rewrite now (105) in the following form

Y { Y N s t ( g Z F C N s t ( Y ) = ν 1 ) y F r ^ N s t ( y , v ) ( g Z F C N s t ( X ) = ν ) [ Pr Z F C N s t ( N s t ( y , v , ν 1 ) ) [ Pr Z F C N s t ( N s t ( y , v , ν 1 ) ) ! X [ Ψ ( X ) Y = X ] ] ] } (106)

Designation 3.3.3. Let N s t ( z ) be a Gödel number of the following wff: Z Z , where g Z F C N s t ( Z ) = z .

Remark 3.3.3. Let N s t above by formula (103), i.e.,

Z [ Z N s t ( Z N s t ) N s t ( Z Z ) ] . (107)

We rewrite now (107) in the following form

Z [ Z N s t ( Z N s t ) g Z F C N s t ( Z ) = z Pr Z F C N s t ( N s t ( z ) ) ] [ Pr Z F C N s t ( N s t ( z ) ) Z Z ] . (108)

Theorem 3.3.1. Z F C N s t N s t N s t N s t N s t .

3.4. Generalized Tarski’s Undefinability Lemma

Remark 3.4.1. Remind that: i) if T h is a theory, let T T h be the set of Godel numbers of theorems of T h [10] , ii) the property x T T h is said to be is expressible in T h by wff T r u e ( x 1 ) if the following properties are satisfied [10] :

a) if n T T h then T h T r u e ( n ¯ ) , b) if n T T h then T h ¬ T r u e ( n ¯ ) .

Remark 3.4.2. Notice it follows from (a) (b) that

¬ [ ( T h T r u e ( n ¯ ) ) ( T h ¬ T r u e ( n ¯ ) ) ] .

Theorem 3.4.1. (Tarski’s undefinability Lemma) [10] . Let T h be a consistent theory with equality in the language L in which the diagonal function D is representable and let g T h ( u ) be a Gödel number of given an expression u of T h . Then the property x T T h is not expressible in T h .

Proof. By the diagonalization lemma applied to ¬ T r u e ( x 1 ) there is a sentence F such that: c) T h F ¬ T r u e ( q ¯ ) , where q is the Godel number of F , i.e. g T h ( F ) = q .

Case 1. Suppose that T h F , then q T T h . By (a), T h T r u e ( q ¯ ) . But, from T h F and (c), by biconditional elimination, one obtains T h ¬ T r u e ( q ¯ ) . Hence T h is inconsistent, contradicting our hypothesis.

Case 2. Suppose that T h F , then q T T h . By (b), T h ¬ T r u e ( q ¯ ) . Hence, by (c) and biconditional elimination, T h F . Thus, in either case a contradiction is reached.

Definition 3.4.1. If T h is a theory, let T T h be the set of Godel numbers of theorems of T h and let g T h ( u ) be a Gödel number of given an expression u of T h . The property x T T h is said to be is a strongly expressible in T h by wff T r u e ( x 1 ) if the following properties are satisfied:

a) if n T T h then T h T r u e ( n ¯ ) ( T r u e ( n ¯ ) g T h 1 ( n ) ) ,

b) if n T T h then T h ¬ T r u e ( n ¯ ) .

Theorem 3.4.2. (Generalized Tarski’s undefinability Lemma). Let T h be a consistent theory with equality in the language L in which the diagonal function D is representable and let g T h ( u ) be a Gödel number of given an expression u of T h . Then the property x T T h is not strongly expressible in T h .

Proof. By the diagonalization lemma applied to ¬ T r u e ( x 1 ) there is a sentence F such that: c) T h F ¬ T r u e ( q ¯ ) , where q is the Godel number of F , i.e. g T h ( F ) = q .

Case 1. Suppose that T h F , then q T T h . By (a), T h T r u e ( q ¯ ) . But, from T h F and (c), by biconditional elimination, one obtains T h ¬ T r u e ( q ¯ ) . Hence T h is inconsistent, contradicting our hypothesis.

Case 2. Suppose that T h F , then q T T h . By (b), T h ¬ T r u e ( q ¯ ) . Hence, by (c) and biconditional elimination, T h F . Thus, in either case a contradiction is reached.

Remark 3.4.3. Notice that Tarski’s undefinability theorem cannot blocking the biconditionals

, s t s t s t s t , N s t N s t N s t N s t , (109)

see Subsection 2.2.

3.5. Generalized Tarski’s Undefinability Theorem

Remark 3.5.1. I) Let T h 1 # be the theory T h 1 # Z F C ¯ 2 H s .

In addition under assumption C o n ˜ ( T h 1 # ) , we establish a countable sequence of the consistent extensions of the theory T h 1 # such that:

i) T h 1 # T h i # T h i + 1 # T h # , where

ii) T h i + 1 # is a finite consistent extension of T h i # ,

iii) T h # = i T h i # ,

iv) T h # proves the all sentences of T h 1 # , which is valid in M, i.e., M A T h # A , see see Subsection 4.1, Proposition 4.1.1.

II) Let T h 1, s t # be T h 1, s t # Z F C s t .

In addition under assumption C o n ˜ ( T h 1, s t # ) , we establish a countable sequence of the consistent extensions of the theory T h 1 # such that:

i) T h 1, s t # T h i , s t # T h i + 1, s t # T h , s t # , where

ii) T h i + 1, s t # is a finite consistent extension of T h i , s t # ,

iii) T h , s t # = i T h i , s t # ,

iv) T h , s t # proves the all sentences of T h 1, s t # , which valid in M s t Z F C , i.e., M s t Z F C A T h , s t # A , see Subsection 4.1, Proposition 4.1.1.

III) Let T h 1, N s t # be T h 1, N s t # Z F C N s t .

In addition under assumption C o n ˜ ( T h 1, N s t # ) , we establish a countable sequence of the consistent extensions of the theory T h 1 # such that:

i) T h 1, N s t # T h i , N s t # T h i + 1, s t # T h , N s t # , where

ii) T h i + 1, N s t # is a finite consistent extension of T h i , N s t # ,

iii) T h , s t # = i T h i , s t #

iv) T h , s t # proves the all sentences of T h 1, s t # , which valid in M N s t Z F C [ P A ] , i.e., M N s t Z F C [ P A ] A T h , N s t # A , see Subsection 4.1, Proposition 4.1.1.

Remark 3.5.2. I) Let i , i = 1,2, be the set of the all sets of M provably definable in T h i # ,

Y { Y i i Ψ ( ) ! X [ Ψ ( X ) Y = X ] } . (110)

and let i = { x i : i ( x x ) } where i A means sentence A derivable in T h i # . Then we have that i i iff i ( i i ) , which immediately gives us i i iff i i . We choose now i A , i = 1,2, in the following form

i A B e w i ( # A ) [ B e w i ( # A ) A ] . (111)

Here B e w i ( # A ) , i = 1,2, is a canonical Gödel formulae which says to us that there exists proof in T h i # , i = 1,2, of the formula A with Gödel number # A .

II) Let i , s t , i = 1,2, be the set of the all sets of M s t Z F C provably definable in T h i , s t # ,

Y { Y i , s t i , s t Ψ ( ) ! X [ Ψ ( X ) Y = X ] } . (112)

and let i , s t = { x i , s t : i , s t ( x x ) } where i , s t A means sentence A derivable in T h i , s t # .

Then we have that i , s t i , s t iff i , s t ( i , s t i , s t ) , which immediately gives us i , s t i , s t iff i , s t i , s t . We choose now i , s t A , i = 1,2, in the following form

i , s t A B e w i , s t ( # A ) [ B e w i , s t ( # A ) A ] . (113)

Here B e w i , s t ( # A ) , i = 1,2, is a canonical Gödel formulae which says to us that there exists proof in T h i , s t # , i = 1,2, of the formula A with Gödel number # A .

III) Let i , N s t , i = 1,2, be the set of the all sets of M N s t Z F C [ P A ] provably definable in T h i , N s t # ,

Y { Y i , N s t i , N s t Ψ ( ) ! X [ Ψ ( X ) Y = X ] } . (114)

and let i , N s t = { x i , N s t : i , N s t ( x x ) } where i , N s t A means sentence A derivable in T h i , N s t # . Then we have that i , N s t i , N s t iff i , N s t ( i , N s t i , N s t ) , which immediately gives us i , N s t i , N s t iff i , N s t i , N s t .

We choose now i , N s t A , i = 1,2, in the following form

i , N s t A B e w i , N s t ( # A ) [ B e w i , N s t ( # A ) A ] . (115)

Here B e w i , N s t ( # A ) , i = 1,2, is a canonical Gödel formulae which says to us that there exists proof in T h i , N s t # , i = 1,2, of the formula A with Gödel number # A .

Remark 3.5.3. Notice that definitions (111), (113) and (115) hold as definitions of predicates really asserting provability in T h i # , T h i , s t # and T h i , N s t # , i = 1,2, correspondingly.

Remark 3.5.4. Of course the all theories T h i # , T h i , s t # , T h i , N s t # , i = 1,2, are inconsistent, see subsection 4.1.

Remark 3.5.5. I) Let be the set of the all sets of M provably definable in T h # ,

Y { Y Ψ ( ) ! X [ Ψ ( X ) Y = X ] } . (116)

and let = { x : ( x x ) } , where A means “sentence A derivable in T h # ”. Then, we have that iff ( ) , which immediately gives us iff . We choose now A , i = 1,2, in the following form

A i [ B e w i ( # A ) [ B e w i ( # A ) A ] ] . (117)

II) Let , s t be the set of the all sets of M s t Z F C provably definable in T h , s t # ,

Y { Y , s t , s t Ψ ( ) ! X [ Ψ ( X ) Y = X ] } . (118)

and let , s t be the set , s t = { x , s t : , s t ( x x ) } , where , s t A means “sentence A derivable in T h , s t # ”. Then, we have that , s t , s t iff , s t ( , s t , s t ) , which immediately gives us , s t , s t iff , s t , s t . We choose now , s t A , i = 1,2, in the following form

, s t A i [ B e w i , s t ( # A ) [ B e w i , s t ( # A ) A ] ] . (119)

III) Let , N s t be the set of the all sets of M N s t Z F C [ P A ] provably definable in T h , N s t # ,

Y { Y , N s t , N s t Ψ ( ) ! X [ Ψ ( X ) Y = X ] } . (120)

and let , N s t be the set , N s t = { x , N s t : , N s t ( x x ) } where , N s t A means “sentence A derivable in T h , N s t # ”. Then, we have that , N s t , N s t iff , N s t ( , N s t , N s t ) , which immediately gives us , N s t , N s t iff , N s t , N s t . We choose now , N s t A , i = 1,2, in the following form

, N s t A i [ B e w i , N s t ( # A ) [ B e w i , N s t ( # A ) A ] ] . (121)

Remark 3.5.6. Notice that definitions (117), (119) and (121) hold as definitions of a predicate really asserting provability in T h # , T h , s t # and T h , N s t # correspondingly.

Remark 3.5.7. Of course all the theories T h # , T h , s t # and T h , N s t # 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 Z F C 2 H s (but iff Z F C 2 H s is consistent) by well-known Tarski’s undefinability theorem [10] .

Theorem 3.5.1. Tarski’s undefinability theorem: I) Let T h L be first order theory with formal language L , which includes negation and has a Gödel numbering g ( ) such that for every L -formula A ( x ) there is a formula B such that B A ( g ( B ) ) holds. Assume that T h L has a standard model M s t T h L and C o n ( T h L , s t ) where

T h L , s t T h L + M s t T h L . (122)

Let T be the set of Gödel numbers of L -sentences true in M s t T h L . Then there is no L -formula T r u e ( n ) (truth predicate) which defines T . That is, there is no L -formula T r u e ( n ) such that for every L -formula A,

T r u e ( g ( A ) ) A (123)

holds.

II) Let T h H s be second order theory with Henkin semantics and formal language L , which includes negation and has a Gödel numbering g ( ) such that for every L -formula A ( x ) there is a formula B such that B A ( g ( B ) ) holds.

Assume that T h H s has a standard model M s t T h L H s and C o n ( T h L , s t H s ) , where

T h , s t H s T h H s + M s t T h L H s (124)

Let T be the set of Gödel numbers of the all L -sentences true in M. Then there is no L -formula T r u e ( n ) (truth predicate) which defines T . That is, there is no L -formula T r u e ( n ) such that for every L -formula A,

T r u e ( g ( A ) ) 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 L -formula True(n) defines T . In particular, if A is a sentence of T h L then T r u e ( g ( A ) ) holds in iff A is true in M s t T h L . Hence for all A, the Tarski T-sentence T r u e ( g ( A ) ) A is true in M s t T h L . But the diagonal lemma yields a counterexample to this equivalence, by giving a “Liar” sentence S such that S ¬ T r u e ( g ( S ) ) holds in M s t T h L . Thus no L -formula T r u e ( n ) can define T .

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 L -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

i i i i , i , , etc ., (126)

see Remark 3.5.14 below.

Remark 3.5.13. I) We define again the set but now by using generalized truth predicate T r u e # ( g ( A ) , A ) such that

T r u e # ( g ( A ) , A ) i [ B e w i ( # A ) [ B e w i ( # A ) A ] ] T r u e ( g ( A ) ) [ T r u e ( g ( A ) ) A ] A , T r u e ( g ( A ) ) i B e w i ( # A ) . (127)

holds.

II) We define the set , s t using generalized truth predicate T r u e , s t # ( g ( A ) , A ) such that

T r u e , s t # ( g ( A ) , A ) i [ B e w i , s t ( # A ) [ B e w i , s t ( # A ) A ] ] T r u e , s t ( g ( A ) ) [ T r u e , s t ( g ( A ) ) A ] A , T r u e , s t ( g ( A ) ) i B e w i , s t ( # A ) (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 , N s t using generalized truth predicate T r u e , N s t # ( g ( A ) , A ) such that

T r u e , N s t # ( g ( A ) , A ) i [ B e w i , N s t ( # A ) [ B e w i , N s t ( # A ) A ] ] T r u e , N s t ( g ( A ) ) [ T r u e , N s t ( g ( A ) ) A ] A , T r u e , N s t ( g ( A ) ) i B e w i , N s t ( # A ) . (129)

holds. Thus in contrast with naive definition of the sets , N s t and , N s t there is no any problem which arises from Tarski’s undefinability theorem.

Remark 3.5.14. In order to prove that set theory Z F C 2 H s + M Z F C 2 H s is inconsistent without any reference to the set , notice that by the properties of the extension T h # it follows that definition given by formula (127) is correct, i.e., for every Z F C 2 H s -formula Φ such that M Z F C 2 H s Φ the following equivalence Φ T r u e ( g ( Φ ) , Φ ) holds.

Theorem 3.5.2. (Generalized Tarski’s undefinability theorem) (see subsection 4.2, Proposition 4.2.1). Let T h L be a first order theory or the second order theory with Henkin semantics and with formal language L , which includes negation and has a Gödel encoding g ( ) such that for every L -formula A ( x ) there is a formula B such that the equivalence B A ( g ( B ) ) holds. Assume that T h L has a standard Model M s t T h . Then there is no L -formula T r u e ( n ) , n , such that for every L -formula A such that M A , the following equivalence holds

A T r u e ( g ( A ) , A ) . (130)

Theorem 3.5.3. i) Set theory T h 1 # = Z F C 2 H s + M Z F C 2 H s is inconsistent;

ii) Set theory T h 1, s t # = Z F C + M s t Z F C is inconsistent; iii) Set theory T h 1, N s t # = Z F C + M N s t Z F C is inconsistent; (see subsection 4.2, Proposition 4.2.2).

Proof. i) Notice that by the properties of the extension T h # of the theory Z F C 2 H s + M Z F C 2 H s = T h 1 # it follows that

M Z F C 2 H s Φ T h # Φ . (131)

Therefore formula (127) gives generalized “truth predicate” for the set theory T h 1 # . By Theorem 3.5.2 one obtains a contradiction.

ii) Notice that by the properties of the extension T h , N s t # of the theory Z F C + M s t Z F C = T h 1, s t # it follows that

M s t Z F C Φ T h , s t # Φ . (132)

Therefore formula (128) gives generalized “truth predicate” for the set theory T h 1, s t # . By Theorem 3.5.2 one obtains a contradiction.

iii) Notice that by the properties of the extension T h , N s t # of the theory Z F C + M N s t Z F C = T h 1, s t # it follows that

M N s t Z F C Φ T h , N s t # Φ . (133)

Therefore (129) gives generalized “truth predicate” for the set theory T h 1, N s t # . By Theorem 3.5.2 one obtains a contradiction.

3.6. Avoiding the Contradictions from Set Theory Z F C ¯ 2 H s , Z F C s t and Set Theory Z F C N s t 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 n + 1 objects are sets of type n objects; sets of type n have members of type n 1 . Objects connected by identity must have the same type. The following two atomic formulas succinctly describe the typing rules: x n = y n and x n y n + 1 .

The axioms of TST are:

Extensionality: sets of the same (positive) type with the same members are equal;

Axiom schema of comprehension:

If Φ ( x n ) is a formula, then the set { x n | Φ ( x n ) } n + 1 exists i.e., given any formula Φ ( x n ) , the formula

A n + 1 x n [ x n A n + 1 Φ ( x n ) ] (134)

is an axiom where A n + 1 represents the set { x n | Φ ( x n ) } n + 1 and is not free in Φ ( x n ) .

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 x n x n 1 x 3 x 2 x 1 . It avoids Russell’s paradox by only allowing stratifiable formulas in the axiom of comprehension. For instance x y is a stratifiable formula, but x x 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 x y appearing in Φ satisfies σ ( x ) + 1 = σ ( y ) and any atomic formula x = y appearing in Φ satisfies σ ( x ) = σ ( y ) .

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:

{ x | Φ s } exists for each stratified formula Φ s .

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 { x | x x } is not an axiom of NF, because x x cannot be stratified.

3.6.2. SET Theory Z F C ¯ 2 H s , Z F C s t and Set Theory Z F C N s t 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 Z F C s t will also fall inside a set.

Stratified Axiom schema of replacement:

Let Φ s ( x , y , w 1 , w 2 , , w n ) be any stratified formula in the language of Z F C s t whose free variables are among x , y , A , w 1 , w 2 , , w n , so that in particular B is not free in Φ s . Then

A w 1 w 2 w n [ x ( x A ! y Φ s ( x , y , w 1 , w 2 , , w n ) ) B x ( x A y ( y B Φ s ( x , y , w 1 , w 2 , , w n ) ) ) ] , (135)

i.e., if the relation Φ s ( x , y , ) represents a definable function f, A represents its domain, and f ( x ) is a set for every x A , then the range of f is a subset of some set B.

Stratified Axiom schema of separation:

Let Φ s ( x , w 1 , w 2 , , w n ) be any stratified formula in the language of Z F C s t whose free variables are among x , A , w 1 , w 2 , , w n , so that in particular B is not free in Φ s . Then

w 1 w 2 w n A B x [ x B ( x A Φ s ( x , w 1 , w 2 , , w n ) ) ] , (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 2 H s , s t and N s t is impossible, because x x 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 Z 2 H s with Henkin semantics. Notice that any standard model M s t Z 2 H s of second-order arithmetic Z 2 H s 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 D 2 of subsets of , which is the range of the set variables. Omitting D produces a model of the first order Peano arithmetic.

When D = 2 is the full power set of , the model M s t Z 2 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 Z 2 f s s 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 T h 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 S and that T h contains S . We assume throughout this paper that formal second order theory S has an ω-model M ω S . The sense in which S is contained in T h is better exemplified than explained: if S is a formal system of a second order arithmetic Z 2 H s and T h is, say, Z F C 2 H s , then T h contains S in the sense that there is a well-known embedding, or interpretation, of S in T h . Since encoding is to take place in M ω S , 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 0 ¯ , 1 ¯ , ). S will also have certain function symbols to be described shortly. To each formula, Φ , of the language of T h is assigned a closed term, [ Φ ] c , called the code of Φ [19] . We note that if Φ ( x ) is a formula with free variable x, then [ Φ ( x ) ] c is a closed term encoding the formula Φ ( x ) with x viewed as a syntactic object and not as a parameter. Corresponding to the logical connectives and quantifiers are the function symbols, n e g ( ) , i m p ( ) , etc., such that for all first order formulae Φ , Ψ : S n e g ( [ Φ ] c ) = [ ¬ Φ ] c , S i m p ( [ Φ ] c , [ Ψ ] c ) = [ Φ Ψ ] c etc. Of particular importance is the substitution operator, represented by the function symbol s u b ( , ) . For formulae Φ ( x ) , terms t with codes [ t ] c :

S s u b ( [ Φ ( x ) ] c , [ t ] c ) = [ Φ ( t ) ] c . (137)

It well known that one can also encode derivations and have a binary relation P r o v T h ( x , y ) (read “x proves y” or “x is a proof of y”) such that for closed t 1 , t 2 : S P r o v T h ( t 1 , t 2 ) iff t 1 is the code of a derivation in T h of the formula with code t 2 . It follows that

T h Φ iff S P r o v T h ( t , [ Φ ] c ) (138)

for some closed term t. Thus we can define

P r T h ( y ) x P r o v T h ( x , y ) , (139)

and therefore we obtain a predicate asserting provability.

Remark 4.1.2. I) We note that it is not always the case that:

T h Φ iff S P r T h ( [ Φ ] c ) , (140)

unless S is fairly sound, e.g. this is the case when S and T h replaced by S ω = S M ω T h and T h ω = T h M ω T h correspondingly (see Designation 4.1.1 below).

II) Notice that it is always the case that:

T h ω Φ ω iff S ω P r T h ω ( [ Φ ω ] c ) , (141)

i.e. that is the case when predicate P r T h ω ( y ) , y M ω T h :

P r T h ω ( y ) x ( x M ω T h ) P r o v T h ω ( x , y ) (142)

really asserting provability.

It well known that the above encoding can be carried out in such a way that the following important conditions D 1, D 2 and D 3 are meeting for all sentences:

D 1. T h Φ implies S T h P r T h ( [ Φ ] c ) , D 2. S P r T h ( [ Φ ] c ) P r T h ( [ P r T h ( [ Φ ] c ) ] c ) , D 3. S P r T h ( [ Φ ] c ) P r T h ( [ Φ Ψ ] c ) P r T h ( [ Ψ ] c ) . (143)

Conditions D 1, D 2 and D 3 are called the Derivability Conditions.

Remark 4.1.3. From (141)-(142) it follows that

D 4. T h ω Φ iff S ω P r T h ω ( [ Φ ω ] c ) , D 5. S ω P r T h ω ( [ Φ ω ] c ) P r T h ω ( [ P r T h ω ( [ Φ ω ] c ) ] c ) , D 6. S ω P r T h ω ( [ Φ ω ] c ) P r T h ω ( [ Φ ω Ψ ] c ) P r T h ω ( [ Ψ ω ] c ) . (144)

Conditions D 4, D 5 and D 6 are called a Strong Derivability Conditions.

Definition 4.1.1. Let Φ be well formed formula (wff) of T h . Then wff Φ is called T h -sentence iff it has no free variables.

Designation 4.1.1 i) Assume that a theory T h has an ω-model M ω T h and Φ

is a T h -sentence, then: Φ M ω T h Φ M ω T h (we will write Φ ω instead Φ M ω T h )

is a T h -sentence Φ with all quantifiers relativized to ω-model M ω T h [11] and T h ω T h M ω T h is a theory T h relativized to model M ω T h , i.e., any T h ω -sentence has the form Φ ω for some T h -sentence Φ .

ii) Assume that a theory T h has a standard model M s t T h and Φ is a T h -sentence, then:

Φ M s t T h Φ M s t T h (we will write Φ s t instead Φ M s t T h ) is a T h -sentence with

all quantifiers relativized to a standard model M s t T h , and T h s t T h M s t T h is a theory T h relativized to model M s t T h , i.e., any T h s t -sentence has a form Φ s t for some T h -sentence Φ .

iii) Assume that a theory T h has a non-standard model M N s t T h and Φ is a T h -sentence, then:

Φ M N s t T h Φ M N s t T h (we will write Φ N s t instead Φ M N s t T h ) is a T h -sentence with

all quantifiers relativized to non-standard model M N s t T h , and T h N s t T h M N s t T h is a theory T h relativized to model M N s t T h , i.e., any T h N s t -sentence has a form Φ N s t for some T h -sentence Φ .

iv) Assume that a theory T h has a model M = M T h and Φ is a T h -sentence, then: Φ M T h is a T h -sentence with all quantifiers relativized to model M T h , and T h M is a theory T h relativized to model M T h , i.e. any T h M -sentence has a form Φ M for some T h -sentence Φ .

Designation 4.1.2. i) Assume that a theory T h with a language L has an ω-model M ω T h and there exists T h -sentence S L such that: a) S L expressible by language L and

b) S L asserts that T h has a model M ω T h ; we denote such T h -sentence S L by C o n ( T h ; M ω T h ) .

ii) Assume that a theory T h with a language L has a non-standard model M N s t T h and there exists T h -sentence S L such that: a) S L expressible by language L and

b) S L asserts that T h has a non-standard model M N s t T h ; we denote such T h -sentence S L by C o n ( T h ; M N s t T h ) .

iii) Assume that a theory T h with a language L has an model M T h and there exists T h -sentence S L such that: a) S L expressible by language L and

b) S L asserts that T h has a model M T h ; we denote such T h -sentence S L by C o n ( T h ; M T h ) .

Remark 4.1.4. We emphasize that: i) it is well known that there exists a ZFC-sentence C o n ( Z F C ; M Z F C ) [8] ,

ii) obviously there exists a Z F C 2 H s -sentence C o n ( Z F C 2 H s ; M Z F C 2 H s ) and there exists a Z 2 H s -sentence C o n ( Z 2 H s ; M Z 2 H s ) .

Designation 4.1.3. Assume that C o n ( T h ; M T h ) . Let C o n ˜ ( T h ; M T h ) be the formula:

C o n ˜ ( T h ; M T h ) t 1 ( t 1 M ω T h ) t 1 ( t 1 M ω T h ) t 2 ( t 2 M ω T h ) t 2 ( t 2 M ω T h ) ¬ [ P r o v T h ( t 1 , [ Φ ] c ) P r o v T h ( t 2 , n e g ( [ Φ ] c ) ) ] , where t 1 = [ Φ ] c , t 2 = n e g ( [ Φ ] c ) or C o n ˜ ( T h ; M ω T h ) Φ t 1 ( t 1 M ω T h ) t 2 ( t 2 M ω T h ) ¬ [ P r o v T h ( t 1 , [ Φ ] c ) P r o v T h ( t 2 , n e g ( [ Φ ] c ) ) ] (145)

and where t 1 , t 1 , t 2 , t 2 is a closed term.

Lemma 4.1.1. I) Assume that: i) a theory T h is recursively axiomatizable.

ii) C o n ( T h ; M T h ) ,

iii) M T h C o n ˜ ( T h ; M T h ) and

iv) T h P r T h ( [ Φ ] c ) , where Φ is a closed formula.

Then T h P r T h ( [ ¬ Φ ] c ) .

II) Assume that: i) a theory T h is recursively axiomatizable.

ii) C o n ( T h ; M ω T h )

iii) M ω T h C o n ˜ ( T h ; M T h ) and

iv) T h ω P r T h ω ( [ Φ ω ] c ) , where Φ ω is a closed formula.

Then T h ω P r T h ω ( [ ¬ Φ ω ] c ) .

Proof. I) Let C o n ˜ T h ( Φ ; M T h ) be the formula:

C o n ˜ ( Φ ; M T h ) t 1 ( t 1 M T h ) t 2 ( t 2 M T h ) ¬ [ P r o v T h ( t 1 , [ Φ ] c ) P r o v T h ( t 2 , n e g ( [ Φ ] c ) ) ] , i .e . t 1 ( t 1 M T h ) t 2 ( t 2 M T h ) ¬ [ P r o v T h ( t 1 , [ Φ ] c ) P r o v T h ( t 2 , n e g ( [ Φ ] c ) ) ] { ¬ t 1 ( t 1 M T h ) ¬ t 2 ( t 2 M T h ) [ P r o v T h ( t 1 , [ Φ ] c ) P r o v T h ( t 2 , n e g ( [ Φ ] c ) ) ] } . (146)

where t 1 , t 2 is a closed term. From (i)-(ii) it follows that theory T h + C o n ˜ ( T h ; M T h ) is consistent. We note that T h + C o n ˜ ( T h ; M T h ) C o n ˜ T h ( Φ ; M T h ) for any closed Φ . Suppose that T h P r T h ( [ ¬ Φ ] c ) , then (iii) gives

T h P r T h ( [ Φ ] c ) P r T h ( [ ¬ Φ ] c ) . (147)

From (139) and (147) we obtain

t 1 t 2 [ P r o v T h ( t 1 , [ Φ ] c ) P r o v T h ( t 2 , n e g ( [ Φ ] c ) ) ] . (148)

But the formula (146) contradicts the formula (148). Therefore T h P r T h ( [ ¬ Φ ] c ) .

Remark 4.1.5. In additional note that under the following conditions:

i) a theory T h is recursively axiomatizable,

ii) C o n ( T h ; M s t T h ) , and

iii) M s t T h C o n ˜ ( T h ; M s t T h ) predicate P r T h ( [ Ψ ] c ) really asserts provability, one obtains

T h Φ ¬ Φ (149)

and therefore by reductio ad absurdum again one obtains T h P r T h ( [ ¬ Φ ] c ) .

II) Let C o n ˜ T h ( Φ ; M ω T h ) be the formula:

C o n ˜ T h ( Φ ; M ω T h ) t 1 ( t 1 M ω T h ) t 2 ( t 2 M ω T h ) ¬ [ P r o v T h ( t 1 , [ Φ ] c ) P r o v T h ( t 2 , n e g ( [ Φ ] c ) ) ] , i . e . t 1 ( t 1 M ω T h ) t 2 ( t 2 M ω T h ) ¬ [ P r o v T h ( t 1 , [ Φ ] c ) P r o v T h ( t 2 , n e g ( [ Φ ] c ) ) ] { ¬ t 1 ( t 1 M ω T h ) ¬ t 2 ( t 2 M ω T h ) [ P r o v T h ( t 1 , [ Φ ] c ) P r o v T h ( t 2 , n e g ( [ Φ ] c ) ) ] } . (150)

This case is trivial because formula P r T h ω ( [ ¬ Φ ] c ) by the Strong Derivability Condition D 4 , see formulae (144), really asserts provability of the T h ω -sentence ¬ Φ ω . But this is a contradiction.

Lemma 4.1.2. I) Assume that: i) a theory T h is recursively axiomatizable.

ii) C o n ( T h ; M T h ) ,

iii) M T h C o n ˜ ( T h ) and

iv) T h P r T h ( [ ¬ Φ ] c ) , where Φ is a closed formula. Then T h P r T h ( [ Φ ] c ) ,

II) Assume that: i) a theory T h is recursively axiomatizable.

ii) C o n ( T h ; M ω T h )

iii) M ω T h C o n ˜ ( T h ) and

iv) T h ω P r T h ω ( [ ¬ Φ ω ] c ) ,

where Φ ω is a closed formula. Then T h ω P r T h ω ( [ Φ ω ] c ) .

Proof. Similarly as Lemma 4.1.1 above.

Example 4.1.1. i) Let T h = P A be Peano arithmetic and Φ 0 = 1 .

Assume that: i) C o n ( P A ; M P A )

ii) M P A C o n ˜ ( P A ; M P A ) where M P A is a model of P A .

Then obviously P A P r P A ( 0 1 ) since P A 0 1 and therefore by Lemma 4.1.1 P A P r P A ( 0 = 1 ) .

ii) Let C o n ( P A ; M P A ) , M P A ¬ C o n ˜ ( P A ; M P A ) and let P A be a theory P A = P A + ¬ C o n ˜ ( P A ; M P A ) and Φ 0 = 1 . Then obviously

P A [ P r P A ( 0 1 ) ] [ P r P A ( 0 = 1 ) ] . (151)

and therefore

P A P r P A ( 0 1 ) , (152)

and

P A P r P A ( 0 = 1 ) . (153)

However by Löbs theorem

P A