GATE IT 2005 | Question: 33

Question

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?$

• A. $n$
• B. $n+1$
• C. $2^{n-1} + 1$
• D. $n!$

Comments

@MSG1999 , In your set $C,$ neither $\{1 \}$ is subset of $\{2 \}$, Nor $\{2 \}$ is subset of $\{1 \}$. So, it is Not correct set $C.$

---

A= {1,2}

P(A) = {phi, {1] ,{2} ,{1,2}}

C ={phi, {1] ,{1,2}}

sir please check now

---

@MSG1999 Correct Now. 

Answer 1

A is a set with n elements, So, any subset of A can have length between 0 to n.

Claim: C can't have two subsets of A which has same cardinality.

Proof: Lets say S1 and S2 are two subsets of A and cardinality of S1 and S2 are same (|S1|=|S2|).

Now since cardinality of S1 and S2 are same, neither S1 is proper subset of S2 , nor S2 is proper subset of S1(S1⊂S2 not possible, also S2⊂S1 not possible). Hence S1 and S2 both can't be there at C(C may have S1 or S2  ----> one of them , but not both).
Hence C can have only one subset of A with cardinality x(where 0<=x<=n, because any subset of A can have length between 0 to n). For example if A={1,2,3} then different subsets of A with cardinality 2 are {1,2} , {1,3} ,{2,3}. Now C can have at most one of them as it's element.

So, at max C can have n+1 elements.

For example if A={1,2,.......n}, then C can be something like this (Note: Cmax (C with maximum cardinality) is not unique)

C={{1,2,.......n-1,n}, {1,2,.......,n-2,n-1} , {1,2,.......n-3,n-2}........................{1,2},{1} ,{}}

Answer 2

$C$ is a totally ordered set. Now it can easily be obtained from the poset $[P(A), \subset]$ where $P(A)$ is the power set of $A$. Draw the hasse diagram for the poset and to get a total order, consider all the elements along the path from $A$ to $\phi$. There are $n+1$ levels and from each level we include an element. So $B$ is the answer.

Answer 3

Here let n=2 A = {1, 2}
All subsets formed by A are: – {}, {1}, {2}, {1,2}.
C is a collection of distinct subsets such that for any S1, S2 either S1⊂S2 or S2⊂S1.
So for C, {} null set can be included always since it null. set is a subset of every set.
We can choose one from either {1} or {2}, {1,2} can be included to maximise the cardinality.
So, here 1) If {1} is chosen then C = {}, {1}, {1,2} here every set is subset of other.
2) If {2} is chosen then C = {}, {2}, {1,2} here also every set is subset of other.

So, answer should be 2 but it includes empty set also therefore the maximum cardinality of C is 3.

Answer 4

Consider an example:
Let A = {a, b, c}, here n = 3
Now, P(A) = {Ø, {a}, {b}, {c}, {a,b}, {b,c}, {{a}, {a,b,c}}
Now C will be contain Ø (empty set) and {a,b,c} (set itself) as Ø is the subset of every set. And every other subset is the subset of {a,b,c}.
Now taking the subset of cardinality, we an take any 1 of {a}, {b}, {c} as none of the set is subset of other.
Let's take {2}
→ Now taking the sets of cardinality 2 -{a,b}, {b,c}
→ {b} ⊂ {a,b} and {b,c} but we can't take both as none of the 2 is subset of the other.
→ So let's take {c,a}.
So, C = {Ø, {b}, {b,c}, {a,b,c}}
→ 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.