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

learn more… | top users | synonyms

7
votes
0answers
120 views

Elementary references on Robinson Arithmetic, Prim. Recursive fns etc.

I'm in the middle of revising my freely available and much-downloaded introductory notes Gödel Without (Too Many) Tears. (They are a sort of cut down version of part of my Gödel book, and I'm ...
2
votes
1answer
151 views

Any “natural” examples of true statements in number theory not provable in 2nd order systems?

I know that there are a few theorems in number theory that are somehow known to be true, but have been shown not to be provable in first-order Peano arithmetic (PA). Have any so-called "natural" ...
1
vote
2answers
74 views

Is this possibility ruled out by Godel's Incompleteness Theorem?

From Wikipedia: "The first incompleteness theorem states that no consistent system of axioms whose theorems can be listed by an "effective procedure" (e.g., a computer program, but it could be any ...
9
votes
1answer
183 views

What was the planned topic of Gödel's second paper on incompleteness?

Gödel's incompleteness theorems first appeared together in a paper titled (translated to English) "On formally undecidable propositions of Principia Mathematica and related systems I," with the Roman ...
3
votes
1answer
118 views

Non-self-referential undecidable sentences in arithmetic

Are there any known undecidable sentences for PA are neither "self-referential" (like a sentence equivalent to its own nonprovability) nor imply consistency of PA (like in the Paris Harrington ...
1
vote
1answer
137 views

Questions on a sentence in ZFC asserting that ZFC has a model

Question 1. Let $\operatorname{con}(\mathsf{ZFC})$ be a sentence in $\mathsf{ZFC}$ asserting that $\mathsf{ZFC}$ has a model. Let $S$ be the theory $\mathsf{ZFC}+\operatorname{con}(\mathsf{ZFC})$. ...
2
votes
1answer
84 views

Expressibility; Incompleteness of Peano Arithmetic

I'm working through Peter Smith's book, 'An Introduction to Godel's Theorems'. One small issue I've encountered is how the notion of expressibility is used to prove the incompleteness of Peano ...
6
votes
2answers
146 views

Formalizing proof of Godel sentence's non-provability?

In the question What does it mean for something to be true but not provable in peano arithmetic? Henning Makholm states, "...he [Godel] gave a (formalizable, with a few additional technical ...
5
votes
1answer
179 views

Explain/illustrate Goedel's theorems and possible implications to non-mathematicians

I am asked to give a talk about (a) mathematical practice, (b) axiomatization, (c) Gödel's theorems and (d) possible antimechanist arguments based on the incompleteness theorems (as mentioned in P ...
1
vote
1answer
43 views

Can we determine which statements are incomplete due to Godel?

Due to Godel's incompleteness theorems we know that there are true statements in a system that cannot be proven with that system. My questions are 1) can we tell which statements in a system are the ...
5
votes
1answer
112 views

Impossibility of theories proving consistency of each other?

By Godel's second incompleteness theorem, a consistent theory (to which the theorem applies) cannot prove itself consistent. I learned that it's also impossible to have a pair of consistent theories ...
2
votes
2answers
83 views

Why does undecidability of arithmetic not follow from that of first-order logic?

As far as I understand, first-order arithmetic incorporates first-order logic. It is a fact that a first-order logic with at least two binary predicates is undecidable. Doesn't this imply immediately ...
5
votes
4answers
148 views

Is every theorem of PA true in the standard model of number theory $N$?

My understanding is that every theorem $\phi$ of $PA$ is true in $N$ because $N$ is a model for $PA$, $N\models PA$. By completeness of first order logic, "$PA\vdash\phi$" implies that "if $N\models ...
4
votes
1answer
255 views

Under the impact of Gödel's incompleteness theorems, are the conclusions of statistics reliable?

After I read the Gödel's incompleteness theorems, I am confused about the following: Could you tell me if the conclusions of mathematical statistics are reliable? Gödel's incompleteness theorems ...
0
votes
1answer
42 views

Are there complete formal systems?

I am relatively new to logic, so forgive my ignorance. My question is: Are there any formal systems that are deemed complete? If so, how did we prove they were complete and which are they?
2
votes
1answer
42 views

Completeness of a Sub Theory of Number Theory

When I was an undergraduate I had a philosophy professor tell me that if you took the axioms of number theory with only addition or only multiplication then the resulting theory was decidable. It is ...
2
votes
2answers
127 views

clarify the term “arithmetics” when talking about Gödel's incompleteness theorems

I am not quite sure what really is meant when talking about "arithmetics" in context of Gödel's incompleteness theorems. How I so far understand it: Gödel proved that every sufficiently powerful ...
0
votes
1answer
94 views

differentiate the terms deductive system, model/structure, formal system, first-order logic

I can not bring the terms deductive system, model/structure, formal system, first-order logic into order in my head ;-) It seems to me that they are not overly used in a consistent manner and ...
2
votes
0answers
84 views

