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

learn more… | top users | synonyms

4
votes
1answer
249 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
421 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
96 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
313 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
55 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
211 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
441 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, ...
7
votes
2answers
204 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
165 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
76 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
58 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
158 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
222 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
147 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))?$$
4
votes
1answer
665 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
246 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
122 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
119 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
231 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
124 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
218 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
76 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
397 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 ...
4
votes
1answer
286 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
67 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
107 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 ...
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 ...
8
votes
1answer
314 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
2answers
202 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 ...
9
votes
3answers
378 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
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 ...
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 ...
1
vote
2answers
142 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
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
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 ...
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 ...
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 ...
16
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
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 ...
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?
4
votes
6answers
776 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 ...
20
votes
2answers
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 ...
6
votes
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 ...
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 ...