x = {x}

Read my previous post regarding proof and lack of proof of existence.

Then I'll come back later and demonstrate more of my mathematical ignorance. — T Clark

I too will plead, as at this time, especially as I am rusty in the subject, I wouldn't be able to marshal enough knowledge to explicate the details of the mathematics mentioned there.

Just give me one instance of a set that contains itself. — TheMadFool

I could only do that by using anti-foundation (or non-wellfounded) set theory.

These are different:

(1) The theory proves that there is not a set that is a member of itself.

(2) The theory does not prove that there is not a set that is a member of itself.

Look at those closely to see that they are different.

These hold:

Z proves that there is not a set that is a member of itself.

ZFC-R does not prove that there is not a set that is a member of itself.

/

So to make it plainly clear:

I have never claimed that ZFC-R proves that there is a set that is a member of itself.

What I have said is that ZFC-R does not prove that there is not a set that is a member of itself.

Put another way:

Ex xex is consistent with ZFC-R.

On the other hand, if you claim that ZFC-R does prove that there is not a set that is a member of itself, then the burden is on you to show such a proof. Hint: Don't bother. There is no such proof.

Where do they meet the world? — T Clark

See sections 4.4 and 4.5 here:

https://plato.stanford.edu/entries/goedel-incompleteness/

For philosophical concerns about mathemtics see:

https://www.cairn.info/revue-internationale-de-philosophie-2005-4-page-513.htm

and

section 6 here again:

https://plato.stanford.edu/entries/goedel-incompleteness/

I thought the law of the excluded middle was also needed for mathematical proofs by contradiction, like Euclid's proof that there are infinitely many primes. — Amalac

No, there are two kinds of proof involving contradiction:

assume ~P
derive contraction
conclude P

assume P
derive contradiction
conclude ~P

The first one requires excluded middle (or double negation, or whatever intuitionistically invalid rule).

The second one does not require excluded middle (or double negation or any intuitionistically invalid rule).

properties of statements – such as their truth and falsehood – would be equivalent to determining whether their Gödel numbers had certain properties. — Wikipedia (Gödel numbering)

That doesn't sound right to me. The properties that are checked are syntactical. What semantical properties does Wikipedia claim are checked?

the law of the excluded middle. — Amalac

The incompleteness proof is intuitionistically valid and does not require excluded middle.

You provided a statement and have not spoken yet of the internal logic that makes it a proof — Gregory

You said that I have difficulty stating the theorem. Stating a proof of the theorem is more than stating the theorem.

I stated the theorem without difficulty.

As I said, I'd like to know whether you recognize that you were incorrect to claim that I have difficulty stating the theorem. Your recognition of that would help to show that you are not entirely irrational and rhetorically irresponsible.

There is no rule of set theory that we must name a set with set abstraction notation.

Moreover, for a finite set with members that are members of themselves, we can do it by extensional notation. For example:

Suppose

y = {y z}

z = {z j}

x = {x y z}

So, extensionally, we named the set whose members are x y z only.

The fact that we can continue to "expand" the notation in ways like this:

x = {x {y z} {z j}}

and

x = {{x y z} {{y z} {z j}} {{z j} j}}

ad infinitum, ad nauseum

doesn't prove without regularity that ~Ex x = {x y z} and doesn't prove ~Ex xex.

To prove something in set theory, you have to do if from the axioms. And set theory without the axiom of regularity does not prove ~Ex x = (x y z} and does not prove ~Ex xex.

C = The set of all sets that contains itself. Doesn't seem to be problematic — TheMadFool

It is problematic, because we cannot use set abstraction properly without first proving that there is a set that satisfies the defining property.

Gödel specifically cites Richard's paradox and the liar paradox as semantical analogues to his syntactical incompleteness result — Wikipedia

Yes, analogues.

I don't take exception to the Goldstein quote. But her book about incompleteness needs to be read critically. As I recall (though I can't cite specifics from memory) she gets too casual sometimes to the point of misstating certain key points.

The Franzen book is the one to read.

Would you say the below is a fair description of what Gödel is saying? Whilst the equation is true according to the rules of the math. The rules of the math cannot prove the equation true. To prove the equation true we need to look outside the rules of the math. — Pop

No.

