Aptitude Overflow
+7 votes

Let $A$ be a set with $n$ elements. Let $C$ be a collection of distinct subsets of $A$ such that for any two subsets $S_1$ and $S_2$ in $C$, either $S_1 \subset S_2$ or $S_2\subset S_1$. What is the maximum cardinality of C?

  1. $n$
  2. $n+1$
  3. $2^{n-1} + 1$
  4. $n!$
asked in Set Theory & Algebra by (19.4k points)  
retagged by | 740 views

3 Answers

+14 votes
Best answer
Let's take an example set {a,b,c}

Now lets try to create the required set of subsets, say S.

Let's start by adding sets of size 1 to S. We can only add one of the sets {a}, {b}, {c}.

Lets say we add {a}, so S now becomes {{a}}

Now lets add sets of size 2 to S. Again we see that we can only add one of {a,b}, {a,c} or {b,c}, and we cannot add {b,c} since we already added {a}.

Continuing this way we see we can add only one set for a all size till n.

So the awnser should be 2) n+1 ( include the empty set )
answered by (2.7k points)  
selected by
Each subset we add to C must have strictly one element more than the set with maximum number of elements already added to C -rt? This means only n sets can be added and adding ∅ gives n+1.
makes sense

S⊂ S2 or S2⊂ S1

does it not mean either of them must be  proper subset only ???

Ans should be n because in cardinality we does not include empty set.
$C$ here is a set of sets- so even empty set must be counted as part of its cardinality. Cardinality of empty set is 0- but that is diffeent.
Why it should be like this? Is it because of 'Distinct' word mentioned there?
yes distinct is required.
It will be like one chain of the relation  or we can say total order set
+3 votes

it is example of " totally ordered set "
let A is set {a,b,c}
then S will be { phi , {a} , {a,b} , {a,b,c}}
so ans should be B. (n+1)

answered by (3.1k points)  
edited by
How can u add {b,c } ?
+1 vote

Lets take an example..

Suppose A= {1,2,3} . here n=3

Now P(A)= {∅,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}

now C will contain ∅ (empty set) and ,{1,2,3} (set itself) as ∅ is the subset of every set. And every other subset is the subset of {1,2,3}.

now taking subsets of cardinality 1. 

We can take any 1 of {1},{2},{3} as none of the set is subset of the other.

Lets take {2}

Now taking the sets of cardinality 2-  {1,2},{1,3},{2,3} .

{2}⊂ {1,2} and {2,3} but we can't take both as none of the 2 is subset of the other.

so lets take {2,3}

so C = {∅,{2},{2,3},{1,2,3}} 

So if we observe carefully . We can see that we can select only 1 set from the subsets of each cardinality 1 to n . 

i.e total n subsets + ∅ = n+1 subsets of A can be there in C

So even though we can have different combinations of subsets in C but maximum cardinality of C will be n+1 only.

So B is the answer. 

answered by (877 points)  
edited by

Related questions

2,455 questions
849 answers
15,474 users