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

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.