All graphs are 1D drawable (in that each can be embedded in a circle without any of its edges crossing) — keystone

Thank you. You saved me a lot of time and effort. Because my prediction that you would resort to half-baked handwaving is confirmed, so I am done with trying to help you formulate your stuff into mathematics.

A circle is an infinite set. But you say you're going to do this without infinite sets. You don't know what you're doing and you don't know what you're talking about. And if you were to say something like "a circle that's only a potential infinity" or whatever, then that would not cut it, since you haven't given a mathematical definition of such a thing. Just as I mentioned, you start to give mathematical definitions, but they finally end up relying on even more complex notions that are themselves presumptuously undefined and only gestured at with half-baked handwaving. You're a vortex.

I don't think it's a theorem in PA, it's a theorem about PA. PA + some additional axiom could make cons(PA) a theorem, but that wouldn't be a theorem in raw PA. — fdrake

Yes, the incompleteness theorem, when about PA in particular, is a meta-theorem about PA.

If PA is consistent, then:

PA |/- G

PA |/- ~G

PA |/- Con(PA)

But, if I'm not mistaken, there are certain statements that PA can prove about itself.

@Tarskian claims ('Inc' here for 'is incomplete'):

PA |- ~Con(PA) v Inc(PA)

equivalently:

PA |- Con(PA) -> Inc(PA)

equivalently:

PA + Con(PA) |- Inc(PA)

I tend to think that that is correct, though I'm not sure.

If at some point I have time enough, I'd like to refresh my knowledge to organize notes on what are some things PA does prove about itself.

Gödel's incompleteness theorem proves that PA is inconsistent or incomplete. — Tarskian

Of course, that is just sentential logic from:

If PA is consistent then PA is incomplete.

That is a perfectly legitimate theorem in PA. — Tarskian

I'm not sure about that; I'd have to think about it.

It does not prove that PA is incomplete. — Tarskian

Correct.

That is a theorem in PA + Cons(PA). — Tarskian

If Con(PA) then PA is incomplete. That is: If PA is consistent then PA is incomplete.

the Gödelian statements that cannot be expressed by language. There are uncountably many of those. — Tarskian

In a given countable language, there are only countably many sentences.

But there are uncountably many languages and systems, so it's trivial that there are uncountably many true but unprovable sentences.

But there are uncountably many languages and systems, so it's trivial that there are uncountably many true and provable sentences across the class of all languages.

I did not say that your remark would be wrong — Tarskian

Here's what you wrote:

it is not possible to preclude the second disjunct. — Tarskian

The use of logical entailment predates model theory by decades — Tarskian

By millennia. But those concepts are not formal.

T ⊨S as a synonym for "S is true in T". — Tarskian

You are so confused.

T |= S stands for "T entails S" not "S is true in T".

We know that 'true' and 'provable' are different notions.

A sentence is provable or not in a theory.

A sentence is true or not in a model.

A sentence is neither true nor false in a theory

A sentence is neither provable nor unprovable in a model.

The concept of 'provable' pertains to theories.

The concept of 'true' pertains to models.

The linkage is the soundness and completeness theorems:

soundness: If a sentence S is provable from a set of sentences G, then S is entailed by G.
That is, if G |- S then G |= S

completeness: If a sentence S is entailed by set of sentences G, then S is provable from G.
That is, if G |= S then G |- S

I think some people do say "S is true in T", but when we unpack it, it is a loose way of saying, "If all the sentences in T are true, then S is true." But what does 'true' mean? In mathematical logic, a sentence is true or not per a model. So "S is true in T" is a loose way of saying "Every model in which the sentences in T are all true is a model in which S is true", which is just to say T |= S, with the completeness theorem T |- S, which is just to say that S is in T (with the definition of 'theory' as a set of sentences closed under provability).

Here are usages:

G is a set of sentences (which could be a theory or not), M is a model, S is a sentence:

G |- S ... G proves S

G |= S ... G entails S ... in mathematical logic, that is: Every model of G is a model of S

|=_M S ... S is true in M

