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

learn more… | top users | synonyms

10
votes
1answer
134 views

Is there a quicker argument from the HBL derivability conditions to the equivalence of fixed points of $\neg\Box$ to $\mathsf{Con}$?

I'm just about to send off the final, final corrected PDF of the second edition of my Gödel book, and the following (neurotic?!?) question occurs to me. In discussing matters around and about the ...
4
votes
2answers
214 views

Sequent calculus and first incompletness theorem

Wikipedia says that sequent calculus is sound and complete (http://en.wikipedia.org/wiki/Sequent_calculus#Properties_of_the_system_LK). Godel first incompleteness theorem says that system capable of ...
2
votes
1answer
102 views

When and why does the Lindenbaum extension construction fail for second order theories?

From any consistent set of first order sentences $\Gamma$, one may generate by an inductive process a unique set of sentences $\Delta(\Gamma)$ such that $\forall A, \Gamma \models A \implies A \in ...
9
votes
3answers
1k views

Consistency of Peano axioms (Hilbert's second problem)?

(Putting aside for the moment that Wikipedia might not be the best source of knowledge.) I just came across this Wikipedia paragraph on the Peano-Axioms: The vast majority of contemporary ...
13
votes
6answers
3k views

Why bother with Mathematics, if Gödel's Incompleteness Theorem is true?

OK, maybe the title is exaggerated, but is it true that the rest of math is just "good enough", or a good approximation of absolute truth - like Newtonian physics compared to general relativity? How ...
9
votes
3answers
379 views

“The set of all true statements of first order logic”

In one of my lectures, the lecturer put a bunch of examples of sets on the board, stuff like the set of all humans, set of all well typed programs in some programming language, the set of all true ...
3
votes
1answer
126 views

Question about $\Sigma_n$-soundness

According to wikipedia (http://en.wikipedia.org/wiki/%CE%A9-consistent_theory#Definition): "$\Sigma_n$-soundness has the following computational interpretation: if the theory proves that a program C ...
2
votes
1answer
134 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
185 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
168 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
208 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
208 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 ...
36
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
98 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", ...
4
votes
1answer
127 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
256 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
543 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
227 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
460 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
192 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
305 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
368 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
133 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
329 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
157 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
173 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
412 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
368 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
507 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
176 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
379 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
87 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
322 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
395 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
988 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 ...
5
votes
1answer
293 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
166 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
238 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 ...