### Archive

Posts Tagged ‘induction’

## On Patchix by Patchix Products – Tying Up Loose Ends - (RWLA,MCT,GT,AM Part V)

In this post I want to "tie up a few lose ends."  For example, in my last post I stated that the patchix pattern

$\begin{array}{ccc} p_1(x,y) & = & 1 - cos(2 \pi x) cos(2 \pi y) \\ p_2(x,y) & = & 1 + \frac{cos(2 \pi x) cos(2 \pi y)}{2} \\ p_3(x,y) & = & 1 - \frac{cos(2 \pi x) cos(2 \pi y)}{4} \\ p_2(x,y) & = & 1 + \frac{cos(2 \pi x) cos(2 \pi y)}{8} \\ \vdots \\ p_t(x,y) & = & 1 - \frac{cos(2 \pi x) cos(2 \pi y)}{(-2)^{t-1}} \end{array}$

for $t \in \mathbb{Z^+}$, but I didn't prove it.  It's simple to do by induction: by the inductive hypothesis,

$p_1(x,y) = 1 - cos(2 \pi x) cos(2 \pi y) = 1 - \frac{cos(2 \pi x) cos(2 \pi t)}{(-2)^{1-1}}$

By the inductive step, assume

$p_k(x,y) = 1 - \frac{cos(2 \pi x) cos(2 \pi y)}{(-2)^{k-1}}$

Then,

$\begin{array}{ccc} p_{k+1}(x,t) & = & \int_0^1 p_1(1-y,t) \cdot p_k(x,y) dy \\ & = & \int_0^1 \left( 1 - cos(2 \pi (1-y))cos(2 \pi t) \right) \cdot \left( 1 - \frac{cos(2 \pi x) cos(2 \pi y)}{(-2)^{k-1}} \right) dy \end{array}$

Now, if one dislikes shortcuts one can expand the product and integrate term by term to one's heart's content.  The "shorter" version is to relate the story: notice the product of 1 with itself is 1, and such will integrate to 1 in the unit interval.  So we save it.  The integrals $\int_0^1 cos(2 \pi y) dy$ and $\int_0^1 cos(2 \pi - 2\pi y) dy$ both evaluate to zero, so we are left only with the task of evaluating the crossterm:

$\begin{array}{ccc} && \int_0^1 cos(2 \pi (1-y))cos(2 \pi t) \cdot \frac{cos(2 \pi x) cos(2 \pi y)}{(-2)^{k-1}} dy \\ & = & \frac{cos(2 \pi t) cos (2 \pi x)}{(-2)^{k-1}} \int_0^1 cos(2 \pi - 2 \pi y) cos(2 \pi y) dy \\ & = & \frac{cos(2 \pi t) cos (2 \pi x)}{(-2)^{k-1}} \int_0^1 cos^2(2 \pi y) dy \\ & = & \frac{cos(2 \pi t) cos (2 \pi x)}{(-2)^{k-1}} \cdot \frac{1}{2} \\ & = & -\frac{cos(2 \pi t) cos (2 \pi x)}{(-2)^{k}} \end{array}$

Let's not forget the 1 we had saved, so:

$p_{k+1}(x,t) = 1 - \frac{cos(2 \pi x) cos(2 \pi t)}{(-2)^{k}} \rightsquigarrow 1 - \frac{cos(2 \pi x) cos(2 \pi y)}{(-2)^{k}} = p_{k+1}(x,y)$

as we wanted to show.

So finally notice that, of course, if we take the limit as $t$ approaches infinity, the patch evolution tendency is to become 1, the uniform distribution:

$\lim_{t \rightarrow \infty} p_t(x,y) = 1 = u(x,y)$

From here on out, I want to set up the operative framework of patchixes, in analogy with discrete matrices.  I want to show that in general, patchix products are non-commutative.  This is easily done by counterexample:

We want to show that $p(x,y) \star q(x,y) \neq q(x,y) \star p(x,y)$. So suppose the patchixes $p(x,y) = x$ and $q(x,y) = y$. Then

$p(x,y) \star q(x,y) = \int_0^1 p(1-y,t) \cdot q(x,y) dy = \int_0^1 (1-y) y dy = \int_0^1 y - y^2 dy = \frac{1}{6}$

