1.4 Exercise 3

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$ .

S	M	T	W	T	F	S
« Aug
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30

Leave a Reply Cancel reply

Categories

Archives

Business

Math