(1) The Godel sentence is not an equation.

(2) "rules of math" is unclear.

(3) We don't look outside the "rules of math" even given a reasonable understanding of what 'the rules of math" might mean.

(4) A correct way to say it this:

For a given system S of a certain kind, there are statements that are arithmetically true but that are not provable in S.

"of a certain kind" can be rendered as "that is recursively axiomatizable, consistent, and and extension of Robinsion arithmetic"

"arithmetically true" can be rendered as "true in the standard model of the language of first order Peano arithmetic):

So the statement is not provable in the system. But when we look at the standard model, we see that the statement is true. Godel didn't himself refer to models, but it's the way we would formalize it now. And if we don't want to be so pedantic to formalize with models, we can say that we see that the statement is true by "outside the system" just looking at the way the statement was formulated and how it relates to ordinary arithmetic.

That's pretty close without splitting hairs technically, as we would split those hairs in a more formal treatment.

I thought that was the point I was trying to make in quoting from his book, but thanks for spelling it out to clear up any ambiguity. — Wayfarer

Yes, your quote from the book is well taken. And it is clear in the context of the book, but some people might not realize that context, so I just wanted to underline it.

Are you [SophistiCat] suggesting that Gödel's incompleteness theorem would be trivially true on a formalist understanding of mathematics because to be true in a language just is to be proven in that language? — Janus

Aside from whatever SophistiCat might say, it is not the case that formalism regards the incompleteness theorem in that way.

(1) Sentences are not true in a language. They are true or false in a model for a language.

(2) Sentences are not proven just in a language, but rather in a system of axioms and rules of inference.

(3) There are different versions of formalism, and it is not the case that in general formalism regards truth to be just provability.

(4) Godel's theorem in its bare form is about provability and does not need to mention the relationship between truth and proof (though a corollary does pertain to truth). The theorem is about provability, which is syntactical. Even if we had no particular notion of truth in mind, Godels' theorem goes right ahead to show that for systems of a certain kind, there are sentences in the language for the system such that neither the sentence not its negation are provable in the system.

Would a formalist allow that there could be mathematical truths that cannot be proven? — Janus

Any formal statement can be proven in some system or another. The incompleteness theorem, where it bears on truth, gives us that for a given system S of a certain kind, there are true arithmetical statements that are not provable in S. But those statements are provable in other systems. Even if a statement is arithmetically false, there are systems that prove the statement. Even if a statement if logically false, there are system that prove that statement (though, of course, those systems are inconsistent). So, if one is self-admittedly speaking only quite loosely to say "there are truths that cannot be proven" then we must regard that as standing for the more careful, "for a given system S of a certain kind, there are arithmetic truths that are nor provable in S".

To be clear, Franzen is taking exception to the theorem being incorrectly co-opted in many of those context.

All of the various self-reference paradoxes — T Clark

"self-reference" used pejoratively in reference to Godel's theorem is a red herring. The self-reference is seen by looking outside the object language. The theorem can be proven in finitistic combinatorial arithmetic. The proof methods are no more suspect than those of proof in finitistic combinatorial arithmetic.

Do these "paradoxes" really have a significant, real-time, practical impact on the effective use of mathematics and computer science in the real world? — T Clark

The proof of the incompleteness theorem does not rely on paradox. Anyway, it's pretty rare for the various non-foundational branches of mathematics, especially applied mathematics to be concerned with the incompleteness theorem. But there are important mathematical questions that are elucidated by the incompleteness theorem, including "There is no general method for deciding whether or not a given Diophantine equation has a solution." That settled a question that even a student of high school algebra might wonder about. Basic mathematical curiosity alone leads to the question whether there is a mechanical procedure to determine whether any given Diophantine equation has a solution. And there are other answers in mathematics that incompleteness elucidates. And the methods and context of the incompleteness theorem led to the earliest developments in computability and recursion theory, as those even became branches of mathematics in light of the techniques and context of the incompleteness proof. And, for philosophy of mathematics, Godel's theorem is a central concern. Perhaps most saliently is that (put roughly) incompleteness settles that Hilbert's hope for axioms that would settle all mathematical questions cannot be achieved.

I told you what I thought of it. — Gregory

