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

learn more… | top users | synonyms

6
votes
1answer
174 views

Are the Godel's incompleteness theorems valid for both classical and intuitionistic logic?

I am studying an undergraduate text about math logic. The proofs of the two Godel's incompleteness theorems are not completely formal: they are admittedly simpler that the real proofs. For what I ...
3
votes
2answers
194 views

Proving and understanding the Fixed point lemma (Diagonal Lemma) in Logic - used in proof of Godel's incompleteness theorem

http://en.wikipedia.org/wiki/Diagonal_lemma I am wondering about the proof of the "Fixed-Point Lemma" $\text{Mod } \Sigma$ is the class of all models of $ \Sigma$. $\text{Th Mod } \Sigma$ is the set ...
0
votes
1answer
44 views

Definability of Kolmogorov Complexity?

This paper claims to have a proof of Godel's Second Incompleteness Theorem using Kolmogorov Complexity: http://www.ams.org/notices/201011/rtx101101454p.pdf As far as I can tell, it seems to assume ...
4
votes
1answer
147 views

How to prove primitive recursive functions are definable in Peano Arithmetic?

Background: I'm working on a talk that presents Godel's first Incompleteness Theorem from a computability-theoretic perspective. The idea is to show that the first incompleteness theorem follows from ...
3
votes
2answers
297 views

Don't Gödel's completeness and incompleteness theorems contradict each other? [duplicate]

Gödel's completeness theorem: Given a set of axioms, if we cannot derive a contradiction, then the system of axioms must be consistent. Gödel's incompleteness theorem:'Given any consistent, ...
4
votes
1answer
93 views

Incompleteness theorem and $\mathbb{L}$.

Let $\alpha > \omega$ and $u = \{\ulcorner \sigma \urcorner : \sigma \in \mathrm{Th}(\mathbb{L}_\alpha, \in)\} \subseteq \omega$, where by $\mathbb{L}_\alpha$ we denote as usual the constructible ...
6
votes
2answers
273 views

Can an unprovable statement be interpreted as being generally true in some cases?

For example, let's say that Goldbach's conjecture turns out to be unprovable. This would mean that a program cannot devise a way to check whether any counterexample exists. This seems to mean that ...
1
vote
1answer
50 views

Can ZFC+A and ZFC+negation of A be both inconsistent where A is some conjecture?

So I know that a conjecture/statement or negation of it plus ZFC can both turn out to be consistent, which means that a statement is not provable. But I would like to go opposite way - and let's say ...
1
vote
1answer
154 views

Decidable and recursively-axiomatizable theories

A few questions: If $T$ is a decidable and consistent theory, can there be any theory $T' \subset T$ that isn't decidable? Is there a decidable theory which isn't complete? How can I prove that any ...
10
votes
2answers
323 views

Is Gödel's incompleteness theorem provable without any model-theoretic notion?

The entry on Gödel's incompletenss theorem in Wikipedia says: Any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete. In particular, ...
6
votes
2answers
167 views

How is the standard model of number theory specified, and why can't we use that specification to prove any number theoretical sentence of interest?

According to Gödel's incompleteness theorem, there exists a sentence $G$ in the vocabulary of number theory ($N$) which is not provable from any (recursively enumerable) consistent set of axioms $T$, ...
5
votes
3answers
153 views

Gödel's incompleteness wrt weakend versions of ZFC

Suppose for the sake of argument that we look at ZFC with the axiom of infinity removed. http://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems#First_incompleteness_theorem ...
3
votes
1answer
70 views

Complexity of transforming an indirect proof into a direct one

Suppose that ZFC is consistent, and let ZFC'=ZFC+Con(ZFC). We can define a reasonable notion of the length of a proof inside ZFC', such that for any $n$ the set $P_n$ of all proofs of length $\leq n$ ...
4
votes
1answer
57 views

Special undecidability situation

Suppose that ZFC is consistent, and let ZFC'=ZFC+Con(ZFC). Can one construct two statements $\phi_1$ and $\phi_2$ such that $$ ZFC' \vdash ((ZFC \vdash \phi_1) \ \text{or} \ (ZFC \vdash \phi_2)) $$ ...
3
votes
2answers
135 views

