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
    Please show what you have tried and ask a concrete question.2011-11-23
  • 2
    Once you have your answer, the proof would be by induction.2011-11-23
  • 1
    You can reason as follows: $1 \in Q$ so $2(1)+1=3 \in Q$ and so on. Thus all positive odd numbers are in $Q$. Likewise, $1 \in Q$ so $2(1)-1=1$, $2(3)-1=5$ and so on. Thus we don't get any new numbers from this second condition. $Q$ is the set of positive odd integers. You will need to use [induction](http://en.wikipedia.org/wiki/Mathematical_induction) to formulate a solid proof (avoiding the use of phrases like "and so on").2011-11-23
  • 1
    @BillCook: As $1 \in Q$, from the first condition it follows that $3 \in Q$. If we apply the first condition again, we have $7 \in Q$, not $5 \in Q$. We get the $5 \in Q$ by applying the second condition on $3 \in Q$.2011-11-23
  • 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).