What makes an uncountable set "uncountable"?

Question

This question is bugging me from a very long time and I don't know whether it can be answered or not but still I am posting to get other's opinions.

Is there any inherent property among all the uncountable sets which make them uncountable ?

Or more precisely:-

If I ever wanted to "make" an uncountable set, what ingredient should I put in so that I am guaranteed of the set being uncountable ?

Edit :-

My apologies for the wrong terminology used. By "ingredient" , I was just trying to refer to some property which is common to all the well known uncountable sets (e.g. the irrational set, set if real numbers) that I should keep in mind while forming a new set of numbers.

Answer 1

The question in its current form is a bit unclear, but I'll try to address your concern below.

Assuming we are working with the axioms of $\mathsf {ZFC}$, we can construct an uncountable set by taking the power set of any set with infinitely many elements (e.g $\mathbb{N}, \mathbb{Z}, \mathbb{R}$, etc.). Of course $\mathbb{R}$ is already uncountable, but the point is that if you are unsure whether or not a set is uncountable, we can always take its power set (provided that it is infinite in cardinality) and this is sufficient to know that the resulting set is uncountable.

This follows because in $\mathsf{ZFC}$, we say that countably infinite sets have cardinality $\aleph_0$ and Cantor's Theorem says that the power set $P(X)$ of any set $X$ has a strictly greater number of elements than $X$ itself. And so, therefore, the power set of any countable set must have a cardinality greater than $\aleph_0$. And since $\aleph_0$ is the cardinality of any countable set, this means that this power set must be uncountable.

Some other ways to construct infinite sets are simply to add elements to an existing set by taking the union of an arbitrary set and known uncountable sets. For example, $(A \cup \mathbb{R})$ will be uncountable for any set $A$ since $\mathbb{R}$ is uncountable. Similarly, the intervals $[a,b], (a,b), [a,b], [a,b)$ are all uncountable sets for $a \neq b$ and so we can find the union between one of these and any arbitrary set and the result will be uncountable.

Lastly, we can always remove countable sets from uncountable sets and still end up with uncountable sets. For example, $(\mathbb{R} \setminus \mathbb{N})$ is still an uncountable set.

Answer 2

In questions of cardinality, it is useful for us to center ourselves in rigorous definitions. Uncountability is generally taken to be defined as the negation of the archetypal definition of countability, that is $A$ is countable if it is finite or there exists some $f$ such that:

$$f : A \rightarrow \mathbb{N} \text{ is a bijection.}$$

Thus, the "recipe" for an uncountable set is a set that is $(1)$ infinite and $(2)$ not capable of being related in bijection to the natural numbers, i.e. not enumerable.

As one can imagine, being able to have a bijection with the natural numbers is surely a very constraining condition, thus we can imagine the universe of uncountable sets to be quite rich (at least I do, philosophical disagreements over this sentiment form a major problem in the philosophy of mathematics, particularly with regard to the continuum hypothesis).

However, it is hard to classify such sets. For the extent of your question then, I would just remind you that the subset of a countable set is countable. By the logical contrapositive then, a set is guaranteed to be uncountable if it contains some uncountable subset. A straightforward ingredient for uncountability is thus inclusion of some interval of real numbers, however arbitrarily small, as they are archetypal examples of uncountable sets!

Answer 3

One, perhaps the only(?), way to construct a "larger set" from a given set is to consider the power set $\mathcal{P}(X)=\{S\subseteq X\}$ (set of all subsets of $X$). For instance, if $|X|$ is finite, then $|\mathcal{P}(X)|=2^{|X|}>|X|$.

When $X$ is infinite, $|\mathcal{P}(X)|>|X|$ as well, say by (Cantor's) diagonal argument, which goes as follows.

Assume not, let $f:X\to \mathcal{P}(X)$ be a surjection, and consider the set $E = \{x\in X : x\not\in f(x)\}$. Because $f$ is surjective, there exists some $x_0$ such that $f(x_0)=E$. We then have $$ x_0\in E\Longleftrightarrow x_0\not\in E, $$ an absurdity. Hence there is no surjection $f$ and $|\mathcal{P}(X)|>|X|$.

Going back to your question, constructing something using "enough" subsets of a countable set will give you something uncountable, e.g. viewing the real numbers as subsets of the natural numbers or rational numbers in various ways (base $b$ expansions, Dedekind cuts, Cauchy sequences, etc.).

Answer 4

For any non-empty set $X$, $X\times \mathbb{R}$ is uncountable.