Questions about Gödel's incompleteness theorems and related topics.

learn more… | top users | synonyms

0
votes
0answers
37 views

Does Gödel sentence depend on numbering?

If we change Gödel's numbering definition of the $Prov$ predicate will change as well, but the meaning won't. How is that going to affect $G$? It seems to me like it will change as it is actually ...
1
vote
0answers
36 views

Is there a consistent arithmetically definable extension of PA that proves its own consistency?

Gödel's second incompleteness applies, for instance, to r.e. extensions of PA. I am wondering if it applies more generally to arithmetically definable extensions of PA. I see that there is a complete ...
1
vote
3answers
61 views

Gödel's Incompleteness Theorem and Numerical Analysis

I am no expert in Mathematical Logic so I can't really express my question formally but I do hope that it will make sense. As far as I know the implication of Gödel's incompleteness theorem for ...
1
vote
1answer
74 views

Is there a difference between induction in Peano Arithmetic and Presburger Arithmetic

Following this question I still do not get clearly the difference between defining exponentiation in PA but impossiblity of recursively define multiplication in Presburger Arithmetics I was thinking ...
2
votes
1answer
32 views

Does the existence of uncomputable functions imply that a theory is incomplete?

For example Kolmogorov complexity is uncomputable and Chaitin used that fact to prove incompleteness. If this is not the case, can you give me a counter example? Set of axioms is countable.
3
votes
2answers
80 views

What is wrong with this deduction of $\text{ZF} \vdash \text{Cons ZF}$

I realize from the answer to this post that the fallacy in my "proof" of "ZF is inconsistent" was that I was not considering that there are models with non-standard integers. However now I think I ...
53
votes
12answers
7k views

What is a simple example of an unprovable statement?

Most of the systems mathematicians are interested in are consistent, which means, by Gödel's incompleteness theorems, that there must be unprovable statements. I've seen a simple natural language ...
2
votes
2answers
60 views

Trying to understand self-reference as it relates to Godel's Second Incompleteness Theorem

As noted in this post, I'm trying to understand how a sufficiently powerful consistent theory $T$ can prove statements about itself without contradicting Godel's Second Incompleteness Theorem. Let ...
0
votes
2answers
65 views

Is it possible to formalize $T \models \sigma$ within the deductive calculus?

I know that the notion of $T \vdash \sigma$ is formalizable within any sufficiently powerful theory $T$ but is $T \models \sigma$ formalizable as well? How is this possible if there are infinitely ...
1
vote
2answers
48 views

What does this deduction involving provability imply?

I recently asked this question asking why my reasoning for ZF being inconsistent was wrong. I didn't realize that we have to account for models with non-standard integers. However, I'm left with the ...
7
votes
1answer
80 views

What's wrong with this proof of ZF being inconsistent?

I'm studying (independently) mathematical logic and in investigating self-referential statements I developed a result which I don't know how to interpret. I'll use the notation from Enderton's "A ...
6
votes
5answers
753 views

Proving Undecidability of first order logic without first proving it for arithmetic.

All text I have read prove the Undecidability of first order logic a bit as an afterthought and after having proved the incompleteness and Undecidability of (Peano) Arithmetic. This proof also ...
4
votes
6answers
1k views

Can we prove that a statement cannot be proved?

Is it possible to prove that you can't prove some theorem? For example: Prove that you can't prove the Riemann hypothesis. I have a feeling it's not possible but I want to know for sure. Thanks in ...
0
votes
1answer
93 views

Analogy between a Gödelian puzzle and Gödel's first incompleteness theorem

I'm studying Gödel's incompleteness theorems. And I have the following slide that defines a version of Gödel's first incompleteness theorem. The point is that one can always follow the math and get ...
0
votes
2answers
66 views

How can Godel's theorem apply to every formal system?

How can Godel's theorem apply to any formal system of logic, if the truth of the theorem itself is only relative to the axioms and rule of inference that were used to generate it. In other words ...
1
vote
1answer
38 views

Expanding arithmetic to a complete theory by a transfinite sequence of expansions.

We all know that Godel first incompleteness theorem states that any recursive sufficiently strong theory to express arithmetic is incomplete. in particular, arithmetic is not complete. It's common ...
1
vote
2answers
75 views

How does Gödel's second incompleteness apply to any theory containing arithmetic?

