0

(b) $\mathbb Z$ and the set $\{x \in \mathbb R \mid (\exists n \in\mathbb Z)(x = 2^n)\}$

(c) $\{0, 1\} \times \mathbb{N}$ and $\mathbb{Z}$

(d) $\{0, 1\} \times \mathbb{N}$ and $\mathbb{N}$

For each of these questions, my logic is as follows;

  • We must show that there exists a bijection between the set A and B.

  • To do this, I must come up with a function that maps the relationship between the two sets.

  • Once I have this function, I can show whether an injection and a surjection exists between these two sets.

  • If both exist, then a bijection exists and thus the two (countably) infinite sets have the same cardinality.

I am at a complete loss as to how to execute my logic over these 3 examples..

Michael Hardy
  • 1
Hearth
  • 21

3 Answers3

0

Hint: for the first pair of sets, use the function $f: n \mapsto 2^n$. Can you show it is injective and surjective? A similar logic can be used for the other two.

Lonidard
  • 4,253
  • b) f(x) = 2^x is the function then. Passes surjective and injective test thus it is a bijection and thus the cardinalities of both functions are equal. I'm not quite sure what to do with c) and d) however.. {0,1}xN is a foreign operation to me ._. – Hearth Aug 08 '15 at 19:39
  • @Hearth It's the set {(a,b) | a \in {0,1}, b \in \mathbb{N}}, which is the set of pairs in which the first element is either zero or one and the second one is a natural number. You could consider the first element (which is "binary") as the sign in front of a natural number. Does this make it any clearer? – Lonidard Aug 08 '15 at 20:37
0

In (b), the bijection is handed to you on a silver platter: $n\in\mathbb Z$ corresponds to $2^n$.

In (c), you can let $(0,n)$ correspond to a non-negative integer and $(1,n)$ correspond to a negative integer. Just let $(1,n)$ correpsond to $-n$ works, but if you then let $(0,n)$ correspond to $n$, then you have nothing to correspond to $0$. You can deal with that by shifting it to $n-1$.

In (d), you can let $(0,n)$ and $(1,n)$ correspond to even and odd integers. Which odd integer should $(1,n)$ correspond to? How about the $n$th one. What is the $n$th odd integer as a function of $n$? I'll leave that as an exercise for now.

I seem to recall that there's book by a Russion named Vilenkin that goes through this subject fairly thoroughly at the most elementary level. Take a look at it.

Michael Hardy
  • 1
0

b) $f(z) = 2^z$ for all $z \in \Bbb{Z}$. In order to verify this is a bijection, you check it is one to one and onto.

To see it is one to one, suppose $f(z) = f(x)$ for some $x,y \in \Bbb{Z}$. Then, $2^z = 2^x$. Take $\log_2$ of both sides, and you see that $x = z$. So the function is injective.

To show it is onto, take any element in $y$ in your set. Then, $y = 2^z$ for some $z \in \Bbb{Z}$. You have to show that for any element, there exists an element $z$ such that $y = 2^z$. Well, there is: namely, that very $z$.

c) $\{0,1\}$ is countable, and $\Bbb{N}$ is countable, so we know that $\{0,1\} \times \Bbb{N}$ is countable. Since $\Bbb{Z}$ is countable, we know there IS a bijection between the two. Two sets have the same cardinality if and only if there is a bijection between the two. For a more explicit example, for $m \in \{0,1\}$ and $n \in \Bbb{N}$ (Assuming $\Bbb{N}$ contains $0$):

$$f(m,n)= \left\{\begin{matrix} -n : m = 0\\ n + 1: m = 1\\ \end{matrix}\right.$$

Without doing the mathematical argument for you, I can explain why this works. It's injective: You know that if the numbers that result when you apply $f$ to $m,n$ are the same, what must be true about $m$ and $n$? It's surjective: Every integer is hit, because we have included all the natural numbers as well as all their negatives.

Can you see how to do a similar type of bijection for the last one?

Race Bannon
  • 1,829