Too simple to prove?

Question

Can a problem be too simple to prove completely one way or the other?

Its a question I've been asking myself for a little while now.

I've been playing around with some open math problems that (at first glance) appear to be simple, but alas,answers to these problems have eluded all.

Also, I'm new here so I'm trying to engage with the community,and so I would like to pose a question.

Along the lines of:

Can an integer be neither odd nor even?

When you first read it it's obvious, "no it can't it has to be one or the other", I agree with that statement but what is the proof?

Looking forward to conversing below.

Answer 1

As there is already a nice proof by Hagen von Eitzen for your odd/integer problem, I won't give another one. Instead I want to talk about the general question of your post:

There are lots of statements one encounters that are "immediately clear" and "require no proof". For example let $A,B$ be sets. Then it is clear from the definition of the two sets, that $A\cap B\subset A$ and $A\cap B\subset B$. Similar things can be said about $A\subset A\cup B$, $A\setminus B\subset A$ etc.

In my oppinion, sentences and proofs in a book like "This is clear/this follows directly from the definition/Obviously we have..." are to be read as a challenge to prove these statements yourself. Only then can you be sure that you understand the basics of whatever you are dealing with.

While you only have limited time during a lecture and it might seem more important to not cover those simple proofs, every statement still needs to be proven to be true. This is where you start to do mathematics, sitting down and rigorously proving even the simplest statements which seemed so obvious back in school (Why is $0\times a =0$ in a field? That must be true because we multiply with zero, but there is a proof for that which is quite difficult for a beginner student).

This doesn't only apply to simple statements but also happened e.g. to the Jordan curve theorem. The statement itself is very simple and can be understood without knowing anything about mathematics: just draw a plane, a simple closed curve and you can explain the meaning of the theorem. Proving this obvious result seemed unnecessary until (I think it was Bolzano) observed, that the statement is not self-evident. And the proof itself is rather difficult and requires advanced mathematics (normally you get to see the proof after taking a course in complex analysis).

Answer 2

Definition 1. Let $n$ be an integer. We say that $n$ is even if there exists an integer $k$ such that $n=2k$.

Definition 2. Let $n$ be an integer. We say that $n$ is odd if it is not even.

Theorem. There is no integer that is neither odd nor even.

Proof. Assume $n$ is an integer that is neither odd nor even. In particular, $n$ is an integer that is not even. By definition 2, $n$ is odd, contradiction! $\square$

---

Remark: This shows that I am not an intuitionist, cf. e.g. https://en.wikipedia.org/wiki/Brouwer%E2%80%93Hilbert_controversy#Validity_of_the_law_of_excluded_middle

Answer 3

An integer $\,n\,$ is even or odd since, by the division algorithm, $\,n\,$ has a unique remainder $0$ or $1$ when divided by $2$. By definition $\,n\,$ is even if it has remainder $0$ and odd if it has remainder $1$.

Similarly many other simply-stated problems have very short, simple proofs. But this does not imply that all simply-stated problems necessarily have simple proofs. Indeed, as you mention there are simple open problems such as the Collatz conjecture that have eluded proof.

It is a common false hunch that simple (short) statements should have short proofs. This is easily refuted using only rudimentary logic. For any formal system that has nontrivial power (e.g. Peano arithmetic) there is no recursive algorithm that decides theoremhood. This implies that there is no recursive bound on the length of proofs (if $\,L(n)\,$ bounds the length of proofs of a statement of length $\,n,\,$ then we could test for theoremhood simply by enumerating and testing all possible proofs of length $\,\le L(n)).\,$ Therefore there exist short-stated theorems with proofs so immensely long that they are probably not amenable to human comprehension (these results date back to Goedel's 1936 paper on speedup theorems).

It remains to be seen if there exist mathematically interesting theorems like this. There may be examples in Collatz-like congruential iterations (similar to the difficult open $3 x+1$ problem) that were discovered in the wild while analyzing Busy Beaver holdout machines (while attempting to find the smallest universal Turing machines). John Conway has shown that there exists similiar simple congruential iterations with undecidable halting problem. That such undecidable problems may be encoded so succinctly in programs for tiny Turing machines should not come as a surprise to anyone familiar with the above simple results from logic. They are a testament to the power of ingenuity - whether it be human (in powerful mathematical theories) or nature (the DNA-based programs designed by evolution).