# “It looks straightforward, but actually it isn't”

In a previous topic, I asked about proof of statements which are simple but incorrect.

Here, I ask about statements which seems, at a first glance, straightforward, but if we try to write a proof, we can see it's much harder than it looked. So I expect the answers to contain:

1. the statement;
2. why it looks easy to prove;
3. why actually it isn't.
-
I love this. It will be a source of examples to show why proofs are required instead of just saying it's obvious. –  Git Gud Jun 9 '13 at 10:44
Similar question on MO.${}{}{}{}{}{}$ –  Git Gud Jun 9 '13 at 10:51
I agree (and I already saw the thread). Here, maybe we can stress on things which are not necessarily of research level. –  Davide Giraudo Jun 9 '13 at 10:57
Perhaps one of the most striking and well-known examples is Jordan's Curve Theorem: en.wikipedia.org/wiki/Jordan_curve_theorem The proof is contained in one little, delicious book: "A Geometric Introduction to Topology" , by C.T.C. Wall. Very recommended. –  DonAntonio Jun 9 '13 at 11:01
@DavideGiraudo Consider a situation in which the actual proof is easy, but the gap between finding the statement intuitively obvious and the actual proof is huge. Should this also be considered? –  Git Gud Jun 9 '13 at 11:07

Continuing my comment, Jordan's Curve Theorem is, perhaps, one of the most well-known, easy-to-grasp, and very hard to prove theorems. We could write it as:

For any closed non self-intersecting smooth curve (i.e., a continuous and injective map from the circle $\,S^1\,$ to the real plane), its complement in the plane has exactly two connectedness components: one bounded and the other one unbounded.

Why does it look easy? Because most curves we can think of fulfilling the above conditions "trivially" fulfill the claim.

Why isn't its proof easy? Because, in the general case, it requires advanced stuff like homotopy groups, Hopf maps, covering maps, lifting properties for maps, etc. (I'm just talking of some aspects of the proof in the above mentioned book. There might be, and almost sure there are, other proofs).

-
The word "smooth" is not what you explain in the parenthesis. The smooth version of the Jordan curve theorem is easier to prove since (piecewise) smooth functions behave quite vell. // Some nice variants are discussed here. –  Martin Jun 9 '13 at 11:51
Yes, smooth is way more (differentiability of all orders and etc.), yet I can't see how JCT is easier in this case... –  DonAntonio Jun 9 '13 at 14:48
@DonAntonio: for an infinitely-differentiable curve you can quite simply construct a vector field flow that deforms it to $S^1$. –  leftaroundabout Jun 9 '13 at 16:12
If your curve, say S, is $C^1$ then, then you can consider the function $a \in \mathbb C \setminus S \mapsto \int_S \frac{\mathrm d z}{z-a}$, it is locally constant. You can use it to have a not-too-difficult proof. –  Lierre Jun 9 '13 at 19:36
Differentiable curves are much more "tame" than general curves. See also Wikipedia: Schoenflies problem. Note that if you go up one dimension, you can have a continuous (but not a differentiable one) embedding of $S^2$ in $R^3$ where the unbounded component of the complement is not simply connected (the Alexander horned sphere mentioned in the link). –  Jeppe Stig Nielsen Jun 9 '13 at 20:10

Property: Let $f : (0,+ \infty) \to \mathbb{R}$ be a continuous function. If $f(nx) \underset{n\to + \infty}{\longrightarrow} + \infty$ for all $x>0$, then $\lim\limits_{x \to + \infty} f(x)=+ \infty$.

Although the property is visual, the only proof I know uses Baire category theorem, a rather abstract viewpoint.

-
In the blog post What is deep mathematics? Gowers gives a rather detailed analysis of this exercise. –  Martin Jun 16 '13 at 13:28

This is not exactly an answer to your question, but I think it is somewhat close.

1. "If all the eigenvalues of a $0-1$ matrix $A$ are positive, they are all equal to $1$."
2. This statement is easy to prove: simply invoke A.M.$\ge$G.M. for the trace and determinant of $A$.
3. However, as far as I know, this is the only known proof. Without using A.M.$\ge$G.M., the problem becomes surprisingly difficult. I think the reason is that, other than the largest (in modulus) eigenvalue, we know very little about the smaller eigenvalues of a (entrywise) nonnegative matrix, not to say a $0-1$ matrix.
-