and

$q(x,y) \star p(x,y) = \int_0^1 q(1-y,t) \cdot p(x,y) dy = \int_0^1 (t \cdot x) dy = t \cdot x \rightsquigarrow x \cdot y$

are clearly not-equal.  It would be great to say that, because patchixes are non-commutative, patches are too, but we don't know that patches as a whole subset of patchixes commute, so let's disprove it.  Now suppose the patches $p(x,y) = x + \frac{1}{2}$ and $q(x,y) = 1 + xy - \frac{y}{2}$.  Then

$\begin{array}{ccc} p(x,y) \star q(x,y) & = & \int_0^1 p(1-y,t) \cdot q(x,y) dy \\ & = & \int_0^1 \left( \frac{3}{2} - y \right) \cdot \left( 1 + xy - \frac{y}{2} \right) dy \\ & = & \frac{5x}{12} + \frac{19}{24} \end{array}$

where

$\begin{array}{ccc} q(x,y) \star p(x,y) & = & \int_0^1 q(1-y,t) \cdot p(x,y) dy \\ & = & \int_0^1 q(1-y,t) \cdot p(x) dy \\ & = & p(x) \int_0^1 q(1-y,t) dy \\ & = & p(x) \cdot u(t) = p(x) \\ & = & x + \frac{1}{2} \end{array}$

By refraining from calculating this last bit explicitly, we have (serendipitously) proved that any patch by a patch that is solely a function of $x$ returns the last patch, a result which reminds us of the analogous distribution by patch result I have shown in my previous post (a distribution on [0,1] times a patch that is solely a function of $x$ returns the patch, that viewed from the point of view of functions is a distribution on [0,1]).  A quick note: the integral $\int_0^1 q(1-y,t) dy$ is the unit distribution because $\int_0^1 q(x,y) dx = u(y)$ and $x \rightsquigarrow (1-y)$ and $dx \rightsquigarrow -dy$.

The end result of these observations is that patches are also, in general, non-commutative.

Next, I want to show that patchixes in general are associative.  This is a bit tricky because of the "after integral" transformations we have to do, but it is doable if we keep careful track of our accounting.  We want to show that $[p(x,y) \star q(x,y)] \star r(x,y) = p(x,y) \star [q(x,y) \star r(x,y)]$.  Let's begin with the left hand side.

$\begin{array}{ccc} [p(x,y) \star q(x,y)] \star r(x,y) & \rightsquigarrow & [p(x,w) \star q(x,w)] \star r(x,y) \\ & = & \left( \int_0^1 p(1-w, y) \cdot q(x, w) dw \right) \star r(x, y) \\ & = & \int_0^1 \left( \int_0^1 p(1-w, t) \cdot q(1-y, w) dw \right) \cdot r(x, y) dy \\ & = & \int_0^1 \int_0^1 p(1-w, t) \cdot q(1-y, w) \cdot r(x, y) dw dy \\ & = & s(x,t) \rightsquigarrow s(x,y) \end{array}$

Now the right hand side

$\begin{array}{ccc} p(x,y) \star [q(x,y) \star r(x,y)] & \rightsquigarrow & p(x,w) \star \left( \int_0^1 q(1-y, w) \cdot r(x,y) dy \right) \\ & = & \int_0^1 p(1-w, t) \cdot \left( \int_0^1 q(1-y, w) \cdot r(x,y) dy \right ) dw \\ & = & \int_0^1 \int_0^1 p(1-w,t) \cdot q(1-y, w) \cdot r(x,y) dy dw \\ & = & s(x,t) \rightsquigarrow s(x,y) \end{array}$

The two sides are equal when we can apply the Fubini theorem to exchange the order of integration.

Of course, patches, being a subset of patchixes, inherit associativity.

Defining a patchix left and right identity is extremely difficult, in the sense that, if we take a hint from discrete matrices, we'd be looking at a very special function on the $xy$ plane, so that $i(1-y,y) = i(x,1-x) = 1$ and $0$ everywhere else.  Because there is no "pretty" way to define this as a function of $x$ and $y$ both, showing that when we multiply a patchix by this function on either the right or the left requires elaborate explication. Unless we take it as axiomatic high ground, postulating the existence of an identity function $i(x,y)$ so that $i(x,y) \star p(x,y) = p(x,y) = p(x,y) \star i(x,y)$ to make the framework work, there is no easy way out.  Let's give it a shot then.

