2
$\begingroup$

This is a kind of "dual" of an older question.

Is there a finite family ${\frak F}\subseteq {\cal P}(\mathbb{N})$ such that for all $a\neq b\in\mathbb{N}$ there is $S\in{\frak F}$ with $|S\cap \{a,b\}| = 1$?

$\endgroup$

1 Answer 1

5
$\begingroup$

$\newcommand\F{\mathfrak F}\newcommand\P{\mathfrak P}\newcommand\N{\mathbb N}\newcommand\om{\omega}$No. Let $\P$ be the partition of $\N$ generated by $\F$.

Detail: If $\F=\{S_1,\dots,S_n\}$, then the members of the partition $\P$ are all the sets of the form $\bigcap_{j=1}^n S_j^{\om_j}$, where $(\om_1,\dots,\om_n)\in\{0,1\}^n$, $S_j^0:=S_j$, and $S_j^1:=\N\setminus S_j$.

Then $\P$ is finite and hence at least one member $P$ of $\P$ is infinite. Taking any distinct $a$ and $b$ in $P$, we see that $|S\cap\{a,b\}|\in\{0,2\}$ for each $S\in\F$.

Detail: If $\F=\{S_1,\dots,S_n\}$ and $P=\bigcap_{j=1}^n S_j^{\om_j}$ for some $(\om_1,\dots,\om_n)\in\{0,1\}^n$, then for each $j\in\{1,\dots,n\}$ we have $|S_j\cap\{a,b\}|=2$ if $\om_j=0$ and $|S_j\cap\{a,b\}|=0$ if $\om_j=1$.


The same argument works if $\N$ is replaced by any set $X$ such that $|X|>2^{|\F|}$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .