Questions About A Pigeonhole Principle Problem

Question

I've encountered the following pigeonhole principle problem. It uses notation from set theory, which is a subject I haven't studied yet. I would like to check if I have understood notation, and the question, correctly.

The problem is:

What I would like to check is that:

1. Does F refer to the set of all subsets of {1,2,3...n}?
2. Does $X, Y ∈ F, X$ intersect $Y=empty$ mean if X and Y are elements of F, they have no element in common?
3. Does $|F|$ mean the number of subsets of {1,2,3...n}, that fulfill the requirements above?
4. Does an empty set count as a subset of {1,2,3...n}? And if so, I have another question. Would the family of subsets of {1,2,3}: {1},{2},{3},{} fulfill the requirements of a subset size 2 power $n-1$?

Thanks in advance.

Answer 1

1. No: $\mathscr{F}$ is some subset of $\wp(\{1,2,\ldots,n\}$, specifically, one with the property that every pair of members of $\mathscr{F}$ have non-empty intersection. Thus, $\mathscr{F}$ cannot include every subset of $\{1,2,\ldots,n\}$, since some of them are disjoint.
2. Yes.
3. $|\mathscr{F}|$ is the number of subsets of $\{1,2,\ldots,n\}$ that are in the family $\mathscr{F}$.
4. Yes: $\varnothing$, the empty set, is a subset of $\{1,2,\ldots,n\}$.
5. No, $\big\{\{1\},\{2\},\{3\},\varnothing\big\}$ does not satisfy the condition on $\mathscr{F}$, because, for instance, $\{1\}\cap\{2\}=\varnothing$. Indeed, the intersection of any two distinct members of this family is empty, so the family fails as badly as possible to satisfy the condition.

HINT for the problem: $\mathscr{F}$ cannot contain both a subset of $\{1,2,\ldots,n\}$ and the complement of that subset, and $\{1,2,\ldots,n\}$ has altogether $2^n$ subsets.

Answer 2

1. No, $F$ is a set of subsets of $S=\{\,1,2,\dots,\,\}$, but not necessarily all the subsets of $S$.

2. $X\cap Y=\emptyset$ does mean $X$ and $Y$ have no elements in common (but note that in the question, $X\cap Y\neq\emptyset$).

3. Yes.

4. Yes. And yes that's a subset of size $2^{n-1}$, but it's not the kind the question asks for. The intersections are supposed to be nonempty.

Answer 3

1. $F$ is some of the subsets of $\{1,\dots,n\} = [n]$.
2. Yes, it means that if $X,Y$ are both subsets of $[n]$ that are in $F$, then they do not intersect.
3. $\vert F \vert$ means the number of sets in the family (set of sets) $F$.
4. Yes, the empty set is a subset and may be in $F$. In your example, $F = \{\{1\},\{2\},\{3\},\{\}\}$ does not work since it asks the intersections to be non-empty.