Archive

Archive for July, 2009

1.4 Exercise 3

July 31st, 2009 No comments

To get acquainted with the set of positive integers and how this set is related to "proving things by induction," this problem is a great primer!

"(a) Show that if  \mathcal{A} is a collection of inductive sets, then the intersection of the elements of  \mathcal{A} is an inductive set.

(b) Prove the basic properties of  \mathbb{Z}_+ :

  • (1)  \mathbb{Z}_+ is inductive;
  • (2) (Principle of induction). If  A is an inductive set of positive integers, then  A = \mathbb{Z}_+ ."

(Taken from Topology by James R. Munkres, Second Edition, Prentice Hall, NJ, 2000. Page 34.)

-----

SOLUTION

(a)

We want to attempt this by contrapositive.  Thus we want to show that if the intersection of the sets in the collection is not inductive, then the collection is not a collection of inductive sets.  There are two ways in which the intersection of the sets in the collection can fail to be inductive: if  1 is not in the intersection of the collection, or if for some element  x in the intersection of the collection,  x + 1 is not in there too.

First, if  1 is not in the intersection of the collection  \mathcal{A} , this means at least one set of such collection does not contain  1 as an element... such a set or several are therefore not inductive, differing from the definition of ``inductive.''  But then  \mathcal{A} is not a collection of (all) inductive sets.

Second, if for some element  x in the intersection the collection,  x+1 is not in the intersection of the collection, then this of course means that at least one of the sets of the collection does not contain  x+1 as an element.  Since each individual set of the collection did contain  x in the first place (this element being in the intersection of the collection), such a set or several fail the definition of ``inductive."  Naturally, then the collection is not a collection of inductive sets.

(b)

To prove (1), we resort to the definition of  \mathbb{Z}_+ :  \mathbb{Z}_+ = \cap_{A \in \mathcal{A}} A , with  \mathcal{A} is a collection of (all) inductive subsets of  \mathbb{R} .  Next, apply the result of Part (a), and  \mathbb{Z}_+ is inductive.

Recall that  A is an inductive set of positive integers. To show (2), we do so in the usual way we show mutual containment, first by proving  A \subset \mathbb{Z}_+ and then  A \supset \mathbb{Z}_+ .  Thus:

 A \subset \mathbb{Z}_+ .   1 \in A since  A is inductive, and  1 \in \mathbb{Z}_+ since  \mathbb{Z}_+ is inductive (by (1)).   Next,  x is an element of  A , and since it is an (positive) integer, we know it is generated by successive additions of 1.  Such an  x is common to all inductive sets, and so it belongs to the intersection of the collection of all inductive sets:  x \in \cap_{A \in \mathcal{A}} A .  Well,  x + 1 is an element of  A being a positive integer too, and such element is common to all inductive sets as well; it lies in the collection of all inductive sets. (Notice we are using actual induction to show this inclusion).  Thus all elements of  A lie in the intersection of all inductive sets of  \mathbb{R} .

 A \supset \mathbb{Z}_+ .  Pick an element  x \in \mathbb{Z}_+ .  Since  x \in \cap_{A \in \mathcal{A}} A , and  A is a member of such collection, then such an  x \in A .

1.4 Exercise 2

July 25th, 2009 No comments

Another one of those really really long problems, but oh well... after this one the exercises seem more interesting.  As before, I'm doing five by five until the end.

"Prove the following laws of inequalities for  \mathbb{R} , using axioms (I)-(VI) along with the results of Exercise 1:

A Mixed Algebraic and Order Property

VI.  If  x>y , then  x + z > y + z .  If  x>y and  z > 0 , then  x \cdot z > y \cdot z .

(a)  x > y and  w > z \Rightarrow x + w > y + z .

(b)  x > 0 and  y > 0 \Rightarrow x + y > 0 and  x \cdot y > 0 .

(c)  x > 0 \iff -x < 0 .

(d)  x > y \iff -x < -y .

(e)  x>y and  z<0 \Rightarrow xz < yz .

(f)  x \neq 0 \Rightarrow x^2 > 0 , where  x^2 = x \cdot x .

(g)  -1 < 0 < 1 .

(h)  xy > 0 \iff x and  y are both positive or both negative.

(i)  x > 0 \Rightarrow \frac{1}{x} > 0 .

(j)  x > y > 0 \Rightarrow \frac{1}{x} < \frac{1}{y} .

(k)  x < y \Rightarrow x < \frac{x + y}{2} < y ."

(Taken from Topology by James R. Munkres, Second Edition, Prentice Hall, NJ, 2000. Page 34.)

----

SOLUTION

(a)

1.4.2.a

(b)

First we prove the implication  x > 0 and  y > 0 \Rightarrow x+y > 0 .

1.4.2.b.I

Next, we show the implication  x > 0 and  y > 0 \Rightarrow x \cdot y > 0 .

1.4.2.b.II

