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

learn more… | top users | synonyms

9
votes
1answer
126 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
193 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
91 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 ...
8
votes
1answer
302 views

Gödelian incompleteness; Smullyan's Puzzle

I am currently doing exercises on the Gödelian theorems; and we are confronted with the introductory puzzle of R. Smullyan's book, which is as follows: Suppose we have a machine which prints strings ...
1
vote
1answer
171 views

Gödel's Incompleteness Theorem — meta-reasoning “loophole”?

Gödel's Theorem says that I can construct a mathematical statement like "f(x1,x2,...,x_n)=0 has no integer solution", where it is impossible (in a certain system of axioms) to formally prove that it's ...
8
votes
3answers
321 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 ...
2
votes
1answer
123 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 ...
3
votes
1answer
118 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 ...
1
vote
2answers
121 views

Question about computability of true/provable formulas

I would like to clarify some things related to the computability of the sets of all theorems and true formulas for the formal arithmetic. Consider the theory $T$ of formal arithmetic (the theory of ...
1
vote
2answers
171 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
37 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 ...
1
vote
1answer
95 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 ...
4
votes
1answer
165 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
194 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 ...
15
votes
6answers
2k views

Does Gödel's Incompleteness Theorem really say anything about the limitations of theoretical physics?

Stephen Hawking believes that Gödel's Incompleteness Theorem makes the search for a 'Theory of Everything' impossible. He reasons that because there exist mathematical results that cannot be proven, ...
1
vote
1answer
76 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
193 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 ...
2
votes
2answers
785 views

Is Gödel's theorem invalid? [closed]

Right now I've skim through Gödel's theorem is invalid by Diego Saá on arXiv (freely available). As it seems very plausible, I ask for any references and scrutinizations of the paper.
2
votes
3answers
92 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?
4
votes
6answers
669 views

prove that it's not provable

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 ...
17
votes
3answers
1k views

What is the prerequisite knowledge for learning Godel's incompleteness theorem

I am very interested in learning the incompleteness theorem and its proof. But first I must know what things I need to learn first. My current knowledge consists of basic high school education and the ...
5
votes
3answers
1k 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 ...
3
votes
1answer
106 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
257 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 ...
31
votes
6answers
2k views

Why is the Continuum Hypothesis (not) true?

I'm making my way through Thomas W Hungerfords's seminal text "Abstract Algebra 2nd Edition w/ Sets, Logics and Categories" where he makes the statement that the Continuum Hypothesis (There does not ...
2
votes
1answer
219 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 ...
8
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 ...
1
vote
2answers
218 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
358 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 ...
5
votes
3answers
480 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 ...
2
votes
1answer
184 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
289 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
335 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
113 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 ...
10
votes
5answers
956 views

Is there a proof of Gödel's Incompleteness Theorem without self-referential statements?

For the proof of Gödel's Incompleteness Theorem, most versions of proof use basically self-referential statements. My question is, what if one argues that Gödel's Incompleteness Theorem only matters ...
5
votes
3answers
304 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
150 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
141 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
177 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
148 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
376 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 ...
9
votes
1answer
268 views

Freeman Dyson's example of an unprovable truth

Freeman Dyson has claimed that $$\nexists m,n \operatorname{Reversed}(2^n) = m ^ 5 $$ (where $\operatorname{Reversed}(l)$ just is the reverse of the digits of $l$ in base 10), is probably an ...
2
votes
1answer
327 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
445 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 ...
1
vote
1answer
177 views

Consequences of Incompleteness.

Suppose that I'm a working mathematician that has just proved a Theorem, say, in Number Theory. Does Gödel's Incompleteness Theorem imply that I can't know for sure if there exists a proof of the ...
0
votes
1answer
316 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 ...
6
votes
3answers
148 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 ...
4
votes
0answers
82 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
204 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 ...