# Non-Constructive Proofs

I have just started to read more about constructivism and its critique towards classical logic. As I was reading, I came across a passage about non-constructive results, that mentioned the following three theorems (without any discussion or proofs) as examples. I have tried to supply each statement with a proof. However, since I don't have any previous experience dealing with this subject, I am sure that there are mistakes contained in my answers. That is why I post my attempts here in the hope that I can receive feedback from this generous community. Cheers!

Theorem 1. Either $e+\pi$ or $e-\pi$ is transcendental.

Proof: Suppose $e+\pi$ and $e-\pi$ are both algebraic numbers.Then, as algebraic numbers are closed under the usual arithmetical operations we would have that the sum $2e$ and the difference $2\pi$ of the two terms would be algebraic. But this contradicts the fact that both $e$ and $\pi$ are transcendental. Hence, either $e+\pi$ or $e-\pi$ is transcendental. $\square$

Theorem 2. Suppose that $P$ is an infinite set of path. Then there is an infinite string $d_{1}d_{2}\dots$ such that for every $n$, the string $d_{1}d_{2}\dots d_{n}$ is an initial segment of some path in $P$.

Proof: Let $p$ be an infinite set of paths. Then if we start at any vertex, say $v_{1}$, we have that every single vertex in the infinite set $P$ can be reached from this point. For if this was false, then the entire $P$ would be the union of finitely many finite sets, and thus finite, which contradicts our initial assumption that $P$ is an infinite set of paths. As such we are in a position to choose another vertex, say $v_{2}$. A similar argument will show that the same procedure can be repeated. Thus, if we continue in this fashion, we find that an infinite simple path can be constructed by the use of mathematical induction. The inductive hypothesis is that there are infinitely many nodes reachable by a simple path from a particular node $v_{j}$ that does not go through the one of the finite set of vertices. The inductive argument is that one of the vertices adjacent to $v_{j}$ satisfies the induction hypothesis, even when $v_{j}$ is added to the finite set. We that for all $n$ it is possible to choose a vertex $v_{k}$ as the construction describes. The set of vertices chosen in the construction is then a chain in the string, because one was selected to be adjacent to the previous one, and as such guaranteeing that the same vertex is not double-counted. Hence, we have that there is an infinite string $d_{1}d_{2}\dots$ such that for any $n$, the string $d_{1}\dots d_{n}$ is an initial segment of some path in $P$. $\square$

For the last theorem, we remind ourselves of the definition of barred by.

Definition An infinite path is said to be barred by $P$, if there is some $n$ such that $d_{1}\dots d_{n} \not \in P$.

Theorem 3. If every infinite path $d$ is barred by $P$, then $P$ must be finite.

Proof: Suppose $P$ were infinite. Then this would imply that we could find a path $\delta$ that continuous indefinitely. But this contradicts the fact that every infinite path $d$ is barred by $P$. Hence $P$ cannot be infinite, but rather finite. $\square$

-
A Nit-Pick: As you've worded the proof of Theorem 1, the transcendence of both $e$ and $\pi$ are used. However, the result can be proved more simply by only making use of the transcendence of $e$. In fact, with a very slight rewording of the proof, you can get by with assuming "$e$ is transcendental or $\pi$ is transcendental". Finally, this last formulation allows you to observe the following: If at least one of $x,$ $y$ is transcendental, then at least one of $x+y,$ $x-y$ is transcendental. [And "transcendental" can be replaced throughout with "irrational" for an additional result.] – Dave L. Renfro Nov 10 '13 at 16:37