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

learn more… | top users | synonyms

2
votes
1answer
133 views

question about Godel numbering

I have a question about Godel numbering, it is trivial but I would like to know how can you know the length of an expression through its Godel number. ¿? I think you can use a recursive function but ...
1
vote
2answers
182 views

I do not understand why the Turing computable sets of N are exactly the sets at level $\Delta_1^0$ of the arithmetical hierarchy

The reason I don't understand it is this. Take for example the twin primes conjecture, which is $\Pi_2^0$. The set of twin primes is computable right? (there is a Turing machine that enumerates all of ...
1
vote
1answer
96 views

Is there a mechanical procedure within PA to reduce any ϕ to its simplest (in terms of the arithmetical hierarchy) logically equivalent form?

The question is motivated because we know that the Turing computable sets of natural numbers are exactly the sets at level $\Delta_1^0$ of the arithmetical hierarchy. We also know that the finite ...
1
vote
1answer
38 views

Finding polynomials with a specific property

I am stuck with the following problem. Show that there exist a $n \in \mathbb{N}$ and polynomials $p,q \in \mathbb{N}[x_1,\ldots,x_n]$ such that neither the formula $$ \phi(n,p,q) = \forall x_1 ...
4
votes
1answer
167 views

Is every φ above the second level of the arithmetical hierarchy independent of PA?

If I am not wrong, every $\Sigma_n$ (or $\Pi_n$ ) statement $\phi$ is equivalent to a statement that says that a given Turing machine halts (or doesn't halt) on input $C$ using a ...
1
vote
3answers
201 views

What is it wrong in this argument about the interpretability hierarchy?

This is a question that I fully reedited to make it more precise. Many thanks to the people that answered the previous version to get this distilled one. Background: (from ...
1
vote
1answer
77 views

Given a φ independent of PA which is true in the standard model, will always (PA+ ¬φ) be Σn-unsound for some n?

Given a φ independent of PA which is true in the standard model, will always (PA+ ¬φ) be Σn-unsound for some n? This is a follow up from a previous question: Given a φ independent of PA which is true ...
9
votes
1answer
206 views

Given a φ independent of PA which is true in the standard model, will always (PA+ ¬φ) be ω-inconsistent?

Given a φ independent of PA which is true in the standard model, will always (PA+ ¬φ) be ω-inconsistent? Does it mean that every such ¬φ can be used to prove that a Turing machine halts on a given C ...
35
votes
5answers
6k views

Understanding Gödel's Incompleteness Theorem

I am trying very hard to understand Gödel's Incompleteness Theorem. I am really interested in what it says about axiomatic languages, but I have some questions: Gödel's theorem is proved based on ...
2
votes
3answers
96 views

Provability becoming decidable in a larger system?

Let $T$ be an effectively axiomatizable system that we believe to be consistent, and expressive enough so that Godel’s theorem applies to it. Then we have that the provability statements related to ...
9
votes
5answers
1k views

What does it mean for something to be true but not provable in peano arithmetic?

Specifically, the Paris-Harrington theorem. In what sense is it true? True in Peano arithmetic but not provable in Peano arithmetic, or true in some other sense?
2
votes
2answers
1k views

Explanation of proof of Gödel's Second Incompleteness Theorem

I am looking for a simple explanation/outline of the proof of Gödel's Second Incompleteness Theorem, and I haven't yet been able to find anything that is within my grasp. I'm looking for something ...
1
vote
1answer
257 views

Use of undecidability

Suppose someone proved that the Goldbach conjecture was undecidable in an axiomatic system that is consistent as far as we know. Then in some sense we know that Goldbach conjecture must be "true", ...
3
votes
1answer
122 views

Can decidability results for monadic second-order logic be extended to monadic higher-order logics?

Call a higher-order logic fully monadic if and only if all of its predicate constants (at any order) and higher-order variables (at any order) are monadic (and it has no function symbols). In Solvable ...
8
votes
2answers
270 views

Axiomatic system and Hilbert's 2nd problem

Hilbert's second problem asks if the axioms of arithmetic are consistent. Has this problem been resolved? Shouldn't an axiomatic system ideally be consistent and complete(given that we have the ...
2
votes
1answer
250 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 ...
15
votes
7answers
2k 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
161 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
526 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
225 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
426 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
190 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 ...
4
votes
5answers
302 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, ...
4
votes
3answers
362 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
129 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
327 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 ...
0
votes
1answer
155 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$), ...
1
vote
1answer
165 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
401 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 ...
2
votes
1answer
350 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
497 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
173 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
149 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
359 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
86 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 ...
13
votes
6answers
2k 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 ...
7
votes
3answers
320 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
385 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
944 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 ...
3
votes
1answer
308 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
290 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
1k 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 ...
4
votes
1answer
165 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 ...
3
votes
1answer
237 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
166 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 ...
12
votes
1answer
425 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
223 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 ...
6
votes
3answers
1k 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 ...
6
votes
4answers
684 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) ...
2
votes
1answer
183 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 ...