(c)

First, we show the forward implication by direct proof.

1.4.2.c.I

Then, the backward implication, also by direct proof.

1.4.2.c.II

(d)

First, the forward implication by direct proof.

1.4.2.d.I

The backward implication is the reverse argument.

1.4.2.d.II

(e)

1.4.2.e

(f)

We separate this by cases.  Case  x > 0 .

1.4.2.f.I

Next, case  x<0 .

1.4.2.f.II

(g)

We will prove that  0<1 by indirect proof/contradiction.  Suppose  1 \leq 0 .   In fact suppose  1 = 0 , but this contradicts Axiom III.  Thus  1 < 0 . Now pick any  z > 0 , as per the hypothesis of Axiom VI.  Then  1 \cdot z < 0 \cdot z by direct application of Axiom VI, which results in  z < 0 .  But this contradicts our picking  z is positive, and thus 1 is not less than zero.

Now, since we've shown that  0 < 1 , direct application of part (2c) suggests that  +0 > -1 , or, by rearranging,  -1 < 0 .  This completes our work, and  -1 < 0 < 1 .

(h)

We prove the forward implication by indirect proof.  Thus suppose either  x or  y is negative (not both positive or both negative), say  x .  Then by the hypothesis of the implication,  xy > 0 .  Following through,  x \cdot y \cdot y^{-1} > 0 \cdot y^{-1} by Axiom IV.  Notice that the existence of the inverse  y^{-1} is given by the fact that  y cannot be zero, since if it were this would imply  0 > 0 , a clear contradiction.  Next,  x \cdot 1 > 0 by Axiom IV, Part (1b). Finally this implies that  x > 0 by Axiom III, a contradiction of our pick of  x negative.  To be extremely thorough (although the above should suffice), next pick  y is negative, and follow the same recipe to obtain  y > 0 , again a contradiction.  This completes the proof of the forward implication.

The backward implication can be proven rather quickly by the direct method.  Suppose  x > 0 and  y > 0 .  Then, by Axiom VI,  x \cdot y > 0 \cdot y , which, by Part (1b), means  x y > 0 , as we wanted to show.  Suppose then  x < 0 and  y < 0 .  By Part (2c), this means  -x > 0 and  -y > 0 .  By Axiom VI,  (-x) \cdot (-y) > 0 \cdot (-y) , and by Part (1e), this means  -(-(xy)) > 0 which implies  xy > 0 using Part (1d). As we wanted to show.

(i)

I proceed here again by contradiction or indirect proof.  Assume that  \frac{1}{x} \leq 0 .  In fact suppose  \frac{1}{x} = 0 .  By the multiplication property of equality,  x \cdot \frac{1}{x} = x \cdot 0 .  Of course we can multiply thusly because the mere existence of the reciprocal implies  x is nonzero. But then we obtain  1 = 0 , which contradicts Axiom III.  Therefore,  \frac{1}{x} < 0 , or, to align notation,  0 > \frac{1}{x} .  Then multiply by  x on both sides, as per Axiom VI:   0 \cdot x > \frac{1}{x} \cdot x .  Applying through the notions we know already, we obtain  0 > 1 , a contradiction of Part (2g).  Thus our initial assumption was wrong, and the implication is true as originally stated.

(j)

Again proceed by contradiction, and assume  \frac{1}{x} \geq \frac{1}{y} .  Suppose first that  \frac{1}{x} = \frac{1}{y} .  Since  x and  y are nonzero by hypothesis, we obtain by the Multiplicative Property of Equality that  x = y , but this then contradicts the premise that  x is larger than  y .   Next suppose that  \frac{1}{x} > \frac{1}{y} .  Since  x is nonzero and positive, we can easily multiply thusly, without affecting the inequality:  \frac{1}{x} \cdot x > \frac{1}{y} \cdot x , and we are justified by Axiom VI.  We obtain  1 > \frac{x}{y} .  Multiply by nonzero and positive  y like this:  1 \cdot y > \frac{x}{y} \cdot y again justified by Axiom VI and without affecting the inequality, to obtain  y > x .  This however contradicts our hypothesis, and we've shown the implication as originally stated actually holds.

(k)

Again suppose otherwise, that either  x \geq \frac{x+y}{2} or  \frac{x+y}{2} \geq y .  In the first case, multiply by two on both sides to obtain  2x \geq x+y , or in effect  (1+1) x \geq x + y .  Multiplying through implies  x + x \geq x + y , or  -x + x + x \geq -x + x + y or  x \geq y .  This last statement contradicts the hypothesis, so our first assumption cannot be true. In the second case, do the same and obtain  x + y \geq 2y or  x + y \geq (1 + 1) y or  x + y \geq y + y or  x + y + -y \geq y + y + -y or finally  x \geq y , again a contradiction of the hypothesis, which means the second assumption cannot be true either.  The statement as originally posited therefore must be true.