Countably Infinite, Uncountable or Finite

Question

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.

For (3), How many constant functions from $\Bbb N \to \Bbb R$ are there? — Paul Sinclair, Dec 05 '15 at 01:00
Obviously, there is one such constant function for each real number. so we can be a little more specific than just "infinite". — Paul Sinclair, Dec 05 '15 at 18:34

score 8 · Accepted Answer · answered Dec 05 '15 at 19:20

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:

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.
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.
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.

Is the "repeating zeroes" representation of a dyadic rational really always the one chosen? Choosing the "evil twin" with the repeating ones can be more convenient, such as for making a bijection between the infinite sets of integers and the interval $(0,1]$. — Spencer, Aug 13 '17 at 01:54
@Spencer - I am defining a function here. What I meant was in defining the function $x \mapsto f_x$, choose the terminating representation of $x$. This provides a 1-1 correspondence between the interval $[0,1]$ and a subset of the set of functions the OP described in his first question. This was sufficient to show his set is uncountable. I certainly did not mean it to be some blanket proscription of all non-terminating representations in all circumstances! — Paul Sinclair, Aug 13 '17 at 17:57

score 1 · Answer 2 · answered Dec 04 '15 at 23:04

1. Imagine writing any real value in binary. Is there, or is there not, a bijection from such numerals to the functions described in this question?

2. These points are just as finite, countable, or uncountable as a single coordinate would be. (I.e., if $a, b, c, d$ are drawn from a finite list, then the $4$-d points are likewise finite; if $a, b, c, d$ are drawn from a countably infinite list, then the $4$-d points are also; etc.)

3. What is $n$ here? If $n$ is bounded, then it seems that the set of functions must also be bounded. But it would help to know what $n$ represents here.

Countably Infinite, Uncountable or Finite

2 Answers2