wiz-icon
MyQuestionIcon
MyQuestionIcon
1
You visited us 1 times! Enjoying our articles? Unlock Full Access!
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 S1 and S2 in C, either S1S2 or S2S1. What is the maximum cardinality of C ?

A
n
No worries! We‘ve got your back. Try BYJU‘S free classes today!
B
n+1
Right on! Give the BNAT exam to get a 100% scholarship for BYJUS courses
C
2n1+1
No worries! We‘ve got your back. Try BYJU‘S free classes today!
D
n!
No worries! We‘ve got your back. Try BYJU‘S free classes today!
Open in App
Solution

The correct option is B n+1
The way C is defined in the question, it contains only comparable subsets of A.
i.e. the set C is the set of all comparable subsets of the set A. Such a set is called a chain.
Consider an example with set A={1,2}
Subsets are ϕ,{1},{2} and {1,2}
Maximum cardinality of collection of distinct subsets is {ϕ,{1} and {1,2}} i.e. 3
So with n elements maximum cardinality is n+1.

flag
Suggest Corrections
thumbs-up
0
similar_icon
Similar questions
View More
Join BYJU'S Learning Program
similar_icon
Related Videos
thumbnail
lock
Sets and Their Representations
MATHEMATICS
Watch in App
Join BYJU'S Learning Program
CrossIcon