0
$\begingroup$

How can we define whether a set is countable or not?

The theory says that if we can build a bijection between a set A and natural numbers than it is countable, if we can build a bijection between set S and the open interval (0,1) then it is continuous (uncountable).

Given an infinite set how do we define whether it is bijective to N or to (0,1)?

Can we always find a bijective function built with domain (0,1) and range of infinite set S to prove its continuity or is there an easier way?

$\endgroup$
4
  • 1
    $\begingroup$ I believe "continuous" is a wrong word here (possibly a mistranslation). In English, we would normally say that the set has "the cardinality of the continuum". $\endgroup$
    – user700480
    Commented Oct 16, 2022 at 8:29
  • 1
    $\begingroup$ And - when proving that the set is either (infinitely) countable or has the cardinality of the continuum (there are also infinite sets that are neither!) there are different tools you can use (making an explicit bijection to $\mathbb N$ or to $(0,1)$ being one of them). Maybe, if you have a particular problem, you could post it here and show what you've tried to do. $\endgroup$
    – user700480
    Commented Oct 16, 2022 at 8:33
  • $\begingroup$ I'll edit the question with continuum, thanks for correcting $\endgroup$ Commented Oct 16, 2022 at 8:37
  • $\begingroup$ Just like "finite" doesn't tell you how big a set is, "uncountable" does not either. In a sense, "most" sets are uncountable, and "most" sets are larger than the continuum. $\endgroup$
    – Asaf Karagila
    Commented Oct 16, 2022 at 13:43

2 Answers 2

2
$\begingroup$

Given an infinite set how do we define whether it is bijective to $\mathbb{N}$ or to (0,1)?

It may happen that there is no bijection on $\mathbb{N}$ or $(0, 1)$. Consider all subsets of $(0, 1)$ - this set has bigger cardinality than cardianlity of continuum. See Cantor's theorem for details.

Moreover, depending on the axioms you use, it may happen that there exist the set $S$ $$ \mathrm{card} \, \mathbb{N} < \mathrm{card} \, S < \mathrm{card} \, (0,1). $$ You can find more details on Continuum hypothesis article in wiki.

Can we always find a bijective function built with domain (0,1) and range of infinite set S to prove its continuity or is there an easier way?

I think you meant should instead of can :)

Sometimes there is indeed an easier way. For example, one may use Cantor-Schröder–Bernstein theorem. It states that $$ \mathrm{card} \, A \le \mathrm{card} B\quad \text{and} \quad \mathrm{card} \, B \le \mathrm{card} \, A \implies \mathrm{card} \, A = \mathrm{card} \, B. $$

As an example, let's show that $$ \mathrm{card} \, (0, 1] = \mathrm{card} \, (0, 1). $$ We have an injection $$ f:(0,1] \longrightarrow (0, 1), \, f(x) = \frac{x}{2} + \frac{1}{4} \implies \mathrm{card} \, (0, 1] \le \mathrm{card} \, (0, 1) $$ and injection $$ g: (0, 1) \longrightarrow (0, 1], \, g(x) = x \implies \mathrm{card} \, (0, 1) \le \mathrm{card} \, (0, 1]. $$ Applying the theorem we get $$ \mathrm{card} \, (0, 1] = \mathrm{card} \, (0, 1). $$ We get the desired result without establishing bijection between the original sets, while we established some simpler injections along the way.

$\endgroup$
1
$\begingroup$

To the well-written answer of Virtuoz, I don't have much more to add but a few other frequently used tools:

  • "equal cardinality" is an equivalence relation (reflexive, symmetric, transitive) on any set of sets, and "less or equal cardinality" is a pre-ordering relation on any set of sets (reflexive, transitive). So $\operatorname{card}A=\operatorname{card}B$ and $\operatorname{card}B=\operatorname{card}C$ implies $\operatorname{card}A=\operatorname{card}C$ (and the same with $\le$). The pre-ordering is total if you assume Axiom of Choice.
  • You can define addition, multiplication and exponentiation on cardinals: $\operatorname{card}A+\operatorname{card}B:=\operatorname{card}(A\sqcup B)$ (disjoint union); $\operatorname{card}A\times\operatorname{card}B:=\operatorname{card}(A\times B)$ (Cartesian product); $\operatorname{card}A^{\operatorname{card}B}:=\operatorname{card}(A^B)$ ($A^B$ is the set of all functions from $B$ to $A$). This lets you do cardinal arithmetic. Those operations all "respect" cardinal equality and inequality, i.e. equal sets give you equal results, bigger sets give you bigger results.
  • It is easily seen that $\operatorname{card}(0,1)=\operatorname{card}\mathbb R$. (Bijection: $f(x)=\tan\left(\pi\left(x-\frac{1}{2}\right)\right)$)
  • $\operatorname{card}(P(A))=2^{\operatorname{card}A}$ where $P(A)$ is the set of all subsets of $A$. (Bijection: map every subset $X\subset A$ into the function $f:x\mapsto\begin{cases}1&x\in X\\0&x\not\in X\end{cases}$).
  • It is also a theorem that $\operatorname{card}(0,1)=2^{\operatorname{card}\mathbb N}$ (with a bit unwieldy proof that I will omit.)

An example how to prove that $\operatorname{card}\mathbb R^2=\operatorname{card}\mathbb R$:

$$\begin{array}{rcl}\operatorname{card}\mathbb R^2&=&(\operatorname{card}\mathbb R)^2\\&=&(2^{\operatorname{card}\mathbb N})^2\\&=&2^{2\operatorname{card}\mathbb N}\\&=&2^{\operatorname{card}\mathbb N}\\&=&\operatorname{card}\mathbb R\end{array}$$

simply because $2\operatorname{card}\mathbb N=\operatorname{card}\mathbb N$ (two copies of $\mathbb N$ have the same number of elements as a single copy, which is easily seen).

$\endgroup$

You must log in to answer this question.

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