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

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

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₁ ⊂ S₂ or S₂⊂ S₁

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

---

phi is a proper subset of every set.

So phi will be included.

Now, from an n element set,

there will be 1 element subset, 2 element subset and so on till n element subset which is the set itself.

Also, no set is a proper subset of itself.

But according to given definition, we should have either S1$\subset$ S2 or S2 $\subset$ S1 for any two subsets S1 and S2 in C.

So, we can take a single element from all possible one element subsets and not more than 1?

Why?

because say if we take two 1 elements subsets like {a}, {b}, then neither of them is proper subset of each other.

Similarly, a single element from all possible two element subsets.

And so on till finally we are left only with set itself and this will also be included because anyhow all subsets taken till now will be subset of this set.

So, in total 1 element taken from each possible subsets, total count this way =n.

And since, phi is also included, so total elements in C is n+1. (B).

---

Definition of the proper subset.

A is a proper subset of B if

∀x((x∈A)->(x∈B) ^ ∃y((y∈B) ^ (y∉A)))

---

Perfect explanation

---

If A= {a,b,c}, here n=3.

So, the resultant relation is : ( {{a},{a,b}} , {{a},{a,b,c}} , {{a}, phi}). We have (n+1) i.e. 4 as maximum cardinality of C which includes {{a} , {a,b} , {a,b,c} , phi}. Please let me know if wrong.

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

Note- ∅ is a subset of every set except itself.

---

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

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.