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 ...
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'...
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 ...
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 ...
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 ...
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-...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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, ...