# Constructing a family of sets

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!

• Consider the partial order defined by inclusion on the set of all families $\mathcal{F}$ of subsets of $X$. – xyzzyz May 28 '16 at 0:06
• @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$. – 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$$.

• +1: Does this proof work for any property of finite sets? – Alberto Takase Feb 16 '19 at 9:16
• Not sure what generalization you have in mind. What exactly do you want to hold for any property of finite sets? – bof Feb 16 '19 at 9:27
• 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. – Alberto Takase Feb 16 '19 at 9:35
• To the proposer: Zorn's Lemma is "hidden" in the existence of the ultra-filter. – DanielWainfleet Feb 16 '19 at 9:50
• @DanielWainfleet Maximality is automatic: one family satisfying (a) and (b) can't be contained in another. – 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.

• I definitely missed the nuance of this question... I am in progress of finding a better idea – Alberto Takase Feb 16 '19 at 6:26
• 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? – bof Feb 16 '19 at 7:23
• yeah currently it doesn't work – Alberto Takase Feb 16 '19 at 7:23
• Thank you for that comment. I was about to ponder for too long before considering that possibility! – Alberto Takase Feb 16 '19 at 7:28