# Tagged Questions

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

154 views

### What percentage of formulas is unprovable in a given axiomatic system?

I am trying to use language I am not familiar with, so bear with me. If I make no sense, I try to be clearer. Assume we are given a formal language. Assume $S$ is the set of every well-formed formula ...
399 views

### System with infinite number of axioms

Assume we have a set of axioms $A_0$. There exists a statement that can be formulated with these axioms that cannot be proven to be true with this system. Assume we give such a statement axiomatic ...
83 views

390 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 ...
299 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 ...
525 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 ...
173 views

I have a question about Gödel numbering, it is trivial but I would like to know how can you know the length of an expression through its Gödel number. ¿? I think you can use a recursive function but ...
148 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 ...
226 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 ...
221 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 ...
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 \... 1answer 100 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 ... 1answer 193 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 \Sigma_{n-1}-... 3answers 255 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 http://plato.stanford.edu/... 6answers 4k 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, ... 1answer 80 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 ... 1answer 228 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 ... 3answers 118 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 ... 5answers 2k 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? 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 ... 2answers 2k 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 ... 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 ... 1answer 198 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 ... 2answers 311 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 ... 7answers 4k 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 ... 1answer 384 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 ... 3answers 2k 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 ... 2answers 254 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, ... 2answers 1k 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 ... 3answers 781 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 ... 1answer 230 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 ... 5answers 362 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, ... 3answers 433 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 ... 1answer 176 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 \mathrm{Pr}... 5answers 1k 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 ... 3answers 405 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 ... 2answers 222 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 ... 1answer 197 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), ... 3answers 549 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 ... 1answer 272 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 ... 1answer 607 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 ... 1answer 338 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 ...
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: ...