# Are my proofs of elaborate consistency?

I have to complete some proofs for homework and here are my attempts. I have reviewed my proofs many times such that there would be no erroneous symbols used, to my best efforts.

For my first proof I have to use the field axioms to prove certain operations are true.

Field axiom (A1) states $x, y \in F \rightarrow x + y \in F$. It was used here to add $(-r)$ to the rational on each side.

Field axiom (A5) states that $\forall x \in F, \exists -x \in F : x + (-x) = 0$. It was used here to show $r + -r = 0.$

Field axiom (M5) states $x \in F, x \neq 0 \rightarrow \exists \frac{1}{x} \in F : x(\frac{1}{x}) = 1$.}

Field axiom (M4) states $F$ contains an element $1 \neq 0 : 1x = x$ for all $x \in F$.

If $r$ is rational $(r \neq 0)$ and $x$ is irrational, prove $r + x$ and $rx$ are irrational.

(Proof by contradiction) Suppose $r + x$ is rational. Then $$\exists a, b \in \mathbb{Q} : \frac{a}{b} = r + x$$ Since $\mathbb{Q}$ is an (ordered) field, the field axioms are applicable. First using field axiom (A1) and then using field axiom (A5), the above equation can be re-written as $$\frac{a}{b} + (-r) = (-r) + r + x \rightarrow \frac{a}{b} + (-r) = x$$ The absurdity is clear now: although the LHS is in $\mathbb{Q}$, the RHS isn't. RAA.

Similarly, suppose $rx$ is rational. Then $$\exists a, b \in \mathbb{Q} : \frac{a}{b} = rx$$ which, by (M5) and (M4) should give us $$(\frac{1}{r})ab = (\frac{1}{r})rx \rightarrow (\frac{1}{r})ab = 1x = x$$ The absurdity is clear now, just as before. RAA.

Let $A$ be a nonempty set of real numbers bounded below. Let $-A$ be the set of all numbers $-x$, where $x \in A$. Prove $$inf A = -sup(-A)$$

Proof: Since $A$ is bounded below, there exists a nonempty set $L$ consisting of the lower bounds of $A$. More specifically, $$\forall a \in A,\hspace{2 pt} \exists l \in L \hspace{2 pt}: l \leq a$$ Thus there exists a greatest lower bound of $A$, denoted as $\gamma \in L$ such that $\hspace{2 pt}l \leq \gamma = inf \hspace{2 pt}A$. Therefore $\sup \hspace{2 pt}L = \gamma$, since $l \leq \gamma$.

Of course, since $-x \leq 0 \leq x$, $sup (-A) = 0 \rightarrow -sup(-A) = 0 = inf(A)$. QED.

Prove that $\sqrt{15}$ is irrational.

(Proof by contradiction) Suppose that $\sqrt{15}$ is rational. Then $$a, b \in L : \frac{a}{b} = \sqrt{15}$$ A little algebra yields $a^2 = 15b^2$. Thus, $15|a^2 \rightarrow 3|a and 5|a$ and so 3 and 5 divide $a$ as well. Since $5|a$, $\exists k : a = 5k$. Some more algebra yields $$5k^2 = 3b^2$$ The absurdity is clear now: Since 5 and 3 are relatively prime, $5|b^2 \rightarrow 5|b \rightarrow b = 5k$ when a and b were originally meant to have no common factor (in this case, 5). RAA.

Prove that if the ordered set $S, <$ satisfies the greatest lower bound property then it satisfies the least upper bound property.

Let $\beta$ be some arbitrary element of $S$. Let $A \subset S$ be a set such that it contains all of the lower bounds $\alpha$ of $S$, so $\alpha \leq \beta$.

Let $\gamma$ be the greatest lower bound of $A$. Then for all $\alpha$, $\alpha \leq \gamma$. Also there exists some $\beta \in S$ such that $\gamma \leq \beta$. Suppose by contradiction $\beta < \gamma$. Then $\beta$ is a lower bound of $A$, but not the greatest; a contradiction. Thus all $\beta$ are upper bounds of $A$, so $\alpha \leq \gamma \leq \beta$. Thus $\gamma$ is the least upper bound of $A$. QED.

-
Your supremum/infimum proof definitely needs some work. I haven't finished the rest. –  dfeuer Aug 31 '13 at 3:13
There's two of them, and I certainly struggled on the first @dfeuer. –  Don Larynx Aug 31 '13 at 3:14
What are you allowed to assume for your $\sqrt {15}$ proof? You write that $15\mid a^2\implies 15\mid a$ without explanation. –  dfeuer Aug 31 '13 at 3:15
They could both use some work, but the first more glaringly so. –  dfeuer Aug 31 '13 at 3:17
@dfeuer fixed the irrationality proof –  Don Larynx Aug 31 '13 at 3:22

The statement that if $(S,\lt)$ satisfies the glb, then it satisfies the lub property is false. For example, let $S$ be the negative reals with the usual $\lt$. Then every non-empty subset $A$ of $S$ which is bounded below has a glb, but $S$, and many of its subsets, does not have a lub.

If you assume that $S$ is an ordered field (and much less will do) then it is indeed true. The proof comes from your second problem.

Let $F$ be an ordered field. Suppose that every non-empty subset of $F$ that is bounded below has an glb (inf). We show that every non-empty subset of $F$ tat is bounded above has a lub (sup).

