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 Correct Now. 

---

For n element set, we create subsets of size 0, 1, 2, 3, 4 till n.

The pattern we can observe after taking some small examples is that we can select exactly 1 subset from each of the sizes for C.

Variation on this question could be number of collection C possible.

---

Note : Amazing concept "TOSET" you will get in my answer .

Proof and Intuition based Explanation

https://gateoverflow.in/3779/gate-it-2005-question-33?show=533199#c533199

 

 

 

Answer 1

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).

Comments

@Ayush Upadhyaya nice explaination sir now i understood

---

very nice solution

---

@ankit3009 so null can also be part of the set?

Answer 2

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. 

Comments

@shubham empty set (∅) is a subset of every set. The empty set is a proper subset of every set except for the empty set.

---

Empty subset is a subset of itself but not a proper subset of itself.

---

Let's understand the Question first

You have a set $A$ with $n$ elements, and a collection $C$ of distinct subsets of $A$.

The condition states that for any two different subsets $S_1, S_2 \in C$:

$$S_1 \subset S_2 \quad \text{or} \quad S_2 \subset S_1$$

So every pair of sets in $C$ is comparable by inclusion. This means the collection $C$ is a chain of subsets (That form a TOSET).

Intuition behind the answer ( aage formal proof krenge )

Think of subsets as being arranged sequentially from smallest to largest:

$$\emptyset \subset \cdots \subset A$$

If every set must contain the previous one, then each new set has to be strictly bigger than the last one. Since the set $A$ has only $n$ elements, the subset size can only range from:

$$0, 1, 2, \dots, n$$

That gives at most $n+1$ different sizes, which means there can be at most $n+1$ subsets in such a chain.

Proof : Taking the concept from intuition and now move to more formal proof 

Let $C = \{S_1, S_2, \dots, S_k\}$ be such a collection.

Because for any two distinct subsets one must be a strict subset of the other, we can order them chronologically as:

$$S_1 \subset S_2 \subset \cdots \subset S_k$$

Now, look at their sizes:

$$|S_1| < |S_2| < \cdots < |S_k|$$

Why strict? Because if $S_i \subset S_{i+1}$, then $S_i \neq S_{i+1}$, meaning the larger set must have strictly more elements.

Each $|S_i|$ is an integer between $0$ and $n$. The longest strictly increasing sequence of integers you can possibly form within this boundary is:

$$0, 1, 2, \dots, n$$

which has exactly $n+1$ terms.

Therefore:

$$k \le n+1$$

So the maximum possible cardinality of $C$ is at most $n+1$.

Why only $n+1$ (means we can visualize by taking a1 ,a2,.... ,a3) ?

Take any ordering of the elements of $A$, say:

$$A = \{a_1, a_2, \dots, a_n\}$$

Now consider the expanding chain:

$$\emptyset \subset \{a_1\} \subset \{a_1, a_2\} \subset \cdots \subset \{a_1, a_2, \dots, a_n\} = A$$

This collection has exactly $n+1$ subsets, and every single pair is perfectly comparable by inclusion. So $n+1$ is not just an upper bound; it is completely achievanle .

Hence, the absolute maximum is:

$${n+1}$$

Answer 3

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)
 

Comments

How can u add {b,c } ?

---

Logic of this answer is not clear.

Answer 4

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.

Comments

Thanks for the clear explanation

Answer 5

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 6

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