If I understand correctly, there are two facts proven by Gödel's second incompleteness theorem, for a formal theory containing arithmetic 1) It is possible to express the consistency of the theory ...
11
votes
4answers
1k views

How does Gödel Completeness fail in second-order logic?

So a while ago I saw a proof of the Completeness Theorem, and the hard part of it (all logically valid formulae have a proof) went thusly: Take a theory $K$ as your base theory. Suppose $\varphi$ ...
0
votes
1answer
49 views

Gödel's Incompleteness theorem in modal logic

I think I once taught that the statement of the Gödel's Incompleteness theorem is equivalent to : $ \diamond \neg \square \square p $, if p is a complex enough system. Is this right?
2
votes
1answer
48 views

Is there a result for second-order theories analogous to Gödel's second incompleteness theorem?

One formulation of Gödel's second theorem says that, if $T$ is a consistent, axiomatisable extension of $PA$, and then $T$ cannot prove $\neg Prv(\ulcorner 0=1 \urcorner)$, where $Prv(-)$ is a ...
5
votes
2answers
755 views

What does Gödel's Incompleteness Theorem prove?

Does Gödel's incompleteness theorem only prove that you can't have a formal system which describes number theory which is both complete and consistent, or is it more general? In other words: does it ...
0
votes
0answers
26 views

Arithmoquine function in Gödel's proof