Left identity:

$i(x,y) \star p(x,y) = \int_0^1 i(1-y,t) \cdot p(x,y) dy$

Now $i(1-y,t) = 1$ only for values where $t = y$, as we've defined it, otherwise the integral is zero and there is nothing to solve.  So then we've got

$\int_0^1 i(1-t,t) \cdot p(x,t) dy = \int_0^1 (1) \cdot p(x,t) dy = p(x,t) \rightsquigarrow p(x,y)$

which is essentially the argument I make for the zero patch power in my informal paper on continuous Markov transition matrices or patches (however, there's a problem with this definition on patches, more of this below).  There's the question of why we didn't force the change of $dy \rightsquigarrow dt$, and this is because the only way to obtain a function of both $x$ and $t$ is to force the patchix to the $x t$ plane and let the integral be taken in the $x y$ plane.  If this argument is unsatisfactory, consider this one:  at $t = 0 = y$ the patchix takes the values $p(x, 0)$ which is a function of $x$ alone.  Thus,

$\int_0^1 i(1,0) \cdot p(x,0) dy = p(x,0) \int_0^1 (1) dy = p(x,0)$

if we do this for all $t \in [0,1]$, we are certainly left with $p(x,t)$.  We may raise the objection that, if we create a mental picture of the situation, at $t = 0$, $i$ takes a value of 1 only at $y = 0$, so that, on the $x y$ plane, all values of $p(x, y)$ are zeroed except those at $y = 0$.  Thinking about it this way creates the difficulty of the integral with respect to $y$: it evaluates to zero (there is no "area" in the $x y$ plane anymore, only a filament or fiber at $y=0$), and we would be left with the zero patchix.  There is no way to resolve this except two ways: to send the patchix $p(x,y)$ to $p(x,t)$ before we take the integral in the $x,y$ plane, and then toss the integral out the window (or take it on the uniform distribution), or, to think of the filament $p(x,0) = p_0(x)$ as $p_0(x) \times [0,1] = p_0(x,y)$ and then integrate in the $x y$ plane to obtain $p_0(x) \rightsquigarrow p(x,0)$ and do this for all $t$ to get $p(x,t)$.  Hence yes, the difficulty of defining the identity function on "surface" matrices (because it is not smooth like they are and because it is defined piece-wise).

Right identity:

$p(x,y) \star i(x,y) = \int_0^1 p(1-y,t) \cdot i(x,y) dy$

Here we remind ourselves that $i(x,1-x) = 1$ and zero otherwise, so that we can make the substitution

$\int_0^1 p(x,t) \cdot i(x,1-x) dy = \int_0^1 p(x,t) \cdot (1) dy = p(x,t) \rightsquigarrow p(x,y)$

We of course have issues: it may seem redundant to send $x \rightsquigarrow 1-y \rightsquigarrow x$, sending $x$ back to itself, but again this is the only way to remain consistent and get back the original function.  Again there's an issue of why we didn't send the integral $dy \rightsquigarrow -dx$, but this has to remain in the $x y$ plane for the mechanics to work.  Other objections are likewise not easily resolved; but the argument would work out algebraically if we concede on a few things: otherwise we cannot but shrug at the fact that it is, indeed, a little bit of hocus pocus, and we return to our suggestion to postulate the identity function as an axiom. Perhaps maybe these issues can be resolved or elucidated a little later, I don't lose hope.

Defining inverse patchixes will also present a great difficulty, particularly because they have to produce the identity function when we "patchix multiply" two mutually inverse patchixes  together.  I was thinking that we could perhaps determine whether a particular patchix has one, by extending Sarrus's rule (for determinants) to be continuous, which would involve, I'm sure, multiple integrations.  This will be a topic of further investigation for me. The cool thing is, if we can elucidate how this "continuous version" of the determinant works, many different results from Linear Algebra could follow.  I am also trying to figure out how two inverse patchixes would look like, and if I can produce an example (at all), virtually from thin air.  If I can, then perhaps we're on our way to constructing patchix groups of all flavors.

Unfortunately, patches can't inherit the identity as we've defined it: the integral with respect to $x$ of $i(x,y)$ is zero for all $y$.  Thus $i(x,y)$ is not a patch.

This problem makes us want to think of the uniform distribution $u(x,y)$ as another possible candidate for the identity for patchixes all, and it might just work if we agree that, when we don't have a function of $t$ or of $x$ after doing the setup-transformations for the integral, we send whatever function remains there before taking the integral.

Left identity:

$u(x,y) \star p(x,y) = \int_0^1 u(1-y,t) \cdot p(x,y) dy \rightsquigarrow \int_0^1 (1) \cdot p(x,t) dy = p(x,t) \rightsquigarrow p(x,y)$

Right identity:

$p(x,y) \star u(x,y) = \int_0^1 p(1-y,t) \cdot u(x,y) dy \rightsquigarrow \int_0^1 p(x,t) \cdot (1) dy = p(x,t) \rightsquigarrow p(x,y)$

This has several happy consequences: we avoid dealing with a piece-wise defined function $i(x,y)$ which is zero everywhere except on $y = 1-x$, the uniform distribution is smooth, we can now more easily define inverses (by finding multiplicative inverse functions, more on this below), and, specifically regarding patches, $\int_0^1 u(x,y) dx = u(y) = 1$ so the uniform distribution is indeed a patch.

In my mental picture, the "patchix product" of the uniform distribution with a patchix (and vice versa) doesn't "add up" (pun intended), but the algebraic trickery would seem to be the same even when using the alternative $i(x,y)$.  So.  At this point I sort of have to convince myself into accepting this for now.

## 1.4 Exercise 5

I had often wondered how to go about proving closure of addition and multiplication of the integers.  After this problem I wondered no more!  It's pretty neat that we can show (by using induction) that by adding any two integers or multiplying them you always get another integer.

"Prove the following properties of $\mathbb{Z}$ and $\mathbb{Z}_+$:

(a) $a, b \in \mathbb{Z}_+ \Rightarrow a+b \in \mathbb{Z}_+$.  [Hint: Show that given $a \in \mathbb{Z}_+$, the set $X = \{x \ | \ x \in \mathbb{R}$ and $a+x \in \mathbb{Z}_+\}$ is inductive.]

(b) $a, b \in \mathbb{Z}_+ \Rightarrow a \cdot b \in \mathbb{Z}_+$.

(c) Show that $a \in \mathbb{Z}_+ \Rightarrow a - 1 \in \mathbb{Z}_+ \cup \{0\}$.  [Hint: Let $X = \{x \ | \ x \in \mathbb{R}$ and $x - 1 \in \mathbb{Z}_+ \cup \{0\}$; show that $X$ is inductive.]

(d) $c, d \in \mathbb{Z} \Rightarrow c + d \in \mathbb{Z}$ and $c - d \in \mathbb{Z}$. [Hint: Prove it first for $d = 1$.]

(e) $c, d \in \mathbb{Z} \Rightarrow c \cdot d \in \mathbb{Z}$."

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

----

SOLUTION

(a)

Using the hint, we proceed by

• Showing $1 \in X$.  Since $a \in \mathbb{Z}_+$, and $\mathbb{Z}_+$ is inductive, it follows that $a + 1 \in \mathbb{Z}_+$.   Therefore $1 \in X$.
• Supposing $k \in X$.  This of course means $a + k \in \mathbb{Z}_+$.
• Showing $k+1 \in X$.  This would mean $a + (k + 1) \in \mathbb{Z}_+$.  Note that by commutativity  and associativity (of the reals, of the integers), we can state $(a + 1) + k$.  But then we know that $(a + 1) \in \mathbb{Z}_+$ by the first point, and that $(a+1) + k \in \mathbb{Z}_+$ by the second point.  So we conclude that indeed $a + (k + 1) \in \mathbb{Z}_+$.

Thus $X$ is inductive.  In particular, then, $\mathbb{Z}_+ \subset X$.  It follows that if we pick $b \in \mathbb{Z}_+ \subset X$, with $a \in \mathbb{Z}_+$ by hypothesis, then we are guaranteed $a+b \in \mathbb{Z}_+$.

(b)

This is proved the same way as before, with a few minor modifications.  Again suppose $a \in \mathbb{Z}_+$.  Let $X' = \{x \ | \ x \in \mathbb{R}$ and $a \cdot x \in \mathbb{Z}_+\}$.  Again we want to show that $X'$ is inductive.

• $1 \in X'$, since $a \cdot 1 = a \in \mathbb{Z}_+$ (by identity axiom of the reals).
• Assume $k \in X'$. This means $a \cdot k \in \mathbb{Z}_+$.
• $k + 1 \in X'$, since $a ( k + 1) = a \cdot k + a$ (by the distributive property axiom of the reals), with $a \in \mathbb{Z}_+$ by the first point and $a \cdot k \in \mathbb{Z}_+$ by the second point.  Finally, $a \cdot k + a \in \mathbb{Z}_+$ by what we proved in part (a).

We conclude $X'$ is inductive, and contains $\mathbb{Z}_+$.  As before, with $a \in \mathbb{Z}_+$, pick $b \in \mathbb{Z}_+ \subset X'$, and we are guaranteed the product $a \cdot b \in \mathbb{Z}_+$.

(c)

Again following the hint, we show:

• $1 \in X$.  This is because $1 - 1 = 0 \in \mathbb{Z}_+ \cup \{0\}$ is true.
• Suppose $k \in X$, which means that $k - 1 \in \mathbb{Z}_+ \cup \{0\}$.
• We show that $k + 1 \in X$.  This would mean that $(k + 1) - 1 \in \mathbb{Z}_+ \cup \{0\}$, or, simplifying, that $k \in \mathbb{Z}_+$, which is true because $k$ is a positive integer by definition.

Thus, $X$ is inductive and $\mathbb{Z}_+ \subset X$.  Picking $a \in \mathbb{Z}_+ \subset X$, we see that $a - 1 \in \mathbb{Z}_+ \cup \{0\}$.

(d)

Taking a hint from previous hints (pun intended), assume $c, d \in \mathbb{Z}$.  Next define $X'' = \{ x \in \mathbb{R}; c + x \in \mathbb{Z}$ and $c - x \in \mathbb{Z}\}$. We want to show that $X''$ is inductive.

• $1 \in X''$.  First of all, we want to show that $c + 1 \in \mathbb{Z}$.  Certainly, $c \in \mathbb{Z}_+ \Rightarrow c+1 \in \mathbb{Z}_+ \subset \mathbb{Z}$ by part (a).  If $c = 0$, then $c + 1 = 1 \in \mathbb{Z}_+ \subset \mathbb{Z}$.  If $c \in \mathbb{Z}_-$, then $c + 1 \Rightarrow -(-c-1)$ with $-c \in \mathbb{Z}_+$, so $-c-1 \in \mathbb{Z}_+ \cup \{0\}$ by part (c), and $-(-c-1) \in \mathbb{Z}_- \cup \{0\} \subset \mathbb{Z}$ (!). Secondly, we want to show that $c - 1 \in \mathbb{Z}$. Then, $c \in \mathbb{Z}_+ \Rightarrow c-1 \in \mathbb{Z}_+ \cup \{0\} \subset \mathbb{Z}$ by part (c). If $c = 0$, $c-1 = -1 \in \mathbb{Z}_- \subset \mathbb{Z}$.  Finally, if $c \in \mathbb{Z}_-$, then $c - 1$ can be rewritten as $-(-c + 1)$ with $-c \in \mathbb{Z}_+$, and $-c + 1 \in \mathbb{Z}_+$ by part (a).  Then certainly $-(-c+1) \in \mathbb{Z}_- \subset \mathbb{Z}$.  Thus $1 \in X''$.
• Suppose that $k \in X''$, which means $c + k \in \mathbb{Z}$ and that $c - k \in \mathbb{Z}$.
• We show that $k + 1 \in X''$.  First, $c + (k + 1)$ means, by rearranging (associativity, commutativity) $(c + 1) + k$.  But we know $(c + 1) \in \mathbb{Z}$ by the first point, and so $(c+1) + k \in \mathbb{Z}$ by the second.  We conclude that indeed $c + (k + 1) \in \mathbb{Z}$.  Next we show $c - (k+1) \in \mathbb{Z}$.  By the distributive property, $c - k - 1$.  Then by associativity, $(c - 1) - k$.  We know $c - 1 \in \mathbb{Z}$ by the first point, and $(c-1) - k \in \mathbb{Z}$ by the second point. We conclude that indeed $c - (k + 1) \in \mathbb{Z}$.

Thus, $X''$ is inductive, and importantly, $\mathbb{Z}_+ \subset X''$. For any integer $c$, picking an integer $d \in \mathbb{Z}_+ \subset X''$ guarantees that $c + d \in \mathbb{Z}$ and $c - d \in \mathbb{Z}$.  If $d = 0$, then simply $c \in \mathbb{Z}$ is true by hypothesis.  This shows quite thoroughly the closure of addition of the integers!

(e)

Again taking a hint from previous hints, assume $c, d \in \mathbb{Z}$.  Next define $X''' = \{x \ | \ x \in \mathbb{R}$ and $c \cdot x \in \mathbb{Z}\}$.  We want to show $X'''$ is inductive.

• $1 \in X'''$. It seems clear that $c \cdot 1 \in \mathbb{Z}$, since simplification means $c \in \mathbb{Z}$, which is true by hypothesis.
• We assume that $k \in X'''$, which means $c \cdot k \in \mathbb{Z}$.
• We show that $k + 1 \in X'''$. This means we will show that $c (k + 1) \in \mathbb{Z}$.  By the distributive property, $c \cdot k + c$.  Now, we know $c \in \mathbb{Z}$ by the first point, and $c \cdot k \in \mathbb{Z}$ by the second.  Thus $c \cdot k + c \in \mathbb{Z}$ by part (d), and indeed $c (k + 1) \in \mathbb{Z}$.

Thus $X'''$ is inductive and $\mathbb{Z}_+ \subset X'''$.  Having $c \in \mathbb{Z}$, pick $d \in \mathbb{Z}_+ \subset X'''$ and we are guaranteed that $c \cdot d \in \mathbb{Z}$.  Next, if $d = 0$, then $c \cdot d = c \cdot 0 = 0 \in \mathbb{Z}$.  If $d \in \mathbb{Z}_-$, make the negative sign explicit, so that $c \cdot (-d)$ and by the properties of the reals this becomes $-c \cdot d$ with $-c \in \mathbb{Z}$ and $d \in \mathbb{Z}_+$, which again guarantees the product to be in $\mathbb{Z}$.  We have just proved closure of multiplication of the integers!

## 1.4 Exercise 4

"(a) Prove by induction that given $n \in \mathbb{Z}_+$, every nonempty subset of $\{1, \ldots, n\}$ has a largest element.

(b) Explain why you cannot conclude from (a) that every nonempty subset of $\mathbb{Z}_+$ has a largest element."

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

(a)

Let $A$ be the set of all positive integers for which this statement is true.  Then $A$ contains 1, since when $n=1$ the only nonempty subset of $\{1, \ldots, n\} = \{1\}$ is $\{1\}$, and the element 1 is the largest element because it's greater than or equal to itself.

Now suppose $A$ contains $n$, we want to show it contains $n+1$ as well.

Let $C$ be a nonempty subset of $\{1, \ldots, n+1\}$.  If $C$ consists of $\{n+1\}$ alone, then this is the largest element of $C$.  In fact $n+1$ is the largest element of all sets containing it.  Notice that the subsets containing $n+1$ constitute the totality of additional subsets that we can append to the set of subsets of $\{1, \ldots, n\}$ (that have a largest element already from the inductive hypothesis).

Thus $A$ is inductive, $A = \mathbb{Z}_+$, and the statement is true for all $n \in \mathbb{Z}_+$.

We can create a little table to show this formally.

(b)

Pick $\mathbb{Z}_+ \subset \mathbb{Z}_+$.  It is nonempty, but has no largest element!  For, suppose it did, and pick it. Say it is $x$.  Then $x+1$ is larger, with $x+1 \in \mathbb{Z}_+$ (since $\mathbb{Z}_+$ is inductive, e.g.).  We've reached a contradiction in our argument, and thus $\mathbb{Z}_+$ has no largest element.

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