Abstractions of Gödel Incompleteness
I'm yet still inquisitive and learning with regards to interpretative ideas forged by Gödel's Incompleteness Theorems, and would consequently be appreciative of any lent thoughts on the subject.
From what I've gathered, one semantic variant that is oftentimes communicated in light of their invocation, is the following:
To commence with, does Gödel's first incompleteness theorem bear a comparable veracity for any arithmetic model (that is to say, when accorded a finite list of axioms or postulates, do there always result either indeterminate, or unprovable truth values)?
Secondly, doesn't the absence of self-consistency foreshadow, that an intractable crisis permeates the heart of all (conceivable) logical architectures?
If it does, then isn't any rational modality that can be mathematically formalized, by virtue of a finite set of elementary axioms, necessarily bound by the same constraint? Won't that imply, that in order to illustrate a logical system's consistency, one must transcend the system entirely (for it can't be ascertained by its own decree)? Isn't that tantamount, for instance, to asserting that all finitely synthesized constructs of reasoning, are by their existence inconsistent? Not all logical edifices are self-referential or amenable to mathematical formalisms, of course; many of them, nevertheless, are.
Do there exist any epistemic ceilings on abstractions of Gödel incompleteness, and if so, what do they entail?
From what I've gathered, one semantic variant that is oftentimes communicated in light of their invocation, is the following:
- Within any systematically finite, axiomatic structure characterized by Peano Arithmetic, one necessarily witnesses the emergence of statements with positive truth values, that are simultaneously unprovable (or, equivalently, there exists no axiomatic system entirely bereft of composite statements, whose truth values necessitate a belief not encompassed by [i]first order predicate calculus[/i]).
- By extension, any axiomatic structure that is underpinned by Peano Arithmetic, ceases to unequivocally demonstrate its own mathematical consistency.
To commence with, does Gödel's first incompleteness theorem bear a comparable veracity for any arithmetic model (that is to say, when accorded a finite list of axioms or postulates, do there always result either indeterminate, or unprovable truth values)?
Secondly, doesn't the absence of self-consistency foreshadow, that an intractable crisis permeates the heart of all (conceivable) logical architectures?
If it does, then isn't any rational modality that can be mathematically formalized, by virtue of a finite set of elementary axioms, necessarily bound by the same constraint? Won't that imply, that in order to illustrate a logical system's consistency, one must transcend the system entirely (for it can't be ascertained by its own decree)? Isn't that tantamount, for instance, to asserting that all finitely synthesized constructs of reasoning, are by their existence inconsistent? Not all logical edifices are self-referential or amenable to mathematical formalisms, of course; many of them, nevertheless, are.
Do there exist any epistemic ceilings on abstractions of Gödel incompleteness, and if so, what do they entail?
Comments (107)
Interpretations may not be sacrosanct to formalized systems of logic, but are they truly nonsensical? Any epistemological modality that isn't purely formalized, is likely underpinned and inspired by interpretations. Not all of them have to be whimsical, or poetically arbitrary; oftentimes, they're necessary in discerning or directing what neither empiricism, nor formal logic can (eg - hidden variable theories in canonical QM paradigms).
Quoting tim wood
Thanks - that's what the literature suggests, too.
Quoting tim wood
Once again, a presumed extension of the first answer.
Quoting tim wood
Contemplating a system externally, is what I meant by 'transcending' them.
Isn't there, however, a self-perpetuating element to Gödel incompleteness (that is, irrespective of how many new axioms one defines a set or structure with, an unprovable sentence can always be derived within it)?
In my view, no.
What Gödel's incompleteness Theorems and other Incompleteness results (Turing, Church) simply show are the limitations of giving a direct proof. And do notice that with giving an indirect proof you cannot say so much as with a direct proof.
Notice that something existing (being logical correct in this case) and something being provable are two different things. This is the basic underlying issue here.
Quoting Aryamoy Mitra
Quoting Aryamoy Mitra
Quoting Aryamoy Mitra
Quoting Aryamoy Mitra
Where do you find such terminology in discussions of incompleteness? Where did you read such things?
Meanwhile, it's better to look at Godel-Rosser incompleteness, since it is stronger than Godel incompleteness and is what most people mean by now when they refer to incompleteness. Also, we should take advantage of certain refinements in mathematical logic that were not present when Godel proved incompleteness.
Godel-Rosser is that any recursively axiomatizable and consistent theory that "expresses enough arithmetic" (such as Robinson arithmetic or Peano arithmetic) is incomplete in the sense that there are sentences in the language of theory such that neither the sentence nor its negation is a theorem of the theory.
From the above it follows that for such theories, there are true (in this context meaning true in the standard model of PA) sentences that are not theorems. Indeed, we may construct a specific such sentence.
Moreover, no such system proves its own consistency.
/
Godel-Rosser has proof that is constructive, intuitionistically (cf. philosophy of intuitionism in mathematics) acceptable, and finitistic (the proof can be carried out in primitive recursive arithmetic).
/
Quoting Aryamoy Mitra
If a theory is recursively axiomatizable, sufficiently arithmetically expressive, and consistent (let's call these 'G-theories'), then it is incomplete, no matter whether the set of axioms is finite or infinite. Some theories that are not G- theories are complete (and some are finitely axiomatizable).
Quoting Aryamoy Mitra
What lack of consistency? Incompleteness doesn't say that e.g. PA or ZFC are inconsistent. Rather, a proof of consistency is not available within their own systems.
Quoting Aryamoy Mitra
Some theories are recursively axiomatizable with even an infinite set of axioms. For some reason you are stuck on a notion of finite axiomatization that is not relevant in this regard.
Also, 'elementary' has a technical meaning different from your use.
Quoting Aryamoy Mitra
You shouldn't generalize about "logical systems" but rather you should be accurate by addressing just G-theories in this context. And the answer is yes; to prove the consistency of a G-theory we have to do that in some other theory (which itself could be another G-theory). For example, Z set theory proves the consistency of PA.
Quoting Aryamoy Mitra
Not at all. The question itself shows a confused understanding of this topic. If you are interested in understanding incompleteness, I suggest studying it from good sources.
Quoting Aryamoy Mitra
The wording of that is not good, but basically yes, you can't add axioms to a G-theory to escape incompleteness.
Quoting TonesInDeepFreeze
Neither of them are terminological, in the first place.
Quoting TonesInDeepFreeze
Here's the crux of the question I was posturing - insofar as arithmetic expression and consistency are prerequisites to Gödel incompleteness.
Quoting TonesInDeepFreeze
That is literally, what 'self-consistency' denotes (demonstrating a self-referential consistency, from within a system).
Quoting TonesInDeepFreeze
There's no fixation on 'finite axiomatization' - I'm only asking whether given a condition of axiomatic finiteness, Gödel incompleteness extends outside Peano Arithmetic.
Quoting TonesInDeepFreeze
What are the (formal) subtleties?. What does a non-elementary axiom entail?
Quoting TonesInDeepFreeze
Discerning which generalizations are appropriate, and which aren't, was the predominant objective of this thread. G-theories, as I'm sure you'd concur, are not a trivial subset of all logical formalisms. If, for example, one were to create and quantify a logical edifice (with arithmetic), might the Gödelian constraints on certain proof-statement correspondences in formal languages, lend itself to the underlying logical edifice?
Quoting tim wood
Why is it speculative, though?
Sincerely, I would like to help you understand this topic and to provide answers, but at many points I don't know what you're trying to say because you use unrecognizable or too vague terminology.
Quoting Aryamoy Mitra
'self-consistency' is not ordinarily used in the sense of "proves its own consistency". Rather, 'self-consistency' is just a longer phrase for 'consistency'.
A theory is consistent if and only if there is not a formula such that the theory proves both the formula and the negation of the formula.
A theory T proves the consistency of a theory S if and only if T proves that that S does not prove a formula and its negation. In particular, a theory T proves the consistency of T if and only if T proves that T does not prove a formula and its negation.
A theory may be consistent and not prove its own consistency.
Quoting Aryamoy Mitra
Do you mean that there are only a finite number of axioms? Or do you mean that the axioms entail that there are only finite sets, or something like that?
Quoting Aryamoy Mitra
What do you mean by 'extends outside' a theory?
Do you mean to ask whether there are theories stronger than PA that are incomplete. Yes.
Or theories with all the axioms of PA plus more axioms and that are incomplete? Yes.
Quoting Aryamoy Mitra
Often, 'elementary' means first-order. Or, in different contexts, it refers to elementary arithmetic with elementary functions, which have a specific technical definition as a certain subset of the set of recursive functions.
Quoting Aryamoy Mitra
I don't know what you mean by 'proof-statement correspondences' nor what you mean by 'underlying logical edifice'.
Sincerely I say that your understanding of this subject would depend on familiarizing yourself with good books or articles on it, and with that you would have recognizable terminology in which to couch your questions about it.
'Godel's Theorem: An Incomplete Guide To Its Use And Abuse' - Torkel Franzen
Probably the best book ever written for introducing the subject of incompleteness to everday readers.
Quoting TonesInDeepFreeze
I was merely shortening (with 'self-consistency'), how I communicated the notion of a (system) proving its own consistency; it may not have been of appropriacy.
Quoting TonesInDeepFreeze
- a finite number of axioms.
Quoting TonesInDeepFreeze
Both; as long as it doesn't consist solely of PA. Thank you, for clarifying that the answer is affirmative either way.
Quoting TonesInDeepFreeze
First-order logic (unless I'm mistaken) is a corollary of propositional logic, insofar as it quantifies the interrelations between its subjects - as opposed to delineating them with logical connectives. With a 'logical edifice', I was referring to a set of ideas that stemmed from propositional conventions, which were then affixed with arithmetic operators. Won't any constraints on the latter, inclusive of Gödel incompleteness, emerge for the former (propositional ideas)? Is this formulation, any more intelligible?
Quoting TonesInDeepFreeze
Quoting TonesInDeepFreeze
That's most certainly an endeavor of mine. I'm not as educated on this subject as you are, since propositional calculus (and its formalized language) is a rarefied discipline. Hopefully, nonetheless, I'll one day be able to contextualize Gödel's incompleteness theorems - as they are meant to be.
Then I don't know what relevance you have in mind. G-theories can have finitely many or infinitely many axioms.
Quoting Aryamoy Mitra
No, the opposite. First-order logic subsumes propositional logic.
Quoting Aryamoy Mitra
First order logic allows predicate symbols, operation symbols, and quantifers, which are not present in propositional logic. But first-order logic does have the connectives also.
Quoting Aryamoy Mitra
I cannot make sense of that. I don't know what you mean by "a set of ideas that stemmed from propositional conventions, which were then affixed with arithmetic operators".
Quoting TonesInDeepFreeze
Yes, that's what I meant with the term 'corollary'. First-order logic, in most contexts, cannot exist without an underlying propositional logic (once again, unless I'm mistaken).
Quoting TonesInDeepFreeze
If logical propositions can be quantified with quantifiers, then can they not (equivalently) be mediated with arithmetic operators (that is to say, 'adding' and 'subtracting' propositional conditions from one another)?
You are correct.
Quoting Aryamoy Mitra
I don't know what you mean.
This is explained in any textbook in mathematical logic, usually chapters 1 and 2.
Proof concerns just formulas in the language - purely syntactical objects.
Truth concerns models for the language. A sentence of the language might be true in some models and false in other models. With incompleteness, by 'true' we leave tacit that we actually mean true in one particular model, which is the standard model for the language of PA.
Proof takes place merely with regard to the theory itself. Truth is handled by a meta-theory (usually set theory) for the theory.
A theorem of a theory is a sentence that is provable from the axioms for the theory.
We say a model is a model of a given theory if and only if every theorem of the theory is true in the model.
If a sentence is provable from the axioms of a given theory, then that sentence is true in all models of the theory.
But a sentence might be true in a given model of the theory and yet not be provable from the axioms of the theory.
Incompleteness of a theory is that there are sentences such that neither the sentence nor its negation is provable from axioms for the theory. But in any given model, a sentence is either true or false. So for an incomplete theory, there are sentences that are true in certain models but not provable. In particular, for certain theories, we show that there are unprovable sentences that are true in the standard model for the language of PA.
1. The theorem F1 is true AND the theorem F1 unprovable (Assume for reductio ad absurdum)
2. IF the theorem F1 is unprovable THEN we don't know the truth value of theorem F1
3 The theorem F1 is true (1 Simp)
4. IF the theorem F1 is true THEN we know the truth value of theorem F1
5. We know the truth value of theorem F1 (3, 4 Modus Ponens)
6. The theorem F1 is unprovable (1 Simp)
7. We don't know the truth value of theorem F1 (2, 6 Modus ponens)
8. We know the truth value of theorem F1 AND We don't know the truth value of thoerem F1 (5, 7 Conj)
9. False that the theorem F1 is true AND the theorem F1 is unprovable (1 to 8 reductio ad absurdum)
:chin:
Incompleteness theorems.
Even if there are the obvious nonsense (just think how much nonsense there is about quantum physics etc), I think there are vast more of those mathematicians who push the theorem to the sidelines close to the border of logic and logical inquiry and insist that it has nothing to do with anything else in the field of math than what the theorems state. It's just an oddity and no reason to think just what those Gödel numbers would be. I think many of these don't even see any link to Turing's Halting problem or with other incompleteness results.
SYNTACTICAL:
1. We have formal languages. These are sets of symbols. And there are rules for sequencing the symbols to make terms and formulas. Sentences are a certain kind of formula. It is computer-checkable whether a given sequence of symbols is or is not a formula for a given formal language. And it is computer-checkable whether a given sequence of symbols is or is not a formula of a given formal language.
2 We have rules of proof. A proof is a certain kind of sequence of formulas. It is computer-checkable whether a given sequence of formulas is or is not a proof.
3. A theory is a set of sentences closed under proof. A theorem is a member of that set of sentences.
4. An axiomatization for a theory is a set of formulas such that every member of the theory is provable from the axioms. So a theorem is a sentence that is provable from a set of axioms for the theory.
4. A theory is decidable if and only if it is computer-checkable whether any given sentence is or is not a member of the theory.
5. A theory is complete if and only if for any given sentence in the language, either the sentence or its negation is a member of the theory.
6. A theory is consistent if and only if there is no sentence such that both the sentence and its negation is a member of the theory.
7. A theory is recursively axiomatizable if and only if there there is a computer-checkable set of axioms for the theory.
8. The notion of a theory being "sufficiently arithmetically expressive" is complicated and can't be summarized here. But basically it means that the theory has the ordinary basic truths about arithmetic.
9. Godel-Rosser incompleteness is that there are recursively axiomatized, consistent, sufficiently arithmetically expressive theories that are incomplete.
P.S. Note that when we say 'unprovable' we mean 'unprovable from certain axioms'. No formula is absolutely unprovable, since any formula is provable from certain axioms (even if just from an inconsistent set of axioms).
SEMANTIC:
10. A model for a language is a non-empty set that is the universe for the model and a mapping from the symbols of the language to individuals in the set, relations on the set, and functions on the set.
11. A model then describes a "state of affairs". That is, some members of the universe and tuples of members are either in the relations or not, or in the functions or not.
12. The Tarski method is applied so that 'truth in the model' is built up in stages for simple sentences to more complicated sentences. A sentence is either true in a given model or false in that model.
13. PA, in this context, is a certain first-order theory.
14. By 'the standard model for the language of PA' we mean the model where the symbols of the language map to the natural numbers and functions on the natural numbers in the way we would expect. For example, '0' maps to the number 0, and '+' maps to the addition operation, etc.
15. (As I explained in my previous post) incompleteness implies that there are sentences true in the standard model but that are not members of the various theories. (Recall that 'member of a theory' just means 'provable in the theory'.) The only sentences that are unprovable from all consistent sets of axioms are sentences themselves that imply inconsistency.
A theorem by definition is a provable sentence.
So what you wrote as the very first line of your argument is a contradiction in terminology.
And the rest of your argument is rife with other terminological mixups and misconceptions about mathematical logic.
It is irrational to mix up your own terminological use with the way the terminology is actually used for the mathematics you are critiquing.
If you wish to critique mathematical logic, then you should learn something about it first.
"1. The theorem F1 is true AND the theorem F1 unprovable (Assume for reductio ad absurdum)"
[i]By definition, a theorem is a provable sentence. So there is no F1 that is a theorem and unprovable.
So, to be generous, let's save 1:
F1 is true but unprovable.[/i]
"2. IF the theorem F1 is unprovable THEN we don't know the truth value of theorem F1"
False premise. A formula may be unprovable but known to be true by the method of models in the meta-theory.
"3 The theorem F1 is true (1 Simp)"
Okay.
"4. IF the theorem F1 is true THEN we know the truth value of theorem F1"
False premise. There are true formulas that we don't happen yet to know the truth value.
"5. We know the truth value of theorem F1 (3, 4 Modus Ponens)"
Incorrect since 4 is false.
"6. The theorem F1 is unprovable (1 Simp)"
When 1 is corrected as I have, then okay.
"7. We don't know the truth value of theorem F1 (2, 6 Modus ponens)"
Incorrect since 2 is false.
"8. We know the truth value of theorem F1 AND We don't know the truth value of thoerem F1 (5, 7 Conj)"
Incorrect since neither 5 nor 7 have been shown.
"9. False that the theorem F1 is true AND the theorem F1 is unprovable (1 to 8 reductio ad absurdum)"
Incorrect since 8 has not been shown.
Not quite. It has the respect of most in the math community, but most of those think they will never come up against that roadblock. Me included. It has arisen, however. For example Goodstein's Theorem.
I'm not so sure but I don't think the problem has been solved. The Godel sentence, G = This theorem, T, is true but unprovable in the axiomatic system A. G makes the claim that T is true in A and not some other axiomatic system. For that, it's necessary for T to be provable in A.
You are completely confused about this subject.
What is the source you read about this subject?
In all these posts about incompleteness, by 'true' I mean 'true in the standard model'.
(1) Sentences are not true or false in a theory. Rather, sentences are true or false in a model for the language of the theory.
(2) G is true but G is not provable in the theory.
(3) G says that the Godel-number for G is not the Godel-number of a theorem of the theory. In other words, G says that G is not provable in the theory.
(4) G is true if and only if G is not provable in the theory.
(5) G does NOT say anything about its own truth value. Indeed, if a theory had a predicate for truth, then the theory would be inconsistent.
https://thephilosophyforum.com/discussion/comment/513487
You maybe right but you didn't answer my question. Why? Please reread your reply to my question and my response to it.
You said:
Quoting TonesInDeepFreeze
Quoting TonesInDeepFreeze
??? :chin:
I'll leave it to you to connect the dots.
I asked you:
Quoting TonesInDeepFreeze
You are using teminology and mentioning concepts in the subject, so it seems you've read something somewhere about it. Would you please tell me the articles or books you read? Then possibly I can look them up to find the passages you've misundertsood.
Quoting TheMadFool
Why what? And if you have particular posts you want me to look back at then please link to them so I know specifically which ones you want me to look at.
The last qustion you asked is this:
Quoting TheMadFool
No, it is not. I explained here:
https://thephilosophyforum.com/discussion/comment/513465
I have no clue whether you even read that post.
And I even followed up with extraordinary specifics here:
https://thephilosophyforum.com/discussion/comment/513476
But I'll say it again:
For convenience, let's suppose the theory is PA. And by 'true' I mean 'true in the standard model for the language of PA'.
G is not provable in PA. The sentence 'G is true' is provable in, e.g. Z set theory. That is, in Z set theory we state the standard model of PA and we can prove that G is true in that model.
Conflating provability with truth is one of the most common mistakes by people who only skim an article here and there about incompleteness and don't apprise themselves of the crucial technical specifics of mathematical logic and the incompleteness theorem.
I'll say it one more time:
G is provable in a theory
and
G is true in a model for the language of the theory
are DIFFERENT notions.
If you have a question or a point to make, then please ask it or state it rather than dropping cryptic instructions for me to connect whatever dots I'm supposed to connect.
Perhaps you think there is an incompatibility here:
Quoting TheMadFool
I explained why those are not incompatible here:
https://thephilosophyforum.com/discussion/comment/513465
and with detailed definitions and points about mathematical logic here:
https://thephilosophyforum.com/discussion/comment/513476
And again in my post above.
And I'll say it yet another way:
Truth and provability are different notions in mathematical logic. While they are different, mathematical logic does study relationships between them. Some of those relationships are the subject of the incompleteness theorem.
Quoting TonesInDeepFreeze
That means, correct me if I'm wrong, given an axiomatic "theory" A, and Godel sentence G = the theorem T is true and unprovable in axiomatic theory A".
G is claiming that T is true in A i.e. my objection that that's impossible since it's unprovable is valid. T isn't true in some other "theory" like you seem to suggesting when you say "Rather what we mean unprovable in whatever theory is in question" but in A.
I'm correcting you; you are wrong. And you're not even coherent. You've got an extra symbol 'T' that makes no sense.
You're not even reading what I wrote:
Again, G says "G is not provable in A" and G does NOT say "G is true and unprovable in A".
Not only does G not say "G is true in A" but A can't even form the predicate 'is true in A' or A would be inconsistent (this is Tarski's theorem that is a kind of semantic variant of incompleteness).
Quoting TheMadFool
I said it about six different ways in the previous posts that that is not correct. I explained in detail why it is not correct.
Quoting TheMadFool
You are not just confused, but you are abysmally confused.
(1) Whatever sentence you mean by T, it's not relevant. The only sentence we are concerned with is G (you called it 'F1' elsewhere).
(2) I did NOT say that anything is true in any theory. About six times I said that sentences are not true or false in a theory but rather sentences are true or false in models for the language of the theory.
Why do you keep getting this wrong?
(3) When I said 'unprovable in whatever theory is in question' I was just pointing out that provability is relative to a theory. A sentence may be provable in some theories but not in others. And I am not evading that we are specifically concerned with a given system whether it be PA or Robinson arithmetic or whatever system A might be.
Again, if the theory in question is A, then G (the Godel sentence for A) says:
G is unprovable in A.
And G does not say
G is true and unprovable in A.
Get it through your head!
Godel's Incompleteness Theorems
I'm quitting the discussion. Thanks for your valuable comments.
A is a recursively axiomatizable, consistent, sufficiently arithmetically expressive theory.
L_A is the language of A.
PA (Peano Arithmetic) is a theory.
L_PA is the language of PA.
M is the standard model for L_A.
M is a model of PA.
Z is set theory.
G_A is the Godel sentence for A.
G_A "says" 'G is not provable in A'.
G_A is true if and only if G is not provable in A.
In Z we prove that G is true in M.
And, get this in your head:
G does NOT say 'G is true in A'.
'is true in a model for A' cannot even be formulated in A, since A is consistent (Tarski's theorem).
Here we go again.
Yes, it is the case that G is unprovable in A. And it is the case that G is true if and only if G is unprovable in A. And G is true in the standard model for the language of A.
But G does not say that G is true in A.
(1) 'True in A' doesn't even make sense. Sentences are not true or false in a theory. Rather, sentences are true or false in models for the language of the theory.
(2) G does not even say that G is true in a model for the language of the theory. The language for A cannot even express 'true in a model for the language of A' since then A would be inconsistent.
Wikipedia in general is not reliable regarding mathematics. Much better is the Stanford Encyclopedia of Philosophy. However, possibly that particular article might be okay. I looked at it only briefly just now. I am wondering what you think is in that article that is not compatible with anything I've said.
From the article:
"The first incompleteness theorem shows that the Gödel sentence G_F of an appropriate formal theory F is unprovable in F. Because, when interpreted as a statement about arithmetic, this unprovability is exactly what the sentence (indirectly) asserts, the Gödel sentence is, in fact, true. For this reason, the sentence G_F is often said to be "true but unprovable." However, since the Gödel sentence cannot itself formally specify its intended interpretation, the truth of the sentence GF may only be arrived at via a meta-analysis from outside the system." - Wikipedia
Those are the very points I said also. Most poignantly, it does not say that the Godel sentence says that the Godel sentence is true, but rather it says that the Godel sentence does not say that it is true and that the truth of the Godel sentence is shown outside the theory.
In my view Gödel's incompleteness theorems, as the other incompleteness results, aren't roadblocks.
The problem is that many view them as like that: hoping that they wouldn't find them in front of them. I think that they, the results I mean, just show that a crucial logical part in our understanding of the foundations of mathematics isn't understood yet. Obviously from our system of natural numbers doesn't come everything in mathematics, that is plain obvious.
I think the problem is that Gödel's theorem is far too complicated and specific to show just where the real problem lies on. People simply fall into the complexities of Gödel numbering etc. I'd prefer something as simple as the diagonalization in Cantor's diagonal argument: the negative self reference. I think there lies the key problem: with negative self reference we get either paradoxes or true but unprovable mathematical objects.
Set theory and foundation people certainly appreciate your perspective. And there are numerous examples of statements - conjectures - that can't be proven within, say, the Peano system, etc. Examples. Some probably are true.
But the fact remains that math people not in those areas are usually not very concerned, even if they are stumped in proving something. However, I haven't been around mathematicians for a long time and I could be mistaken.
Indeed! You're right.
Godel sentence = G = There's a mathematical theorem, call it T, in a given axiomatic system A, such that T is unprovable/undecidable (which word is apt?) in A.
Kurt Godel's tour de force was proving G, the Godel sentence, is true. Am I right?
SEP = Stanford Encyclopedia Of Philosophy
[quote=SEP]statement GF in F is often called “the Gödel sentence” of F[/quote]
[quote=SEP]Therefore (1), GF cannot be false, and must be true. For this reason, the Gödel sentence is often called “true but unprovable (2)”[/quote]
The word "therefore" (1) suggests an argument i.e. there's a proof for the Godel sentence GF. However, the next line asserts that GF is ...often called "true but unprovable (2)".
What puzzles me is that the unprovable status of GF is not what matters. GF should be asserting a mathematical theorem, call it T, and asserting that T is unprovable and not that GF itself can't be proved.
What gives? :chin:
This discussion is becoming unwieldy with different letter-symbolizations with your own your letters and also letters from Wikipedia and SEP. For example, you use 'A' when Wikipedia uses 'F'. I'm going to stick with Wikipedia here, since its explanation is coherent and quotable.
Quoting TheMadFool
That is all messed up.
You seem to be conflating the statement of the incompleteness theorem itself with the Godel-sentence G_F. The statement of the incompleteness theorem is not the Godel-sentence.
By 'the incompleteness theorem' I am referring to the Godel-Rosser incompleteness theorem. I'll call it 'C'. You attempted to express a part of C, but with terrible errors when you wrote:
"There's a mathematical theorem, call it T, in a given axiomatic system A, such that T is unprovable/undecidable (which word is apt?) in A."
Let's fix that (and recall that by 'true' in this context I mean 'true in the standard model of arithmetic').
I think the part of C you have in mind is:
There is a sentence G_F that is true but not provable in F.
I'll call that statement C* (it is a part of the incompleteness theorem C). Both C and C* are not stated in the language of F, but rather in a meta-language for F. And neither C nor C* are the Godel-sentence. In other words, the statement of the incompleteness theorem is different from the Godel-sentence that is used to prove the incompleteness theorem.
Each (appropriate) theory F has its own Godel-sentence that we call 'G_F'. And G_F "says" that G_F is not provable in F.
Quoting TheMadFool
There's a lot more in the proof of incompleteness that is remarkable other than the fact that G_F is true.
When SEP says "true but unprovable" it understood that 'unprovable' is informally brief for 'unprovable in F'.
Quoting TheMadFool
The word 'therefore' is not being used in the proof of G_F in the theory F. Rather, 'therefore' is being used in the argument in the meta-language that G_F is true.
Quoting TheMadFool
No, that G_F is unprovable in F is at the crux of the incompleteness proof.
Quoting TheMadFool
No, that's where you're mixed up. G_F is a statement in the language of F. G_F is a mathematical statement about natural numbers. But G_F is constructed so that in the meta-theory we show that G_F is true if and only if G_F is not provable, and in the meta-theory we show that G_F is true, i.e. that G_F is not provable.
Two different things:
(1) G_F is a statement in the language of F but not a theorem of F.
(2) 'G_F is true' is a theorem of a metatheory for F.
It's crucial to distinguish between (1) the statement G_F itself in the theory F and (2) the statement 'G_F is true' which is a meta-theoretic statement about G_F.
There are two levels of proof: (1) proofs in F and (2) proofs (such as the incompleteness theorem and the statement 'G_F is true' in the meta-theory.
Thanks for the tip. I don't follow what you're saying but I can make some sense of what tim wood is trying to get at. Please join the conversation if you feel so inclined.
Quoting tim wood
So, the key proposition in Gödel's proof is K = The proposition with Gödel number G is not provable (in T) and the "coincidence" is that K is the proposition with Gödel number G. In other words, K is not provable.
But...
K has to be a mathematical theorem, no? After all, "incompleteness" in Gödel's incompleteness theorems refer to mathematical theorems that aren't provable but K [The proposition with Gödel number G is not provable] is definitely not a mathematical theorem. What gives?
It's invigorating, though. When I commenced this discussion, I'd never envisioned my own ignorance of the subject it pertained to. Nevertheless, this has been a revelation.
Quoting TonesInDeepFreeze
For anybody who's enthused and willing, here's a thorough exposition of Gödel incompleteness - distilled in formal logic. I'm reading it, too.
https://www.math.wisc.edu/~miller/old/m571-08/smith.pdf
Quoting TonesInDeepFreeze
What's a meta-language for F? Does that imply that C, and C* are statements that concern or describe the language of F?
I think that the incompleteness results have an effect on a wide range of things not just in the set theoretic realm and with the foundations of mathematics. We just don't want to make or are ignorant about the link to the incompleteness results.
I think the classic example of something being true but unprovable is a game theoretic situation where it's easy to show that a correct solution exists, yet there seems to be no way to get there. The existence of a correct solution can be shown...based on mathematics. Yet then how to get there seems impossible, actually illogical. Hence for example in economics these problem are dealt with taking the approach of there being a "black box" where "something happens" and the correct result is reached. Great! The economist has his function (with the black box) and can say that the issue has been modelled. But then opening up the black box cannot be done. Which basically is sophistry, but it goes with the remark "this is hopefully resolved later".
Why I say that these problems are similar to the incompleteness results is because in many of these cases there is the negative self-reference that similarly is in use in Gödel theorem and in the Halting Problem of Turing.
Mathematicians are far more rigorous. They cannot just assume something will work. Or, as the joke goes, they can have everything work and get every kind of result they want when 0=1. But that is hardly useful.
I want to see something like this: AxAy(x + y = y + x) in a Godel sentence but I don't and if that's the case, the Godel sentence isn't about mathematical theorems. Just so you know, if there's a side to me that's wise which I doubt, I would take your word for it. Thanks. :up:
Maybe somebody already told you this, but Gödel also uses something called Gödel numbering.
The Gödel statement is coded in a particular Gödel number, and in that way the Gödel statement is a statement about mathematics, since it is statements about mathematics that can be coded in such a way.
This Numberphile video might help:
https://youtu.be/O4ndIDcDSGc
(Around 5:32 he starts to talk about Gödel numbering)
Quoting Amalac
That's an engaging talk, and certainly an unsophisticated introduction of the idea. It may consist, nonetheless, of certain oversimplifications (which might be worth mentioning).
For instance, at one phase, it asserts that the provability of a theorem hinges on its Gödel number being divisible, by the Gödel numbers of a formalized system's constituent axioms. I'm hardly acquainted with the specifics of Gödel Coding, but that appears to be an overly reductionist idea (acknowledged, of course, by the professor).
Quoting Amalac
It's an excellent resource, for anyone seeking to immerse in the concept.
If only the particulars were that elementary, though - Gödel might have devised a pathway, to resolving all of mathematical enigma. Reverse-mathematics, unsurprisingly enough, is likely to have been standardized.
Please, let's stick with one set of letter-symbols, so 'F' rather than 'T'.
The Godel-sentence G_F is a formula in the language of number theory. It can be reduced to the primitive language of PA, with only the symbols '0', 'S', '+', and '*', and a quantifier and connectives (even just one connective would work). It is a pure mathematical formula. The ordinary interpretation of the symbols is that they refer to arithmetic.
Then, we show in the meta-theory that G_F is true if and only if G_F is not provable in F. So we say that G_F "says" that G_F is not provable in F. Note that we put 'says' in scare quotes; what we mean more technically than "says" is that we show that G_F is true if and only if G_F is not provable in F.
Quoting TheMadFool
I think you are conflating 'sentence' with 'theorem'.
Theoremhood is always relative to a theory. A sentence is a theorem of a theory if and only if the sentence is provable in the theory. In the case of incompleteness, we sometimes leave tacit the theory, and say 'provable' rather than the actually correct 'provable in F'. Also, every sentence is a theorem of some theory or another. The only sentences that are theorems of all theories are the logical validiites.
G_F is not a theorem of F. And the negation of G_F is not a theorem of F. That's the point of incompleteness.
Quoting tim wood
That's certainly a thought-provoking analogy.
If the notion of Gödel divisibility was of an exact accuracy, though, one might witness a multitude of surprising repercussions emerge. Wouldn't it then be plausible, to Gödel code every unsolved hypothesis - and reverse-trace an axiomatic proof? I'm certain the idea exists at a concrete threshold; only one far more intricate than arithmetic divisibility.
Quoting tim wood
I've searched comprehensively for short translations of Gödel's 1931 paper, to no success. I do, nonetheless, intend to learn the language of formal logic, prior to readily engaging in the paradigm (such that to learn Gödel incompleteness with the context it was synthesized in); the 150-page variant is consistent with the second phase.
Godel's second incompleteness theorem explained in words of one syllable
Thank you; these are invaluable.
I never foresaw a page-long explanation, but it was most certainly worth it.
I'm affixing the entirety of it herein, with a few observational comments - for it definitely simplifies the overarching rigor of the subject, and necessitates a read.
[i]'First of all, when I say "proved", what I will mean is "proved with the aid of
the whole of math". Now then: two plus two is four, as you well know. And,
of course, it can be proved that two plus two is four (proved, that is, with the
aid of the whole of math, as I said, though in the case of two plus two, of
course we do not need the whole of math to prove that it is four). And, as
may not be quite so clear, it can be proved that it can be proved that two plus
two is four, as well. And it can be proved that it can be proved that it can be
proved that two plus two is four. And so on. In fact, if a claim can be proved,
then it can be proved that the claim can be proved. And that too can be
proved.'[/i]
What this predominantly suggests, is that if an assertion can be proved, then one may also (successfully) prove that it can be proved, in a recursive manner. I don't know why this bears veracity, especially in a formalized system characterized by a certain degree/class of arithmetic. Will you able to shed any light, on this matter?
[i]'Thus: it can be proved that two plus two is not five. Can it be proved as well
that two plus two is five? It would be a real blow to math, to say the least, if
it could. If it could be proved that two plus two is five, then it could be
proved that five is not five, and then there would be no claim that could not
be proved, and math would be a lot of bunk.
So, we now want to ask, can it be proved that it can't be proved that two plus
two is five? Here's the shock: no, it can't. Or, to hedge a bit: if it can be
proved that it can't be proved that two plus two is five, then it can be proved
as well that two plus two is five, and math is a lot of bunk. In fact, if math is
not a lot of bunk, then no claim of the form "claim X can't be proved" can be
proved.'[/i]
Does this (the latter) entail the crux of Gödel incompleteness, insofar as contradictions are concerned?
Here's a simplistic, non-technical sequence of rationalizations - identical to the ones in the exposition above (it doesn't consist of any jargon - inclusive of languages, theorems, proofs or axioms).
1) Hypothetically, there exists a statement A (2+2=5).
2) A's negation can be proven.
3) Ideally, A should not be provable.
4) Unfortunately, one can't prove, that one can't prove A.
5) If 4 holds true, then one can simultaneously prove A (since A must demonstrate a specific truth value).
6) Therefore, there exists an inconsistency between 2 and 5, implying that certain truths will necessarily remain unprovable.
Have I significantly misapprehended the argument, or is it at all substantive?
[i]'By the way, in case you'd like to know: yes, it can be proved that if it can be
proved that it can't be proved that two plus two is five, then it can be proved
that two plus two is five.'[/i]
Interpreting this sentence, is harder than accruing a mastery over all of Mathematics.
No. Sorry.
Quoting Aryamoy Mitra
At (5) and (6), yes.
Quoting Aryamoy Mitra
But you have undertaken to follow the copious and kind advice of @TonesInDeepFreeze, so you may be pleasantly surprised. Good luck.
Yes.
Quoting Aryamoy Mitra
No.
Rest assured that the Godel sentence G_F is a purely symbolic formula of arithmetic, using symbols like the ones you mentioned, though it is not a universal generalization of an equation and it is much more complicated. It is for this form:
~ExPx where P is a purely symbolic mathematical formula in the language of, say, first order PA, but too complicated to type out here.
When reading informal accounts of incompleteness it might be mistaken that G_F is not a purely symbolic mathematical formula, because in informal accounts we say that G_F says "G_F is not provable in F". Yes that is what G_F "says" in that G_F is true if and only if G_F is not provable in F, but G_F actually is a purely symbolic mathematical formula and not the English captioning of it as "G_F is not provable in F".
Peter Smith's 'An Introduction To Godel's Theorems' is a real good book. I recommend it. But that PDF is only a shorter warmup for the actual book published a couple years later. There were some fairly bad mistakes in the original edition that were corrected in a later edition, so the PDF might have some of those mistakes, I don't know.
Quoting Aryamoy Mitra
A meta-theory for F is either a formal theory or an informal context. The meta-theory for F formulates the language for F, the syntax for F, the semantics for F, and formulates F itself, and has meta-theorems about all that. In that context, the meta-language for F is the language of the meta-theory for F.
We say informally "the meta-theory for F" and "the meta-language for F" when it should be "a meta-theory for F" and "a meta-language for F" since F may have many meta-theories and meta-languages, depending on what the mathematician chooses. For incompleteness, a very roomy meta-theory for F in which to work easily is set theory, but even PRA ("finitistic arithmetic") could be the meta-theory, or an informal English context. Godel himself used a mix of German and mathematical and logical symbols.
Like others here, I don't know what he has in mind about division.
Some people who have not very much background in mathematical logic have been able to understand incompleteness by first directly reading Godel's paper. But my native abilities would not allow me to understand the paper without having first studied incompleteness in textbooks in undergraduate level mathematical logic, and to get to mathematical logic I needed firs to study basic symbolic logic and set theory. Here are additional reasons I think it is better to learn from textbooks than from Godel's own paper.
* Godel-Rosser strengthens Godel's original and is what people actually mean now by incompleteness.
* Godel uses old-fashioned notation and terminology that is hardly used for many decades now. The newer notation, now decades established, is more streamlined and more aesthetically pleasing, and, for me at least, easier to understand. I think one is more conversant about incompleteness with the more modern notation and exposition.
In particular, since Godel's paper, the terminological distinction between recursion and primitive recursion became the prevailing convention, so some people get tripped up by Godel's older terminology.
The second incompleteness theorem is usually only sketched at the undergraduate level. And a full proof of the second incompleteness theorem is hard to find. It is in Hilbert-Bernays but it was only recently translated from German to English. But there are still some good undergraduate level books about the second theorem. Also, Godel didn't provide much proof of the Representation theorem that is a crucial lemma for incompleteness. I've read that a proof of the Representation theorem is a lot of tedious technical detail. If I'm not mistaken, it also is in Hilbert-Bernays.
The aforementioned Peter Smith book is really good, but again, I think it is better appreciated by first studying basic symbolic logic, set theory, and mathematical logic.
And for an everyman's introduction, Torkel Franzen's book is superb and a joy to read. Though again, personally, I doubt I would have appreciated it as much as I did without having first studied mathematical logic.
As Nash demonstrated fixed-point theory is useful in game theory. Brouwer's fixed-point theorem was proven indirectly, with no simple path to its value, and this distressed Brouwer, who later turned to intuitionism. Proving a math object exists indirectly, but without a process for its construction, is still proving a theorem. This sort of thing has a superficial relation to Godel's works, but I don't think it's what he had in mind. Others here, with more knowledge of the matter can correct me if I'm in error.
We must keep in mind that when he says 'proved' it's really 'proved in [whatever particular theory we're talking about]'.
The insightful and witty George Boolos is one of the great writers about foundations - mathematical logic and set theory.
His 'The Logic Of Provability' might be the definitive treatment of the particular topics in that book.
He is a co-author of 'Computability And Logic', which is really nice classic overview.
He is a co-author of 'Logic, Logic, And Logic' which is a wonderful set of essays. Especially welcome is his cogent explanation of the intuitive basis of the set theory axioms in terms of hierarchy.
EDIT CORRECTION: Strike "We must keep in mind that when he says 'proved' it's really 'proved in [whatever particular theory we're talking about]'. He says that he means proved by "the aid the whole of math". I would take that to mean ZFC, which is ordinarily understood to provide an axiomatization for mathematics. So, as far as I can tell, he's talking about the second incompleteness theorem for ZFC.
I suggest this course of readings, in order:
Logic:Techniques Of Formal Reasoning - Kalish, Montague, and Mar
Elements Of Set Theory - Enderton (perhaps supplemented with Axiomatic Set Theory - Suppes)
A Mathematical Introduction To Logic - Enderton (definitely supplemented with the chapter on mathematical definitions in Inroduction To Logic - Suppes)
The Enderton logic book will take you through a proof of Godel-Rosser.
Quoting bongo fury
Can you pinpoint how I've faltered? I ask, since (5) was at the heart of Gödel incompleteness.
Quoting fishfry
As a clarity, are you refuting the original exposition? This passage, for instance, was word-for-word sourced from another, non-technical resource.
I did see the italics but I did not see a link to the source. So I couldn't tell if you were quoting someone else or quoting yourself from some other publication or forum, or just separating out your ideas into quoted form. But in that case I haven't criticized you, I've criticized whoever wrote that passage. Which was:
I believe what they mean is this. For definiteness let's take Peano arithmetic (PA). By Gödel's second incompleteness theorem, PA can not prove its own consistency. That means PA can not prove that it can't prove that 2 + 2 = 5. Agreed so far? Then if PA can prove that it can't prove that 2 + 2 = 5, then PA must have proved its own consistency, which it can only do if it's inconsistent; and if it's inconsistent, then it can prove that 2 + 2 = 5.
Have I got that right?
Now my complaint is that you did not distinguish between "PA can prove ..." and "It can be proved ..."
Because in fact we CAN prove that PA is consistent. The easiest consistency proof is to assume Zermelo-Fraenkel set theory, ZF. In ZF we have the axiom of infinity, which gives us a model of PA. Since there's a model, PA is consistent by Gödel's completeness theorem.
There's another famous proof of the consistency of PA, by Gerhard Gentzen. As Wiki puts it:
[quote "Wikipeda"]
Gentzen's consistency proof is a result of proof theory in mathematical logic, published by Gerhard Gentzen in 1936. It shows that the Peano axioms of first-order arithmetic do not contain a contradiction (i.e. are "consistent"), as long as a certain other system used in the proof does not contain any contradictions either. This other system, today called "primitive recursive arithmetic with the additional principle of quantifier-free transfinite induction up to the ordinal [math]\varepsilon_0[/math]", is neither weaker nor stronger than the system of Peano axioms. Gentzen argued that it avoids the questionable modes of inference contained in Peano arithmetic and that its consistency is therefore less controversial.[/quote]
https://en.wikipedia.org/wiki/Gentzen%27s_consistency_proof
The point is that proof and consistency are relative to given axiom systems. It's true that PA can't prove its own consistency; but we CAN prove the consistency of PA by other means.
So, to sum this all up: Using ZF or Gentzen's proof, I can indeed prove that PA is consistent, and that PA can't prove that 2 + 2 = 5, and that PA can prove that it can't prove that 2 + 2 = 5.
I can always do this as long as I'm willing to go outside PA. And this is true in general. Just because some given system can't prove its own consistency doesn't mean we can't prove its consistency.
Let me know if I've missed your point. And if you'd just say where you got the quote it would be helpful.
I should add for clarity that having used ZF to prove the consistency of PA, I now have the question of whether ZF is consistent. You can push the problem around but never nail it down. Maybe after all that's what the paragraph means, but without the surrounding context it's hard to tell. I admit to being confused as to why Gentzen's proof isn't problematic in exactly the same way.
I think by now you can see why I I originally gave a one word answer. :-)
Quoting fishfry
Pardon me, for not properly citing the source; here's the mystical entity, from which this passage stems.
Quoting fishfry
For everyone else's following (and that of my own), let me distill this with arrows:
A) Gödel incompleteness (2)[math]\longrightarrow[/math]PA can't demonstrate its own consistency[math]\longrightarrow[/math]PA can't prove, that it can't prove that 2+2=5;
B) Now, if PA can prove, that it can't prove that 2+2=5 [math]\longrightarrow[/math]PA shall be consistent;
C) And, if PA can prove, that it can't prove that 2+2=5 [math]\longrightarrow[/math]PA needs to be inconsistent[math]\longrightarrow[/math]PA should be able to prove, that 2+2=5.
Quoting fishfry
Thank you, for expanding. PA can't show its own consistency, but PA can be proved consistent outside itself (with other axioms) - and that's a generality that may hold for other arithmetic systems; is that the crux of the argument?
Yes, exactly. The proof from ZF is trivial. ZF contains a model of PA; that is, a set in which, with the proper interpretation, every axiom of PA is true. Therefore PA is true if ZF is. And ZF is consistent if we assume the existence of an inaccessible cardinal, which itself is a model of ZF. You just keep adding axioms to push the inconsistency problem up the chain.
And now that I see that the author is the great George Boolos, I am unhappy, because I disagree with what he said. He starts: "First of all, when I say "proved", what I will mean is "proved with the aid of
the whole of math.""
I disagreed with that the first time you wrote it. It's wrong. Proved means, "proved in a given system of axioms." If you take the "whole of math," you lose the entire point of the subject. Given some axiom system we want to know what sentences it can prove. Those are the theorems. But "the whole of math?" I don't even know what that means. Do I get to include the entire hierarchy of the large cardinal axioms? Do I include the continuum hypothesis or not? I was hopelessly annoyed as soon as I read that remark.
Having read Boolos's article, I disagree with it entirely. Incompleteness is NOT about "the whole of math." It's about particular systems of axioms. I believe he's destroyed the essence of the subject in his effort to simplify it. And that's why when you quoted that paragraph, I instinctively said, "No." It's not true that "the whole of math" is either consistent OR inconsistent, nor is it subject to incompleteness. You have to say what the axioms are, then I can say if they're consistent or inconsistent or whether certain statements are independent of the axioms.
But then again I could be wrong. Perhaps he is making the more subtle point that even if I can use ZF to prove the consistency of PA, I still don't know if ZF is consistent. So maybe in the end he's right and I'm wrong. I admit to not being sure whether he's right or wrong. But I still have the right to be annoyed that he ignored the essence of the matter, which is that we are talking about particular axiom systems and not "the whole of math."
In fact if by "the whole of math" we might mean for example the set-theoretic multiverse of Joel David Hamkins, then "the whole of math" includes the models of set theory in which CH is true, and the models of set theory in which it's false; and even perhaps the possibility that PA is consistent, and the possibility that PA is inconsistent [that latter concept is not part of Hamkins's idea, I don't think].
So I just found "the whole of math" to be too imprecise to be correct. Didn't someone (Feynman? Einstein? ) write, Things should be made as simple as possible, but no simpler.
Einstein in fact. https://www.championingscience.com/2019/03/15/everything-should-be-made-as-simple-as-possible-but-no-simpler/
Boolos's article violates the spirit of that saying.
Yes, you got the point exactly. I would say that the issue has more than just a superficial relation, but that is just my personal view about the subject.
Perhaps it is a far more simple issue and has less to do with Gödel, but this is exactly where Oskar Morgenstern saw a problem in economic forecasting in the American Journal of Economics in the 1930's. And I have forgotten which Nobel-laureate responded to him back then 1930's that Morgenstern is wrong while there is obviously is a correct solution: because fixed point theorem proves that there exists a correct solution. Yet the whole problem is that an indirect proof, a reductio ad absurdum proof leaves things unanswered.
The most simple example (well, how simple it is remains questionable) is with Cantor's proof that there are more reals than natural numbers. The issue here is that the reductio ad absurdum proof uses negative self reference. And then we are left with the Continuum Hypothesis being unanswered. In my view, with real numbers our finite mathematical system that starts from counting natural numbers gets into some foundational problems.
I wrote some time ago in PF that our understanding of mathematics has started from a necessity, from counting and thus we lay the foundations of math to natural numbers and counting. Hence it is a bit hard to add into the picture the uncomputable / uncountable afterwards. Counting and the number system should rather be seen as part of mathematics, a very natural and obvious part, which is possible to use in nearly every part of mathematics, but not with everything and especially not being a foundation. Logic in my view should be the foundation for math. It might be that it is the historical foundation of math, but not perhaps the logical foundation of mathematics.
Isn't he just ensuring that what 2 + 2 is equal to is being discussed with respect to a system big enough for the second theorem to apply?
https://en.wikipedia.org/wiki/Hilbert%E2%80%93Bernays_provability_conditions?wprov=sfla1
Boolos says that he means proved by "the aid of the whole of math". My guess is that he means ZFC, which is ordinarily understood to provide an axiomatization for mathematics. So, as far as I can tell, he's talking about the second incompleteness theorem for ZFC.
Cantor's proof is not a reductio ad absurdum.
Cantor's proof can be outlined:
Show that there is no enumeration of the naturals onto the reals.
Show that any enumeration of the naturals is not onto the reals.
Let f be an enumeration of the naturals.
Blah blah blah and we've shown that f is not onto the reals.
So any enumeration of the naturals is not onto the reals.
So there is no enumeration of the naturals onto the reals.
Cool, although it didn't matter what he meant, so long as it was bigger than e.g. Robinson arithmetic, was my point.
I've worked with fixed points for a long time, mostly recreational now, but a few years ago one of my theorems was applied to decision making, specifically the psychology of groups involved. It surprised me. But I don't recall the title or authors, otherwise I would link it here for you to see. :cool:
Quoting TonesInDeepFreeze
My point exactly. We have people speculating on what he meant, since what he wrote was wrong.
We don't know what he meant. One must always lie a little in order to simplify, and in this case the wrong judgment was made (IMO) as to what to lie about. Einstein would say he simplified too much.
How?
I wrote a long post about it here ...
https://thephilosophyforum.com/discussion/comment/514425
I couldn't add anything. Ok well I'll just give the tl;dr version. Boolos is trying to simplify the issue by talking about "the whole of math." That's incorrect. Consistency and provability are always relative to a given axiom system. PA can't prove its own consistency, but ZF proves PA consistent. ZF and ZFC can't prove their own consistency, but assuming an inaccessible cardinal proves ZFC consistent. And so forth. By omitting the fact that we are always working in a particular axiomatic system, the essence of the matter is ignored. That's a simplification too far in my opinion. Because the heart of the subject is axiomatic systems, and NOT "the whole of math." My opinion is supported by the fact that Kurt Gödel was a Platonist, and believed that there was a true fact of the matter for every mathematical proposition. For example he (and Cohen, for that matter) believed that the Continuum hypothesis is false; notwithstanding the fact that it's independent of ZFC.
Sure. I was assuming that by "the whole of math" Boolos meant simply the maximal (consistent) extension or union of all the systems you mention. Thereby saving himself the bother of translating "any system strong enough to satisfy the Hilbert-Bernays provability conditions" into words of one syllable.
Quoting fishfry
But on my assumption,
is hardly omitting the fact (of the relativity of proof to system).
What is that?
Haha. No? Not a plausible reading of "the whole of math"?
You said:
Quoting bongo fury
I don't know what that means or what that is. I asked in good faith for you to explain to me what that phrase means, with perhaps an example or two and some context. As it is I have no idea what this phrase means. So I asked.
What does that mean? I have no idea what "the maximal (consistent) extension or union of all the systems you mention" means. Are you saying you don't either?
One source says that the bit comes from a lecture he gave. It might have been a lecture for logicians and students who would understand that he means whatever theory one might take as encompassing the branches of mathematics, whether it's ZFC or, for category theory, ZFC+inaccesible_cardinal, or whatever.
The piece is just a bit of fun, a bit of a stunt - outlining some deep mathematics with just one syllable words - obviously not pretending to include all the specifics.
A simplification too far IMO, and as evidence, it was presented in this thread as being meaningful. A belief I corrected.
It is meaningful. People who understand that proof is relative, and who are already familiar with incompleteness, might appreciate that a brief spoken word bit doesn't have to provide all the qualifications.
That Godel was a platonist supports your opinion that Boolos's rhetorical lark is wrong and meaningless?
Of course. But that's not who the article is aimed at. I respect that you have a different opinion, this is not a hill I'm going to choose to die on.
Quoting TonesInDeepFreeze
It's a slow afternoon over here too. But since you asked ... yes. "The whole of math" includes the ultimate truth or falsity of any given proposition, irrespective of its provability in any given axiomatic system. If one is a Platonist, as Gödel was. As "the greatest logician since Aristotle," he'd never have agreed with what Boolos wrote, even in a lighthearted manner. Gödel doesn't strike me as much of a lighthearted person.
I hope you don't mind if I stop responding to this topic. I've said my piece and stand by my opinion.
It seems it wasn't an article but something from a lecture. In any case, I would allow him some liberties when the purpose is to have some rhetorical fun rather than purporting to be an academically rigorous article.
Quoting fishfry
Yeah, I don't think that's what's mean by Boolos.
And it wouldn't make sense anyway to take him that way, since there is no known axiomatic theory that upholds such a collection of truths.
Would it be fair for me to say that I'm perfectly willing to allow Boolos his rhetorical fun; but that I was perfectly justified, and in fact helpful to the discussion, to point out the error of a poster quoting Boolos as if the out-of-context paragraph were meaningful and true?
It's a little like Hilbert's hotel, which Hilbert mentioned only once in his life in a public lecture, and never mentioned again; versus the legions of philosophers and especially theologians like William Lane Craig, who make a living off misunderstanding it? Hilbert was having fun, but those who misinterpret or misuse the story need to be corrected. Likewise, my complaint isn't with Boolos having fun and grossly simplifying a complicated subject. It's with anyone who takes what he said so literally that they'd use it as a talking point in a discussion on incompleteness.
Quoting TonesInDeepFreeze
What do you think he meant? I think me meant exactly what the incompleteness theorems say, namely axiomatic systems meeting certain technical conditions. And instead of saying that, he used "the whole of math" in a nontechnical sense. He clearly did not mean for people to be quoting him in conversations about incompleteness.
What?
Cantor's diagonal argument is a reductio ad absurdum proof. The link to incompleteness results should be obvious.
I'm guessing he means constructive in the sense that, given any countable list of real numbers, one can construct a real number not on that list, from that list. This shows that every injection fails to be a surjection. (In the same way, Euclid gave a way to construct a prime not already on a list of prime numbers. )
That's the reference part.
Actually not. It can be expressed in positive form. It shows that for every list[math]^*[/math] of real numbers, there is some real number that's not on the list. Equivalently, no list of reals enumerates or contains all the reals. No reductio necessary. It's often presented as a reductio, which is why everyone think's that's a necessary feature of the argument.
(*) A list is an ordered set order-isomorphic to the natural numbers in their usual order 0, 1, 2, 3, .... That is, a list is countable by definition; and it's NOT some exotic alternative ordering like 0, 2, 4, 6, ..., 1, 3, 5, 7, ... in which all the evens precede all the odds.
Quoting TonesInDeepFreeze
Quoting T H E
What they said.
Quoting ssu
Yes, the Halting problem, the first incompleteness theorem, Cantor's theorem, etc. have all been subsumed into a category-theoretic framework as described here.
https://ncatlab.org/nlab/show/Lawvere's+fixed+point+theorem
There's a somewhat more accessible version of this idea here.
http://math.andrej.com/2007/04/08/on-a-proof-of-cantors-theorem/
An interesting historical note is that Cantor didn't invent the diagonal argument. It was invented by Paul du Bois-Reymond in 1875. He was investigating the growth rates of functions, essentially anticipating modern complexity theory in computer science. Although from the checkmarked answer on that page, maybe he didn't really invent the diagonal argument. It's kind of borderline.
https://hsm.stackexchange.com/questions/3812/did-du-bois-reymond-invent-the-diagonal-argument-before-cantor
You realize that you have just outed yourself as being of a certain age . . . :razz:
Quoting EricH
Is that an archaic movie quote, or something of antiquity?
I did - and whilst it's a novelty relating to a statement first imparted more than 4 decades prior to my arrival, it's unsurprising that this particular reference hasn't entirely obsolesced (thematically).