2
$\begingroup$

I have a set and its cardinality. How can I calculate the cardinality of its complementary set?

EDIT: Gotta apologize. I was talking about well-defined sets with a fairly low positive integer as cardinality. Qwirk comes pretty close when talking about subsets and a given superset.

So see it this way. I have a certain set of numbers. Take some extra condition to get a subset, know its cardinality and now try to calculate the cardinality of a subset with the negated condition.

Sorry for being unclear.

  • 2
    Yes,I assumed that U is finite.However I should have mentioned that!2010-11-16

3 Answers 3

6

So, you have a given set $X$, and a specific subset $A$. You know the cardinality/size of $A$, and want to know the cardinality of $X\setminus A$, the (relative) complement of $A$ in $X$. Use $|X|$ to denote the size/cardinality of the set. I will assume the Axiom of Choice so that all sets have comparable cardinalities.

In two cases, this is completely determined by the cardinalities of $A$ and of $X$. They are:

  1. If $X$ is finite, of size $n$; then $A$ is finite, and the size of $X\setminus A$ is $|X|-|A|$.

  2. If $X$ is infinite, and the cardinality of $A$ is strictly smaller than the cardinality of $X$, then the cardinality of $X\setminus A$ equals the cardinality of $X$.

    • Reason: If $\kappa$ and $\lambda$ are cardinals, and at least one of them is infinite, then $\kappa+\lambda = \kappa\lambda = \max\{\kappa,\lambda\}$. Here, $\kappa+\lambda$ is the cardinality of the disjoint union of a set of cardinality $\kappa$ and a set of cardinality $\lambda$; $\kappa\lambda$ is the cardinality of the set $X\times Y$, where $|X|=\kappa$ and $|Y|=\lambda$.

For example, $|\mathbb{R}\setminus\mathbb{Q}|=|\mathbb{R}|$, because $|\mathbb{Q}|=\aleph_0 \lt 2^{\aleph_0}=|\mathbb{R}|$. If $A$ is a finite subset of $|\mathbb{N}|$, then $|\mathbb{N}\setminus A|=\aleph_0 = |\mathbb{N}|$.

Unfortunately, this is all you can say. If $X$ is infinite and $|A|=|X|$, then the cardinality of the complement $X\setminus A$ could be anything from $0$ and up to $|X|$. To get a set of size $n$ with $n$ finite, pick any subset $B$ of $|X|$ of size $n$, and take $A=X\setminus B$. To get a set with complement of cardinality $\kappa$ for any $\kappa\lt|X|$, biject $X$ with the cardinal $|X|$, which has a subset of cardinality $\kappa$; take the complement. To get a set of cardinality $|X|$, use the fact that $|X|=|X\times X|$. Then, if $x\in X$ is a particular element, then the subset that corresponds under a given bijection to $X\times\{x\}$ has complement of size $|X|$. For specific sets $X$ it is possible to find specific examples. For $\mathbb{N}$, the even numbers have complement of size $|\mathbb{N}|$. In the real numbers, the unit interval has complement of size $|\mathbb{R}|$. And so on.

  • 1
    @Asaf Karagila: Good point; it should be "so all cardinalities are comparable."2010-11-16
2

Possible slight rephrasing of the question:

Given a set $X$ and a subset $S$ then calculate the cardinality of the complement of $S$ with respect to $X$.

In general, this can be uncountably infinite, countably infinite or even have finite cardinality!

  • 0
    I $t$hink this should have been written as a comment and not an answer.2010-11-16
0

To elaborate on Qwirk's answer, look at $\mathbb{R}$.

$\mathbb{R} \setminus \mathbb{R}^+$ is uncountably infinite, even though $\mathbb{R}^+$ is uncountably infinite. On the other hand, let $T$ be the set of all real transcendental numbers. The set $\mathbb{R} \setminus T$ is exactly the set of all algebraic numbers, which we know to be countable. Finally, let $S = \mathbb{R} \setminus \{0, 1, \dots, n\}$ for some $n \in \mathbb{N}$. Taking the complement of $S$ in $\mathbb{R}$, you see that you can also get a finite set.

Hence, in general, you can not say anything about the cardinality of the complement of a set. However, if the cardinality of a subset $S \subset X$ is strictly less than that of $X$, then the cardinality of $X - S$ must be the same as $X$. You should try to see this for yourself.

  • 0
    Edited my questio$n$.2010-11-16