Linked Questions

82
votes
11answers
22k views

What is a simple example of an unprovable statement?

Most of the systems mathematicians are interested in are consistent, which means, by Gödel's incompleteness theorems, that there must be unprovable statements. I've seen a simple natural language ...
27
votes
12answers
5k views

BIG LIST: Statements that look obviously false but cannot be disproved

I'm looking for statements that look obviously false but have no disproof (yet). For example The base-10 digits of $\pi$ eventually only include 0s and 1s. To make this question a little objective, I'...
53
votes
5answers
13k views

Understanding Gödel's Incompleteness Theorem

I am trying very hard to understand Gödel's Incompleteness Theorem. I am really interested in what it says about axiomatic languages, but I have some questions: Gödel's theorem is proved based on ...
50
votes
5answers
4k views

What do logicians mean by “type”?

I enjoy reading about formal logic as an occasional hobby. However, one thing keeps tripping me up: I seem unable to understand what's being referred to when the word "type" (as in type theory) is ...
23
votes
6answers
4k views

Is consistency an axiom of mathematics?

I watched the numberphile video on Gödel's Incompleteness Theorem today, and I was wondering about something. It seems the key to accepting the truth of Gödel's Theorem is to demand that mathematics ...
19
votes
8answers
2k views

Gödel's paradox: Why is “a proof that some universal statement is unprovable” not a valid proof that this statement is true? [duplicate]

Here is a paradox I have some difficulty resolving: As far as I understand, by one of Gödel's incompleteness theorems, in a first order logic theory with Peano arithmetic, one can find some non-...
19
votes
4answers
3k views

How to prove a non-provable statement? That is weird…

a) there are mathematical statements, eg. formulated in Peano, which are known to be true but not provable. If not provable, how do we "prove" they are true? Is it not fishy? (I think Gödel does not ...
35
votes
1answer
2k views

How long can proofs be?

Let $$f(n) = \max\{\text{length of shortest proof of }\varphi \mid \varphi \text{ is a provable ZFC sentence of length } \leq n\}$$ How fast does $f$ grow? Is it polynomial, exponential, more than ...
9
votes
3answers
3k views

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

I've read and heard in lectures that A way to prove that the Riemann hypothesis is true is to show that its negation is not provable. The argument (informally) usually goes like If a ...
13
votes
3answers
4k views

What are the prerequisites for studying mathematical logic?

I am looking to study mathematical logic, however, I find that introductory books are very daunting, which kind of disheartens me. You see, slowly but surely, I started to realize that the maths which ...
11
votes
2answers
2k views

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

I know of the continuum hypothesis (CH) and how it was proven to be unprovable under ZFC, but this was after Gödel's incompleteness theorems. And in fact Gödel (and Paul Cohen) were the ones who ...
8
votes
9answers
887 views

Is induction something we take on faith?

I understand that in mathematics and logic we can continue to reduce things to simpler axioms, principles, and so on, and we have to "stop" at some point otherwise we're just going on forever. We ...
7
votes
5answers
1k views

Set theoretic concepts in first order logic

I have been reading introductory texts on first order logic (for example, Leary&Kristiansen). All of them used concepts that I have heard in set theory courses - ordered pairs, functions, ...
16
votes
1answer
2k views

Are sets and symbols the building blocks of mathematics?

A formal language is defined as a set of strings of symbols. I want to know that if "symbol" is a primitive notion in mathematics i.e we don't define what a symbol is. If it is the case that in ...
13
votes
1answer
2k views

Predicate logic: How do you self-check the logical structure of your own arguments?

In propositional logic, there are truth tables. So you can check if the logical structure of your argument is, not correct per se, but if it's what you intended it to be. In predicate logic, I have ...

15 30 50 per page