[Math] Countably Infinite, Uncountable or Finite

discrete mathematics

I am having trouble with the following terms: countably infinite, uncountable, and finite. In addition, for the following problems I need to select which category they fall into.

$1)$ Consider a set of every function from integers to the set ${false, true}$.

Would this be finite?

$2)$ Points in $4D$ (coordinates written as $(a,b,c,d))$;

This is uncountable, right?

$3)$ The set of functions from natural numbers to the reals that are within $O(n^2)$.

No idea where to start for this one.

Best Answer

  • A set is "finite" if it can be placed in 1-1 correspondence with the set of natural numbers $< n$ for some $n$. More generally, it is sufficient to place it in 1-1 correspondence with some set of integers which is bounded both above and below.
  • A set is "countable" if it can be placed in 1-1 correspondence with some subset of the natural numbers. Note that this includes finite sets, but also some infinite sets. Since the sets of all rationals is in 1-1 correspondence with the set of naturals, it is sufficient to place a set in 1-1 correspondence with some set of rationals to show that it is countable.
  • A set is "infinite" if it is not finite. Since any finite set of real numbers is bounded, to prove a set is infinite, it is sufficient to put it in 1-1 correspondence with any unbounded set of real numbers.
  • A set is "countably infinite" or "denumerable", if it is both countable and infinite. From the above remarks, it follows that to prove denumerability, it is sufficient to put a set in 1-1 correspondence with some unbounded set of rational numbers.
  • A set is "uncountable" if it is not countable. Since all finite sets are countable, uncountable sets are all infinite. Per Cantor's theorem, the real numbers are uncountable. Further, since any interval can be put in 1-1 correspondence with the entire set of real numbers, to show a set is uncountable, it is sufficient to put it in 1-1 correspondence with some interval.

The size of any set is obviously greater than or equal to the size of any subset. This gives us some inheritance relations:

  • Any subset of a finite set is also finite.
  • Any subset of a countable set is also countable.
  • Any superset of an infinite set is also infinite.
  • Any superset of an uncountable set is also uncountable.

For your problems:

  1. for each real number in the interval $(0,1)$, we can consider its binary expansion. Certain numbers have two binary expansions, one ending in repeating $0$s and one ending in repeating $1$s. For example: $$0.10000\ldots_2 = 0.01111\ldots_2$$ For definiteness, we always choose the one with repeating $0$s. Each $x \in (0,1)$ can be translated into the function $f_x : \Bbb N \to \{\text{true},\ \text{false}\}$ that carries $i$ to the value $\text{true}$ if the $i^\text{th}$ bit of $x$ is $1$, and $\text{false}$ otherwise. The map $x \mapsto f_x$ is a 1-1 correspondence between the interval (0,1) and a subset of your set of functions. Since the subset is therefore uncountable, your set is uncountable.
  2. The map $x \mapsto (x, 0, 0, 0)$ is a 1-1 correspondence between $\Bbb R$ and a subset of $\Bbb R^4$. Hence $\Bbb R^4$ is uncountable.
  3. Any constant function of $n$ is $O(n^2)$. For each $a \in \Bbb R$, define $g_a\ :\ \Bbb N \to \Bbb R\ :\ n \mapsto a$. I.e., $g_a$ is the constant map with image $\{a\}$. Then $a \mapsto g_a$ is a 1-1 correspondence between $\Bbb R$ and a subset of the set of $O(n^2)$ functions. Hence the set of $O(n^2)$ functions is also uncountable.
Related Question