I am completely stuck at the following question.

Suppose $X$ is an infinite set. Show that there is a family $\mathcal{F}$ of subsets of $X$ satisfying the following:

(a) If $A \subseteq X$ is finite, then $A \in \mathcal{F}$ iff $|A|$ is even.

(b) If $A, B$ are disjoint subsets of $X$, then $A \cup B \in \mathcal{F}$ iff either $A, B $ are both in $\mathcal{F}$ or $A, B$ are both not in $\mathcal{F}$.

What I tried: I started by adding all even size sets to $\mathcal{F}$ and then tried to use Zorn's lemma but could not come up with a partial order to make it work.

Could someone give me any hints? Thanks!

  • $\begingroup$ Consider the partial order defined by inclusion on the set of all families $\mathcal{F}$ of subsets of $X$. $\endgroup$ – xyzzyz May 28 '16 at 0:06
  • 3
    $\begingroup$ @xyzzyz Your hint is too cryptic for me. The "set of all families $\mathcal F$ of subsets of $X$" has a unique maximal element, namely $\mathcal P(X)$, which indeed satisfies (b), but does not satisfy (a) unless $X=\emptyset$. $\endgroup$ – bof Feb 16 '19 at 6:18

Let $[X]^{\lt\omega}$ be the set of all finite subsets of $X$. Let $\mathcal U$ be an ultrafilter on $[X]^{\lt\omega}$ such that $\{E\in[X]^{\lt\omega}:x\in E\}\in\mathcal U$ for each $x$ in $X$. Let's say that a statement $P(E)$ holds for almost all $E\in[X]^{\lt\omega}$ if $\{E\in[X]^{\lt\omega}:P(E)\}\in\mathcal U$. Now define $$\mathcal F=\{A\subseteq X:|A\cap E|\text{ is even for almost all }E\in[X]^{\lt\omega}\}.$$ Then (a) and (b) are satisfied.

More generally: For any positive integer $n$ and any set $A$, there is a function $f:\mathcal P(A)\to\{0,\dots,n-1\}$ satisfying the conditions:
(1) $f(X)\equiv|X|\pmod n$ for every finite set $X\subseteq A$;
(2) if $X,Y\subseteq A$ and $X\cap Y=\emptyset$, then $f(X\cup Y)\equiv f(X)+f(Y)\pmod n$.

  • $\begingroup$ +1: Does this proof work for any property of finite sets? $\endgroup$ – Alberto Takase Feb 16 '19 at 9:16
  • $\begingroup$ Not sure what generalization you have in mind. What exactly do you want to hold for any property of finite sets? $\endgroup$ – bof Feb 16 '19 at 9:27
  • $\begingroup$ An example of a property I have in mind (substituting "is even") is "the elements are pairwise comparable (given an established ordering)". I'm trying to connect the ideas I learned from this proof to the well-ordering theorem or more interestingly/plausible Teichmuller-Tukey lemma. $\endgroup$ – Alberto Takase Feb 16 '19 at 9:35
  • 1
    $\begingroup$ To the proposer: Zorn's Lemma is "hidden" in the existence of the ultra-filter. $\endgroup$ – DanielWainfleet Feb 16 '19 at 9:50
  • 1
    $\begingroup$ @DanielWainfleet Maximality is automatic: one family satisfying (a) and (b) can't be contained in another. $\endgroup$ – bof Feb 17 '19 at 23:44

Have you considered the following?

$$\mathcal{F}:=\{A\subseteq X:\#A\in2\mathbb{N}\text{ or ($A$ is infinite and $\#(X\setminus A)\in 2\mathbb{N}$})\}$$

Let me know if you need more details.

  • 1
    $\begingroup$ I definitely missed the nuance of this question... I am in progress of finding a better idea $\endgroup$ – Alberto Takase Feb 16 '19 at 6:26
  • $\begingroup$ Not sure I understand your updated answer. If $A$ and $X\setminus A$ are both infinite, I guess that means $A\notin\mathcal F$? But then what if you partition $A$ into two disjoint sets $X$ and $Y$, you will have $X\notin\mathcal F$, $Y\notin\mathcal F$, and $X\cup Y\notin\mathcal F$, right? $\endgroup$ – bof Feb 16 '19 at 7:23
  • $\begingroup$ yeah currently it doesn't work $\endgroup$ – Alberto Takase Feb 16 '19 at 7:23
  • $\begingroup$ Thank you for that comment. I was about to ponder for too long before considering that possibility! $\endgroup$ – Alberto Takase Feb 16 '19 at 7:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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