Theorem: 1 + 1 = 2

Proof:

Many pages of...

Whitehead, Alfred North, and Bertrand Russell (1910, 1912, 1913).
Principia Mathematica, 3 vols, Cambridge: Cambridge University Press.
Second edition, 1925 (Vol. 1), 1927 (Vols 2, 3).

Note that "The above proposition is occasionally useful."

-

Below I present a proof which is probably an overkill, however whenever I tried to simplify things I ended up finding it necessary to use some relatively deep stuff.

If anyone can provide a more elementary proof, I'll either delete this answer or add the proof to the answer, depending on how easy it is.

First a definition which I didn't explicitly use, but it's useful for whoever tries to give a more elementary proof.

Definition: A set is said to be finite if it is equinumerous to (with?) $[k\textbf{]}\color{grey}{(=\{x\in \omega :x<k\})}$, for some $k\in \omega$.

Statement: Let $A,B$ be finite sets. If $|B|\leq |A| \land A\subseteq B$, then $A=B$.

Proof: Suppose that $|B|\leq |A| \land A\subseteq B$ and $A\neq B$. Then $A\subset B$ and since they are finite $|A|<|B|$, (this uses the fact that a set is finite if, and only if, it isn't Dedekind infinite which is something way too deep considering out strongly the statement is assessed as intuitively true). And this is a contradiction due to the trichotomy of cardinal numbers (which isn't skin deep either).

The following proof was suggested (and typed) by T. Verron. Even though it is elementary it still serves my purpose: the gap between how easy it is to believe the statement and the proof is huge.

A possible elementary proof: Let $m = |A|$ and $n= |B|$. Let $f$ be a bijection from $A$ to $[m]$, and let $g$ be a bijection from $B$ to $[n]$. Define a new map $h : B \to [n]$, whose restriction to $A$ is $f$. For example, let $\sigma$ be a permutation of $B$, such that $\sigma(g^{-1}[m]) = f^{-1}([m])=A$, and define $h$ by

$h(x) = \begin{cases}f(x) & \text{if}\;\; x \in A \\ g \circ \sigma^{-1}(x) & \text{else}\end{cases}$

Then $h$ is a bijection from $B$ to $[n]$, and $h \circ f^{-1}$ is an injection from $[m]$ to $[n]$. That shows that $m \leq n$, and thus by assumption, that $m = n$. Now $f^{-1} \circ h$ is a bijection from $A$ to $B$, and by construction is the identity.

-
I disagree that the gap between T. Verron's proof and the statement is huge. To start with, the statement itself is obviously true, and any complexity in the proof is entirely due to the hoops you have to jump through to use the somewhat arbitrary definition of a finite set to make the proof 'rigorous'. Every step in T. Verron's proof is obvious and it's just a translation of our intuition into formal language. –  Donkey_2009 Sep 12 '13 at 17:54
Also, I'd remove the 'if and' from your 'this uses the fact that a set is finite if and only if it is [Dedekind finite]' - you only use the 'only if' direction, and the 'if' direction is independent of ZF, so it's definitely overkill! –  Donkey_2009 Sep 12 '13 at 17:55

I remember a lecture in measure theory, when we studied monotone convergence theorem.

One of my colleagues suggested to approximate the involved functions by simple ones, hence the result reduces to show it for such functions.

We can approximate in $L^1$ an non-decreasing sequence of integrable functions by a non-decreasing sequence of simple functions. But proving the result for simple functions is not so easy because the number of needed characteristic may vary with $n$. In particular, it seems it's not an immediate consequence of the fact that $\mu(A_n)\to \mu(A)$ when $A_n\uparrow A$.