Minimal number of variables in a ZFC-undecidable sentence?

Let $\phi$ be a sentence of set theory. In Prenex form, $\phi$ can be written $$ {\bf Q}_1 x_1 {\bf Q}_2 x_2 \ldots {\bf Q}_n x_n \ \ \psi(x_1,x_2, \ldots ,x_n) $$ where each ${\mathbf Q}_i$ is ...
10
votes
1answer
170 views

Problem with completeness theorem and $\mathsf{Con(ZFC)}$

Using the reflection theorem we can prove in $\mathsf{ZFC}$ that for any finite $\Lambda\subseteq\mathsf{ZFC}$ there is some limit ordinal $\gamma$ such that $R(\gamma)\models\Lambda$. Then by the ...
2
votes
1answer
55 views

Are forcing techniques possible to automate for mechanized reasoning?

Looking at Cohen's success at proving independence of the Axiom of Choice and the Continuum Hypothesis, I was wondering if it was possible to mechanize forcing techniques for the purpose of proving ...
6
votes
2answers
180 views

What is the notion of truth used in Godels incompleteness theorem?

First-order logic is complete & sound. The notion of truth used here is model-theoretic. Informally Godels incompleteness theorem says that for a sufficiently strong formal language there are ...
2
votes
2answers
72 views

Completeness condition in Gödel first incompleteness theorem superflous

Wikipedia says: Theory is complete if it is a maximal consistent set of sentences. Than it says: Any effectively generated theory capable of expressing elementary arithmetic cannot be both ...
3
votes
1answer
87 views

Looking for counterexamples where the output of a computable function always has a computably checkable property, but PA cannot prove this

Suppose we have a computable function $f$, say over the naturals, and a decidable set $S$ of naturals, such that $f(x) \in S$ for all $x$. In this case, for any specific $x$, there is some specific ...
11
votes
2answers
837 views

Examples of statements which are true but not provable

Speaking informally and working, for example, in Peano Arithmetic (PA), we know that the essence of the Gödel's first incompleteness theorem is that there are true statements (in our model PA), which ...
6
votes
2answers
299 views

$\omega$-consistency and related terms

We know that a theory $T$ is $\omega$-inconsistent if there is a formula $\psi$ such that $T$ proves $(\exists x)\psi(x)$, and $T$ also proves $\lnot \psi(n)$ separately for each standard natural ...
2
votes
1answer
78 views

In Godel's first incompleteness theorem, what is the appropriate notion of interpretation function?

Wikipedia states Godel's first incompleteness as follows. Any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete. In particular, for ...
2
votes
5answers
870 views

Are (some) axioms “unprovable truths” of Godel's Incompleteness Theorem?

Like any math newbie, Godel's Incompleteness Theorems are easy to understand in general layman's terms, but difficult to understand beyond the typical "liar's paradox" and "barber's paradox" type ...
9
votes
2answers
481 views

Where, specifically, did Principia Mathematica fail?

I'm very fascinated by the book Principia Mathematica. From what I've learned so far, Principia Mathematica set out to be, essentially, the bible of mathematics and logic, from which all mathematical ...
1
vote
1answer
83 views

Have I understood the whole Incompleteness business correctly?

I am reading Gödel-Escher-Bach and a good dialogue by Eliezer Yudkowsky and I think I might have understood the nature of the Completeness and Incompleteness theorems (at least regarding Peano ...
1
vote
3answers
113 views

On consistency of axiomatic systems

Can an axiomatic system (which is capable of expressing arithmetic) be complete and consistent? Let me explain my motivation a little bit (though it can be a kind of a mess...) I'm aware of Goedel's ...
5
votes
2answers
124 views

Running programs in nonstandard models of PA

I came across the following problem in several places, to paraphrase: Let $T$ be a recursively axiomatizable, consistent extension of PA. Then there exists some $e$ such that the $e'$th program ...
51
votes
13answers
9k views

Can someone explain Gödel's incompleteness theorems in layman terms?

Can you explain it in a fathomable way at high school level?
6
votes
1answer
219 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
356 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 ...
1
vote
1answer
51 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
217 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
378 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
305 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
53 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
179 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
410 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
190 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
161 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
75 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
147 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
210 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))?$$