3
votes
2answers
72 views

If $T$ proves any incorrect $\forall$-rudimentary sentence, then $T$ is inconsistent

A theory $T$ in the language of arithmetic is called $\omega$-inconsistent if for some formula $F(x)$, $\exists x F(x)$ is a theorem of $T$, but so is $\neg F(n)$ for each natural number $n$. ...
2
votes
2answers
90 views

Gödel's incompleteness theorems: where to learn? Is there a straightforward relation between the two?

What would be a good textbook or paper to learn the proofs of the two Gödel's incompleteness theorems from? I would prefer it to be as close to the original proofs as possible. I have not tried to ...
4
votes
2answers
113 views

Modern book on Gödel's incompleteness theorems in all technical details

Is there a modern book on Gödel's incompleteness theorems that goes into each and every technical aspect of the proof of them (a classical one, if such exists)? I'm not interested in popular ...
1
vote
1answer
60 views

Must every decidable theory be axiomatizable?

Note: By "theory" I mean a set of sentences, not assumed to be closed under logical consequence (otherwise the question would be trivial). Comments/ideas: There's a well-known result that every ...
0
votes
1answer
71 views

Peano's theory of arithmetic and Gödel's 1st Incompleteness Theorem

Let $\mathcal{N}$ be Peano's 1st order theory of arithmetic and $\mathscr{A}$ it's standard model (which we assume exists). Infer from Gödel's 1st Incompleteness Theorem that there exists a closed ...
2
votes
1answer
40 views

Does second-order arithmetic (Z2) prove soundness and uniform reflection for first-order arithmetic (PA)?

(1) Does full second-order arithmetic (Z2) prove soundness and uniform reflection schemas for first-order arithmetic (PA)? That is, do we have for all formulas $\phi$: $$ \underset \phi \forall \; ...
2
votes
1answer
43 views

Con(PA) implies consistency of $\mathsf{PA}$ + ¬Con($\mathsf{PA}$)

The Wikipedia article for $\omega$-consistency says "Now, assuming PA is really consistent, it follows that $\mathsf{PA}$ + ¬Con($\mathsf{PA}$) is also consistent, for if it were not, then PA would ...
4
votes
2answers
164 views

Interaction of completeness and second incompleteness theorems

So I was reading the Wikipedia article on Godel's completeness theorem, the section on its relation to completeness. It says that completeness gives the existence of a model of arithmetic $\mathcal M ...
3
votes
1answer
48 views

The effects of requiring a recursive vs. a recursively enumberable axiomatization in the incompleteness theorem

I believe that the (paraphrased) original statement of Gödels first incompleteness theorem (including Rosser's trick) is If T is a sufficiently strong recursive axiomatization of the natural ...
0
votes
1answer
29 views

Logic soundness and completeness

I have to do a number of similar type questions, but I am having trouble grasping the general concepts around soundness and completeness. I have read up on the general definitions and think I ...
5
votes
3answers
157 views

Proving Undecidability of first order logic without first proving it for arithmetic.

All text I have read prove the Undecidability of first order logic a bit as an afterthought and after having proved the incompleteness and Undecidability of (Peano) Arithmetic. This proof also ...
0
votes
1answer
31 views

Kolmogorov (Kolmogoroff-) Complexity, Contradiction with Invariance Theorem.

Fix some programming languages $S$ which is rich enough such that one can write interpreters for $S$ in $S$. Define $$ K(w) := \mbox{length of a shortest program producing $w$}. $$ Now fix some ...
3
votes
1answer
106 views

What other unprovable theorems are there? [duplicate]

Gödel's incompleteness theorem presents us with the possibility of having theorems that are neither provable nor disprovable in a given axiomatic set. Already we have the continuum hypothesis which ...
0
votes
1answer
72 views

How can a statement be known to be undecidable in ZFC without ZFC being inconsistent?

I'm attempting to understand the answer to the question, Is there a statement whose undecidability is undecidable (as in independent, not a decision problem)? The answer appears to be "Yes". However, ...
5
votes
0answers
102 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
118 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
67 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
106 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 ...
2
votes
0answers
69 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
132 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
77 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
113 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
156 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 ...
5
votes
1answer
91 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
78 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 ...
4
votes
4answers
131 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 ...
3
votes
0answers
196 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 ...
2
votes
1answer
84 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
78 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
82 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 ...
9
votes
1answer
123 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
51 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 ...
5
votes
2answers
158 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 ...
1
vote
2answers
64 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
80 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 ...
10
votes
2answers
629 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 ...
5
votes
2answers
219 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
74 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
533 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
417 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
3answers
98 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
119 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 ...
47
votes
13answers
5k 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
173 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
191 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 ...
4
votes
1answer
145 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
294 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
272 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 ...