So suppose that $A$ is bounded above, say by $b$. Let $-A$ be the set of all $-x$, where $x\in A$. We show that $-A$ is bounded below. For let $-x\in -A$. Since $x\le b$, we have $-b\le -x$, and therefore $-b$ is a lower bound of $-A$.

By the glb property, $-A$ has a glb, which it is convenient to call $-c$. We show that $c$ is a lub of $A$. (Note: we are saying "a" glb, but we know that glb, and lub are unique when they exist.)

So first we show that $c$ is an upper bound of $A$, that is, that $x\le c$ for all $x\in A$.

We know $-c$ is a lower bound of $-a$. So $-c\le -x$ for all $x\in A$. It follows that $x\le c$ for all $x\in A$.

Finally, we show that $c$ is (the) least upper bound of $A$, in other words that there is no cheaper upper bound. Suppose to the contrary that $d\lt c$ is an upper bound for $A$. Then $x\le d$ for all $x\in A$. It follows that $-d\le -x$, so $-d$ is an upper bound for $-A$. But $-d\gt -c$, which contradicts the fact that $-c$ is the greatest lower bound of $-A$.

Remark: Over and over, we have used only one fact: multiplying by $-1$ reverses inequalities.

-
So if I assume that transitivity holds, then the statement is still true? –  Don Larynx Aug 31 '13 at 4:03
I don't know what you mean by transitivity in this case. The assertion, unless you are, say, working in an ordered field is false. The argument is completely unclear, and cannot be made clear, since it fails for the counterexample I gave in my answer. –  André Nicolas Aug 31 '13 at 4:09
You start with the mysterious "Let $A \subset S$ be a set such that it contains all of the lower bounds $\alpha$ of $S$." You should start with: Let $A$ be a non-empty set which is bounded above. We will show that $A$ has a least upper bound (sup). But you will not be able to use the glb property to do that, unless, for example, you have the $-$ operation available, i.e. you are working in an ordered field, or at least ordered abelian group. –  André Nicolas Aug 31 '13 at 4:18
True, and I have been noticing I have been rather unclear in my definitions. –  Don Larynx Aug 31 '13 at 13:20
Nicolas where do I go after glb? I re-defined it correctly offline. –  Don Larynx Aug 31 '13 at 22:16

For the first proof, you don't need $a, b \in \Bbb{Q}$, since that's not the definition of a rational number. I think you mean $a, b \in \Bbb{Z}$, but it's slightly more convoluted than it needs to be in that case.

I advise you not to use the compact notation in your second proof, since it's not actually correct. Until you're experienced with proofs, avoid trying to take shortcuts.

You also come to an incorrect conclusion, namely that $\inf A = 0$.

Your conclusion that $b = 5k$ is not correct, since you already have defined $k$ in a different context, but the general logic is fine. You also don't state all your assumptions, so the contradiction isn't clear.

But really, in stating that $15 | a^2 \implies 15 | a$ uses some facts about numbers that you never state. Since $15$ is not prime, the statement isn't immediately clear.

The fourth proof needs a fair amount of work, too. I've noticed that, in a number of the questions you've asked, you put quantifiers and definitions of objects out of order. In general, make sure that you define objects before you start using them.

-
I think the problem is not so much that $15$ isn't prime as that proving that fact for primes takes some work. I imagine it requires the fact that every natural number has a unique prime factorization, no? –  dfeuer Aug 31 '13 at 3:28
@dfeuer Yes, that's the most salient property. My awkward phrasing was due to keeping this question in mind, in which the asker has shown some misunderstandings of how to carry out the mechanics of these proofs. I was hoping to encourage details. –  user61527 Aug 31 '13 at 3:32
@T.Bongers I re-attempted my proof and realized you are correct. However where do I go from where I stopped on greatest lower bound? –  Don Larynx Aug 31 '13 at 22:15

You are being careful and correct, but I find your proofs a little elaborate, maybe wordy.

For example in the first case x + r, you could say that if x + r is rational, so is x + r - r = x; you don't have to get into a/b. Similarly for rx just say if it is rational so is (1/r)rx = x.

With your $\sqrt 15$ you start out well with 5a2 = 3b2. This tells you immediately that b must be a multiple of 5. I don't know what all the other things are about such as |b2 → 5|. Just take your information that b = 5c and plug it back into a/b = $\sqrt 15$. You can get another equation like the first which will give you a contradiction.

In your inf/sup case, you can start by saying that if A has a lower bound it has a greatest lower bound L (I use greek letters only when I have to). You do not have to discuss sets of lower bounds. What you said after the greatest lower bound is okay. But more simply if -a ε-A it cannot be greater than -L because that would imply a < L. And -L cannot be less than any -a, because that would imply L > a, and thus not a lower bound.

I'm stumped on your last one because I don't know what is meant by the lower bound property on an ordered set S.

-
A set S satisfies the greatest lower bound property when $E \subset S$, $E$ is nonempty, and $E$ is bounded above, $inf E = S$ follows I'll try again on my glb/lub questions.. –  Don Larynx Aug 31 '13 at 3:52
where do I go after greatest lower bound? –  Don Larynx Aug 31 '13 at 22:16
Sorry Jossie, I'm still not getting it. infE is a number and S is a set, so I don't see how infE could equal S. –  Betty Mock Sep 1 '13 at 1:52