What you think about it is one matter. (What you think about it is based on a collection of confusions and misunderstandings you have.)

But you said that I have difficulty stating Godel's theorem. Yet I stated it without difficulty. So I'd like to know whether you recognize that you were incorrect to claim that I have difficulty stating the theorem. Your recognition of that would help to show that you are not entirely irrational and rhetorically irresponsible.

It's a contradiction for something to be a member of itself twice. — Philosopher19

Why don't you look up a text in set theory so you would know how set theory axiomatically, clearly and unambiguously proves theorems and defines terms?

It's a contradiction for something to be a member of itself twice. — Philosopher19

"member of itself twice" has no apparent mathematical meaning.

But a couple of points:

Do you see the inconsistency in saying "you cannot have a set of all sets that are not members of themselves, but you can have a set of all sets that are members of themselves". — Philosopher19

It's not inconsistent. It does not imply a contradiction. A contradiction is a statement and its negation. If you claim to point out an inconsistency, then you need to show a statement and its negation that are both implied.

saying there can be no set that encompasses all sets is blatantly contradictory — Philosopher19

Nope. You have not shown that it implies a statement and its negation.

Now consider this: x, y, and z, are sets that are members of themselves. It cannot be the case that x = {x, y, z} [...] — Philosopher19

Wrong. It is possible that all these are the case: x = {x y z} (so x is a member of itself), and y is a member of y, and y is a member of x, and z a member of z, and z is a member x.

That's enough for now. At this time, I'm not going further with your argument.