Does $\Sigma_1 \cup \Pi_1$ generate the complete first order theory of arithmetic?

If a set $T$ of sentences in the language of arithmetic is deductively closed under the usual inference rules of first order logic, and includes all true $\Sigma_1$ sentences and all true $\Pi_1$ ...
6
votes
4answers
176 views

Second order logic question.

I'm reading Michael Potter's book "Set Theory and its Philosophy" and where he's explaining why he chose to use first-order predicate calculus with identity instead of second order logic to reason ...
2
votes
3answers
137 views

If $\newcommand\PA{\mathrm{PA}}\newcommand\Con{\operatorname{Con}}\Con(\PA)$, then $\Con(\PA+\Con(\PA))$?

Assume that $\PA$ is consistent. Then we know that $\PA$ cannot prove $\Con(\PA)$. I was wondering. Can $\PA$ prove that $$\Con(\PA) \Rightarrow \Con(\PA + \Con(\PA))?$$
3
votes
1answer
454 views

Are Real Numbers axioms a consistent or complete system?

Do we know if the axioms of the real numbers are consistent, complete or neither of both? And if so, is it a consequence of Godel's theorem or of something else?
7
votes
2answers
219 views

Proof of Proposition/Theorem V in Gödel's 1931 paper?

Proposition V in Gödel's famous 1931 paper is stated as follows: For every recursive relation $ R(x_{1},...,x_{n})$ there is an n-ary "predicate" $r$ (with "free variables" $u_1,...,u_n$) such that, ...
4
votes
1answer
95 views

How many digits of Chaitin's $\Omega$ constant would we know if we had a $\Sigma_1$-Oracle?

According to Wikipedia (and it seems intuitive from the definition itself), $\Omega$ is Turing equivalent to the halting problem and thus at level $\Delta_2^0$ of the arithmetical hierarchy. Do this ...
3
votes
2answers
110 views

Talking about Gödel's incompleteness theorems…

I will give a talk about Gödel's incompleteness theorems to a group of people consisting of undergraduates of mathematics, graduates of informatics and etc (they are not really familiar with the ...
4
votes
1answer
171 views

Understanding the syntactical completeness

A formal system is syntactically complete if for each sentence (closed formula) $\varphi$ either $\varphi$ or $\lnot \varphi$ is provable. A formal system is semantically complete if every ...
2
votes
2answers
109 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 ...
3
votes
1answer
170 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 ...
1
vote
1answer
75 views

One cannot know if a number could be written any shorter according to Gödel's incompleteness theorem

I am reading Tor Nørretranders (cannot find the English version, sry) and he states that Gödel's incompleteness theorem implies that we cannot know if we can write a number any shorter (e.g. ...
0
votes
1answer
390 views

URM computable indicating RAM computability

How can we show that every URM computable function is RAM computable? I can see that that from Church's thesis, URM Computability iff p.r., but now sure how to get this claim above. Taking the hint ...
3
votes
1answer
252 views

Gödel Completeness theorem

I realized recently that I did not understand well the completeness theorem of Godel, and how it interacts with the incompleteness theorems. What I understand now (and you will see my understanding ...
0
votes
1answer
62 views

Completeness and consistency of system of calculus

It is widely held that ZFC cannot be shown to be self-consistent or complete. So, what happens to the system of calculus? Can it be shown to be complete or self-consistent? (Edit: Oops. So, two ...
7
votes
2answers
102 views

Is Goedel term (in incomleteness theorem) both true and unproveable?

In Goedel incompleteness theorem is Goedel term both true and unproveable, or just unproveable and truth neutral? Can we add Goedel term to the theory as axiom and get new theory? Can we add Goedel ...
9
votes
1answer
122 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
187 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
88 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
292 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 ...
0
votes
1answer
159 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
304 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
116 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
111 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
89 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
164 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
90 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
151 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
187 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
75 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
188 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
750 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
90 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
913 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
613 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 rieman hypothesis. I have a feeling it's not possible but I want to know for sure. Thanks in ...