Linked Questions

4
votes
1answer
522 views

What other unprovable theorems are there? [duplicate]

Gödel's incompleteness theorem presents us with the possibility of having theorems that are neither provable nor disprovable in a given axiomatic set. Already we have the continuum hypothesis which ...
212
votes
36answers
21k views

What are some counter-intuitive results in mathematics that involve only finite objects?

There are many counter-intuitive results in mathematics, some of which are listed here. However, most of these theorems involve infinite objects and one can argue that the reason these results seem ...
112
votes
26answers
10k views

Examples of problems that are easier in the infinite case than in the finite case.

I am looking for examples of problems that are easier in the infinite case than in the finite case. I really can't think of any good ones for now, but I'll be sure to add some when I do.
67
votes
12answers
18k 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 ...
88
votes
5answers
22k views

Is infinity an odd or even number?

My 6 year old wants to know if infinity is an odd or even number. His 38 year old father is keen to know too.
29
votes
3answers
4k views

What is this operator called?

If $x \cdot 2 = x + x$ and $x \cdot 3 = x + x + x$ and $x^2 = x \cdot x$ and $x^3 = x \cdot x \cdot x$ Is there an operator $\oplus$ such that: $x \oplus 2 = x^x$ and $x \oplus 3 = {x^{x^x}}$? ...
19
votes
5answers
1k views

How can Busy beaver($10 \uparrow \uparrow 10$) have no provable upper bound?

This wikipedia article claims that the number of steps for a $10 \uparrow \uparrow 10$ state (halting) Turing Machine to halt has no provable upper bound: "... in the context of ordinary ...
5
votes
2answers
198 views

How can you come to the truth of a statement without proving it?

I was reading a bit about Gödel's incompleteness theorems. I haven't took the time to really study it, but I'm very curious about statements like these: In other words, if our axioms are consistent ...
8
votes
1answer
101 views

Can PA prove very fast growing functions to be total?

The Goodstein-sequence is a total function, but PA cannot prove this. Is this true for any other function with growth rate at least $f_{\epsilon_0}$ or are there functions growing at least as fast ...
4
votes
1answer
143 views

Is there any identity which cannot be proved

For example, if we want to prove that $a^2+b^2\ge 2ab$ for all $a,b\in\mathbb{R}$, we will start from something which is true (axiom or something that is already proved). In this case we will use fact ...
1
vote
3answers
120 views

Some kind of incompleteness over proofs

There are some mathematical questions which one wants to knows if are demonstrable or refutable, for instance the Goldbach conjecture, Collatz conjecture and so on. But what happens if that can't be ...