Skip to main content
57 votes
Accepted

Decidability of the Riemann Hypothesis vs. the Goldbach Conjecture

The issue here is how complicated is each statement, when formulated as a claim about the natural numbers (the Riemann hypothesis can be made into such statement). For the purpose of this discussion ...
Asaf Karagila's user avatar
  • 397k
54 votes
Accepted

Computability viewpoint of Godel/Rosser's incompleteness theorem

Here I shall present very simple computability-based proofs of Godel/Rosser's incompleteness theorem, which require only basic knowledge about programs. I feel that these proofs are little known ...
user21820's user avatar
  • 59.2k
52 votes
Accepted

Difference between provability and truth of Goodstein's theorem

Good question! If you were to consider the system PA + $\neg$G, wouldn't G still hold in the sense that you could never find a counterexample? This gets at an important subtlety here - the issue ...
Noah Schweber's user avatar
48 votes
Accepted

Are there more truths than proofs?

That's correct, but it is not very interesting: we don't have "access" to most mathematical facts. It is not even clear what a proof of an arbitrary mathematical fact would mean, because to ...
mihaild's user avatar
  • 15.9k
36 votes

What axioms Gödel is using, if any?

Gödel's paper was written in the same way as essentially every other mathematical paper. To prove a theorem about a formal system does not require one to prove that theorem within a formal system. ...
Carl Mummert's user avatar
  • 82.2k
36 votes
Accepted

Can Peano arithmetic prove the consistency of "baby arithmetic"?

$\mathsf{PA}$ has a very interesting property, namely that it proves the consistency of each of its finitely axiomatizable subtheories. This is usually called the reflection principle for $\mathsf{PA}$...
Noah Schweber's user avatar
35 votes

With this definition of completeness, Gödel's Incompleteness result seems not surprising, so why it was back then?

Did people really thought that for every theory and a given formula, either it or its negation are semantically valid, i.e. fulfilled by every model? (Emphasis added). No, of course not. It's easy to ...
hmakholm left over Monica's user avatar
35 votes
Accepted

I don't understand Gödel's incompleteness theorem anymore

This answer only addresses the second part of your question, but you asked many questions so hopefully it's okay. First, there is in the comments a statement: "If Goldbach is unprovable in PA ...
halrankard's user avatar
  • 3,454
33 votes

Question about Gödel's Incompleteness Theorem

"To encode each statement" is not quite right. "I had Cheerios for breakfast," for example, cannot be encoded. The set of things encoded is a quite carefully described set, and metastatements like ...
John Hughes's user avatar
  • 94.3k
33 votes
Accepted

Is consistency an axiom of mathematics?

Yes. That is exactly what it means. Consistency assumptions are axioms. This gives rise to a natural hierarchy of axioms, specifically part of set theory, called large cardinal axioms which are ...
Asaf Karagila's user avatar
  • 397k
32 votes
Accepted

How can we know we're not accidentally talking about non-standard integers?

