elementary set theory - Functions from a powerset to itself

Let $S$ be a set, and let $f$ be a function from the powerset of $S$ to the powerset of $S$. If, for all subsets $A$ of $S$, both 1) $f(f(A))=A$ and 2) $A \cap f(A)= \emptyset$, must $f$ be the complement function $S-A$? My 2nd question is, if we replace condition 2 by 2') A union $f(A) = S$, is $f$ the complement function $S-A$? I have tried working on both these problems, but I haven't made any progress.

Answer

I. Your two questions are equivalent.

Suppose $f:\mathcal P(S)\to\mathcal P(S)$ satisfies $f(f(A))=A$ and $A\cap f(A)=\emptyset$ for all $A$, and is not the complement function; then the function $g:\mathcal P(S)\to\mathcal P(S)$ defined by $g(A)=S-f(S-A)$ satisfies $g(g(A))=A$ and $A\cup g(A)=S$ for all $A$, and is not the complement function.

Likewise, if $f:\mathcal P(S)\to\mathcal P(S)$ satisfies $f(f(A))=A$ and $A\cup f(A)=S$ for all $A$, and is not the complement function, then the function $g(A)=S-f(S-A)$ satisfies $g(g(A))=A$ and $A\cap g(A)=\emptyset$ for all $A$, and is not the complement function.

II. For finite sets the answer is positive.

Let $S$ be a finite set, and suppose the function $f:\mathcal P(S)\to\mathcal P(S)$ satisfies the conditions $f(f(A))=A$ and $A\cap f(A)=\emptyset$ for all $A$. Call a set $A\subseteq S$ good if $f(A)=S-A$, bad if $f(A)\ne S-A$. If $A$ is good, then the set $f(A)=S-A$ is good; therefore, if $A$ is bad, then $f(A)$ and $S-A$ are bad.

Assume for a contradiction that $f$ is not the complement function, i.e., bad sets exist. Let $A$ be a bad set of minimum cardinality. Since $S-A$ is bad, $f(S-A)$ is a proper subset of $A$; but then $f(S-A)$ is bad and $|f(S-A)|\lt|A|$, contradicting the minimality of $A$.

III. For infinite sets the answer is negative.

Let $S$ be an infinite set, $|S|=\kappa$ an infinite cardinal. We will construct a function $f:\mathcal P(S)\to\mathcal P(S)$ such that $f(f(A))=A$ and $A\cap f(A)=\emptyset$ for all $A$, but $f$ is not the complement function.

If $|A|\lt\kappa$ or $|S-A|\lt\kappa$, we simply let $f(A)=S-A$. Let $\mathcal H=\{A\subset S:|A|=|S-A|=\kappa\}$. Since $\kappa$ is infinite, $|\mathcal H|=2^\kappa$. By a straightforward transfinite recursion of length $2^\kappa$, we define sets $X_\alpha,Y_\alpha$ for $\alpha\lt2^\kappa$, so that:

• $\mathcal H=\bigcup\{\{X_\alpha,Y_\alpha\}:\alpha\lt2^\kappa\}$;


• $X_\alpha,Y_\alpha\notin\bigcup_{\beta\lt\alpha}\{X_\beta,Y_\beta\}$;


• $Y_\alpha$ is a proper subset of $S-X_\alpha$.

Finally, we get our counterexample by defining $f(X_\alpha)=Y_\alpha$ and $f(Y_\alpha)=X_\alpha$.