Analysis for Realsies: 4

As promised, here're a few alternative solutions to questions 2 and 3 from your second assignment!

Question 2: Carefully prove that if \(p\) is a prime number, then \(\sqrt{p}\) is irrational.

 We'll prove this by contradiction. Assume that \(p\) is a prime number and that \(\sqrt{p}\) is rational (premise). This means that there are coprime integers \(a\in\mathbb{Z},b\in\mathbb{N}\) such that  \(\sqrt{p}=\frac{a}{b}\). Hence, \(p=\frac{a^2}{b^2}\), which in turn means that \(a^2=pb^2\). By definition, this means that \(p\) is a factor of \(a^2\). At this point, the proof can take one of two directions...

Proof 1 (the direct approach):
Invoking the unique-prime-factorisation theorem (better known as the fundamental theorem of arithmetic), we see that \(a\) and \(b\) may be respectively uniquely expressed as a product of prime factors: \begin{align} a=p_1\times p_2\times\ldots\times p_n\text{ and }b=q_1\times q_2\times\ldots\times q_n\end{align}. Thus, the equation \(a^2=pb^2\) becomes: \begin{align} p_1\times\ldots\times p_m\times p_1\times\ldots\times p_m=p\times q_1\times\ldots\times q_n\times q_1\times\ldots\times q_n.\end{align} Since \(a^2=pb^2\) is an integer - \(\mathbb{Z}\) is, after all, closed under multiplication - the above expressions must both be the unique (up to reordering of factors) prime factorisation of \(a^2\). However, the left-hand-side has \(2n\) terms, whilst the right-hand-side has \(2m+1\) terms\(\Rightarrow\)CONTRADICTION!

Comments: this is a very elegant approach - and to be honest, I've never thought of it before. Probably because I've always just gone to this second method:

Proof 2 (the standard approach):
Similarly invoking the unique-prime-factorisation theorem, we express the equation \(a^2=pb^2\) as: \begin{align} p_1\times\ldots\times p_n\times p_1\times\ldots\times p_n=p\times q_1\times\ldots\times q_m\times q_1\times\ldots\times q_m.\end{align} This means that \(p\) must be equal to one of the \(p_i\). Thus, \(p=p_i\) is a divisor of \(a\), that is: there exists \(k\in\mathbb{Z}\) such that \(a=pk\). This in turn implies that \(p^2k^2=pb^2\), and hence \(pk^2=b^2\). By the same argument as above, this means that \(p\) is also a divisor of \(b\). But this then means that \(a\) and \(b\) both have \(p\) as a factor, thus contradicting the fact that \(a\) and \(b\) are coprime...and we're done.

Comments: this more-or-less follows the approach you guys took for proving that \(\sqrt{2}\) is irrational.

Note that the rough ideas of these proof should work more generally. And you should be able to use this to show that the square roots of "square-free" integers are irrational!

And now, it's time for...

Question 3: Carefully prove that if \(A\) and \(B\) are nonempty [bounded] sets such that for each \(a\in A, \exists b\in B\) with \(a<b\) and for each \(b\in B,\exists a\in A\) with \(a<b\) then \begin{align} \inf A\leq\inf B\text{ and }\sup A\leq \sup B.\end{align} Well, the thing about this question is that it really should have been split into two questions. Instead of showing that: \begin{align} (\forall a\in A, \exists b\in B, a<b)&\wedge (\forall b\in B, \exists a\in A, a<b)\\ \Rightarrow (\inf A\leq \inf B)&\wedge (\sup A\leq \sup B), \end{align} I would have liked you guys to try to prove the following two facts: \begin{align}(\forall a\in A, \exists b\in B, a<b)&\Rightarrow (\sup A\leq \sup B)\text{ and}\\ (\forall b\in B, \exists a\in A, a<b)&\Rightarrow (\inf A\leq \inf B). \end{align} These are really disparate facts, and it might be a bit more illuminating to consider them separately. In fact, I'm just going to prove the first of these two facts - I'll leave it as an exercise for you to repeat the proof and derive the second.

Method 1 (by definition):

This first method utilises one of the defining properties of the supremum of a set - that is is the smallest upper bound. So, if we can show that \(\sup B\) is also an upper bound for the set \(A\), then by definition, the smallest upper bound \(\sup A\) of \(A\) must be less than or equal to \(\sup B\). In order to show that \(\sup B\) is an upper bound of \(A\), consider an arbitrary element \(a\in A\). Unpacking our premise that \begin{align}\forall a\in A, \exists b\in B, a<b \end{align} we see that there is some \(b\in B\) such that \(a<b\). But then, by the definitional fact that the supremum \(\sup B\) of \(B\) must be greater than or equal to anything in \(B\), we conclude that: \begin{align} \text{given an arbitrary }a\in A, \exists b\in B, a<b<\sup B.\end{align} This of course tells us that \(\sup B\) is an upper bound for \(A\), and we're done.

Comment: this is a particular elegant/clean method, and as such might be difficult to see the first few times that you approach questions of this nature. But with more practice, you'll be able to see this no probs!

Method 2 (by another definition):

Our second method is based on the slightly more geometric/intuitionistic characterisation of the supremum \(\sup A\) of a set \(A\) satisfying the properties that:

1. an upper bound of \(A\), and
2. for any \(\epsilon>0\), \(\sup A-\epsilon\) is less than some element \(a\in A\).

 Combining this second statement and our premise, we see that for every \(\epsilon>0\), there exists some \(a(\epsilon)\in A\) and some \(b(\epsilon)\in B\) (I put in the \(\epsilon\)s to remind us that these two numbers depend on which \(\epsilon\) we choose) such that \begin{align}\sup A-\epsilon <a<b\leq\sup B.\end{align}. So, we see that \(\forall \epsilon>0, \sup A-\epsilon<\sup B\). Now, at this point, most of us are probably happy to conclude from this (and from taking \(\epsilon\) to be aribitrarily small) that \(\sup A\leq\sup B\). But let's prove this properly by contradiction:

Let's assume that \(\sup A>\sup B\), then choose \(\epsilon=\sup A-\sup B>0\) and we know that \(\sup A-\epsilon<\sup B\), hence: \begin{align}\sup B=\sup A-(\sup A - \sup B)=\sup A-\epsilon>\sup B.\end{align} Which, is a contradiction, because a number cannot be strictly greater than itself. This then gives us the desired conclusion that \(\sup A\leq\sup B\). =)

Now, I also promised to write up solutions to Question 6 from your tutorial because that was kinda tricky (and the official solutions don't have it). And I will...at some point during the week? For now, I just want to really encourage you guys to try those "Do this for homework" exercises - they're pretty involved, but they're questions that you can learn a HUGE deal from.

Huzzah?!??

=)