2
$\begingroup$

This question is loosely inspired by the exact cover / partition problem in computer science.

Let $X\neq \emptyset$ be a set and let ${\cal E}\subseteq {\cal P}(X)$. For $x\in X$ we let $c_{\cal E}(x) = \big|\{e\in E: x\in e\}\big|$ be the covering number of $x$ (by members of ${\cal E}$). Note that ${\cal E}$ is a partition of $X$ if and only if $c_{\cal E}(x) = 1$ for all $x\in X$. We call ${\cal E}$ a pseudo-partition if there is a unique element $x_0 \in X$ with $c_{\cal E}(x_0) = 2$ and $c_{\cal E}(x) = 1$ for all $x\in X\setminus\{x_0\}$, and we denote this exceptional element $x_0$ by $\newcommand{\exc}{\text{exc}}\exc({\cal E})$.

Question. Is there a collection ${\cal E}\subseteq {\cal P}(\mathbb{N})$ with the following properties?

  1. If ${\cal E}'\subseteq {\cal E}$, then ${\cal E}'$ is not a partition of $\mathbb{N}$, and
  2. For every $n\in\mathbb{N}$ there is a pseudo-partition ${\cal E}_n\subseteq {\cal E}$ with $\exc({\cal E}_n)=n$.
$\endgroup$
6
  • $\begingroup$ Does taking all pairs and all cosingletons work? $\endgroup$ Commented Apr 4 at 18:33
  • $\begingroup$ No, {{0,1},{2,3},{4,5},...} is a partition of $\mathbb{N}$. $\endgroup$
    – paste bee
    Commented Apr 4 at 18:33
  • $\begingroup$ Ah, right, the collection can be infinite. What about $\mathbb{N} \setminus \{0\}$ and all pairs which contain $0$? $\endgroup$ Commented Apr 4 at 18:35
  • $\begingroup$ That doesn't have a pseudo-partition with $0$ as the exceptional element. $\endgroup$
    – paste bee
    Commented Apr 4 at 18:36
  • 2
    $\begingroup$ Yep. (I had already mostly written an answer, ...apparently we came up with the exact same example). $\endgroup$
    – paste bee
    Commented Apr 4 at 18:39

1 Answer 1

5
$\begingroup$

Yes. Let $\mathcal{E} = \{\mathbb{N} \setminus \{0\}, \mathbb{N} \setminus \{1\}\} \cup \{\{0,n\} : n \in \mathbb{N}\}$. No subset of this is a partition of $\mathbb{N}$, because too many of the sets contain $0$. $\{0,1\}$ and $\mathbb{N} \setminus \{1\}$ is a pseudo-partition with exceptional element $0$. For any $n \neq 0$, $\{0,n\}$ and $\mathbb{N} \setminus \{0\}$ is a pseudo-partition with exceptional element $n$.

$\endgroup$

You must log in to answer this question.

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