Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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. –  Grumpy Parsnip Nov 16 '10 at 11:09
    
@Debanjan: this is nonsense. Infinite cardinalities cannot be subtracted. –  Qiaochu Yuan Nov 16 '10 at 12:39
    
@ 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. –  Quixotic Nov 16 '10 at 13:35
    
@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. –  Qiaochu Yuan Nov 16 '10 at 13:37
2  
Yes,I assumed that U is finite.However I should have mentioned that! –  Quixotic Nov 16 '10 at 13:39

3 Answers 3

up vote 5 down vote accepted

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.

share|improve this answer
2  
Even without AC cardinality is still well-defined, it is just not always an aleph number. –  Asaf Karagila Nov 16 '10 at 17:41
    
@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. –  Arturo Magidin Nov 16 '10 at 18:31
    
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. –  Asaf Karagila Nov 16 '10 at 18:35
1  
@Asaf Karagila: Good point; it should be "so all cardinalities are comparable." –  Arturo Magidin Nov 16 '10 at 19:10

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!

share|improve this answer
    
+1,That's seems correct rephrasing. –  Quixotic Nov 16 '10 at 13:43
    
Looks good. I'm not talking about infinite stuff, though. Sorry, edited my question. –  Franz Nov 16 '10 at 14:17
    
I think this should have been written as a comment and not an answer. –  Asaf Karagila Nov 16 '10 at 16:27

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.

share|improve this answer
    
Edited my question. –  Franz Nov 16 '10 at 14:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.