2
$\begingroup$

Show that the set $A $ × $ \Bbb Z^+$ where $A=\{2,3\}$ is countable.

I checked the answer and it says that the set is infinitely countable, could someone explain why? I don't understand how this set contains an unlimited amount of integers for it to be infinite.

I also don't understand how to read this set, could someone explain what $\{2,3\}$ actually means? If that makes sense.

$\endgroup$
  • 1
    $\begingroup$ $\{2,3\}$ is the set having precisely the two$^1$ elements $2$ and $3$. $^1$ I take here for granted that $2\ne 3$. $\endgroup$ – Hagen von Eitzen Feb 26 '19 at 7:48
  • $\begingroup$ Each element of the set $A \times \mathbb{Z}$ consists of two things, first an element of $A$, so either $2$ or $3$ and second an element of $\mathbb{Z}$, that is an integer. $\endgroup$ – quarague Feb 26 '19 at 7:48
  • $\begingroup$ @UsamaGhawji Because the question is about $A\times \Bbb Z^+$, not about $A$ $\endgroup$ – Hagen von Eitzen Feb 26 '19 at 7:49
1
$\begingroup$

The set you defined, let us call it $X=\{2,3\}\times \mathbb{Z}^+$ has elements of the form $(2,n)$ and $(3,n)$. The symbol $\times $ in the context of set theory usually means Cartesian product that is the set of all ordered pairs where the pairs come from the two sets you took the product of, in symbols

$$ X=\{(a,b)\mid a\in\{2,3\}, b\in\mathbb{Z}^+ \}. $$

You can show that a set (in your case $X$) is countably infinite by finding a function $\phi:\mathbb{N}\to X$ and showing that $\phi$ is a bijection that is one-to-one and onto. In more common terms you have to show that you can order the elements of $X$.

In this case it would be easier to show this graphically. Imagine the elements of $X$ thought of as coordinate-pairs in a cartesian coordinate system. You can easily imagine connecting these points in the following fashion:

Start at $(2,1)$ and draw a horizontal line all the way to $(3,1)$. Next without lifting the pen draw a line to the point $(2,2)$ diagonally. You can continue by drawing a line horizontally again to the point $(3,2)$ an continue in this fashion. You will be able to reach each element of $X$ in this fashion and hence number them first, second and so on. This way you give this bijection $\phi$.

For an explicit definition of this bijection look at Chris Custers answer

$\endgroup$
3
$\begingroup$

$\{2,3\}$ is the set consisting of two elements, $2$ and $3$.

$\{2,3\}×\Bbb Z^+=\{2\}×\Bbb Z^+\cup \{3\}×\Bbb Z^+$ consists of all ordered pairs $(2,k)$ and $(3,l)$, where $k,l\in \Bbb Z^+$.

So, we essentially have (the union of) two copies of $\Bbb Z^+$.

But, $\Bbb Z^+$ is countably infinite. The union of two countably infinite sets is countably infinite, by a well-known result.

For instance, let $\phi:\Bbb N\to \{2,3\}×\Bbb Z^+$ be given by $\phi(n)=\begin{cases}(2,k),n=2k\\(3,k),n=2k+1\end{cases}$.

Then $\phi$ is a bijection.

$\endgroup$
  • $\begingroup$ for this example it's pretty simple to get a map from naturals to this union set $\endgroup$ – qwr Feb 26 '19 at 8:06
  • $\begingroup$ You're right. Perhaps I should try it. @qwr $\endgroup$ – Chris Custer Feb 26 '19 at 8:08
  • $\begingroup$ This way you nothing is mapped on $(3,2)$ $\endgroup$ – Vinyl_cape_jawa Feb 26 '19 at 8:20
  • $\begingroup$ @Vinyl_coat_jawa $\phi (5)=(3,2)$. $\endgroup$ – Chris Custer Feb 26 '19 at 8:22
  • $\begingroup$ ohh true! Sorry...my bad :) $\endgroup$ – Vinyl_cape_jawa Feb 26 '19 at 8:23
2
$\begingroup$

The set $\{2,3\}$ is the set containing exactly two elements. One element is $2$; one element is $3$.

$\mathbb{Z}^+$ contains infinitely many integers: $1, 2, 3, \dots$. (It's down to your course's definitions whether $0 \in \mathbb{Z}^+$.)

The product $A \times \mathbb{Z}^+$ consists of all pairs $(2, n)$ and $(3, n)$ where $n$ is a positive integer. There's clearly infinitely many of them - there are two for every natural number!

$\endgroup$

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.