7 votes 7 votes Consider a family $\mathcal{F}$ of subsets of $\{1, 2, \dots , n\}$ such that for any two distinct sets $A$ and $B$ in $\mathcal{F}$ we have: $A \subset B$ or $ B \subset A$ or $A \cap B = \emptyset$. Which of the following statements is TRUE? (Hint: what does the Venn diagram of this family look like?) $\mid \mathcal{F} \mid \leq 2n$ and there exists a family $\mathcal{F}$ such that $\mid \mathcal{F} \mid =2n$ $\mid \mathcal{F} \mid \leq n^2$ and there exists a family $\mathcal{F}$ such that $\mid \mathcal{F} \mid =n^2$ $\mid \mathcal{F} \mid \leq 2n^2$ and there exists a family $\mathcal{F}$ such that $\mid \mathcal{F} \mid =2n^2$ $\mid \mathcal{F} \mid \leq 2^{n-1}$ and there exists a family $\mathcal{F}$ such that $\mid \mathcal{F} \mid =2^{n-1}$ None of the above Set Theory & Algebra tifr2016 set-theory&algebra set-theory + – go_editor asked Dec 29, 2016 recategorized Nov 23, 2022 by Lakshman Bhaiya go_editor 1.0k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply dd commented Dec 29, 2016 reply Follow Share Is it 2n ???? 0 votes 0 votes KISHALAY DAS commented Dec 29, 2016 reply Follow Share Official ans given A..please explain 0 votes 0 votes Please log in or register to add a comment.
7 votes 7 votes This is what I thought ..please correct if wrong ! $\text{Assuming } \;\;\ \{1, 2, \dots , 4\}$ With following recurrence relation: $\begin{align*} f(n) = 2+ f(n-1) \;\; n\geq 2 \text{ and } \;\;\ f(1) = 2 \end{align*}$ dd answered Dec 29, 2016 edited Dec 29, 2016 by dd dd comment Share Follow See all 4 Comments See all 4 4 Comments reply dd commented Dec 29, 2016 reply Follow Share This is not the only maximal family $F$. $F_{MAX}$ is not unique. 0 votes 0 votes dd commented Dec 29, 2016 reply Follow Share $\phi$ is considered only once and in the base case $f(1)$ 0 votes 0 votes Aghori commented Dec 29, 2016 reply Follow Share Very good solution. 0 votes 0 votes r.tanuj commented Apr 2, 2021 reply Follow Share Why are only subsequeces considered here ? Why not subsets like {1,3} ? Where is it specified that subsets shouldn’t be considered ? 0 votes 0 votes Please log in or register to add a comment.