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.
 A: 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$.
A: Suppose first that $S$ is finite of cardinal $n$. Condition $1)$ says in particular that $f$ is bijective and condition $2)$ says in particular that $|A| + |f(A)| \leq n$. Take the sum over all sets in $P(S)$, you get:
\begin{align}
2 \sum_{A \subset S} |A| &= \sum_{A \subset S} |A| + |f(A)| \\
&\leq \sum_{A \subset S} n \\
&= n \times 2^n.
\end{align} 
In the first line, I use that $f$ is bijective. On the other hand, 
\begin{align}
\sum_{A \subset S} |A| &= \sum_{k=0}^n \binom{n}{k} k \\
&= P'(1),
\end{align}
where $P(x) = (1 + x)^n = \sum_{k=0}^n \binom{n}{k} x^k$. It follows that $P'(1)$ is $n \times 2^{n-1}$ and the inequality $|A| + |f(A)| \leq n$ is thus an equality for all $A$; this shows that $f$ is indeed the complementary function.
Remark that we only use that $f$ is bijective instead of $1)$. Moreover, the same computations work with $2)$ replaced by $2')$.
If $S$ is infinite, I think this is wrong but I have to think a little more.
