edited by
11,691 views
44 votes
44 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!$
edited by

10 Answers

Best answer
66 votes
66 votes
Let's take an example set $\{a,b,c\}$.

Now let's 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 $\left \{ a \right \},\left \{ b \right \},\left \{ c \right \}$

Lets say we add $\left \{ a \right \}$, so $S$ now becomes $\left \{ \left \{ a \right \} \right \}$.

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

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

So, the answer should be (B) $n+1$ (include the empty set).
edited by
91 votes
91 votes

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. 

edited by
17 votes
17 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)
 

edited by
12 votes
12 votes

A={1,2,3,4.....n}

A total number of all possible subsets that we can make from A is P(s).P(s) will contain all subsets of different length, it means no of subsets with the same cardinality may also be more than one. 

now, the question says that "C be a collection of distinct subsets of A such that for any two subsets S 1 and S2 in C,
either S1 ⊂ S2 or S2⊂ S1".

It means no two subsets in C with the same cardinality bcoz that can't be the proper subset of each other. ex: if set ={1,2,3}   ==> {1,2} ,{1,3},and {2,3} are subsets of set but they are not proper subset or subset of each other whether it will be proper subset of  3 length subset .

so, The KEY is : take only one subset of each length(1 length,2 length......n length) subset, that will be a proper subset of each other . The possible subset that satisfies the given condition is N + empty set  .

so N+1 will be the answer.

Answer:

Related questions

31 votes
31 votes
7 answers
1
26 votes
26 votes
3 answers
3
Ishrat Jahan asked Oct 31, 2014
6,437 views
What is the cardinality of the set of integers $X$ defined below?$X=\{n \mid 1 \leq n ≤ 123, n$ is not divisible by either $2$, $3$ or $5\}$$28$$33$$37$$44$