1
$\begingroup$

hello i have a problem with exercise the problem is follow:

Consider the set $Q$ of integers defined as follows:

$1 ∈ Q$

If $b ∈ Q$, then $2b-1 ∈ Q$

If $b ∈ Q$, then $2b +1 ∈ Q$

What is the total $Q$? Prove your answer carefully.

I have found a solution but I have not shown with any particular methodology. Is there concrete evidence; thank you very much

  • 1
    @Huy Oops! Thanks. $I$ guess I unintentionally demonstrated the danger of using "and so on" :)2011-11-23

2 Answers 2

3

Let's add some rigor to David's post.

Claim: The set of odd positive integers is contained in $Q$.

Proof: (Induction) We are given $1 \in Q$. Now assume all odd positive integers less than $2n+1$ are in $Q$ (inductive hypothesis). Consider $n$. Either $n$ is odd so that $n<2n+1$ and thus by hypothesis $n \in Q$ and therefore, by the third condition $2n+1\in Q$. Or $n$ is even. In this case $n+1$ is odd and $n+1<2n+1$ thus by hypothesis $n+1\in Q$. Thus by the second condition, $2(n+1)-1=2n+1 \in Q$. Therefore, by induction all positive odd integers are included in $Q$.

Claim 2: These are the only elements of $Q$ (i.e. Q={ n \in \mathbb{Z} \;|\; n>0 \;\mathrm{and}\; n \;\mathrm{odd}}).

Proof: Since $1>0$ and given $n\geq 1$ then $2n\pm 1 \geq 1$, we have that all elements in $Q$ must be positive. Next, since $1$ is odd and $2n\pm 1$ is odd for an integer, it must be that all the elements of $Q$ are odd. Therefore, $Q$ is precisely the set we claimed it is.

1

Start with $1\in Q$

Applying the other conditions to $\{ 1\}$, we see that $3\in Q$.

So $\{1,3\}\subseteq Q$.

Applying the conditions to each new element of the above, we see $ 5 $ and $7$ are in $Q$.

So $ \{1,3,5,7\}\subseteq Q. $

Applying the conditions to each new element of the above, we see $ 9 $, $11$, $13$, and $15$ are in $Q$.

So $ \{1,3,5,7, 9, 11, 13, 15\}\subseteq Q. $

The next step will give you

$ \{1,3,5,7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31\}\subseteq Q. $

And you can continue in this manner to show that $Q$ contains all odd integers. Since the conditions always give odd integers, $Q$ is in fact the set of odd integers. (That is, if $Q$ is determined by the conditions. As stated, there is the possibility that other even numbers are in it. But the conditions won't give new even numbers).