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

learn more… | top users | synonyms

5
votes
3answers
1k 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 ...
3
votes
1answer
96 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
246 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 ...
30
votes
6answers
1k views

Why is the Continuum Hypothesis (not) true?

I'm making my way through Thomas W Hungerfords's seminal text "Abstract Algebra 2nd Edition w/ Sets, Logics and Categories" where he makes the statement that the Continuum Hypothesis (There does not ...
2
votes
1answer
199 views

About a step in the proof of Gödel-Rosser Theorem.

I am reading about the Gödel-Rosser Theorem, i.e. the Rosser's refinement of first Gödel's incompleteness Theorem, which states that if $\mathbf{PA}$ is consistent then it is incomplete. I am posting ...
7
votes
3answers
1k views

Consistency of Peano axioms (Hilbert's second problem)?

(Putting aside for the moment that Wikipedia might not be the best source of knowledge.) I just came across this Wikipedia paragraph on the Peano-Axioms: The vast majority of contemporary ...
1
vote
2answers
217 views

Is there a non-contradictory non-trivial axiomatic system in which Gödel's theorem is undecidable?

Gödel's Incompleteness Theorem states that in any non-contradictory non-trivial axiomatic system there are certain statements or theorems whom cannot be proved in that system, For example in ZFC, ...
0
votes
2answers
318 views

What is actually “relatively consistent”?

Gödel's incompleteness theorem states that: "if a system is consistent, it is not complete." And it's well known that there are unprovable statements in ZF, e.g. GCH, AC, etc. However, why does this ...
5
votes
3answers
443 views

Is the negation of the Gödel sentence always unprovable too?

The incompleteness theorem says that certain theories+deduction system contain at least one sentence (the Gödel sentence "$G$"), which can't be proven (in the system in which it holds). (i) Is ...
2
votes
1answer
170 views

A qualitative, yet precise statement of Godel's incompleteness theorem?

I read online a statement to the effect that (I'm paraphrasing): Goedel's incompleteness theorem shows that we cannot even have a complete and consistent theory for the natural numbers. I am ...
4
votes
5answers
281 views

Gödel says: countable proofs, uncountable conjectures?

I thought I understood Gödel's Incompleteness Theorem to say: Starting from ZF, there only a countable number of proofs you can write The number of possible conjectures is uncountable. Thus, ...
4
votes
3answers
321 views

Aftermath of the incompletness theorem proof

This is somewhat of a minor point about the incompletness theorem, but I'm always a little unsure: So one proves that there is a formula which is unprovable in the theory of consideration. Okay, at ...
3
votes
1answer
105 views

properties of the provability predicate applied to open formulas

Good day! Let $\mathrm{T}$ be a first-order theory which contains the Peano arithmetic and has a recursively enumerable set of axioms. It is well known that one can construct a predicate ...
10
votes
5answers
898 views

Is there a proof of Gödel's Incompleteness Theorem without self-referential statements?

For the proof of Gödel's Incompleteness Theorem, most versions of proof use basically self-referential statements. My question is, what if one argues that Gödel's Incompleteness Theorem only matters ...
5
votes
3answers
288 views

An ignorant question about the incompleteness theorem

Let me preface this by saying that I have essentially no background in logic, an I apologize in advance if this question is unintelligent. Perhaps the correct answer to my question is "go look it up ...
2
votes
2answers
145 views

What does the completeness of a system mean for the provability of certain statments?

Through the 16th to 19th centuries mathematicians tried to prove the Euclids parallel postulate from Euclid's other four postulates. In the beginning of the 19th century the mathematics community ...
0
votes
1answer
131 views

Why isn't GL system of provability logic reflexive?

Formula $\square p \rightarrow p$ (axiom T; corresponding to reflexive modal frames) is interpreted as "if p is provable, then p", or more precisely: for all realizations (all substitutions for $p$), ...
3
votes
1answer
152 views

The Penrose–Lucas argument

I was looking at the Penrose–Lucas argument as discussed on Wikipedia. It states: In 1931, the mathematician and logician Kurt Gödel proved that any effectively generated theory capable of ...
1
vote
1answer
144 views

Definition and meaning of “Proof Schema”, “Class Sign”

I'm a newbie in advanced mathematics, and I'm trying to understand Godel's theorem. I came across these two words which I couldn't understand clearly. "Proof Schema" and "Class-Sign" Can anybody ...
5
votes
1answer
350 views

Is there any direct application of Gödel's Theorems outside of logic?

Gödel's incompleteness theorems was a major achievement with ramifications outside the field of mathematics itself. Are there any direct applications of the theorem(s), or any of the methods pioneered ...
9
votes
1answer
261 views

Freeman Dyson's example of an unprovable truth

Freeman Dyson has claimed that $$\nexists m,n \operatorname{Reversed}(2^n) = m ^ 5 $$ (where $\operatorname{Reversed}(l)$ just is the reverse of the digits of $l$ in base 10), is probably an ...
2
votes
1answer
311 views

Gödel's Incompleteness Theorem - Diagonal Lemma

In proving Gödel's incompleteness theorem, why does he needed the Diagonal Lemma or the Fixed Point Theorem for building a formula $\phi$ that spoke about itself? Can't this formula be built this way: ...
0
votes
1answer
398 views

Gödel Incompleteness Theorem - Primitive Recursive Functions

I'm currently studying Gödel's Incompleteness Theorem and I am in doubt about his use of primitive recursive functions. To study it, i'm in the point of view of a system of predicate logic with the ...
1
vote
1answer
172 views

Consequences of Incompleteness.

Suppose that I'm a working mathematician that has just proved a Theorem, say, in Number Theory. Does Gödel's Incompleteness Theorem imply that I can't know for sure if there exists a proof of the ...
0
votes
1answer
264 views

Consistent but incomplete formal axiomatic systems

Is there any known consistent but incomplete formal axiomatic system apart of and simpler than one "capable of doing arithmetic"? Is it even possible? Even if this capability of arithmetic were a ...
6
votes
3answers
146 views

If $T$ proves $\operatorname{Con}(ZFC)$, is $T$ at least as strong as set theory?

I am looking for either a proof of counterexample of this: Lemma: Let $\pi$ be a faithful interpretation of $PA$ into $ZFC$, and let $PA'$ be the image of $PA$ under $\pi$. If there is a $T$ with ...
4
votes
0answers
80 views

An “internal” condition on $T$ so that for the standard provability predicate, $T$ proves $\text{Pf}(\underline S)$ implies $T$ proves $S$?

This is probably quite basic, but I'd like to make sure I got this right. Regarding the proof of Goedel's first incompleteness theorem, say that we have $T$ containing $PA$ effectively axiomatizable ...
1
vote
2answers
200 views

Is this incompleteness result easier to get than incompleteness of PA?

Gödel's theorem for Peano Arithmetic shows that (under consistency hypothesis on PA) there is a statement which cannot be proved or disproved within PA that is true under the standard model ...
1
vote
2answers
152 views

How can you add 'not G' to a formal system without introducing omega inconsistency?

In any formal system S that is susceptible to Godel's proof, we can make a formula G which is undecidable. That should mean that we can add either $G$ or $\neg G$ as an axiom to S and still end up ...
13
votes
6answers
1k views

What philosophical consequence of Goedel's incompleteness theorems?

I want to write a philosophical essay centered about Goedel's incompleteness theorem. However I cannot find any real philosophical consequences that I can write more than half a page about. I read the ...
2
votes
1answer
151 views

Differences between between concepts related to Gödel's Incompleteness theorems: self-referencing, diagonalization and fixed point theorem?

I am studying the proof of Gödel's first Incompleteness theorem at the moment and I don't understand the differences between self-referencing, diagonalization and fixed point related to Gödel's proof. ...
0
votes
1answer
127 views

Uniqueness of super godel numbers of $\varphi$ and $\neg \varphi$

Let $e_{0},e_{1},...,e_{n}$ be a sequence of wffs or other expressions. Code each $e_{i}$ by a regular godel number $g_{i}$, to yield a sequence of numbers $g_{0},g_{1},...,g_{n}$. Then encode this ...
5
votes
2answers
226 views

“Completeness modulo Godel sentences”?

So this has been bugging me for roughly four years. When I was an undergraduate, I attended a colloquium in which the speaker was a 'cheerleader' for AD (the axiom of determinacy- an alternative to ...
1
vote
1answer
106 views

Relationship between $\Sigma_{1}$ and $\Pi_{1}$ functions (Logic)

I am working on the following homework problem for a logic class on Godel's incompleteness theorems and the following question is asked. Is the converse of Theorem $13.1$ true? Explain. Theorem ...
4
votes
1answer
155 views

Is there any recursive definition, using only addition, of the set of values of $x^2+y^2$?

There is a recursive definition of the set of squares which uses only addition: $CS(x,y) := IS(x) \wedge IS(y) \wedge x \lt y \wedge \forall z: (x \lt z) \wedge (z \lt y)⇒\neg IS(z)$ $IS(x)⇔ x=0 ...
7
votes
3answers
307 views

Can ZFC decide number theory?

Among the versions of the Incompleteness Theorem that I've seen are the following: Assuming the Peano axioms are consistent (which they are, if we accept the existence of the natural numbers), there ...
2
votes
2answers
316 views

How it is posible that $\omega$-inconsistency does not lead to inconsistency

After wikipedia: Theory is $\omega$-inconsistent if, for some property P of natural numbers, T proves P(0), P(1), P(2), and so on (that is, for every standard natural number n, T proves that P(n) ...
1
vote
4answers
608 views

Consistency VS Inconsistency , semantics and syntactics

What does it mean when we say that a set of formulas , Sigma , is Consistent , or Inconsistent ? Is ...
6
votes
5answers
5k views

What is the difference between Completeness and Soundness in first order logic?

Completeness is defined as if given $\Sigma\models\Phi$ then $\Sigma\vdash\Phi$. Meaning if for every truth placement $Z$ in $\Sigma$ we would get $T$, then $\Phi$ also would get $T$. If the previous ...
2
votes
1answer
251 views

About Godel Incompleteness and Multiplication

Godel proved that every system strong enough to include standard arithmetic with multiplication is incomplete. But I've read that systems that do not include multiplication are complete. But ...
1
vote
1answer
235 views

Use of undecidability

Suppose someone proved that the Goldbach conjecture was undecidable in an axiomatic system that is consistent as far as we know. Then in some sense we know that Goldbach conjecture must be "true", ...
5
votes
1answer
256 views

Completeness of Real Number Arithmetic?

I've recently read that, although Godel Incompleteness holds for the theory of natural numbers, the theory of the real numbers is actually complete. So, why is Godel's Theorem still considered ...
8
votes
2answers
1k views

Gödel's incompleteness theorem can't be proven?

I have a very simple question, that I still haven't found an answer to yet: Gödel is said to have proven that Peano Arithmetic (or any system capable of expressing it) can't prove its own ...
2
votes
1answer
135 views

Why does the existence of independent statements not prove completeness?

I've read before that, by the Principle of Explosion, if a theory is inconsistent, then absolutely any statement can be proven within it. Obviously, there are statements which are independent of ZFC ...
8
votes
3answers
959 views

Why Euclidean geometry cannot be proved incomplete by Gödel's incompleteness theorems?

Wikipedia mentioned the limitation of Gödel's theorems. According to it, Euclidean geometry doesn't satisfy the hypotheses of Gödel's incompleteness theorems, that is, it cannot define natural ...
4
votes
1answer
158 views

Does robinson arithmetic satisfy modal logic's “axiom 4”?

Does Robinson arithmetic prove the theorem "if sigma is provable then 'sigma is provable' is provable' for a fixed sentence sigma? It's clear to me that you can get a primitive recursive function f ...
2
votes
1answer
174 views

How to express Con(PA) as a first-order statement?

I read from somewhere that Fact 1. PA, which refers to the first-order version, is not finitely axiomatizable. At the same time, the second incompleteness theorem says that there is no proof in ...
1
vote
1answer
160 views

Quantitative version of Godel's incompleteness theorem

Let $A$ be a list of axioms which we assume to be sound (for example, PA or ZFC). Godel's incompleteness theorems imply that if we add only finitely many (true) axioms to $A$, the new list $B$ will ...
13
votes
7answers
2k views

True vs. Provable

Gödel's first incompleteness theorem states that "...For any such system, there will always be statements about the natural numbers that are true, but that are unprovable within the system". What ...
2
votes
2answers
1k views

Explanation of proof of Gödel's Second Incompleteness Theorem

I am looking for a simple explanation/outline of the proof of Gödel's Second Incompleteness Theorem, and I haven't yet been able to find anything that is within my grasp. I'm looking for something ...