1
$\begingroup$

Let $[\omega]^{<\omega}$ denote the collection of finite subsets of the integers, and let us call $E\subseteq [\omega]^{<\omega}$ non-nested if $a\not\subseteq b$ whenever $a\neq b\in E$.

Is there a non-nested set $E \subseteq [\omega]^{<\omega}$ with the following properties?

  1. Every $n\in \omega$ is contained in infinitely many members of $E$, and
  2. For every bijection $\varphi:\omega\to\omega$ and for every $a\neq b\in E$ we have $\sum_{n\in a} \varphi(n) \neq \sum_{n\in b} \varphi(b)$.
$\endgroup$
4
  • 2
    $\begingroup$ Isn't your notion of "non-nested" simply an antichain? $\endgroup$
    – Wojowu
    Commented Oct 25, 2021 at 22:52
  • 3
    $\begingroup$ It also seems to me that the condition 2 alone, for any one pair $a,b$ incomparable under $\subsetneq$, itself is inconsistent. For instance if they are disjoint, we can just map them by some bijection to some pair of disjoint subsets of the same sizes and with equal sums. $\endgroup$
    – Wojowu
    Commented Oct 25, 2021 at 22:55
  • 2
    $\begingroup$ @Wojowu actually you need condition 1, since otherwise $E$ could consist of all the singletons. $\endgroup$ Commented Oct 25, 2021 at 23:37
  • 1
    $\begingroup$ @BjørnKjos-Hanssen That's a good point! $\endgroup$
    – Wojowu
    Commented Oct 25, 2021 at 23:47

1 Answer 1

2
$\begingroup$

Theorem: There is no such $E$.

Claim: for each $a\in E$ there exists $b\in E$ with $|b\setminus a|\ge 2$. Proof of Claim: Let $a$ be a counterexample. Then all $b\ne a$ contain exactly one element each that's not in $a$. Let $n\not\in a$. Since $n$ is in infinitely many $b$'s, some $b$'s must be equal, contradiction.

Proof of Theorem: Fix any $a\in E$, and a corresponding $b$ as in the Claim.

To show that some $\varphi$ exists with $\sum_{n\in a}\varphi(n)=\sum_{n\in b}\varphi(n)$, we may assume $a\cap b=\emptyset$ since $a\cap b$ contributes the same to both sides.

Let $a=\{\alpha_1,\dots,\alpha_n\}$ and $b=\{\beta_1,\dots,\beta_m\}$.

Let $\varphi(\alpha_i)$ for $i<n$ be distinct and arbitrary.

Let $\varphi(\beta_i)$ for $i\le m$ be distinct, with each $\varphi(\beta_i)> \sum_{j<n}\varphi(\alpha_j)$.

Then for any $k$ and $t\ne k$ we have $$\sum\varphi(\beta_i)\ge \varphi(\beta_t)+\varphi(\beta_k) >\varphi(\beta_t) + \sum_{j<n}\varphi(\alpha_j)$$ so $\sum\varphi(\beta_i)-\sum\varphi(\alpha_i)> \varphi(\beta_t)$. Therefore we are free to define $$\varphi(\alpha_n)=\sum\varphi(\beta_i)-\sum_{j<n}\varphi(\alpha_i),$$ and we have defined an injective function from $a\cup b$ to $\omega$. This can now be extended to a bijection of $\omega$ arbitrarily.

This completes the construction of the desired $\varphi$ showing that no such $E$ exists. $\Box$

$\endgroup$
1
  • $\begingroup$ Beautiful, thanks Bjorn! (Apologies for not being able to type the o-accent) $\endgroup$ Commented Oct 26, 2021 at 9:14

You must log in to answer this question.

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