-
How about this? Clearly $\int f\geq\sup_n\int f_n=:I$. Assume $I\lt\infty$. Let $g$ be an integrable simple function $g\leq f$ a.e. The support $G=\{g>0\}$ has finite measure and $g\leq C$. Fix $\varepsilon\gt0$ and consider $A_n=\{g\geq\varepsilon+f_n\}$. Then $\bigcap A_n=\{g\geq\varepsilon+\sup_n f_n\}\subseteq\{g>f\}$ is null, so $\mu(A_n) \to 0$. Since $g\leq f_n+C\chi_{A_n}+\varepsilon\chi_G$ integration gives $\int g \leq I+\varepsilon\mu(G)$ upon $n\to\infty$. Letting $\varepsilon \to 0$, it follows that $\int g\leq I$ and since $\int f =\sup_{g\leq f}\int g\leq I$, we're done. –  Martin Jun 11 '13 at 21:56
So, it works when $g$ is essentially bounded. But what is $C$ in your proof? –  Davide Giraudo Jun 12 '13 at 11:00
Since I took $g$ to be a simple function it only takes finitely many values, so it is automatically bounded by some constant $C$. The reason I chose $g$ to be simple is that this yields boundedness, and the additional hypothesis of integrability of $g$ ensures that the support $G$ of $g$ is of finite measure so that I can conclude $\mu(A_n) \to 0$ since $A_n \subseteq G$. Moreover, taking a simple $g$ allows me to use the definition of the integral of a non-negative function in the last sentence. –  Martin Jun 12 '13 at 11:10
Ah, I missed the word "simple" in the first line of your first comment. Thank you! –  Davide Giraudo Jun 12 '13 at 11:13
Thinking about this argument again, it looks like the standard argument and it is certainly less direct than what your colleague's idea would suggest, so +1. For some reason I am used to thinking of monotone convergence as a consequence of Fatou's lemma, but actually you can go the other way: first monotone convergence and then Fatou. If you prove Fatou's lemma directly, you use a very similar argument and if you look at what's used in the monotone convergence theorem you get the argument I gave above. –  Martin Jun 12 '13 at 11:21

In this thread, it is asked to show that given a continuous function on $[0,+\infty)$ for which $\lim_{x\to +\infty}f(x)=0$, there is a sequence of polynomials $(P_n,n\geqslant 1)$ such that $\sup_{x\geqslant 0}|f(x)-e^{-x}P_n(x)|<n^{-1}$.

The result seems to be a straightforward application of Stone-Weierstrass theorem (we could think that we have to reduce to a bounded interval using $f(x)\to 0$ at infinity), but the argument is circular.

We have to transform $[0,+\infty]$ into a compact interval by a continuous bijection.

-

An example is Prohorov theorem. I recall the context.

We have a metric space $(X,d)$ endowed with its Borel $\sigma$-algebra, and a collection of probability measures, say $\mathcal M$. We say that such a collection is tight if for each $\varepsilon>0$, one can find a compact $K$ such that for all $\mu\in\mathcal M$, we have $\mu(K)>1-\varepsilon$.

1. Prokhorov theorem states that for each tight sequence, one can find a subsequence which converges in law (that is, $\limsup_k\mu_{n_k}(F)\leqslant\mu(F)$ for all closed set $F$.

2. At a first glance, it's seems just a corollary of Riesz theorem, because we can characterize linear functional on the space of continuous functions.

3. But it's not so easy. For example, we have to reduce to the case where $X$ is a countable union of compact sets, and check consistency property (actually, Kolmogorov extension theorem is used). Billingsley's book Convergence of probability measures gives a complete proof and Koshnevisan's Multiparameters processes asks us to fill the details in an exercise.

-
I think the problem with 2 is that the Riesz theorem applies to compact (or locally compact) spaces, which we are not assuming for $X$. –  Nate Eldredge Jun 9 '13 at 14:09
I agree. And the assumption of tightness seems to say "Well, the behavior of the $\mu_n$ is quite similar to those on a compact up to $\varepsilon", but indeed, it's more subtle. – Davide Giraudo Jun 9 '13 at 14:27 I don't remember Billingsley using the Kolmogorv exten theorem in the proof. Ar you sure about that? – Michael Greinecker Jun 15 '13 at 20:45 @MichaelGreinecker It seems yes (p.38 in the 1968 edition), in order to go from the case$\Bbb R^k$to$\Bbb R^{\infty}\$. –  Davide Giraudo Jun 15 '13 at 20:52
@Davide Thanks. In his short "Weak convergence of measures", Billingsley gives a different proof that does without the Kolmogorov extension theorem and shows the result directly. –  Michael Greinecker Jun 15 '13 at 21:02