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.

Say an integer is silly if it is more than nine; otherwise call it sullen. Can you prove that there is no integer that is neither silly nor sullen? — symplectomorphic, Aug 12 '16 at 07:37
I edited your question and changed "to simple" into "too simple". Was I correct in doing so? — drhab, Aug 12 '16 at 07:49
Yes the subtlety of English is often lost when typing on a device that one usually uses for texting, lol — Lonnie Hibbs Jr, Aug 12 '16 at 07:58
@drhab all I'm not 100% positive I know that too usually means "also", but I would guess that they are relatively interchangeable for everyday needs, people get it. — Lonnie Hibbs Jr, Aug 12 '16 at 08:06
@LonnieHibbsJr I added an answer which I think touches on some of the ideas implicit in your question. — Bill Dubuque, Aug 12 '16 at 13:55

score 6 · Accepted Answer · answered Aug 12 '16 at 07:49

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).

+1. I was wondering how a question of this kind can be answered reasonably satisfactorily. You've done a good job! — P Vanchinathan, Aug 12 '16 at 07:59
Thank you for your response, great points, I'm am very amateur only graduated highschool but love mathematics, it's fascinating how what can appear to be very daunting is quite easy and what seems like it should be easy seem quite impossible, example: collate conjecture — Lonnie Hibbs Jr, Aug 12 '16 at 08:03
Problems that - at first sight - seem to be easy to solve can be very very difficult. This also occurs in real life. E.g. stop smoking? Well, just don't touch any cigarettes and the problem is solved (easy solution)... — drhab, Aug 12 '16 at 08:17

Hagen von Eitzen · Answer 2 · 2016-08-12T07:49:24.933

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

edited Aug 12 '16 at 07:49

answered Aug 12 '16 at 07:33

Hagen von Eitzen

374,180

True but in an infinite set of integers is it proven you will either find integer K or not. I mean mathematically not intuitively. – Lonnie Hibbs Jr Aug 12 '16 at 07:39
3

This is a mathematical proof. The logic behinsd it is indeed: There either is or is not such a $k$. Interestingly, the word "intuitive" in a different meaning comes into play. In intuitionism, a statement of the form $P\lor \neg P$ need not be true. As in: The number of protons in the Universe is either even or odd. But as we can neither prove that it is even, nor can we confidently say that it is odd, intuitionists may not take for granted that it is either odd or even ... – Hagen von Eitzen Aug 12 '16 at 07:39
I understand, but it doesn't say, as n get tremendously huge that the number you have , has a K or not. – Lonnie Hibbs Jr Aug 12 '16 at 07:47

Bill Dubuque · Answer 3 · 2022-04-28T15:59:18.453

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).

Too simple to prove?

3 Answers3