[I will take for granted in this answer that the standard integers "exist" in some Platonic sense, since otherwise it's not clear to me that your question is even meaningful.] You're thinking about ...
Eric Wofsey's user avatar
29 votes
Accepted

Why can't we prove consistency of ZFC like we can for PA?

The problem is that, unlike the case for PA, essentially all accepted mathematical reasoning can be formalized in ZFC. Any proof of the consistency of ZFC must come from a system that is stronger (at ...
spaceisdarkgreen's user avatar
28 votes

I don't understand Gödel's incompleteness theorem anymore

Let me try to get at the heart of your misunderstanding as concise as possible: 1. We are not deliberately choosing to use a language that permits self-reference, we are forced to do so. The only ...
mlk's user avatar
  • 3,960
25 votes

What axioms Gödel is using, if any?

As a footnote to Carl Mummert's terrific answer, it is worth adding the following remark. Yes, Gödel was giving an informal mathematical proof "from outside" (as it were) about certain formal systems....
Peter Smith's user avatar
  • 55.4k
25 votes
Accepted

What's wrong with this "proof" that Gödel's first incompleteness theorem is wrong?

There are at least two problems here. First, when you say "we take this process to infinity and just keep going", that is a very informal description, and without spending some work on making it more ...
hmakholm left over Monica's user avatar
24 votes
Accepted

Why doesn't Gödel's incompleteness theorem apply to false statements?

That is, how do we know that all false statements are provably so? This is simply wrong. There are both true and false statements that cannot be proven. What is true is that any sufficiently nice ...
user21820's user avatar
  • 59.2k
23 votes

Statement provable for all parameters, but unprovable when quantified

Great question! Yes, there are specific examples. One of the most famous is Goodstein's theorem. If $A(n)$ is the statement that Goodstein's sequence starting at $n$ terminates, then it is known (via ...
Caleb Stanford's user avatar
22 votes
Accepted

Were there any proofs of whether or not a statement could be proved true or false before Gödel's Incompleteness Theorems?

The parallel postulate is a good example. Another one is that the proof of any theorem is also a proof of the provability of the theorem. For one more, Turing, Kleene, and Gödel all worked on ...
Stella Biderman's user avatar
20 votes
Accepted

Statement provable for all parameters, but unprovable when quantified

Possibly the easiest example is to let $A(x)$ say that $x$ is not the Gödel number of a proof of $0=1$ from the axioms of PA. Because there is no such proof, $A(0)$ is true, $A(1)$ is true, etc., ...
Carl Mummert's user avatar
  • 82.2k
20 votes

Question about Gödel's Incompleteness Theorem

It is impossible to encode the statement "Statement X is true." This follows from Tarski's Undefinability Problem: The formula $True(n)$, which defines the set of Godel numbers $n$ corresponding to ...
Mark H's user avatar
  • 1,283
20 votes
Accepted

With this definition of completeness, Gödel's Incompleteness result seems not surprising, so why it was back then?

EDIT: I've added here some of the facts from the discussion between me and the OP in the comments below the question. These doesn't address the actual OP - "why was Godel's theorem surprising?" - but ...
Noah Schweber's user avatar
20 votes

Is consistency an axiom of mathematics?

Well, we must be careful about what 'mathematics' means here. We generally mean some kind of formal system (the things Godel's theorem talks about) capable of formalizing and proving theorems of ...
spaceisdarkgreen's user avatar
19 votes

Decidability of the Riemann Hypothesis vs. the Goldbach Conjecture

The last bullet point, saying that this constitutes a proof it is decidable, does not follow. $X$ is decidable means either $X$ is provable or $\neg X$ is provable. It's possible that both are ...
Dan Brumleve's user avatar
  • 17.8k
19 votes

With this definition of completeness, Gödel's Incompleteness result seems not surprising, so why it was back then?

It may be useful to point out that there are (at least) two purposes for which axiomatic theories are created and, as a result, two sorts of theories, for which we may have very different expectations....
Andreas Blass's user avatar
19 votes

I don't understand Gödel's incompleteness theorem anymore

Allow me to start by pointing out that Gödel's theorems are usually studied in the context of first-order logic, whereas you are describing propositional logic in your understanding of theory and ...
Asaf Karagila's user avatar
  • 397k
19 votes
Accepted

In his 1931 incompleteness proof, how does Godel's definition of "immediate consequence" work?

Welcome to Math.SE! Maybe every other mode of logical consequence is in some sense equivalent to modus ponens? Yes, modus ponens is the only propositional inference rule defined in Principia ...
Z. A. K.'s user avatar
  • 11.7k
16 votes

Does it follow from Gödel's theorem that this world cannot be fully described by math?

The major flaw is in your presumption that humans can find and prove statements that are true but not provable within math. Think about what exactly you mean by "math": you presumably mean something ...
Reese Johnston's user avatar
15 votes
Accepted

Are Godel's incompleteness theorems proven non-trivial?

It seems you are confused about the statement of Godel's theorem: If $T$ is a "reasonable" first-order theory, then there is a first-order sentence $\varphi$ in the language of $T$ such that ...
Noah Schweber's user avatar
15 votes

Are there uncountably infinite complete extensions of finite theories of the natural numbers?

There is no uncountable extension because a theory is set of wffs, and there are only countably many wffs. But there are uncountably many complete extensions, each of which is countably infinite. (...
hmakholm left over Monica's user avatar
15 votes

Are there uncountably infinite complete extensions of finite theories of the natural numbers?

Yes, there are uncountably many (in fact, continuum many) complete theories extending any given finite (in fact, any given computable) true theory of arithmetic strong enough for Godel's theorems to ...
Noah Schweber's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible