0
$\begingroup$

Let $ O=${$2n+1|n \in \Bbb N$} the odd natural numbers.

Show $|O|= \aleph_0$

I need to show that if there is a bijection $ \Bbb N \to O$, then $|O|=| \Bbb N|= \aleph_0$

Claim: $f$ is injective

Suppose $f(x)=f(x')$, $ \Rightarrow 2x+1=2x'+1 \Rightarrow 2x=2x' \Rightarrow x=x'$. So, $f$ is injective.

Claim: $f$ is surjective

$ \forall y \in O, \exists x=(y-1)/2 \in \Bbb N$ such that f(x)=y.

Then $f((y-1)/2)=2((y-1)/2)+1 \Rightarrow y-1+1=y$. Thus, $f$ is surjective.

Conclusion, $f$ is bijective. Thus, $| \Bbb N|=|O|=\aleph_0$.

If I have made any mistakes, please correct me. Thank you.

$\endgroup$
1
  • $\begingroup$ "do I ned to show that it is a bijective" really makes no sense, even adjusted for the misspelling. $\endgroup$
    – The Count
    Mar 21 '17 at 1:51
2
$\begingroup$

Here's a hint to get you started. To prove that two sets, $A$ and $B$, have equal cardinality (to show that $|A|=|B|$), we show that there exists a bijection $\phi: A\to B$. When dealing with $\aleph_n$, the typical procedure is to find a set $X$ with cardinality $\aleph_n$, and then prove the existence of a bijection from our set to $X$.

So, we know that $|\mathbb{N}|=\aleph_0$. Can you prove that there exists a bijection from $\mathbb{N}$ to $O$? You might try constructing one!

$\endgroup$
8
  • $\begingroup$ So, I need to show that $ | \Bbb N|=|O|$? $\endgroup$
    – Lily
    Mar 21 '17 at 1:55
  • $\begingroup$ Yes! Can you explain why? $\endgroup$ Mar 21 '17 at 1:56
  • $\begingroup$ If $| \Bbb N|=\aleph_0=|O|$. Then by its definition, there is a bijection from $ \Bbb N \to O$. $\endgroup$
    – Lily
    Mar 21 '17 at 2:02
  • 1
    $\begingroup$ True, but we want to work the other way -- if there is a bijection from $\mathbb{N}$ to $O$, then $|O|=|\mathbb{N}|$. Try coming up with this bijection, and post your proof as an answer! This way you can get feedback on your proof, too. $\endgroup$ Mar 21 '17 at 2:05
  • $\begingroup$ So, can I just say that my function $f(n)=2n+1$ and go from there? $\endgroup$
    – Lily
    Mar 21 '17 at 2:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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