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.

  • 1
    The cardinality of the complement is not determined by the cardinality of the original set as Qwirk mentions below. For example the even integers, and the nonzero integers both have the same cardinality but their complement in the set of integers is infinite in one case and a singleton in the other.2010-11-16
  • 0
    @Debanjan: this is nonsense. Infinite cardinalities cannot be subtracted.2010-11-16
  • 0
    @ Qiaochu Yuan : Is it ? I thought it depends in the definition of the problem ? How will you explain if we define U = {1,2,3,4} , and A = {2,3}. I have faced this type of question and I commented based on the fact that Universal set is defined like this (i.e finite).So i guess my comment of $n(\overline{A}) = n(U)-n(A)$ is not nonsense for this type of problems.However you are correct in your own way.2010-11-16
  • 0
    @Debanjan: the cardinality of the complement of a set S in an infinite universal set U is not determined by |S|, and several examples have already been given. This is possible if and only if U is finite.2010-11-16
  • 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.

  • 2
    Even without AC cardinality is still well-defined, it is just not always an aleph number.2010-11-16
  • 0
    @Asaf Karagila: But without AC, some sets may be incomparable, not all infinite sets have denumerable subsets, not all infinite sets have subsets of all cardinalities less than or equal to their cardinality.2010-11-16
  • 0
    Madigin: Of course, I was just nitpicking "I will assume the Axiom of Choice so that all sets have a well-defined cardinality.", it will be well-defined, just not well-behaved.2010-11-16
  • 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
    +1,That's seems correct rephrasing.2010-11-16
  • 0
    Looks good. I'm not talking about infinite stuff, though. Sorry, edited my question.2010-11-16
  • 0
    I think 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 question.2010-11-16