M |= S ... (not "M entails S" as it would appear, which would make no sense, since a model doesn't entail, but rather |=_M S)

In fact, by introducing the assumption "If PA is consistent", Gödel's theorem is no longer a theorem in PA. In that case, it is a theorem in PA + Cons(PA). That is not the same theory as PA. — Tarskian

You are very confused.

Incompleteness is not a theorem of PA, unless PA is inconsistent.

[EDIT: I'm not happy now with my wording above. I should have said, "there is a PA-unprovable sentence" is not a theorem of PA unless PA is inconsistent. And that actually accords with Tarskian, so I should not claim that he is confused on that point. However, I would need to think more whether "Con(PA) then PA is incomplete" (or "If PA is consistent then PA is incomplete") is a theorem of PA.]

Incompleteness is ordinarily proved informally or formally in a variety of theories (most signficantly, finitistically in, say, PRA). Proofs of incompleteness do not require Con(PA) as an assumption.

The theorem is: If PA is consistent, then there is a true but unprovable sentence.

I think you're saying, drop the antecedent, and we have: There is a true but unprovable sentence or there is false but provable sentence.

So what?

If PA is consistent, then there is a true but unprovable sentence. So, by disjunction introduction, there is true but unprovable sentence or there is a false but provable sentence.

If PA is inconsistent, then there is a false but provable sentence. So, by disjunction introduction, there is a true but unprovable sentence or there is a false but provable sentence.

For the fourth time: My statement is correct: If we assume soundness then we can preclude the second disjunct.

true and unprovable statements are non-denumerable. — Tarskian

There are not only finitely many of them, and there are not uncountably many of them (there are only countably many sentences in the language), so there are denumerably many.

there is no need to prove soundness theorem — Tarskian

You keep using 'the soundness theorem' in a way that invites confusion.

For the third time, the soundness theorem is:

"If a sentence P is provable from a set of sentences G, then all models of G are models of P"

Soundness can also be defined without using model theory:

https://en.wikipedia.org/wiki/Soundness — Tarskian

You are very confused. That page relies on '|=' which is from model theory.

I am obviously not against using model-theoretical notions to define soundness — Tarskian

What's your definition?

If you look at what exactly Gödel's theorem says — Tarskian

https://en.wikipedia.org/wiki/Diagonal_lemma — Tarskian

I'm asking where Godel says, not what Wikipedia says.

G is (true and not provable) or G is (false and provable)

This is somewhat equivalent to the alternative phrasing in which we assume consistency:

https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems

First Incompleteness Theorem: "Any consistent formal system T within which a certain amount of elementary arithmetic can be carried out is incomplete; i.e. there are statements of the language of T which can neither be proved nor disproved in T." (Raatikainen 2020) — Tarskian

If PA is consistent, then there are true but unprovable sentences. So, trivially, by disjunction introduction, it follows that there are true but unprovable sentences or there are false but provable sentences.

Meanwhile, for the third time, my remark is correct: If we assume soundness, then the second disjunct is precluded.

not assume consistency — Tarskian

The theorem doesn't assume consistency. Rather, the theorem has consistency as a conjunct in the antecedent of a conditional. If you drop that conjunct, then you don't have the theorem that there is an unprovable sentence.

True but unprovable statements vastly outnumber the true and provable ones — Tarskian

There are denumerably many of each.

Here's a breakdown:

'true' and 'false' here mean, respectively, 'true in the standard model for the language of PA' and 'false in the standard model for the language of PA'.

'sound' and 'unsound' here mean, respectively, 'every theorem is true' and 'it is not the case that every theorem is true'.

'provable' and unprovable here mean, respectively, 'theorem of PA' and 'not a theorem of PA'.

PA is formal and arithmetically adequate.

(1) If PA is consistent, then there is a true but unprovable sentence.

(2), From (1), by disjunction introduction, if PA is consistent, then there is a true but unprovable sentence or there is a false but provable sentence.

(3) If PA is sound, then PA is consistent.

(4) From (1) and (3), if PA is sound, then there is a true but unprovable sentence and there is not a false but provable sentence.

If you look at what exactly Gödel's theorem says, There exist propositions in Russell's system that are (true and not provable) or (false and provable) — Tarskian

Where did Godel say that?

if PA is not sound, then it is actually unusable — Tarskian

It wouldn't be used for arithmetic. But it would still have models if it is consistent.

However, proving soundness is even irrelevant. — Tarskian

Irrelevant to what? Irrelevant to whom?

It's relevant to whomever would like to see it proven for whatever reasons.

Imagine that we prove soundness theorem. — Tarskian

I guess by "the soundness theorem" you mean "PA is sound". That's not what "the soundness theorem" ordinarily means in mathematical logic. The soundness theorem is:

"If a sentence P is provable from a set of sentences G, then all models of G are models of P"

That is not hard to prove, though it requires many steps and details.

No, because the proposition that proof implies truth is exactly what we are trying to prove. — Tarskian

Who is trying to prove? Do you mean "If P is a theorem of PA then P is true in the standard model for the language of PA"?

If the standard model for the language of PA is a model of PA, then of course any theorem of PA is true true in the standard model.

The part that requires much proof is that the standard model is a model of PA.

There is no circularity there.

As to proving soundness in set theory, notice that I did not claim that that has epistemological clout.

Again, what I said is correct: IF the system is sound then the second disjunct is precluded.

Moreover, I don't think there are more than a rare few mathematicians who seriously doubt that PA is sound. Pretty much, we, along with Godel, live in world of mathematics in which the soundness of arithmetic is taken for granted.

/

And I should have mentioned that not only is PA proven consistent in set theory (and note that I didn't claim that that has epistemological clout) but the consistency of PA is proven by Gentzen from assumptions that are considered quasi-finitistic, which, if I am not mistaken, is regarded by a lot of people as having epistemological clout.

The soundness theorem is "If a sentence P is provable from a set of sentences G, then all models of G are models of P". We don't prove that from PA.

What we do prove (in, for example, set theory) is that PA has a model thus PA is consistent.

It is possible to preclude the second disjunct if we assume or prove that PA is sound. Meanwhile, I know of only a rare few mathematicians who even seriously doubt that PA is sound. I didn't say that PA itself proves that PA is sound.

The incompleteness theorem is that any consistent, formal, arithmetically adequate theory is incomplete, thus there is a true but PA-unprovable sentence. And PA is formal and arithmetically adequate, and one may take PA to be consistent, thus to infer that there is a true sentence that is not a theorem of PA. Moreover one may take PA to be sound, thus to infer that there is not a false theorem of PA.

That does not violate that PA does not itself prove that there is a true but PA-unprovable sentence, nor that PA itself proves that there is not a false but PA provable sentence.

In any case, notice what I said: IF the system is sound then the second disjunct is precluded. That is a correct statement.

We usually know that a proposition is true because it is provable — Tarskian

There are two ways:

(1) Prove a theorem from axioms. Then the theorem is true in any model in which the axioms are true.

(2) Prove that the sentence is true in a given model or given class of models.

If you look at what exactly Gödel's theorem says, There exist propositions in Russell's system that are (true and not provable) or (false and provable) — Tarskian

But if the system is sound, then the second disjunct is precluded.

I accept your disclaimer.

But I point out still that your comment gratuitously shifted from you to me. I asked for definitions and your retort was to falsely insinuate that I don't know about something, even though knowledge of that thing doesn't provide the definitions. My point is not that I take umbrage at that; but rather to catch your rhetorical dodge.

As to what you participate in, suit yourself, of course.

no point in trying to cow down other members, which in this case is your personalization of the issue. — Shawn

Like I said, I didn't get personal with you until you did with me.

You must mean that there's no point in you continuing.
— TonesInDeepFreeze

No, you telling me at this point to simply 'shut up' won't happen, sorry. — Shawn

Amazing that you got that exactly backwards.

You must mean that there's no point in you continuing. Others can choose for themselves.

Isomorphisms have everything to do with structuralism. An isomorphism says that two things are the same that are manifestly not the same. That's structuralism. — fishfry

In set theory, 'isomorphism' is not 'two things are the same that are not the same'. Rather, two things are similar; they have structures that are similar. But it's not the case that different objects that are not the same are the same.

Here's the most trivial example:

<{0} 0> and <{1} 0> are isomorphic but <{0} 0> not= <{1} 0> and {0} not= {1}.

I didn't say isomorphism isn't relevant to discussion about structuralism.

I'm always amused by this common philosophical example, since Venus isn't a star at all. — fishfry

Just to be clear, the example doesn't assert that Venus is a star.

I actually said that it was not meant to be a snide comment — Shawn

I put that in the category of "Don't micturate on me and tell me it's precipitation."

It was a stupid comment: There's no reason to think I don't know what the halting problem is; and knowing what the halting problem is doesn't fill in the definitions I asked about.

To think that Einstein didn't have discussions about the import of the defining work of Godel, being his Incompleteness Theorems, would seem like a moot issue to profess skepticism over. — Shawn

Wow! What a great stawman! I will get decidedly personal at this point: You're a sneaky poster. The question was not about Einstein discussing incompleteness. The question was your claim that Einstein thought "nature was "incomplete," for lack of a better word".

this thread was mostly about why Wittgenstein or what Wittgenstein could have meant by claiming that Godel's Incompleteness Theorems are logical tricks. — Shawn

Your post was about different things. I comment on what I feel like commenting on.

I have no comment on Wittgenstein.

My posts were about correcting misstatements about the theorem and about the lack of clarity in your errant arguments about reactions to the theorem. And deserved though quite slight sarcasm about your claim about Einstein.

Before my previous post, there were no overly personal comments about you. I responded sharply back only when you falsely and snidely insinuated regarding my acquaintanceship with the halting problem and the method of definition.

I don't claim any authority.

I did not mention our personal comparative knowledge until my previous post in reply to your false insinuations about my knowledge.

You seem not to know the meaning of the word 'tirade'.



I have no comment on Wittgenstein.

You don't know what you're talking about:

(1) Of course I know the halting problem. You make no point with the false insinuation that I don't.

(2) I know a lot better than you how definitions are stated and applied, since I've actually studied the details about definitions in logic, especially the forms that provide for eliminability and non-creativity.

(3) I don't claim that there are not definitions of 'complete for a complexity class size' and 'consistent for a complexity class size' such that a logic can be complete and consistent for a complexity class size, nor that, even if your verbiage is not exact then it still couldn't be explicated. I merely asked for your definitions. If you don't have definitions to share or have them but don't wish to share them, then so be it. But without them, you cannot reasonably expect another to appreciate your arguments. And shifting to a phony insinuation about my acquaintance with the halting problem caps you as a fool.

(4) My best guess is that you're throwing around a lot of technical verbiage for effect. And the basis for that guess is that, from your first post, you've been flat out incorrect about the incompleteness theorem.

(5) I do mean to be snide; if you haven't acquainted yourself with what the incompleteness theorem actually is, then it's likely that your confusions and false statements about it will persist.

if say that the legs of a horse are the set {1, 2, 3} — Pneumenon

I wouldn't say that.

(1) the set has only three members, not four, (2) the legs of the horse is not that set; rather the cardinality of the set of legs of the horse is that set.

So, I would say: The cardinality of the set of legs of the horse is 4 = {0 1 2 3}.

then I've said that the number of horse legs is the natural number four. But is that even true? What if the number of horse legs is the set of all rationals smaller than 4, i.e. the real number 4? How would we know which one it is? — Pneumenon

You could say that there are different forms of "number of":

cardinality - every cardinality is an ordinal (a finite ordinal, i.e. a natural number if the set is finite).

cardinality_q - every finite cardinality is the embedded natural number in Q

cardinality-r - every finite cardinality is the embedded natural number in R

Then each appropriate statement, couched in each form, about the set of horse's legs is true,

1. To say that a certain thing exists, you need an identity condition for it.
2. You can't always get those identity conditions for mathematical object — Pneumenon

If we're talking about formal mathematics:

(1) To define a constant symbol, we need first an existence_&_uniqueness theorem.

That's syntactical.

There are only countably many constant symbols, so only countably many such definitions.

(2) To define an object b in a model M (hope I've not made a mistake):

we need a formula F, whose only free variable is x, such that M satisfies F iff x is assigned to b.

Then b = the p such that M satisfies F iff x is assigned to p.

/

Perhaps, this might work (I don't know, it only occurred to me just now):

Let the mysterysaurus be a dinosaur that we inferred existed but don't know the number of its legs. To say that the mysterysaurus had four legs might not require a mathematical definition of 'four'. Rather, you could be saying "If you were an observer when the mysterysaurus was extant, then when you looked at one leg after another, and said the words, 'one', 'two', 'three', 'four' - one of those for each leg - then you would stop at 'four'". Yes, observation is mentioned, but isn't the statement independent of my knowledge? Does that hold up?

It seems that most often I'm not patient. In these situations, patience is a fault.

Two different senses of 'complete':

(1) a theory T is complete iff for every sentence P in the language of T, either P is a theorem of T or ~P is a theorem of T

(2) a logic L is complete iff for every valid formula P, P is a theorem of L

The incompleteness theorem concerns (1).

The completeness theorem is that first order logic is complete in the sense of (2).

Higher order logic, if formalized, is not complete in the sense of (2); that is, there is no formal set of axioms that proves all the validities.

I didn't intend my posts to comment on structuralism.
— TonesInDeepFreeze

My point. That was the subject of the conversation. — fishfry

It's not clear to me whether you're suggesting that my remarks were not pertinent. But in case you are:

The conversation has had many subjects. You mentioned certain isomorphisms. I was interested in that. My remarks about that don't have to comment on structuralism.

one could call propositional logic complete and even consistent for the complexity class size of P versus NP! — Shawn

What are the definitions of 'complete for a complexity class size' and 'consistent for a complexity class size' such that a logic can be complete and consistent for a complexity class size?

given the assumption that a sufficiently sophisticated computable logical system with the capacity to compute with an ever expanding alphabet, in hypothetical terms, would be able to simulate reality. Again, this is an ad hoc argument against incompleteness — Shawn

How so? How would such a thing show that it is not the case that every consistent, formal theory sufficient for arithmetic is incomplete?

at the time Hilbert's program was one instance — Shawn

What's another? If it's just Hilbert's program, then why not just say that from the start? But then your reasoning about that limitation in connection with incompleteness was ill-premised and confused about what the incompleteness theorem even is.

one may be able to do so in come other formal language? — Shawn

Depends on what you mean by "everything".

for a complexity class size to be complete and consistent, such as P v NP, then everything within such a set constitutes a complete and formal theory. — Shawn

We were talking about incompleteness, in which context 'complete' and 'consistent' have certain definitions. So I couldn't follow what might be your intent in using them in another sense. I don't know what definitions of them you have in mind related to complexity. It seems there are such definitions, but I don't know enough about them.

[the incompleteness theorem] was perceived by many as a hard limit on the ability to understand the world. — Shawn

So one of the conclusions you are referring to is "incompleteness puts a hard limit on understanding the world"? Are there any writers who you think are well paraphrased with that, and what writings of theirs do you have in mind?

Decidability for P verses NP is considered complete and consistent. — Shawn

What are complete and consistent, or incomplete or inconsistent are theories, not whatever "decidability for P v NP" is supposed to mean.

everyone concluded that this was the end of the possibility of proving everything in logic — Shawn

It is taken that incompleteness quashes Hilbert's program. I think it might depend on one's definition of 'logicism' whether incompleteness also quashes logicism.

It has not been demonstrated that propositional logic is the only logic that could accomplish the goals of unifying logic with mathematics or proving everything in logic alone. — Shawn

Not only has it not been demonstrated that propositional logic is not the only logic adequate for that task, but it's overwhelmingly clear that propositional logic is not adequate for that task.

I do not like stating this in formal systems like Peano Arithmetic; but, rather in decidability. — Shawn

What do you mean by 'decidable'? 'decidable' in context of incompleteness and computability theory has a definition. Is yours the same?

I always thought the solution to the problem of insufficient logic needed to compute certain undecidable problems is solved by appealing to greater complexity class sizes, which avoids the inherent limitations of a formal system which is incapable of decidability given its inherent limitations. — Shawn

I don't know what that is supposed to mean. But incompleteness is not avoided by greater and greater proof capability. No matter how capable, if the system is formal, consistent and provides for arithmetic, then it is incomplete.

If you allow for higher-order logic then all odds are off and even less can be asserted about the properties of the theories involved, such as incompleteness. — Tarskian

I don't know what that is supposed to mean, but, to be clear, the incompleteness theorem applies also to theories in higher order logic. Indeed, Godel's own proof regarded a theory in an omega-order logic.

I think you are referencing Rosner. — Shawn

Maybe you mean Rosser. Rosser improved Godel's theorem, but that has nothing to do with what I said in my post.

it seems that it relies on a contradiction performed in the system — Shawn

That is very wrong and backwards. No contradiction is shown in the system. Rather the system is assumed to be consistent*. From the assumption that the system is consistent*, formal and sufficient for arithmetic, we derive that the system is incomplete.

*Here, Rosser does play a role. For Godel it's w-consistent but for Rosser it's plain consistent.

the liar paradox, which Rosner utilizes. — Shawn

The incompleteness theorem does not use the liar paradox. The incompleteness uses something only analogous to the liar paradox. The liar paradox is "this sentence is false". Incompleteness uses "this sentence is unprovable". "This sentence is false" leads to contradiction. "This sentence is unprovable" does not lead to contradiction.

II hope that I might have gotten the gist of it. — Shawn

You didn't. You got it very wrong.

Moreover, the proof make use of only finitistic, intuitionistically acceptable principles.
— TonesInDeepFreeze

I am not denying the logical validity of Godel's Incompleteness Theorems. — Shawn

The theorems are not validities. Rather, the proofs are valid. The theorems are not true in every model. Rather, if the proof is formal, then there are no models in which the axioms used for the proof are true and which the theorem is not true.

And what I responded to in this context is this:

What Gödel proved was a truth that can only be seen in a formal system such as Peano Arithmetic. — Shawn

That is wrong.

the impact or the conclusions mathematicians reached at the time were too profound to the field of mathematics. — Shawn

What specific mathematicians and conclusions are you referring to? And how the conclusions too profound?

"Incompleteness is a property of certain formal systems. I don't know what it means to say that nature is or is not complete."— TonesInDeepFreeze

"Einstein had discussions with Gödel about how singularities and indeterminism could partake in physics and nature, which made him think nature was "incomplete," for lack of a better word."— Shawn

"Who used the word, for lack of a better one? And what is your source?"— TonesInDeepFreeze

Well, at the time, many physicists were of the opinion that mathematics governs physics. So, I hypothesized that Einstein was aware of Godel's Incompleteness Theorems, since they had many discussions between each-other. I can only imagine that Einstein was interested in Godel's thoughts about physics according to Godel given his Incompleteness Theorems. — Shawn

So you don't know that Einstein said that nature is incomplete. You only imagine that he did. You imagine it on the basis that Einstein discussed the incompleteness theorem with Godel. That's compelling.

What "conclusions" do you have in mind? The incompleteness theorem is a mathematical theorem with mathematical corollaries. Of course, some people make philosophical inferences based on the theorem, but such inferences are not of the mathematical theorem itself.
— TonesInDeepFreeze

Sure; well, I won't comment on the effect Godel had on logic and mathematics. There are intellectuals that still ponder about it to this day, since this is a fundamental problem of mathematics at the time when Godel made his discovery. — Shawn

You referred to conclusions that were drawn. But you don't have any in particular to mention.

The defintion of 'formal language' includes that the language is countable.
— TonesInDeepFreeze

There are potentially infinitely countable alphabets that could allow one to continuously expand the alphabet by including new terms in the formal system itself according to the principles of the formal system itself. — Shawn

For every countable language L, there is another countable language K that is a proper superset of L. So what?

Maybe model theory can actually simulate reality with this possibility in mind. — Shawn

Whatever that is supposed to mean, adding countably many symbols to a countable language doesn't bear upon the incompleteness theorem. And adding countably many variables has no substantive effect on a language.