There is no object named 'infinity'. Rather, there is the property of being infinite.

There is not a "minus" operation involving infinite cardinals in the same way as with integers.

Rather:

For any set x, there is its cardinality called card(x).

Now let '\' stand for the complement operation:

x\y = {p | p in x and p not in y}

If x is infinite and y is finite then

card(x) = card(x\y)

That is meaningful and correct.

Saying x-y is not even meaningful.

There is no definition of cardinal subtraction with infinite cardinals in a way such as with the integers.

Usually, in mathematics we do not use 'infinity' as a noun. There is not an object that we call 'infinity'.*

Rather, we use the adjective 'is infinite'.

To define 'is infinite' we may:

First, define 'finite'. That can be done in various ways. One way is to define:

x is an ordinal if and only if (x is membership-transitive and x is well ordered by membership)

n is a natural number if and only if (n is an ordinal and n is well ordered by the inverse of membership)

x is finite if and only if there is a natural number n and a one-to-one function from n onto x

x is infinite if and only if x is not finite.

/

In mathematics, 'equinumerous' is defined:

x is equinumerous with y if and only if there is a one-to-one function from x onto y.

That corresponds to the utterly basic intuition that sets have the same number of elements if and only if they can be put in one-to-one correspondence. For example, proverbially, there are the same number of sheep in the flock as there are stones in the pile if and only if for each stone there is a corresponding sheep and no stone corresponds to more than one sheep.

Set theory uses this definition for both finite and infinite sets.

Given this definition, we have prove that the set of natural numbers is not equinumerous with the set of real numbers.

Now, if one has different intuitions about equinumerosity, then one may imagine set theory not to use the word 'equinumerous' but instead 'zequinumerous' or whatever, for mathematics does not depend on the words it happens to use but rather on the formal relations, no matter what natural language words we use to nickname those relations.

/

* But there also are the points of 'infinity' and 'negative infinity' on the extended real line. But these are not indications of CARDINALITY. They regard two elements in addition to the set of real numbers and an ordering that such that infinity is greater than every real and greater than negative infinity, and negative infinity is less than every real and less than infinity. The points themselves may be of any cardinality.

* We also use phrasing and/or the lemniscate, for example, "as n goes to infinity". But this is a facon de parler that can be explicated in various ways such as "n rangers over the natural numbers" or "the domain of the function is the set of natural numbers".

NOTE: Earlier in this thread, with a different username, I used the word 'onto' not intending its mathematical meaning of a function onto a set, but rather to mean 'in and of itself'. I have later found out that it is not recognized English to use the word 'onto' that way, so I should have said 'in and of itself'. That caused confusion. I regret that.

Where I said things like 'EyAx xey' is not inconsistent onto itself', I meant 'EyAx xey' is not inconsistent in and of itself' (though it is inconsistent with the axiom schema of separation).

It was claimed that

R = {x | x not-e x}

has not been explicated.

'{ x | }' is the abstraction operator. It is variable binding notation that takes any formula P and names a set {x | P(x)} that is the set of all and only the x such that P(x).

However, proper use of the abstraction operator requires first proving that indeed there is such a set for a given property P.

And we prove that for the property P, where P(x) iff x is not a member of x, there is no such set of all and only the x such that x is not a member of x.

There are different ways of handling such situations (Russellian vs Fregan, e.g.).

In ordinary discourse, mathematicians would say that

R = {x | x not-e x} is an "illegal" definition, as there is no such object described by the right side of the equation.

With the Russell treatment, names with abstraction operators are regarding not standalone but rather contextually, so that we evaluate the truth value or satisfiability of formulas without regarding the abstraction operator expression as naming but rather as a nested component indicating an assertion about existence of an object having certain properties.

With the Fregean treatment, if we have at least one constant symbol, then we may set all non-referring abstraction operator expressions to that constant.

Again, what Russell's paradox shows is that by pure logic:

There is no set y whose members are all and only the sets that are not members of themselves.

Then, from Russell's paradox, along with the subset schema we show:

There is no set z that has every set as a member.

and

There is no set such z such that for every x, if x is not a member of itself then x is a member of z.

An argument was made that it is contradictory for a set to have as members all and only the sets that are not members of itself (correct) but that it is not contradictory for a set to have as members all the sets that are not members of themselves along with other set (incorrect in context of set theory).

In set theory, from any set, we can take subsets defined by any property.