Suppose B is a set that contains itself:.{1, 2, {1, 2, {1, 2,..the task can't be completed. — TheMadFool

Set theory doesn't prove things in this kind of context by saying "the task cannot be completed".

However, the axiom of regularity disallows infinite descending membership chains and
circular memberships (so also no sets being members of themselves).

Can we construct a set of all sets that don't contain themselves? Why not? — TheMadFool

Because the axioms don't provide for such a construction while also the axioms prove that there is no such set nor such a construction.

Of course we can because ALL sets can't contain themselves. — TheMadFool

It is correct that with regularity, no set is a member of itself. But that doesn't imply that there is a set whose members are all and only the sets that are not members of themselves.

.
1. All sets don't contain themselves.
2. The set of all sets that don't contain themselves = The set of all sets.
3. The set of all sets is impossible because it can't be member of itself and so it can't be the set of all sets. (from 1)
4. The set of all sets that don't contain itself is also impossible (from 2 and 3).
5. For Russell's paradox, the set of all sets that don't contain itself must be a set.
6. The set of all sets that don't contain itself is impossible i.e. it isn't a set.
Ergo,
7. Russell's paradox is not a paradox. — TheMadFool

1. Correct. With regularity, ~Ex xex

2. You cannot refer to "the set of all sets" without first proving there is such a set. And we prove that there is not such a set.

3. Correct. If there were a set of all sets then that would violate regularity. But, we don't need regularity (used for your item 1.) to prove there is no set of all sets.

4. Correct. But again, we don't need regularity (used for your item 1.) to prove there is no set of all sets.

5. What do you mean "for Russell's paradox"? The role of Russell's paradox is this:

Suppose ExAy(yex <-> ~yey).

Then xex <-> ~xex.

Therefore, ~ExAy(yex <-> ~yey)

6. Correct.

7. What do you mean by "it's not a paradox". The paradox (the contradiction) comes from the claim that there is a set of all sets that are not members of themselves. That contradiction implies that there is not a set of all sets that are not members of themselves.

he set of all sets encompasses all sets. It encompasses all sets that are not members of themselves, and it is a member of itself (because it encompasses itself). No contradictions here. — Philosopher19

You didn't go far enough in the argument:

If there is a set of all sets, then it has the subset that is the set of all sets that are not members of themselves. But the claim that there is the set of all sets that are not members of themselves implies a contradiction. Therefore, the claim that there is a set of all sets implies a contradiction.

there wasn't enough clarity with regards to what it is for a set to be a member of itself, and what it is for a set to not be a member of itself. — Philosopher19

Usually, we have an intuitive notion that sets are not members of themselves. However, since 'is a member' is primitive, we will not have a formal explication of the notion.

This is handled typically in three ways (not necessarily in order of preference):

Z set theory includes the axiom of regularity. And the axiom of regularity proves that no set is a member of itself.

ZFC-R set theory drops the axiom of regularity. The existence of a set that is a member of itself is independent of those axioms.

Z-R+D set theory [where D is an appropriate anti-foundation axiom] set theory drops the axiom of regularity and adds an axiom so that the theory proves that there are sets that are members of themselves.

/

Call any set that is not a member of itself a -V. Call any set that is not the set of all sets a V'. Call any set that's simply a set, a V (the V of all Vs = the set of all sets). — Philosopher19

Your notation is mixed up (especially as you conflate 'V' as naming an object with 'V' standing for a predicate). I'll use ordinary notation:

Is the V of all -Vs a member of itself? — Philosopher19

First we must ask whether ExAy(yex <-> ~yey). The answer is no. It is a theorem of first order logic:

~ExAy(yex <-> ~yey)

However, toward a contradiction, we do start with the assumption:

ExAy(yex <-> ~yey)

Then we show xex & ~xex.

Thus ~ExAy(yex <-> ~yey).

It is impossible to have a V of all -Vs that contains all -Vs and no other sets. — Philosopher19

Correct. ~ExAy(yex <-> ~yey).

You cannot have a set of all sets that are not members of themselves that is itself not a member of itself. — Philosopher19

Correct, because there is no set of all sets that are not members of themselves anyway.

one V can contain all -Vs and something more. — Philosopher19

Incorrect. ~ExAy(~yey -> yex). The "and something more" doesn't get around that fact.

That's enough for now; I'm not at this time going on with the rest of your argument, especially to untangle your poorly chosen notation.

you cannot have a set of all sets that are members of themselves — Philosopher19

With regularity, there is a set whose members are all and only those sets that are members of themselves. That set is the empty set. And if we drop regularity, then the statement that there is a set whose members are all and only those sets that are members of themselves is independent of the axioms.

it will result in at least one set being a member of itself twice — Philosopher19

'member of itself twice' has no apparent mathematical meaning.

No, you know it.

(1) is set theory proving there is no set whose members are all and only those sets that are not members of themselves.

(2) is Tarski's theorem.

I don't like using markup. The text is plenty clear enough.

You can't invoke unrestricted comprehension. — fishfry

I didn't.

All you've done is remind me that when I tell people that "the empty set is the set of all purple, flying elephants," I'm violating the axiom schema of specification. — fishfry

No, I'm not violating separation. Separation and extensionality were used to prove the existence of 0 (in an axiomatization where the existence of an empty set is not taken as an axiom).

To prove the existence of a set, we don't always have to do it directly from separation. We have union, power set, etc. But in this case I did prove it from separation, extensionality, and whaever other axioms prove ~Ex xex from regularity, as separation was used in the previous result that ExAy ~yex.

Then do so. Let me see it. — fishfry

Are you serious? Come on, you know how to do it yourself:

ZF |- ~ExAy(yex <-> ~yey)

ZF |/- ~ExAy(yex <-> yey).

ZF-R |/- ~ExAy(yex <-> yey)

ZF |- ExAy(yex <-> yey)

ZF-R |/- ExAy(yex <-> yey)

/

But there is NOT a SET of all sets that are members of themselves, not even the empty set. — fishfry

With regularity, yes the empty set 0.

E!yAx(xey <-> yey_

In English: There exists a unique set whose members are all and only those sets that are members of themselves. Proof:

xe0 <-> xex

So Ax(xe0 <-> xex)

So E!y(xey <-> xex)

So 0 = the-y Ax(xey <-> xex) = {x | xex}

So you are saying that some set exists that's not given by the axioms? — fishfry

No, I am not. Read what I said. I said that we can only prove existence from the axioms. But we can't prove non-existence from the axioms except when the axioms actually prove the non-existence. And in the case of ZF-R, the axioms don't prove the non-existence of a set whose members are all and only those sets that are members of themselves. And with ZF, the axioms do prove there is such a set; it's the empty set.

I thought Russell's paradox was meant to undermine set theory. — TheMadFool

Russell's paradox shows the contradiction in set theory with unrestricted comprehension. After Russell's note, we moved to a set theory that does not have unrestricted comprehension.

What follows as of necessity? — TheMadFool

That there does not exist such a set.

I believe the liar sentence too is treated in a similar way - banished from the world of propositions.

If you can formalize that for mathematics, fine. But meanwhile, ordinary mathematical logic and set theory do not "ban" such a formulation.

(1) In set theory, we don't ban writing "ExAy(yex <-> ~yey)". Rather, we prove ~ExAy(yex <-> ~yey).

(2) In mathematical logic, we don't dispute that some theories may formalize a liar-like sentence. Rather, we prove that any theory that can do so is inconsistent.

Is it still bad? — fishfry

Looks okay now.

Then we're in agreement and you have conceded my point, since that is exactly the set you claim exists. — fishfry

No, I don't. Indeed, I said the opposite in my original post.

Write out your claim formally and you'll get exactly what you just wrote. — fishfry

Howzabout you quote me where you think I claimed that there exists a set whose members are all and only the sets that are not members of themselves.

Indeed, I pointed out that there is not such a set, and even on logical principles alone.

that also is not a legal set specification. — fishfry

It doesn't depend on the abstraction operator. I could just as well write the whole conversation without the abstraction operator.

In order to form the set of all sets that are members of themselves, you have to start with some existing set and then apply specification to the predicate "x element of x". — fishfry

To prove the existence of sets having a certain property, we can only use the axioms. But the axioms don't say that other sets don't exist, except as we can prove from the axioms that there do not exist sets of a certain property.

Again, the axioms don't prove that there does not a exist a set whose members are all and only those sets that are members of themselves. Indeed, with regularity, the axioms prove that here does exist such a set.

we really haven't agreed on any specific type of order yet. — Metaphysician Undercover

Yes, when 'we' includes you. But with math, we do specify specific kinds of order.

I apprehend, that at the base of the idea of infinity in natural numbers, is the desire, or intention to allow that numbers can be used to count anything. — Metaphysician Undercover

The notion of infinite sets is used calculus, which is mathematics for the sciences, which is mathematics for the technology you enjoy.

Before and after, are temporal terms. — Metaphysician Undercover

'before' and 'after' are often in a temporal sense, but clearly not exclusively. Not in English. And surely not in math that doesn't mention temporality.

Your math notation in your previous post does not format form me.

Anyway, {x | ~xex} is not at question. There is no such set.

You would like to form the set R={x:x∉x}R={x:x∉x} but you haven't got an existing set to start wit — fishfry

I don't think you mean {x | ~xex}. We're talking about {x | xex}.

And yes, without regularity, we can't prove there is a nonempty set {x | xex}.

But that's not the question. The question is whether we can prove that it is not the case that there is a set {x | xex}. And we can't. It is consistent with set theory that there is a set {x | xex}. And with regularity, it is provable that there is a set [x | xex}.

I'm interested in why Godel's Theorems 'are unquestionably among the most philosophically important logico-mathematical discoveries ever made' (says this article.) — Wayfarer

That article gives an answer. It's a great article. (By the way, Panu Raattkainen is a top notch source on the subject.)

I do not believe there could be a set of all sets that contain themselves — fishfry

With regularity, It's the empty set.

And we can't derive a contradiction by dropping an axiom, so such a set is consistent also without regularity. But it would be inconsistent with set theory without regularity if every set were a member of itself, but "every set is a member of itself" is already inconsistent with set theory (even without regularity).

Such a set would be subject to Russell's paradox. — fishfry

Nope.

can you tell me if it's giving people false ideas? — fishfry

Maybe I need to be double-checked, but my reasoning tells me that undecidability follows right from incompleteness.

is it any good? — fishfry

It is terrible. I mentioned why earlier in this thread.

I defer to your better judgement — TheMadFool

You mentioned the benefit of a course in logic. In another thread, I have listed what I consider to be the best textbooks leading to the incompleteness thereom. If you like, I can link to that post. And, for a more casual, everyperson read, I highly recommend:

Godel's Theorem: An Incomplete Guide To Its Use And Abuse - Torkel Franzen

It's readable for people with just a modest knowledge of logic and math, authoritative, pays attention to crucial technicalities but not bogged down with them, very nicely written, entertaining and witty too.