Questions about Gödel's incompleteness theorems and related topics.
22
votes
6answers
794 views
Why is the Continuum Hypothesis (not) true?
I'm making my way through Peter J. Cameron's seminal text "Sets, Logics and Categories" where he makes the statement that the Continuum Hypothesis (There does not exist a set with a cardinality less ...
2
votes
1answer
151 views
About a step in the proof of Gödel-Rosser Theorem.
I am reading about the Gödel-Rosser Theorem, i.e. the Rosser's refinement of first Gödel's incompleteness Theorem, which states that if $\mathbf{PA}$ is consistent then it is incomplete.
I am posting ...
13
votes
7answers
1k views
True vs. Provable
Gödel's first incompleteness theorem states that "...For any such system, there will always be statements about the natural numbers that are true, but that are unprovable within the system".
What ...
1
vote
2answers
134 views
How can you add 'not G' to a formal system without introducing omega inconsistency?
In any formal system S that is susceptible to Godel's proof, we can make a formula G which is undecidable. That should mean that we can add either $G$ or $\neg G$ as an axiom to S and still end up ...
5
votes
3answers
299 views
Is the negation of the Gödel sentence always unprovable too?
The incompleteness theorem says that certain theories+deduction system contain at least one sentence (the Gödel sentence "$G$"), which can't be proven (in the system in which it holds).
(i) Is ...
1
vote
2answers
184 views
Is there a non-contradictory non-trivial axiomatic system in which Gödel's theorem is undecidable?
Gödel's Incompleteness Theorem states that in any non-contradictory non-trivial axiomatic system there are certain statements or theorems whom cannot be proved in that system,
For example in ZFC, ...
0
votes
2answers
156 views
What is actually “relatively consistent”?
Gödel's incompleteness theorem states that: "if a system is consistent, it is not complete." And it's well known that there are unprovable statements in ZF, e.g. GCH, AC, etc.
However, why does this ...
2
votes
1answer
141 views
A qualitative, yet precise statement of Godel's incompleteness theorem?
I read online a statement to the effect that (I'm paraphrasing):
Goedel's incompleteness theorem shows that we cannot even have a complete and consistent theory for the natural numbers.
I am ...
3
votes
5answers
241 views
Gödel says: countable proofs, uncountable conjectures?
I thought I understood Gödel's Incompleteness Theorem to say:
Starting from ZF, there only a countable number of proofs you can write
The number of possible conjectures is uncountable.
Thus, ...
3
votes
3answers
251 views
Aftermath of the incompletness theorem proof
This is somewhat of a minor point about the incompletness theorem, but I'm always a little unsure:
So one proves that there is a formula which is unprovable in the theory of consideration. Okay, at ...
3
votes
1answer
69 views
properties of the provability predicate applied to open formulas
Good day!
Let $\mathrm{T}$ be a first-order theory which contains the Peano arithmetic and has a recursively enumerable set of axioms. It is well known that one can construct a predicate ...
5
votes
3answers
211 views
An ignorant question about the incompleteness theorem
Let me preface this by saying that I have essentially no background in logic, an I apologize in advance if this question is unintelligent. Perhaps the correct answer to my question is "go look it up ...
2
votes
2answers
115 views
What does the completeness of a system mean for the provability of certain statments?
Through the 16th to 19th centuries mathematicians tried to prove the Euclids parallel postulate from Euclid's other four postulates. In the beginning of the 19th century the mathematics community ...
0
votes
1answer
95 views
Why isn't GL system of provability logic reflexive?
Formula $\square p \rightarrow p$ (axiom T; corresponding to reflexive modal frames) is interpreted as "if p is provable, then p", or more precisely: for all realizations (all substitutions for $p$), ...
3
votes
1answer
113 views
The Penrose–Lucas argument
I was looking at the Penrose–Lucas argument as discussed on Wikipedia. It states:
In 1931, the mathematician and logician Kurt Gödel proved that any
effectively generated theory capable of ...
1
vote
1answer
90 views
Definition and meaning of “Proof Schema”, “Class Sign”
I'm a newbie in advanced mathematics, and I'm trying to understand Godel's theorem. I came across these two words which I couldn't understand clearly.
"Proof Schema" and "Class-Sign"
Can anybody ...
5
votes
1answer
259 views
Is there any direct application of Gödel's Theorems outside of logic?
Gödel's incompleteness theorems was a major achievement with ramifications outside the field of mathematics itself. Are there any direct applications of the theorem(s), or any of the methods pioneered ...
4
votes
0answers
119 views
Freeman Dyson's example of an unproveable truth
Freeman Dyson has claimed that
$\not \exists m,n Reversed(2^n) = m ^ 5 $
(where Reversed(l) just is the reverse of the digits of l in base 10), is probably an example of an unproveable truth ...
2
votes
1answer
219 views
Gödel's Incompleteness Theorem - Diagonal Lemma
In proving Gödel's incompleteness theorem, why does he needed the Diagonal Lemma or the Fixed Point Theorem for building a formula $\phi$ that spoke about itself? Can't this formula be built this way:
...
0
votes
1answer
246 views
Gödel Incompleteness Theorem - Primitive Recursive Functions
I'm currently studying Gödel's Incompleteness Theorem and I am in doubt about his use of primitive recursive functions.
To study it, i'm in the point of view of a system of predicate logic with the ...
2
votes
1answer
127 views
Differences between between concepts related to Gödel's Incompleteness theorems: self-referencing, diagonalization and fixed point theorem?
I am studying the proof of Gödel's first Incompleteness theorem at the moment and I don't understand the differences between self-referencing, diagonalization and fixed point related to Gödel's proof.
...
6
votes
3answers
131 views
If $T$ proves $\operatorname{Con}(ZFC)$, is $T$ at least as strong as set theory?
I am looking for either a proof of counterexample of this:
Lemma: Let $\pi$ be a faithful interpretation of $PA$ into $ZFC$, and let $PA'$ be the image of $PA$ under $\pi$. If there is a $T$ with ...
0
votes
1answer
130 views
Consistent but incomplete formal axiomatic systems
Is there any known consistent but incomplete formal axiomatic system apart of and simpler than one "capable of doing arithmetic"? Is it even possible?
Even if this capability of arithmetic were a ...
4
votes
0answers
69 views
An “internal” condition on $T$ so that for the standard provability predicate, $T$ proves $\text{Pf}(\underline S)$ implies $T$ proves $S$?
This is probably quite basic, but I'd like to make sure I got this right. Regarding the proof of Goedel's first incompleteness theorem, say that we have $T$ containing $PA$ effectively axiomatizable ...
1
vote
2answers
101 views
Is this incompleteness result easier to get than incompleteness of PA?
Gödel's theorem for Peano Arithmetic shows that (under consistency hypothesis on PA) there is a statement which cannot be proved or disproved within PA that is true under the standard model ...
11
votes
6answers
975 views
What philosophical consequence of Goedel's incompleteness theorems?
I want to write a philosophical essay centered about Goedel's incompleteness theorem. However I cannot find any real philosophical consequences that I can write more than half a page about. I read the ...
0
votes
0answers
101 views
Uniqueness of super godel numbers of $\varphi$ and $\neg \varphi$
Let $e_{0},e_{1},...,e_{n}$ be a sequence of wffs or other expressions. Code each $e_{i}$ by a regular godel number $g_{i}$, to yield a sequence of numbers $g_{0},g_{1},...,g_{n}$. Then encode this ...
0
votes
0answers
79 views
Relationship between $\Sigma_{1}$ and $\Pi_{1}$ functions (Logic)
I am working on the following homework problem for a logic class on Godel's incompleteness theorems and the following question is asked.
Is the converse of Theorem $13.1$ true? Explain.
Theorem ...
3
votes
0answers
125 views
Is there any recursive definition, using only addition, of the set of values of $x^2+y^2$?
There is a recursive definition of the set of squares which uses only addition:
$CS(x,y) := IS(x) \wedge IS(y) \wedge x \lt y \wedge \forall z: (x
\lt z) \wedge (z \lt y)⇒\neg IS(z)$
$IS(x)⇔ x=0 ...
7
votes
3answers
274 views
Can ZFC decide number theory?
Among the versions of the Incompleteness Theorem that I've seen are the following:
Assuming the Peano axioms are consistent (which they are, if we accept the existence of the natural numbers), there ...
2
votes
2answers
187 views
How it is posible that $\omega$-inconsistency does not lead to inconsistency
After wikipedia:
Theory is $\omega$-inconsistent if, for some property P of natural numbers, T proves P(0), P(1), P(2), and so on (that is, for every standard natural number n, T proves that P(n) ...
1
vote
4answers
253 views
Consistency VS Inconsistency , semantics and syntactics
What does it mean when we say that a set of formulas , Sigma , is Consistent , or Inconsistent ?
Is ...
2
votes
1answer
190 views
About Godel Incompleteness and Multiplication
Godel proved that every system strong enough to include standard arithmetic with multiplication is incomplete. But I've read that systems that do not include multiplication are complete. But ...
5
votes
1answer
196 views
Completeness of Real Number Arithmetic?
I've recently read that, although Godel Incompleteness holds for the theory of natural numbers, the theory of the real numbers is actually complete. So, why is Godel's Theorem still
considered ...
9
votes
2answers
941 views
Gödel's incompleteness theorem can't be proven?
I have a very simple question, that I still haven't found an answer to yet:
Gödel is said to have proven that Peano Arithmetic (or any system capable of expressing it) can't prove its own ...
2
votes
1answer
124 views
Why does the existence of independent statements not prove completeness?
I've read before that, by the Principle of Explosion, if a theory is inconsistent, then absolutely any statement can be proven within it.
Obviously, there are statements which are independent of ZFC ...
7
votes
2answers
675 views
Why Euclidean geometry cannot be proved incomplete by Gödel's incompleteness theorems?
Wikipedia mentioned the limitation of Gödel's theorems. According to it, Euclidean geometry doesn't satisfy the hypotheses of Gödel's incompleteness theorems, that is, it cannot define natural ...
4
votes
1answer
137 views
Does robinson arithmetic satisfy modal logic's “axiom 4”?
Does Robinson arithmetic prove the theorem "if sigma is provable then 'sigma is provable' is provable' for a fixed sentence sigma?
It's clear to me that you can get a primitive recursive function f ...
2
votes
1answer
128 views
How to express Con(PA) as a first-order statement?
I read from somewhere that
Fact 1. PA, which refers to the first-order version, is not finitely axiomatizable.
At the same time, the second incompleteness theorem says that there is no proof in ...
1
vote
1answer
142 views
Quantitative version of Godel's incompleteness theorem
Let $A$ be a list of axioms which we assume to be sound (for example,
PA or ZFC). Godel's incompleteness theorems imply that if we add
only finitely many (true) axioms to $A$, the new list $B$ will ...
2
votes
3answers
334 views
Classifying Types of Paradoxes: Liar's Paradox, Et Alia
The well-known Liar's Paradox "This statement is false" leads to a recursive contradiction: If the statement is interpreted to be true then it is actually false, and if it is interpreted to be false ...
11
votes
1answer
342 views
What's the theory in which incompleteness of PA is proved?
Maybe this is a dumb question, but I have to admit that it is not really clear to me what the theory is, in which incompleteness of PA and stronger theories is proved. The texts I did study so far are ...
6
votes
1answer
197 views
Best known theory for proving statements about natural numbers
Gödel's incompleteness theorems imply that there is no consistent theory that can be effectively generated and contains all true statements about the natural numbers.
Well, what known consistent ...
4
votes
3answers
630 views
Prove Gödel's incompleteness theorem using halting problem
How can you prove Gödel's incompleteness theorem from the halting problem? Is it really possible to prove the full theorem? If so, what are the differences between original proof and proof by ...
5
votes
4answers
539 views
A naive inquiry of Godel's incompleteness--or why does mathematics need proofs of unprovability?
My question stems from reading Swetz, 1994 (mostly excerpts from the journal Mathematics Teacher) and Berlinski, 2005 (a popular book on 10 most important mathematical breakthroughs in history).
1) ...
1
vote
1answer
151 views
Construction of a sequence of theorems with increasing and unbounded “difficulty”?
Let's define the "difficulty" of a theorem as the logarithm of the size of its shortest proof divided by the logarithm of the size of the theorem itself. For example, if a theorem has difficulty less ...
9
votes
2answers
242 views
How to show the existence of an infinite set of independent undecidable sentences?
How to show the existence of an infinite set of independent undecidable sentences?
By "independent" I mean that no implication between any two elements is provable. A finite set that satisfies the ...
4
votes
3answers
409 views
P vs NP and Goedel
I apologize for the, perhaps, silly question. My impression, as a layman, is that Godel Incompleteness Theorem should rule out the possibility that P=NP. Is that true or there are deeper technical ...
1
vote
1answer
279 views
Why is Godel's first theorem not a proof from the inside?
Why is Godel's first theorem not a proof for the truth of the so called undecidable proposition? You may say it's a proof from the outside, but if not all proofs from the outside be formalized inside ...
2
votes
1answer
375 views
Is Robinson Arithmetic complete and not-complete?
Is Robinson Arithmetic complete in the sense of Gödels completeness theorem? And is Robinson Arithmetic incomplete in the sense of Gödels first incompleteness theorem?
If RA is both it would be a good ...
