0
$\begingroup$

This is probably a stupid question but I will ask it anyway.

Take the set of all integers $ \Bbb Z = \{ ... , -2, -1, 0, 1, 2, 3, ... \}$.

$$n \in \Bbb{N} \text{ and } n \ge 2$$ If I then do $\Bbb Z/n$, is $|\Bbb Z/n| > |\Bbb Z|$, $= |\Bbb Z|$, or $< |\Bbb Z|$?

For example, if $n = 2$, $\Bbb Z$ will now contain real numbers $1\over 2$ and $3\over 2$ in place of 1 and 3, but will also contain 1 and 3. Does this resulting set $\Bbb Z/n$ now have a higher cardinality than $\Bbb Z$, or do they remain the same since they are both technically infinite sets?

$\endgroup$
3
  • 1
    $\begingroup$ $\frac1n\Bbb Z \ne \Bbb Z/n$ $\endgroup$
    – Kenny Lau
    May 13, 2018 at 12:42
  • $\begingroup$ What do you mean, precisely, by $\mathbb{Z}/n$? $\endgroup$
    – egreg
    May 13, 2018 at 12:50
  • $\begingroup$ I mean dividing the set by the number $n$. $\endgroup$
    – NotAPro
    May 13, 2018 at 15:01

3 Answers 3

3
$\begingroup$

Intuition often breaks down with infinite sets.

If you have two finite sets and a bijection (one to one and onto map) between them then they are the same size and you will not be able to find a map from one to the other which is one to one but not onto.

However, this is not so with infinite sets. You might have a bijection between them and also a map which is one to one but not onto. In fact, this is characteristic of infinite sets.

The simplest example is the set of all natural numbers $\mathbb{N}$ and just the even ones $2 \mathbb{N}$. There is an obvious map from $2 \mathbb{N}$ to $\mathbb{N}$ which is one to one but not not onto so it seems that $2 \mathbb{N}$ is smaller. On the other hand, there is also a bijection from $\mathbb{N}$ to $2 \mathbb{N}$: $n \rightarrow 2n$. So, they are the same size. Your example is similar.

For infinite sets, the existence of a bijection between two sets becomes the definition being the same size though the posher phrase having the same cardinality is normally used.

With finite sets, if you can find a map that is one to one but not onto then you have proved that the first is smaller than the second. For infinite sets, you would have only proved that the first is smaller or the same size as the other. You would need to prove that no bijection is possible and not just that one example is not a bijection.

Many apparently different sized sets turn out to be the same size: $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$, and $\mathbb{A}$ (the algebraic numbers). So many turn out to be the same size that you may begin to wonder whether all infinite sets are the same size. However, this is not so: $\mathbb{R}$ (the real numbers) is bigger than $\mathbb{N}$ and those others that I just named. However, observing that the obvious map from $\mathbb{N}$ to $\mathbb{R}$ is one to one but onto is not sufficient to prove this. You need to prove that no bijection can exist. Look up Cantor's Diagonal Argument.

$\mathbb{C}$ (the complex numbers) is not bigger than $\mathbb{R}$.

But even bigger sets exist and there is no bigger one.

$\endgroup$
2
$\begingroup$

So I suppose $\mathbb Z/n := \{a/n: a \in \mathbb Z\}$. Then the map:

$$x \in \mathbb Z/n \mapsto nx \in \mathbb Z$$

is obviously a bijection.

P.S. The notation is a bit off because usually, $\mathbb Z/n$ is used to denote the ring of integers modulo $n$.

$\endgroup$
2
  • $\begingroup$ More exactly $\mathbf Z/n\mathbf Z$. $\endgroup$
    – Bernard
    May 13, 2018 at 12:48
  • $\begingroup$ @Bernard sure, though we mostly write $\mathbb Z/(n)$ or $\mathbb Z/\langle n \rangle$ or (less frequently) $\mathbb Z/n$. $\endgroup$
    – user525755
    May 13, 2018 at 12:51
2
$\begingroup$

As User has pointed out, those sets have the same cardinality.

More generally it is possible to have $X,Y$ to be infinite sets and have $X\subsetneq Y$ and $|X|=|Y|$.

Consider the sets $2\mathbb{N}\subsetneq \mathbb{N}$. The even numbers and the natural numbers.

$f:\mathbb{N}\to 2\mathbb{N} : n \mapsto 2n$ is a bijection, so they have the same cardinalities.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .