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.

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

share|improve this question
1  
Please show what you have tried and ask a concrete question. –  lhf Nov 23 '11 at 13:52
2  
Once you have your answer, the proof would be by induction. –  GEdgar Nov 23 '11 at 13:53
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 to formulate a solid proof (avoiding the use of phrases like "and so on"). –  Bill Cook Nov 23 '11 at 13:56
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$. –  Huy Nov 23 '11 at 14:04
1  
@Huy Oops! Thanks. I guess I unintentionally demonstrated the danger of using "and so on" :) –  Bill Cook Nov 23 '11 at 14:26

2 Answers 2

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.

share|improve this answer

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

share|improve this answer

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.