Showing that a set is countably infinite by defining a bijection between $\Bbb N$ and that set.

2,165

Solution 1

The problem is asking you to precisely describe a function from $\mathbb Z^+$, that is, from the set $\{1,2,3,\ldots\}$, to another set, and to prove that the function you have described is one-to-one and onto.

When you have done that, by doing this you will have shown that the other set is countably infinite.

For example, suppose the "other" set were the set all integers greater than $3$, namely, $\{4,5,6,\ldots\}$. Let $f$ be the function given by $f(n) = n + 3$.

The "one-to-one" property requires that for any distinct numbers $a$ and $b$ in $\mathbb Z^+$, it will always be true that $f(a) \neq f(b)$. So let $a$ and $b$ be any distinct numbers in $\mathbb Z^+$; then $$f(a) - f(b) = (a + 3) - (b + 3) = a - b \neq 0,$$ therefore $f(a) \neq f(b)$. Hence the function is one-to one.

The "onto" property requires that for any $b$ in the $\{4,5,6,\ldots\}$, there must be an $a$ in $\mathbb Z^+$ such that $f(a) = b$. So let $b$ be any number in $\{4,5,6,\ldots\}$, and let $a = b - 3$, treating these numbers as integers. But $b \geq 4$, therefore $a = b - 3 \geq 4 - 3 = 1$, hence $a$ is a positive integer, that is, $a \in \mathbb Z^+$ and $f(a) = b$, so $f$ is an onto function.

There are actually two problems in the problem statement, because you have to do all this for the positive integers divisible by $5$, and then do it all over again (with a new function) for the set $\{1,2,3\} \times \Bbb Z$.

Solution 2

Hint for the second item: Every element in $\mathbb N$ can be written uniquely as $3q+r$, with $r \in \{1,2,3\}$.

Share:
2,165
Hani Al-shafei
Author by

Hani Al-shafei

Updated on November 16, 2020

Comments

  • Hani Al-shafei
    Hani Al-shafei almost 3 years

    I'm a little confused on what is being asked here:

    Show that the following sets are countably infinite, by defining a bijection between $\Bbb N$ (or $\Bbb Z^+$) and that set.

    • The set of positive integers divisible by $5$.

    • $\{1,2,3\} \times \Bbb Z$.

    • André Nicolas
      André Nicolas almost 8 years
      Let $S$ be our set of positive multiples of $5$. You are supposed to come up with an explicit bijection $f$ from $\mathbb{N}$ to $S$.
    • Crostul
      Crostul almost 8 years
      Did you understand what is meant by a countable infinite set?
    • JMoravitz
      JMoravitz almost 8 years
      Are you familiar with all terms involved? Do you know what a bijection is? Do you know why having a bijection between two sets implies that they have the same cardinality? An example of such a bijection for showing that $\Bbb N$ and $\Bbb Z$ have the same cardinality would be something like $f:\Bbb N\to\Bbb Z$ where $f(n)=\begin{cases} \frac{n}{2}&\text{if}~n~\text{is even}\\ \frac{-n-1}{2}&\text{if}~n~\text{is odd}\end{cases}$.
    • Hani Al-shafei
      Hani Al-shafei almost 8 years
      My understanding is: A countably Infinite set is such that every unique item of the set can be listed in an infinite list. Uncountable sets cannot have their items listed one-to-one in an infinite list. I believe my confusion is coming from the bijection and what that implies.
    • JMoravitz
      JMoravitz almost 8 years
      A bijection is a function which is both surjective (onto) and injective (one-to-one) implying that every element in the codomain is mapped to by exactly one element in the domain. For example, the function from $\Bbb R\to\Bbb R$ given by $f(x)=2x$ is a bijection (since if $f(x_1)=f(x_2)$ then $2x_1=2x_2$ and so $x_1=x_2$ so all elements in codomain are mapped to by at most one preimage, and since any $y$ in the codomain has an $x$ (namely $\frac{y}{2}$) such that $f(x)=y$, so all elements in codomain have at least one preimage). See wiki.
    • fleablood
      fleablood almost 8 years
      A countable set is, as you say, is one in which the items can be list in 1-1 corespondence with the positive integers. In other words 1<=>item1, 2<=> item2 and so on. Another way to say this is there is a map (1,item1)(2,item2) etc. but that's just another way to say that there is a function f such that f(1) = item1, f(2) = item2. This function must have domain N, and range The Set. And it must be a bijection, which is defined in JMoravitz's comment.
  • Hani Al-shafei
    Hani Al-shafei almost 8 years
    So, for the first set: The set of positive integers divisible by 5. We have: f(n) = 5n. I have to show that this is onto and one-to-one with Z+?
  • fleablood
    fleablood almost 8 years
    That's the bijection. So yes, show it is onto and one-to-one with Z+. Which is easy.
  • Hani Al-shafei
    Hani Al-shafei almost 8 years
    So, since it is true that $f(a) \neq f(b)$ for any distinct numbers $a$ and $b$ in Z+, we have 5a - 5b = a - b \neq 0 therefore, $f(a) \neq f(b)$ so the function is one-to-one? Little confused on the onto property.
  • David K
    David K almost 8 years
    Be careful writing equalities: $5a-5b = 5(a-b)$. Also remember that for "one-to-one" you are usually start with $a\neq b$ and try to show that this implies $f(a)\neq f(b)$.