[Math] Inductive definition of a set

elementary-set-theoryinduction

I'm a beginner in set theory and I have doubt regarding mathematical induction. I came across the following examples.

Example 1:

Find the set given by the following definition:

1) $ 3 \in P $

2) For $x,y \in P, x + y \in P $

3) Only those elements obtained from steps (1) and (2) are in $P$

Solution: The set $P$ consists of positive integers which are multiples of 3.

Example 2:

Give an inductive definition of the set

$ P = \{2,3,4,\ldots\} = N – \{0,1\}$

Solution:

1) $ 2 \in P$ and $3 \in P $

2) If $x,y \in P$, then $x+y \in P$.

3) Only those elements obtained from steps 1 and 2 are in $P$.

Could anyone explain the above two examples and how to write this kind of definitions? I googled it, but couldn't get what I need. Thanks in advance.

Best Answer

Let us review the first solution, it's a bit simpler.

We begin with a set $P_0=\{3\}$. That is the base of the induction. Now suppose that $P_n$ was defined, we take $P_{n+1}$ to be $P_n$ with the addition of all elements of the form $x+y$ where $x,y\in P_n$.

Finally, $P$ is the union of the $P_n$'s, namely $\bigcup_{n=0}^\infty P_n$.

We can do the first few steps explicitly, to get the feel:

  • $P_0=\{3\}$, that's the definition of the first step.
  • $P_1=\{3,3+3\}$, we took $P_0$ and added $3+3$, which is the only possible combination of $x+y$ where $x,y\in P_0$.
  • $P_2=\{3,6,9,12\}$, we took $P_1$ and now we add $3+6$ and $6+6$. We don't need to add $3+3$ because it's already in there.
  • $P_3=\{3,6,9,12,15,18,24\}$, we added $3+12,6+12,9+12,12+12$. Note that this also included other pairs such as $6+9,9+9$, etc.

To prove that indeed $P$ is all the multiples of $3$ we need to argue that if $n=3m$ then there is some $k$ such that $n\in P_k$. We prove this by induction, of course, on $m$.

  1. If $m=1$ then $n=3$ and therefore $n\in P_0$.
  2. Suppose that for $3m$ we proved that $3m\in P_k$ for some $k$, and let $n=3(m+1)$. Since $3\in P_k$ we have that $3m+3\in P_{k+1}$, and therefore $n=3(m+1)=3m+3\in P_{k+1}$.

Now we need to prove that if a number is in $P$ then it is a multiple of $3$. Again we do this by induction, for example we can do this by induction on the index of $P_k$, namely:

  • We know that $P_0=\{3\}$ and therefore all its elements are multiples of $3$.

  • Suppose that for $P_k$ it is true that all its elements are multiples of $3$, we will show this is true for $P_{k+1}$.

    Suppose that $n\in P_{k+1}$, then by the definition of $P_{k+1}$ there are $x,y\in P_k$ such that $n=x+y$. From the induction hypothesis for $P_k$ we have that $x,y$ are both multiples of $3$ and therefore their sum, $n$, is also a multiple of $3$.

Finally:

We have seen what exactly is the definition of $P$, and we have seen how to prove that it indeed has the wanted property. We prove these things carefully by induction, using the inductive definition of the stages constructing $P$.

Related Question