Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Which part do you not understand? –  01000100 Aug 23 '12 at 9:46
    
@DanielPietrobon How did they found that the set has multiples of 3 in example 1 and how to write the definitions in Example 2, Sir? –  Gomathi Aug 23 '12 at 9:55
    
Well, what is 3+3? –  01000100 Aug 23 '12 at 10:00
    
@DanielPietrobon But, they didn't mention that y is also 3, Sir. –  Gomathi Aug 23 '12 at 10:02
    
@DanielPietrobon So, initially as they have mentioned 3 belongs to P, we take both x and y as 3. Am I right, Sir? –  Gomathi Aug 23 '12 at 10:06

2 Answers 2

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

share|improve this answer

We will prove the correctness of the two solutions first:

  1. $P = 3\mathbb{N}$.

    • Given $z \in P$, then either $z = 3$, in which case $z \in 3\mathbb{N}$ or $z = x+y$ for $x,y\in P$. After a finite number of steps and substitutions (at most $\frac{z}{3}$) we see that $z = \underbrace{3+\cdots+3}_n = 3n \in 3\mathbb{N}$.
    • Conversely, let be given $3n\in 3\mathbb{N}$. For $n=1$, $3n=3\in P$. Suppose $3(n-1)\in P$ for some $n$, then $3n = 3+3(n-1)\in P$ by part 2 of the definition of $P$. By induction on $n\in\mathbb{N}$ we see $3\mathbb{N}\subset P$.
  2. $P = \mathbb{N}\setminus\left\{0,1\right\}$

    • Clearly, any finite sum of 2's and 3's is in $\mathbb{N}$, so $P\subset\mathbb{N}\setminus\left\{0,1\right\}$
    • Conversely, given $z\in\mathbb{N}\setminus\left\{0,1\right\}$. Consider the largest $n\in\mathbb{N}$, such that $z_n:=z-2n>1$. If $z_n=2$, then $z$ is a finite sum of 2's, such that $z\in P$. If $z_n=3$, then $z=2n+3\in P$. This exhausts all possibilities, for if $z_n>3$, then $z_{n+1}>1$, which contradicts the maximality of $n$.

The examples you gave are not so much related to set theory as they're related to number theory. To come up with such examples yourself, you need to understand the basic principles of recursion and induction. See also, http://en.wikipedia.org/wiki/Mathematical_induction

A typical set theoretic example of induction is the following: A set $T$ is called transitive if $\forall x\in T: x\subset T$. A set is called an ordinal if it's transitive and well-ordered by $\in$. Let $S$ be the set of all finite ordinals. You can now prove that there is a bijection $\mathbb{N}\to S$. Hint: $0\mapsto \emptyset$, $1\mapsto\left\{\emptyset\right\}$, $2\mapsto\left\{\emptyset,\left\{\emptyset\right\}\right\}$, $\cdots$

share|improve this answer
1  
I think that the point of these exercises is to help the student understand and be comfortable around inductive definitions, rather than focus on the number-theoretic properties of the example. $${}$$ The term "special" is often applied to other things in order-theory, what you described as special is known as "ordinal". –  Asaf Karagila Aug 23 '12 at 10:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.