So, let B be a set that has as members all the sets that are not members of themselves plus some other members. Now take the subset of B that has only the sets that are not members of themselves, and we are back to the contradiction.

So it is a theorem of pure logic:

There is no y such that for all x, x is a member of y iff x is not a member of x.

And it is a theorem from the subset axiom schema:

There is no y such that for all x, if x is not a member of x, then x is a member of y.

/

Moreover, given the subset axiom schema, it is a theorem:

There is no z such that for all x, x is a member of z.

/

Again, one may wish to conceive of mathematics and sets in some other way than as usual in mathematics, but then we may ask, "What are your primitives, your rules of inference and your axioms to express your alternative conception and to prove things about it?"

To properly discuss 'lists' in the context of set theory, we need to have a formalization of the notion of lists:

At least personally I would take 'list' to mean a function whose domain is either a natural number or the set of natural numbers.

A finite list has a natural number as its domain (recall that every natural number is the set of its predecessor natural numbers).

A denumerable list has the set of natural number as its domain.

I guess one might say that any ordinal could be the domain of a list, including countable ordinals other than the set of natural numbers or even uncountable ordinals.

/

Then, what would be involved here is not lists being members of lists, but rather lists being in the RANGE of lists. So it is not "a list being a member of itself" but rather a list being in the RANGE of itself. That is, to say "the list lists itself" doesn't mean "the list is as a member of itself" but rather "the list is in the RANGE of itself".

For example, If I have a list L of three lists, then it looks like this

L = {<1 List-a> <2 List-b> <3 List-c>}

List-a, List-b, and List-C are not in L. Rather they are in the RANGE of L.

/

In any case, there is no known contradiction in set theory arising from questions of lists

Just to be clear, neither Regularity nor Pairing are needed to prove:

There is no y such that for all x, x is a member of y iff x is not a member of x

nor

There is no z such that for all x, x is a member of z.

Regarding a notion that ZF is "inadequate/incomplete".

If ZF is consistent then ZF is incomplete, in the sense that there are sentences in the language of ZF such that neither they nor their negations are theorems of ZF. But any consistent, recursively axiomatized theory that expresses a certain amount of arithmetic is incomplete.

'inadequate' is not defined here.

/

Regarding the claim that set theory is contradictory.

A contradiction is a sentence P along with not-P.

There is no known proof of a contradiction in set theory.

One may find that the theorems of set theory go against one's own intuitions or conceptions about mathematics, but that does not establish a claim that the theory is contradictory, since 'contradictory' doesn't mean "Goes against the way I conceive things" but rather means "Proves both a sentence P and not-P".)

