3
$\begingroup$

Definition: a set $X$ is to be labeled as "non-exhaustively overlapping" if and only if each element of $X$ is not a subset of any other element of $X$; formally:$$ X \text { is non-exhaustively overlapping } \equiv_{df}\\ \forall x,y \in X (x \not \subsetneq y) $$

Question 1: Is it consistent with ZF to have a set $X$ such that there is subset $S$ of $\mathcal P(X)$ that is non-exhausively overlapping and such that: $$ |S|=|\mathcal P(X)|$$

Another related question is about "strict non-exhaustive overlaps" here it is meant a set where each element of it has a subset that do not overlap with any other element of that set. Formally: $$ X \text { is strictly non-exhaustively overlapping } \equiv_{df} \\\forall x \in X \exists m \in x \forall y \in X (y \neq x \to m \not \in y)$$

Question 2: the same question above but when $S$ is strictly non-exhaustively ovelapping.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ I think you intend $x\neq y$ in the definition of non-exhaustively overlapping. $\endgroup$
    – Joel David Hamkins
    Oct 30, 2019 at 13:26
  • $\begingroup$ Your formal statement of strictly non-exhaustively overlapping is different from what you say in natural language, so I'm not sure what you mean. $\endgroup$
    – Joel David Hamkins
    Oct 30, 2019 at 13:30
  • 2
    $\begingroup$ @JoelDavidHamkins Aren't these the same because having a non-empty subset which does not overlap with any other element of the set is equivalent to containing one element which does not overlap any other element of the set, at least if "overlap" means "intersect"? In any case for the formal question 2, the answer is clearly "no" as there is at most one $m$ for each $x$. $\endgroup$
    – Will Sawin
    Oct 30, 2019 at 13:37
  • 1
    $\begingroup$ Yes, you are right. But this uses AC to pick elements, and something like it can happen in ZF, as I mention in my answer. $\endgroup$
    – Joel David Hamkins
    Oct 30, 2019 at 13:45
  • $\begingroup$ I find it interesting to interpret question 2 as asking, in the specific case of the reals, whether it is consistent with ZF that one can make those strange partitions of $\mathbb{R}$ with not only more than $\mathbb{R}$ many members, but $2^{\mathbb{R}}$ many members. $\endgroup$
    – Joel David Hamkins
    Oct 30, 2019 at 14:04

1 Answer 1

Reset to default
7
$\begingroup$

The answer to question 1 is yes. Take the binary binary branching tree $2^{<\omega}$ and label every node with a different natural number. Now, for each branch $b$ through the tree, let $X_b$ be the set of labels on those nodes. Distinct branches $b$ will give continuum many set $X_b$, and none of these is a subset of another. Indeed, they are an almost-disjoint family of size continuum, a family of infinite sets, with any two having finite intersection.

For question 2, the answer is negative in ZFC, since we would be assigning to each element of the family a distinct element of the set, and so it couldn't be larger.

But in ZF, if we replace "$|S|=|P(X)|$" with "$|S|>|X|$", then it can happen (with the subset characterization, rather than element characterization, since without AC you can't pick the element). Namely, it is known to be relatively consistent with ZF that there is a partition $S$ of the real numbers $X=\mathbb{R}$ into strictly more than $\mathbb{R}$ many elements. Basically, if there is no $\omega_1$-sequence of reals, then we can define an equivalence relation on $\mathbb{R}$ by the coding-the-same-countable-ordinal relation, where two reals are equivalent if they both code the same countable ordinal and otherwise inequivalent, unless identical. Now, we get at least $\omega_1$ many equivalent classes, plus continuum many more, and so the number of partition elements exceeds $\mathbb{R}$, but they are disjoint.

Meanwhile, if you insist on $|S|=|P(X)|$, then I can prove it is impossible in ZF. By picking for each element of $S$ the largest subset of it that is disjoint from all the other elements of $S$, we can thereby produce a partition of $X$ of size $P(X)$. This is precisely the situation I mentioned in the comments, which I can now rule out.

Specifically, suppose that $S$ is a partition of a set $X$ and $S$ has size $P(X)$. So to each subset $A\subseteq X$, we have a distinct element $X_A\in S$. Define a map $f:X\to P(X)$ by $f(x)=A$, when $x\in X_A$. Since $S$ is a partition, this defines a function. And our assumptions ensure that this is surjective. But there is no surjection of a set $X$ to $P(X)$ by Cantor's argument.

So the answer to question 2 is negative.

Improve this answer
$\endgroup$
2
  • $\begingroup$ In the proof of impossibility of $|S|=|P(X)|$, the set produced is not necessarily a partition of $X$. However, that doesn't affect the proof, since it would be a subset of a partition on $X$, and so the proof go through. $\endgroup$
    – Zuhair Al-Johar
    Oct 30, 2019 at 17:56
  • $\begingroup$ I had meant that you would just add all the left over points as another set, thereby getting a partition. $\endgroup$
    – Joel David Hamkins
    Oct 30, 2019 at 17:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.