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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let's say that $A$ is a subset of $B$ and be is a subset of a set $S$ of $n$ elements.

How big is the set $\{(A,B)\}$ then.

share|cite|improve this question
Do you want to know the cardinality of $\{(A,B)\}$, or of $\{A,B\}$? These are not the same thing. – Chris Eagle Feb 17 '13 at 0:52
the former option – user60862 Feb 17 '13 at 3:54

Assuming $A \neq B$, then there are exactly two elements in $\{A, B\}$, elements which happen to be sets $A, B$. Hence, the cardinality of $\{A,\,B\}$ is $2$. I.e., $|\{A, \,B\}| =2.$ Else, we can only say $|\{A, \,B\}| \leq 2$.

The set $\{(A, B)\}$ has one element, (cardinality 1), which happens to be an ordered pair of sets.

The information about the relation between sets $A, B,$ and between $B, S$ and the elements of $S$ is irrelevant: that information is what they call a "red herring."

share|cite|improve this answer
Unless, of course, $A=B$. – Chris Eagle Feb 17 '13 at 0:52
Ahha, you're correct, @Chris – amWhy Feb 17 '13 at 0:54

The set $\{A,B\}$ has at most two elements, and if $A\neq B$ then it has exactly two.

The set $\{(A,B)\}$ has exactly one element, the ordered pair $(A,B)$.

share|cite|improve this answer

Perhaps you are asking to find $|N|$ where $N = \{(A, B) \mid A \subseteq B \subseteq S, |S| = n\}$ for some integer $n$.

To solve this, let's first fix some $B_0$ and let $m = |B_0|$. Then the number of subsets of $B$ is just $2^m$. Clearly, $0 \leq m \leq n$. So $|N| = \sum_{i=0}^{n}{2^i}=2^{n+1}-1$

share|cite|improve this answer
I appreciate your answer, but to indicate that the OP's question could be read in a different way is slightly misleading. The notation is clear and unambiguous, and for the set(s) that the OP asked about, several people have answered the question. What you are doing is answering the question for the set (you think) the OP meant to ask about. – Michael Albanese Feb 17 '13 at 1:20
@MichaelAlbanese Yes, I see that my original wording is misleading. I will edit it for clarification. – Code-Guru Feb 17 '13 at 1:25

Your Answer


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.