Could someone explain as detailed as possible how the Arithmoquine{a,a'} function works or is the defined in Gödel's proof of the incompleteness theorem? To describe my question better... In this ...
20
votes
7answers
3k 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 ...
0
votes
1answer
30 views

How to show factorial is recursive?

In my textbook Fact : Given recursive $G:\omega^{n}\rightarrow\omega$ and $H:\omega^{2}\times\omega^{n}\rightarrow\omega$ , a function $F:\omega\times\omega^{n}\rightarrow\omega$ defined by ...
1
vote
1answer
52 views

understanding gödel's 1931 paper - number theoritical formulae

I am reading a translation of Gödel's original paper about in completeness theorem and there are a couple things i don't understand. Here is the document i am using primarily : ...
1
vote
0answers
22 views

How to show that F is recursive?

In the road to Godel's incompleteness theorem, Problem saying: Show that Frame For $G:\omega\times\omega\times\omega^{n}\rightarrow\omega$ a recursive function, the function ...
9
votes
1answer
309 views

Gödel's Second Incompleteness Theorem and Arithmetically Non-Definable Theories

My recursion theory knowledge has become a bit rusty, so I will appreciate any corrections for misstatements. Gödel's incompleteness theorem is often exploited by philosophical discussions which ...
0
votes
1answer
44 views

Can any statement about natural numbers be written in TNT?

I was trying to understand Godel's theorem from here Godel's First Incompleteness theorem. I still do not completely understand the theorem, but have a broad idea about it. As the link mentions ...
1
vote
1answer
30 views

What is the diagonalization of ‘∀x¬Gdl(x,y)'?

Correct me if I am wrong here.‘∀x¬Gdl(x,y)' simply states that There does not exist godel number for a given number y, right? So if we say that there exist a diagonalization of ‘∀x¬Gdl(x,y)', then we ...
3
votes
1answer
134 views

How to show incompleteness of second order logic?

I'm trying to see/show that second order logic (with full semantics) is incomplete - i.e. that there are sentences that are true in all models of some theory $T$, and yet still can not be proved from ...
6
votes
1answer
89 views

How do inconsistent arithmetics get around Gödel incompleteness?

Gödel theorems imply that arithmetic can not be complete under recursive axiomatization and consistency assumptions. Unexpectedly, consistency can be dropped in a meaningful way by switching to a ...
6
votes
3answers
2k views

are there non-standard models of arithmetic in second order arithmetic?

non-standard models of arithmetic in second order arithmetic? Background: According to Godel's theorem, if we have, in a given consistent system S, a non-provable wff. A, then we can extend the ...
4
votes
1answer
70 views

Proving that the existence of strongly inaccessible cardinals is independent from ZFC?

ZFC can't prove that strongly inaccessible cardinals exist, or else it would prove that a model of itself exists and hence $Con(ZFC)$. So this leaves us with two options: ZFC proves there are no ...
5
votes
0answers
51 views

Vaught's essentially undecidable set theory

Today I was reading this paper, which includes discussion of essential undecidability of various weak theories. On page 24, I was surprised to find out that Vaught has showed that set theory with the ...
21
votes
3answers
2k views

Why is Gödel's Second Incompleteness Theorem important?

Given that the consistency of a system can be proven outside of the given formal system, Gödel says, It must be noted that proposition XI... represents no contradiction to the formalities ...
2
votes
2answers
90 views

understanding gödel's 1931 paper - gödel numbers

I am a little confused about gödel numbers and what numbers exactly we are manipulating. are the numbers "real" natural numbers (than we obviously represent as) 1, 2, ... or are we always dealing ...
3
votes
1answer
142 views

understanding gödel's 1931 paper - the undecidability theorem

I am reading a translation of Gödel's original paper about in completeness theorem and there are a couple things i don't understand. Here is the document i am using primarily : ...
0
votes
1answer
68 views

Concerning the canonical example for Gödel's first incompleteness theorem

Concerning the canonical example for Gödel's first incompleteness theorem: G cannot be proved within the theory T If G were provable under the axioms and rules of inference of T, then T would ...
0
votes
1answer
88 views

understanding gödel's 1931 paper - elementary formulae

I am trying to understand Gödel's first incompleteness theorem from his original 1931 paper. Here is a translation i am using for my studies : ...
3
votes
2answers
48 views

Gödel's theorems and nonstandard model of $PA$

According to the Second incompleteness theorem $Con(PA)$ is independent of $PA$. So if $PA$ is consistent $PA + \neg Con(PA)$ is also consistent which means that there exist a number $t$ which codes a ...
0
votes
1answer
57 views

understanding gödel's 1931 paper - proof of theorem / proposition V 5

I am trying to fully understand gödel's proof of the first incompleteness theorem from it's original 1931 paper. Here is the document I am using : ...
0
votes
0answers
37 views

Standard model of the Meta theory in the proof of arithmetic incompleteness

I have a question about the incompleteness of arithmetic. I wonder in which meta theory we are reasoning. For example, if we are in ZFC, then there are some non standard models of ZFC. As far as I ...
0
votes
0answers
20 views

Completeness of the space $C_{2\pi} \left ( \mathbb{R} \right )$ [duplicate]

Denote $C_{2\pi} \left ( \mathbb{R} \right )$ is the set of complex-value, continuous on $\mathbb{R}$, periodic functions with period $2\pi$. Fix $p \in \left [1, \infty \right )$. For each $x \in ...
11
votes
2answers
123 views

Proportion of true statements that are provable

In an axiomatic system, there are true statements, some but not all of which are provable. Is there any sense in which we can quantify the proportion of those statements that are true? Here's an ...
1
vote
1answer
59 views

Infinitely many nonequivalent unprovable statements in ZFC because of Gödel's incompleteness theorem?

Am I right in thinking that there are countably infinitely many nonequivalent unprovable statements in ZFC due to the Gödel's first incompleteness theorem? If not, why?
1
vote
3answers
118 views

[Paradox]How can Godel prove that Godel sentence is unprovable but true, if such proof itself proves that Godel sentence is true?

Isn't the proof that Godel sentence is unprovable but true a proof itself that Godel sentence is true? Godel in the preface of his proof remarked: “From the remark that [the unprovable statement] ...
3
votes
2answers
89 views

understanding gödel's 1931 paper - primitive recursive functions - projection and equality

I am reading a translation of gödel's original, and i'm a bit confused about the primitive recursive functions. Everywhere on the internet (or some resources like courses/classes i could put my hands ...
3
votes
1answer
149 views

What does a Godel sentence actually look like?

My understanding is that Godel's first theorem says that there is a sentence that is in a sense true in a formal system F but cannot be derived in that system. I then hear that Godel actually goes on ...
0
votes
1answer
55 views

understanding gödel's 1931 paper - primitive recursive functions “FR(x)” and “n Gl x”

I am trying very hard to fully understand gödel's paper on the incompleteness theorem. I have a slight technical question about one of the 45 primitive recursive functions introduced to build the ...
0
votes
1answer
38 views

Godel's Incompleteness Theorem and Algorithms [closed]

According to Godel's incompleteness theorem, not every problem can be solved using algorithms. How do we know if a problem can be solved using algorithm? How do we know that NP problems are ...