The problem (and a definition first):

The following definition explained

Let $U \subseteq \mathbb{N}$.

We say that a function $x: \{0,1\}^U\to \{0,1\}$ is a $xor$ on the set $U$ if the following condition is met:

$x(a)=1-x(a')$, if $a$ and $a'$ are function that differ for exactly one argument $a \in U$. That is, there is such $n \in U$, that $a(n)\neq a'(n)$ and for all $m \in U-\{n\}$ $a(m)=a'(m)$.

Example (not a very helpful one):

For $U=\{0,...,10\}$ function $x:\{0,1\}^U\to \{0,1\}$ defined as: $$ x(a)=(\sum_{i=0}^{10}a(i))(\mod 2)$$ is a xor on the set U.

Show that there is a xor function for $\mathbb{N}$.

Hint: consider the order by inclusion of all xor functions for all subsets of $\mathbb{N}$: $(\{x: x$ is a $xor$ for some subset $U\subseteq \mathbb{N}\}, \subseteq)$

Order by inclusion on functions is defined as:

$f \subseteq g \iff (Dom(f) \subseteq Dom(g)) \land (\forall x \in Dom(f): f(x)=g(x)) $

My solution:

Let $\mathcal{F}=(\{x: x$ is a $xor$ for some subset $U\subseteq \mathbb{N}\}, \subseteq)$ and $\mathcal{C}$ be a chain in $\mathcal{F}$.

$\sup(\mathcal{C})=f: X \to \{0,1\}$, such that $f(x)=g(x)$ for any $g \in \mathcal{C}$ and where $X=\bigcup \{Dom(f): f \in \mathcal{C}\}$.

This is a supremum, because the domain of this function is a sum of all domains in $\mathcal{C}$ (so it is the "biggest" domain). Thus any given chain in $\mathcal{F}$ has an upper bound, and we can use the Kuratowski-Zorn lemma to show that $\mathcal{F}$ has at least one maximal element.

The maximal element of $\mathcal{F}$ must be a function $f_{max}: \mathbb{N} \to \{0,1\}$ because all domains in $\mathcal{F}$ are subsets of $\mathbb{N}$, and $\mathbb{N}$ is the maximal element of $(P(\mathbb{N}), \subseteq)$.


Well it sounds solid to me but it's a bit complicated (and me passing the semester heavily depends on this solution...), and I've never felt strong in elementary math. By the way, can you show me an example function that is a $xor$ for $\mathbb{N}$ (please include it in your answer)? I can't think of any...

Thanks a lot!


The conclusion that the domain of $f_{max}$ is all of $\mathbb N$ cannot be done the way you do. But assume $X$ is the domain of $f_{max}$ and there exists $n\in\mathbb N\setminus X$. Then you can define $f\colon \{0,1\}^{X\cup \{n\}}\to\{0,1\}$ by $$ f(a)=f_{max}(a|_X)+ a(n)\bmod 2$$ which is xor function that is "bigger" than $f_{max}$, contradiction.

For the additional question: No such maximal function can be described explicitly. The proof of its existence relies heavily on Zorn's lemma, i.e. the axiom of choice.


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.