There are too many confusions in this thread. This post can be used for correct and definite formulations. (For more, see https://plato.stanford.edu/entries/russell-paradox)

Below are three theorems, using only intuitionistic (thus classical too) rules of inference, applied to certain axioms:

One may wish to conceive mathematics in some other way, but if the discussion pertains to the rules of inference and axioms of ordinary mathematics, then below are English renditions of formalizations that have formalized proofs that are are machine-checkable from the stated axioms and rules of inference; that cannot be rationally disputed.

(1) There is no y such that for all x, x is a member of y if and only if x is not a member of itself.

Proof is by pure logic alone, no set theory need be invoked, as it is merely a case of:

There is no relation M such that there is a y such that for all x, x bears M to y if and only if x does not bear M to x.

(2) There exists a unique y such that for all x, x is member of y if and only if x is a member of x. That y is 0 (the empty set).

Proof uses the axiom of regularity, the schema of separation for existence, and the axiom of extensionality for uniqueness.

(3) There is no z such that for all x, x is a member of z.

Proof uses (1) and the axiom schema of separation.

EXPLANATIONS:

'The set of all sets that are not members of themselves' refers to a set, call it 'R', such that for any set x, x is a member of R if and only if x is not a member of x.

Russell's paradox is this contradiction:

The set of all sets that are not members of themselves is a member of itself, and the set of all sets that are not members of themselves is not a member of itself.

A proof* is obvious:

Suppose there is a set R such that for all sets x, x is a member of R if and only if x is not a member of x.

So substituting R for x, we have:

R is a member of R if and only if R is not a member of R.

Suppose R is a member of R. So R is not a member of R. So both R is a member of R and R is not a member of R.

Suppose R is not a member of R. So R is a member of R. So both R is member or R and R is not a member of R.

But either R is member of R or R is not a member of R. And, in either case, as above, R is a member or R and R is not a member of R. So R is a member of R and R is not a member of R. QED.

/

So, the supposition 'There is a set R such that for all sets x, x is a member of R if and only if x is not a member of x' yields a contradiction. So we infer the negation of that supposition, viz. 'There is no set R such that for any set x, x is a member of R is and only if x is not a member of x'.

But the earliest version of set theory had an axiom schema we all 'unrestricted comprehension', which is (read 'P(x)' as 'x has property P'):

For any property P that we can formulate, we have the axiom:

There is a set y such that for all sets x, x is a member of y if and only if x has property P.

Then let P(x) be 'x is not a member of x'.

Then we have:

There is a set y such that for all sets x, x is a member of y if and only if x is not a member of x.

But above (using 'R' instead of 'y') we proved that there is no such set y.

So the axiom schema of unrestricted comprehension yields a contradiction.

/

So set theory was reformulated to not have the unrestricted axiom axiom schema of comprehension but instead a restricted axiom schema (called the 'separation schema' or the 'specification schema' or the 'subset schema'):

For any property P that we can forumulate, we have the axiom:

For all sets z, there is a set y such that for all sets x, x is a member of y if and only if (x is a member of z and P(x)).

And to that schema we add the axioms: Extensionality, Pairing, Union, Power Set, Infinity and Regularity. (This is known as 'Z set theory').

In Z set theory (and in the extended theories, ZF, ZFC, etc.), there is no known proof of 'There is a set R such that for all sets x, x is a member of R if and only if x is not a member of x', and no known proof of any contradiction.

Moreover, in Z set theory there is a proof of 'There is not a set R such that for all sets x, x is a member of Y if and only if x is not a member of x'. It's just Russell's argument again:

Suppose there is a set R such that for all sets x, x is a member of R if and only if x is not a member of x.

So substituting R for x, we have:

R is a member of R if and only if R is not a member of R.

Suppose R is a member of R, so R is not a member of R. So both R is a member of R and R is not a member of R.

Suppose R is not a member of R, so R is a member of R. So both R is member or R and R is not a member of R.

But either R is member of R or R is not a member of R. And, in either case, as above, R is a member or R and R is not a member of R. So R is a member of R and R is not a member of R.

NOTICE that that argument didn't even need any axioms of set theory anyway. Moreover, we don't even have to mention the notion of 'set' nor 'member of'. We have (read 'M(x y) as 'x bears property M to y'; with one instance being 'x bears the property of being a member of y'):

There is no 2-place relation T such that there is a y such that for all x, T(x y) if and only if it is not the case that T(x x). I.e., 'There is no 2-place relation T such that there is a y such that for all x, x bears T to y if and only if x does not bear T to x.'

It's purely logical, not needing to mention sets nor membership:

Suppose there is a T such that there is a y such that for all x, T(x y) if and only if it is not the case that T(x x).

So, substituting y for x, we have T(y y) if and only if it is not the case that T(y y). And, as seen above, we then derive a contradiction.

Indeed, this may be seen as the lesson of the Barber Paradox in its purest form (don't even have to mention 'village' or 'barber'). There, instead of the 2-place property 'is a member of' we use the property 'shaves':

There is no y such that for all x, y shaves x if and only if x does not shave x.

/

Moreover, even in set theory, we don't have to mention the term 'set'. Rather, the only primitive is 'member of'. Indeed, though most people don't bother to do state these trivial steps, we can actually define 'set' ('iff' stands for 'if and only if'):

First with the axiom of extensionality, we define a unique y such that for all x, x is not a member of y. We dub that unique y as '0':

Axiom of extensionality:

For all x and y, if for all z, z is a member of x iff z is a member of y, then x equals y.

Also, from the logic of identity, we already have:

For all x and y, if x equals y, then for all z, z is a member of x iff z is a member of y.

So putting that together with the axiom of extensionality we have:

For all x and y, x equals y iff for all z, z is a member of x iff z is a member of y.

Then:

From the schema of separation we have:

For all z, there is a y, such that for all x, x is a member of y iff (x is a member of z and (x is a member of x and x is not a member of x)).

Let z be any object. (There is at least one object, as provided by the logic itself).

So there is a y, such that for all x, x is a member of y iff (x is a member of z and (x is a member of x and x is not a member of x)).

By logic, we can reduce that to:

There is a y, such that for all x, x is a member of y iff (x is a member of x and x is not a member of x)).

By the axiom of extensionality, such a y is unique, since there is no x such that x is a member of x and x is not a member of x.

Then:

df. 0 is the unique y such that for all x, x is a member of y iff (x is a member of x and x is not a member of x).

df. x is a class iff there is a y such that y is a member of x or x is 0.

df. x is a set iff x is a class and there is a z such that x is a member of z.

So, since the context here is set theory, we can drop mentioning 'set' throughout. Though, we use the nickname for 0 as "the empty set".

/

Next, using only the schema of separation we prove that there is no z such that for all x, x is a member of z:

Suppose there is a z such that for all x, x is a member of z:

So, by the schema of separation:

There is a y such that for all sets x, x is a member of y iff (x is a member of z and x is not a member of x).

With some routine logic steps, we get:

There is a y such that for x, x is a member of y iff x is not a member of x.

Thus, there is no z such that for all x, x is a member of z.

NOTICE, we need no invoke extensionality nor regularity, only an instance of the axiom schema of separation.


/

* That proof uses excluded middle, but we can prove it intutionistically too:

Instead of proving that both R is a member of R and R is not a member of R, we prove a different contradiction, viz. that both R is not a member of R and it is not the case that R is not a member of R:

Suppose there is a set R such that for any set x, x is a member of R if and only if x is not a member of x.

So substituting R for x, we have:

R is a member of R if and only if R is not a member of R.

If R is a member of R then both R is a member of R and R is not a member of R. But it is not the case that both R is a member of R and R is not a member of R. So, by modus tollens, R is not a member of R.

If R is not a member of R then both R is a member of R and R is not a member of R. But it is not the case that both R is a member of R and R is not a member of R. So, by modus tollens, it is not the case that R is not a member of R.

But both 'If R is a member of R then R is not a member of R' and 'If R is not a member of R then R is a member of R'. So both R is not a member of R and it is not the case that R is not a member of R. QED.

It is recommended that anyone truly interested in the subject may read a book in mathematical logic (for example, Enderton's 'A Mathematical Introduction To Logic'), which is the remedy for continual exposure on Internet forums to the bizarre misrepresentations of the subject by self-misinformed, confused and dogmatically prolific Internet cranks.

I wrote here an outline of a proof of Tarski's theorem. But it incorrectly glossed over crucial details. So I have deleted it here.

For the fourth time: The incompleteness theorem pertains only to recursively axiomatizable theories.

A set of statements that includes a proper subset that is a recursive set is not thereby itself a recursive set. And it is howlingly ridiculous to cite some set of statements that includes all recursive axiomatizations, such such a set is patently inconsistent. Claims about "every recursively axiomatizable theory" in a larger theory then with implications for incompleteness is howlingly ridiculous ignorance.

But as a free speech hawk, I do applaud The Philosophy Forum for not ejecting such patently misinformational postings even though that restraint comes at the price of contributing that much further to the degradation of sincere discussion on such topics.

Tarski says no such thing as claimed two posts above.

And, for the third time: The incompleteness theorem pertains only to recursively axiomatizable theories.

If I don't comment to further replies, it's because meaningful discussion is not possible, and engagement is a waste of time, with a person who refuses to properly inform himself on the subject matter.

As I said, the incompleteness theorem pertains only to recursively axiomatizable theories. Montague grammar does not in and of itself make a general set of statements, even ones regarded as formalized by Montague grammar, a recursively axiomatizable theory. Understanding of the incompleteness theorem may be obtained by study of a textbook in mathematical logic.

Tarski's proof makes no false assumptions, no matter whatever incoherent ersatz pseudo formulations a crank on the Internet wishes to cook up.

But Godel was speaking of a small finite collection of axioms — jgill

Not a finite set of axioms, rather a countably infinite set of axioms. However, indeed, not an uncountable set of axioms as was incorrectly claimed by a poster earlier in this thread.

The incompleteness theorem applies to formal theories, not to any set that includes natural language expressions. Moreover, the incompleteness theorem applies only to formal theories of a certain kind.

And subsequent discussion has been confused on other crucial points.

In the following, the context is formal theories.

/

A theory is a set of sentences closed under provability.

A theory has a language. For any language L, there are models for L.

For any model M for a language L, every sentence in L is either true or false, and not both, in M.

A model M for the language L for a theory T is a model of T if and only if every theorem of T is true in M.

A theory T is consistent if and only if there is no sentence S in the language for T such that both S and the negation of S are theorems of T.

A theory T is inconsistent if and only if T is not consistent.

A theory T is consistent if and only if there is an M that is a model of T.

A theory T is inconsistent if and only if there is not M that is a model of T.

A theory T is complete if and only if, for every sentence S in the language L for T, either S is a theorem of T or the negation of S is a theorem of T.

A theory T is incomplete if and only if T is not complete.

The Godel-Rosser incompleteness theorem is: If a theory T is recursively axiomatizable, sufficiently arithmetic, and consistent, then T is incomplete.

A formula is valid if and only if it is satisfied by all models and assignments for the variables.

The Godel completeness theorem (not to be confused with the incompleteness theorem) is that if a formula P is valid then P is derivable in the pure first order predicate calculus.

The soundness theorem is that if a formula P is derivable in the pure first order predicate calculus then P is valid.

There is a particular model of PA (first order Peano arithmetic) that we call "the standard model of arithmetic". Since there are sentences in the language for PA such that neither the sentence nor its negation is a theorem of PA, there are sentences that are true in the standard model that are not theorems of PA. Moreover, the particular sentence G (that we call "the Godel sentence") is proven outside of PA to be true in the standard model.

/

No recursively axiomatizable theory has an uncountable number of axioms. Theories with an uncountable number of axioms are not a consideration regarding the incompleteness theorem. Indeed, a language for a formal theory has only a countable number of symbols, thus only a countable number of expressions, thus only a countable number of formulas, thus only a countable number of sentences, thus there can be only a countable number of axioms in any axiomatization of the theory.

/

For any model M, there is the theory T whose theorems are all and only the sentences true in M. It was Tarski who proved "the undefinability of truth" theorem, which says that the set of sentences true in the standard model for the language of arithmetic is not definable in the language of arithmetic. For example, there is no formula in the language for PA that is true of all and only the Godel numbers of sentences true in the standard model of arithmetic.

/

The incompleteness theorem may be proved finitistically and contructivistically. While the proof is complicated, its methods are reducible to the basic reasoning of arithmetic by finite operations on single, discrete token objects. Thus, if the proof is considered dubious, then so is the basic reasoning of arithmetic on single, discrete token objects, which is to say that if the proof is considered dubious, then even the most basic arithmetic should be considered dubious.

/

To reiterate regarding this thread:

(1) The incompleteness theorem does not pertain to any set that includes informal expressions. And the incompleteness theorem does not pertain to sets of expressions other than those of recursively axiomatized, sufficiently arithmetic, and consistent theories.

(2) Sentences are not true or false in theories or systems. Rather sentences are true or false in models.

(3) No recursively axiomatizable theory has an uncountable number of axioms.

R is mostly a black and seamless sea in the darkness. — plaque flag

I don't have anything immediate to say about people's subjective impressions of mathematics.

we can enumerate Q and all finite sequences in Q. — plaque flag

Q is enumerable and so is the set of finite sequences of members of Q. The set of infinite sequences of members of Q and R are not enumerable. Okay, some things are enumerable and others aren't.

There's a kind of mystic fog that hangs around it. — plaque flag

I don't see it as mystic or foggy.

But what is an example of G for some system T? — FrancisRay

The one constructed in the proof. When you read the proof, you see the G that is constructed.

I just don;t see it's significance beyond mathematics. — FrancisRay

Of course you're free to investigate whatever you like. On the other hand, for example, the undecidability of the halting problem, which is another way of couching incompleteness, has implications for actual computing.

It ought to mean that metaphysics cannot be completed — FrancisRay

Metaphysics is not usually formulated as a formal system. On the other hand, if you state a formal system, we can see whether it has the attributes to which the incompleteness theorem applies.

My view is that if mathematicians are unable to work out and clarify the implications of incompleteness for philosophy then philosophers can ignore it — FrancisRay

Of course. Anyone, including advanced mathematicians, may ignore it and still work productively.

I wish a mathematician would tell me but they don't seem to know either/ . — FrancisRay

Read 'Godel's Theorem' by Torkel Franzen. He discusses your question in layman's terms.

Thanks, jgill. Good to see you too. Probably only a brief stopover for me though. My lifecoach pandemic response guru (just kidding) tells me that my path to cyberlife pandemic era self-actualization (just kidding) is better charted away from forums.

Thank you for that.

I am not an expert, but sometimes I have good (rigorous) understanding of some of the basics, though, over time I've become rusty on some of the more advanced details.

The reals are constructed in set theory usually in one of two ways: As equivalence classes of Cauchy sequences or as Dedekind cuts. Also, there is a way to have reals as actual individual denumerable sequences, but I don't know the details of that, and it is not a common approach.

What did you have in mind about the reals?

it must be frustrating trying to talk to people who can't follow the calculations. — FrancisRay

To be clear, the problem is not people who can't understand the mathematics, but those (not necessarily ones lately in this thread) who refuse (through years and years of their ignorant, confused, and arrogantly prolific disinformational posting) to even read the first page of a textbook on the subject. Such people are a bane and toxic to knowledge and understanding.

The basic idea of what the theorem says can be stated roughly in common language:

If T is a consistent theory that expresses basic arithmetic, then there are sentences in the language for T such that neither they nor their negations are provable in T; moreover, either such a sentence is true or its negation is true, so there are true sentences not provable in T.

The basic idea of the proof is not as easy to say in common language, but we have:

For a consistent, arithmetically expressive theory T, we construct a sentence G in the language of T such that G is true if and only if G is not provable in T. Then we prove that G is not provable in T. But this cannot really be understood and be convincing if one doesn't study the actual mathematics of it; otherwise it can seem, at such a roughly simplified level, as nonsense or illegitimate trickery, though it is not, as would be understood when seeing the actual mathematics, not the oversimplified common summary.

/

Mathematically, there is no legitimate debate about the theorem. It is as rock solid a mathematical proof as any mathematical proof. It can be reduced to methods of finitistic constructive arithmetic.

In the philosophy of mathematics and philosophy of computability, there are different diverging perspectives about the theorem.

In epistemology and metaphysics, even wider divergence about the theorem.

But again, no matter the philosophical responses, the theorem is rock solid mathematics.

In any case, one cannot reasonably philosophize about the theorem without actually understanding it mathematically as a starting point. I wouldn't make claims about the philosophy of mind based on studies about the electrical chemistry of the human brain without first really understanding those studies. Should be the same with metaphysics referring to mathematics.

knowing a consistent system is incomplete — jgill

Just to be clear, some consistent systems are incomplete while others are complete.

How did Godel make numbers self-referential? — Patterner

Forget about the idea that's been presented in this thread, in connection with incompleteness, of numbers referring to themselves.

I assume you mean his original paper? Any particular translation? — Patterner

If I'm not mistaken, the only authoritative translation is the one in 'From Frege To Godel'.

Why is it not equally unnatural for Gödel to assign number values to things like "and", "negation", and "all"? — Patterner

It's not a question of "natural". It is utterly rigorous though. We define a certain function from the set of symbols into the set of natural numbers. There is nothing suspect about that in the least. Not even suspect in terms of common sense, such as assigning numbers to the players on a sports team, let alone the purely mathematical context of incompleteness. ADDED EDIT: For that matter, we don't begrudge that the computers were using to type these messages code symbols - letters, numerals and characters - as strings of 0s and 1s. And no sense in begrudging a mathematician from encoding symbolic mathematical notation with natural numbers.

I guess there's no hope for me in this. — Patterner

Sure there is. Just read a textbook on the subject. But if you're not interested in doing that, then indeed there's little hope that you'll understand the subject.

This is a technical subject. It requires study. Just as, say, microbiology is a technical subject and you can't expect to understand results in microbiology without knowing at least the basics.

Godel's completeness conjecture — sime

[italics in original]

The completeness theorem is not a mere conjecture. It is a theorem of mathematics. For any given consistent theory in a countable language, the proof of completeness provides a construction of a model of the theory. For an uncountable language (which is an unusual situation and not relevant to the languages for theories of which the incompleteness theorem pertains), still we have a model for each consistent theory though the proof of that is not constructive.

It would help if I could find a statement that is true but provably undecidable, but I've never seen one. Do you have an example? — FrancisRay

Yes, the one that we show in the proof of incompleteness.

By the way, it is not undecidable in every theory. It is undecidable in particular theories.

Also, earlier in this thread, there were mentioned more substantive statements. They are usually mentioned in overviews, such as in encyclopedia articles, of incompleteness. Moreover, there is the major result about Diophantine equations.

"The statement on the list at location G is not provable." — tim wood

No. As an illustration, it should be "The statement on the list at location n is not provable" and the location on the list for that statement is n.

G is not a location nor a number. You are conflating the sentence G with the Godel number for the sentence G.

I need to find a professor of mathematics to sit down with me and help me understand it. — Patterner

You need to read a textbook. Then you could ask about what you don't understand. A few chats with a mathematician might give you an overview, but to actually understand the actual content, you need to study it.

G is a number constructed following explicit rules. — tim wood

G is not a number. G is a formula. Then G is also coded by a number, which is its Godel number. The formula G and the number that codes G are two different things, though they can, in a certain sense, serve interchangeably in the particular context of the arithmetization of syntax.

For me the problem starts with 'This sentence is not provable'. This is meaningless. It does not state what is not provable. — FrancisRay

And the incompleteness proof doesn't say "this sentence". It's more complicated than that, and thoroughly rigorous.

I'll pick some highlights in this thread.

Either G is provable or not provable — TheMadFool

Either G is provable in T or G is not provable in T.

1. G is provable. So G is unprovable
2. G is not provable

So, there is G in the theory T

Have I got it right? — TheMadFool

No.

In context of proofs of incompleteness, we don't have numbers referring to themselves. Rather, numbers are used to refer to symbols, to strings of symbols (such as formulas) and to strings of strings of symbols (such as proofs).

Context:

(1) Godel's theorem was strengthened by Rosser. Subsequently, when we say 'Godel's incompleteness theorem' we usually actually mean the Godel-Rosser theorem. And Godel's notation is old-fashioned and hardly used anymore. And we now have much more streamlined expositions of the proof. For those reasons, to best understand the theorem, it is much better not to first study the original proof but rather more modern expositions of it. (Though, of course, after understanding the proof, we can deepen our appreciation and understanding, both mathematically and historically, by also going back to study the original proof).

(2) A proper understanding of Godel-Rosser requires understanding basic symbolic logic and mathematical logic. For that I recommend this sequence of books:

Logic: Techniques of Formal Reasoning - Kalish, Montague and Mar. For basic symbolic logic.

Elements Of Set Theory - Enderton. For understanding the set theoretic rubrics and methods of mathematical logic.

A Mathematical Introduction To Logic - Enderton. For a systematic treatment that works up to and includes a proof of Godel-Rosser.

/

Without at this juncture going into the proof of Godel-Rosser, I will outline (in rough oversimplifications that would need to be made rigorous for a truly proper exposition) some starting points, and pleading that I am rusty on the subject myself. This will at least clear up the matter of numbers and referring and give some crucial overall context.

(3) We have formal languages (I'll just say 'languages'). A language has a set of symbols, a classification of the kinds of symbols, and rules for concatenating symbols into sequences of symbols that are the terms (names, both definite and indefinite) and the formulas (open statements, i.e. expressions that would be sentences if we filled in definite names for the variables). Certain of the formulas are sentences. The symbols, terms, formulas and sentences have no meaning merely by themselves.

Some of the symbols are logical symbols: the sentential connectives (representing 'not', 'and', 'or' and 'implies') and the quantifiers ('all' and 'some'). Also, usually '='. The logical symbols are in every language. Non-logical symbols (such as '0', '+', etc.) are not in every language.

In this context, we restrict discussion to languages such that there is an algorithm to determine whether any given symbol is a symbol of the language, whether any given sequence of symbols is a term, whether any given sequence of symbols is a formula, and whether any given formula is a sentence.

(4) For a given language, we may provide an interpretation to give denotations for the symbols, meanings for the formulas, and a specification of what it means for a sentence to be true or to be false per the interpretation. Such interpretations are called 'models for the language'.

(5) A set of axioms is a set of sentences from a given language. Some of the axioms are logical axioms, in the sense that they are true per every interpretation. Some of the axioms are non-logical axioms, in the sense that it is not the case that they are true per every interpretation.

A proof system (I'll just say 'system') for a language is a specification of a set of axioms and a set of rules for proofs, which are certain finite sequences of formulas.

In this context, we restrict discussion to systems such that there is an algorithm to determine whether any given sequence of formulas is a proof.

Any sentence that is the last entry in a proof is called a 'theorem' of the set of axioms.

A theory is a set of all theorems of a set of axioms.

(6) A model is a model of a given theory if an only if every member of the theory is true in the model.

(7) For every formula P, there is the formula ~P, which is the negation of P. With an interpretation, a sentence P is either true or false and not both, and ~P is true if and only if P is false.

A theory is consistent if and only if there is no sentence P such that both P and ~P are in the theory.

A theory is complete if and only if, for every sentence P, either P is in the theory or ~P is in the theory. A theory is incomplete if and only if it is not complete.

A system is complete if and only if, for every sentence P that is true in every interpretation, P is a theorem of the axioms of the system. A system is complete if and only if it is not complete.

So note that there are two different senses of 'complete', and two different senses of 'incomplete'.

We talk about theories that are "sufficient to express a certain amount of arithmetic". However, usually, that is not given as a rigorous notion. Instead, in any exact context, we would specify which particular theory we mean.

(8) Godel-Rosser is a theorem of mathematics about mathematical systems. It is usually presented with some rubrics and methods of set theory, but actually it can be carried out within merely the rubrics and methods of arithmetic. Moreover, it can be carried out within merely finitistic and constructive arithmetic. So, it is impeccable arithmetical reasoning that in principle could be reduced to primitive reckoning about finite sequences of stroke marks on a page. I don't know of any mathematical methods that a person would trust but that would leave the reasoning of Godel-Rosser as not trusted.

(9) Godel-Rosser is the theorem that any consistent theory sufficient to express a certain amount of arithmetic is incomplete. Note that thereby any consistent extension of such a theory is incomplete.

But rather than rely on the unrigorous notion "sufficient to express a certain amount of arithmetic", instead we mention particular theories such as PA (first order Peano arithmetic), Q (Robinson arithmetic), etc. Here I'll discuss PA.

(10) The non-logical symbols for PA are:

0 (intuitively, zero)
S (inutivively, the successor of a number)
+ (intuitigely, addition)
* (intuitively, multiplication)

The non-logical axioms of PA (stated here semi-formally) are:

For all n and m,

0 is not Sn (intuitively, 0 is not a successor)

If Sn = Sm, then n = m (intuitively, successor is one-to-one)

n+0 = n

n+Sm = S(n+m)

n*0 = 0

n*Sm = (n*m)+n

For every formula P, if P(0) and for all n, if P(n) then P(n+1), then for all n, P(n). (intuitively if 0 has property P, and if for every n, n having property P implies that the successor of n has property P, then every number has property P)

(11) One model of PA is called 'the standard model'. With the standard model:

the universe of discourse is the set of natural numbers

'0' stands for zero

'S' stands for the successor operation

'+' stands for addition

'*' stands for multiplication

When we say 'true' in context of arithmetic, that can be understood formally as 'true in the standard model'.

(12) PA is one of theories that is incomplete by Godel-Rosser. So there is a sentence in the language of PA such that neither it nor its negation is a theorem. But either the sentence or its negation is true in the standard model. So there is a true sentence of arithmetic that is not true in PA. And note, that any consistent extension of PA is incomplete. But to do basic mathematics, we would want to have at least PA, so Godel-Rosser provides that in a common sense, we can't even a complete basic arithmetic, let alone a complete comprehensive mathematics (such as includes calclus, etc.) that subsumes arithmetic.

(13) The proof of Godel-Rosser uses the arithmetization of syntax, which maps each symbol of PA to a different number. Then it maps each finite sequence of symbols to yet another number. Then it maps each finite sequence of finite sequences of symbols to yet another number. Such numbers are called 'Godel numbers'.

So, each sentence in the language is mapped to a different Godel number.

So, with the incompleteness proofs, numbers are used to refer to (to "code") symbols, strings of symbols, and strings of strings of symbols.

Without going further into the proof at this juncture, we can preview by saying that the Godel sentence named 'G' is a sentence in the language of PA that has a Godel number n such that G "says" that the sentence with Godel number n is not provable in PA.

So G "says": G is not provable in PA.

That is the "self-reference" in play.

The number n is the Godel number of G. And G mentions its own Godel number. So, the number of the sentence G is n and G also mentions n. This is not a number referring to itself. It is a sentence referring to its own Godel number.

So we can dispense with inapposite puzzlements about "numbers referring to themselves".

deleted by author

ey — TonesInDeepFreeze

Good post. Interesting.

I'd need to read that essay, but meanwhile, what does he mean by "fundamental logical notion"? And why does he say there is not such a thing? As you mentioned, modal logic has come a long way since 1905, and the debate with Copleston was in 1948 by which time modal logic had been much better explicated but not nearly as robust as with Kripke semantics that came later. If Russell had kept up with such improvements (maybe he did? but I doubt it since, if I'm not mistaken, Russell's attention was generally turning to subjects other than logic or mathematics), then I wonder whether his views would have changed.

"We must distinguish between a necessary proposition and a proposition which predicates necessity" - Russell

Of course.