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

learn more… | top users | synonyms

0
votes
2answers
254 views

Undecidable sentence in Godel's incompleteness theorem

In Godel's incompleteness theorem, the undecidable sentence is g: I am not provable. Ok. I accepted it and realized that in satandard interpretation it is true. So we found a true sentence which ...
0
votes
2answers
109 views

Scapegoat theory and PA

A theory T is scapegoat if for every formula A with only one free variable there exist a closed term s such that T proves: (∃x(¬A(x)))⇒¬A(s) I think it is an expectable property for each theory since ...
1
vote
5answers
228 views

Understanding ω-consistent and ω-incomplete theory

A theory $K$ is said to be $ω$-consistent if, for every formula $B(x)$ of $K$, if $﹁ B(n)$ is a theorem in $K$ for every natural number $n$, then it is not the case that $(∃x)B(x)$ is a theorem in ...
4
votes
3answers
292 views

Concrete example for diagonal lemma

Diagonal lemma says that in a theory with enough assumption for any formula $A(x)$ there exist a sentence $B$ such that $B$ $\iff$ $A(\#(B))$ is a theorem in that theory, in which $\#(B)$ represents ...
8
votes
1answer
297 views

How did Kurt Gödel's Incompleteness Theorem affect the mathematical world?

Hi I am looking not to understand the Incompleteness Theorem, but to find out more about how and what this has effected the mathematics world. I am in high school, in Honors Algebra II, and I am ...
-9
votes
2answers
179 views

How is Goedel's 1st incompleteness theorem related to the Axioms of a theory [closed]

i am thinking of various connections and formulations of Goedel's 1st incompleteness theorem. Apart from connections to Turing's Halting Problem and Algorithmic Complexity Theory, i am looking for ...
7
votes
2answers
436 views

Why doesn't “$V$ is a model of $ZF$” imply consistency of ZF?

One can prove that $V$, Von Neumann's universe, satisfies all of $ZF$ axioms, so it's a model of $ZF$. But I can't see why this doesn't imply the consistency of that theorem. I'm aware that ...
1
vote
1answer
278 views

Is Douglas Hofstadter's version of Godel's proof utter nonsense?

Is Douglas Hofstadter's version of Godel's proof, which he offers in his book Godel, Escher, Bach, utter nonsense? Hofstadter goes to great length to disguise the fact that there are two distinct ...
3
votes
0answers
92 views

Maths, esp. Godel, and poetry

At the risk of being an interloper: I'm a poet with a bit of mathematical training. Right now I've got a grant from the Arts Council of Northern Ireland to write a collection (loosely) based on the ...
3
votes
2answers
127 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$. ...
3
votes
2answers
200 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 ...
6
votes
2answers
221 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
241 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
95 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 ...
3
votes
1answer
109 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
148 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 ...
5
votes
2answers
221 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
80 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 ...
1
vote
1answer
87 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 ...
6
votes
5answers
753 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
53 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
186 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 ...
7
votes
2answers
811 views

Gödel's (in)completeness theorems and the axiomatization of Euclidean geometry

In David Hilbert's 1899 Grundlagen der Geometrie, Hilbert gives a rigorous axiomatization of Euclidean geometry. As I understand it, some of Hilbert's axioms must be expressed in second order logic ...
0
votes
1answer
204 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, ...
9
votes
0answers
155 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
246 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
91 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 ...
10
votes
1answer
212 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
148 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
155 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})$. ...
3
votes
1answer
102 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
203 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
229 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
51 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
131 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
94 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
184 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
327 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
58 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
45 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
228 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
116 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
92 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
278 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
60 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
222 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
80 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
112 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 ...
14
votes
2answers
2k 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
488 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 ...