86
votes
Accepted
Is linear algebra more “fully understood” than other maths disciplines?
It's closer to true that all the questions in finite-dimensional linear algebra that can be asked in an introductory course can be answered in an introductory course. This is wildly far from true in ...
- 51.4k
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 ...
- 388k
50
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 ...
- 237k
49
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 ...
- 56k
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 ...
- 14.2k
39
votes
Is linear algebra more “fully understood” than other maths disciplines?
The hard parts of linear algebra have been given new and different names, such as representation theory, invariant theory, quantum mechanics, functional analysis, Markov chains, C*-algebras, numerical ...
- 35.1k
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. ...
- 80.6k
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 ...
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 ...
- 3,424
35
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}$...
- 237k
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 ...
- 91.4k
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 ...
- 323k
32
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 ...
- 388k
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 ...
- 55.5k
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 ...
- 3,921
25
votes
Accepted
How does Gödel Completeness fail in second-order logic?
The property that "every consistent theory has a model" does not hold for second-order logic.
Consider, for example the second-order Peano axioms, which are well known to have only $\mathbb N$ as ...
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....
- 53.1k
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 ...
24
votes
Accepted
What does a Godel sentence actually look like?
Here's an explicit example, due to Hagen von Eitzen (I've made this answer community wiki so I don't get rep bonus for someone else's hard work):
¬∃b:∃c:∃d:〈∃e:∃f:∃g:〈a=((((((e+ f)+ g)· ((e+ f)+ g))· (...
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 ...
- 56k
23
votes
Is linear algebra more “fully understood” than other maths disciplines?
Journals such as "Linear Algebra and its Applications" still publish papers, so certainly not everything about Linear Algebra is known. It's definitely not exempt from Gödel. However, it is ...
- 437k
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 ...
- 45.3k
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 ...
- 30.8k
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., ...
- 80.6k
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 ...
- 1,273
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 ...
- 55.5k
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 ...
- 17.6k
19
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 ...
- 237k
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 ...
- 388k
18
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....
- 70.4k
Only top scored, non community-wiki answers of a minimum length are eligible