10
$\begingroup$

We work in $\sf ZF$.

An amorphous set is a set that cannot be partitioned into $2$ disjoint infinite sets.

If $A$ is an amorphous set then it has an equal number of finite subsets and infinite subsets, with the bijection $x \mapsto x^c$. Is the opposite also true? That is, given a nonempty set $x$ with an equal number of infinite and finite subsets, is it amorphous?

I showed that it is enough to show that $2^A$ is Dedekind finite: define $B$ as the set of finite subsets of $A$ and $C$ as the set of cofinite subsets of $A$. If there exists a bijection $f:B \to [A]^{\not<\omega}$, then define $g : B \cup C \to \mathcal P (A)$ as $x \mapsto f(x)$ if $x \in B$ and $x^c$ otherwise. $g$ is a bijection, so if $\mathcal P (A)$ is Dedekind finite, $B \cup C = \mathcal P (A)$.

$\endgroup$
6
  • 2
    $\begingroup$ @lulu the tag description says the tag is also for questions we explicitly don't use AC: "this tag is for [...] how things would work without the assumption of this axiom". The axiom set is ZF $\endgroup$
    – Holo
    Commented Mar 25 at 14:49
  • $\begingroup$ @ℋolo Ah, good point. $\endgroup$
    – lulu
    Commented Mar 25 at 14:57
  • $\begingroup$ Note sure if this helps: notice that if $2^A≥\aleph_0$ then $A$ can be partitioned into $\aleph_0$ infinite parts, in particular it has at least $\frak c$-many infinite subsets. Hence at least $\frak c$-many finite subsets $\{F_i\mid i\in\frak c\}$ so there exists $D\subseteq A$ such that $D$ is a countable disjoint union of finite sets, furthermore by looking at $R_n=\{F_i\mid |F_i|=n\text{ and }i\in\frak c\}$ we get that either there is $k\inℕ$ such that $|R_k|≥\aleph_0$ (and hence we may assume $D$ is a countable disjoint union of sets of size $k$) or $ℝ$ is countable union of d-finite sets $\endgroup$
    – Holo
    Commented Mar 25 at 21:48
  • 3
    $\begingroup$ See Combinatorial Set Theory by Lorenz Halbeisen, Thm 4.21, Prop 4.22. It's not exactly what you're asking, but can be altered. Show first that $\aleph_0\le|\text{fin}(A)|$. Then follow the guideline in the last paragraph of the proof of Prop 4.22, using that there's a bijection $\mathcal P(A)\to 2\times \text{fin} A$. Lotsa luck! (Note that the counterexample in Prop 7.5 mentioned there is based on an amorphous set...) $\endgroup$
    – Chad K
    Commented Mar 26 at 9:18
  • $\begingroup$ Hi @ChadK. I'm trying to understand your comment - I think I might be being silly (sorry). Is your comment a hint to prove "if $A$ has the same number of finite and infinite subsets, then $A$ is amorphous"? If so I can't see why $\aleph_0 \le |\mathrm{fin}(A)|$ (I was under the impression that the powerset of an amorphous set is always D-finite). $\endgroup$ Commented Mar 26 at 15:14

1 Answer 1

3
$\begingroup$

Referring to Theorem to 4.21, Proposition 4.22 In L. Halbeisen's book as explained in the comment:

Let $A$ be an infinite set.

Let $\text{fin}(A)$ be the finite subsets of $A$, $\text{cof}(A)$ the cofinite subsets of $A$. Write $\mathcal P(A)=\text{fin}(A)\sqcup\text{cof}(A)\sqcup \text{binf}(A)$, where $\text{binf}(A)$ is the rest.

If $|\mathcal P(A)\setminus \text{fin}(A)|=|\text{fin}(A)|$ then $|\mathcal P(A)|=2|\text{fin}(A)|$.

Now assume $A$ is not amorphous (so $\text{binf}(A)\ne\emptyset$) and $|\mathcal P(A)\setminus \text{fin}(A)|=|\text{fin}(A)|$. Let $\sigma\colon\mathcal P(A)\setminus \text{fin}(A)\to\text{fin}(A)$ be a bijection. Let $\tau\colon \mathcal P(A)\setminus\text{cof}(A)\to\text{fin}(A)$ be defined by $$ \tau(x)=\begin{cases} \sigma(A\setminus x)&x\in\text{fin}(A)\\ \sigma(x)&x\in\text{binf}(A) \end{cases} $$ Then $\tau$ is a bijection. Let $u\in\text{binf}(A)$. Then $\tau(u)\in\text{fin}(A)$, so $\tau(u)\not\in\tau(\text{fin}(A))$. Therefore $\tau\rvert_{\text{fin}(A)}$ is an injective map from $\text{fin}(A)$ onto a proper subset of itself. Therefore $\text{fin}(A)$ is Dedekind infinite (i.e. $\aleph_0\le|\text{fin}(A)|$.)

Now consider the proof of Prop 4.22. The restriction that $n$ not be a power of two is only used in the previous-to-last paragraph, and it's used to show that under the assumptions of the proposition (which permit amorphous!) $\aleph_0\le|\text{fin}(A)|$. Once that is shown, what's described in the last paragraph is applicable to any $n$, including powers of $2$. In the present case we have $|\mathcal P(A)|=n|\text{fin}(A)|$ where $n=2$. The last paragraph describes how to modify the proof of Theorem 4.21 (which is fairly complicated) to get a contradiction by injecting $\text{Ord}$ into $\text{fin}(A)$. So for any infinite $A$ for which $\aleph_0\le|\text{fin}(A)|$, it follows that $|\mathcal P(A)|\ne n|\text{fin}(A)|$ for any $n\ge 1$.

$\endgroup$
2
  • $\begingroup$ Nice job making the connection to this theorem! The construction in 4.21 is really nice, and I'm always surprised to see non trivial results like 4.22 in ZF. $\endgroup$
    – Ynir Paz
    Commented Mar 26 at 18:11
  • $\begingroup$ Right, I was being silly - you were arguing by contradiction. Very nice answer, thanks for typing it up! $\endgroup$ Commented Mar 26 at 18:58

You must log in to answer this question.

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