Prove that $\forall A \exists !B \big (B \subseteq A \wedge \forall C(C \subseteq A \rightarrow B \vartriangle C = A \setminus C)\big)$

56 Views Asked by At

Prove that for every set $A$ there is a unique set $B \subseteq A$ such that for every $C \subseteq A$, $B \vartriangle C = A \setminus C$.

Is this the correct way to convert the question to a logical form, and does the proof make sense?

$\forall A \exists !B \big (B \subseteq A \wedge \forall C(C \subseteq A \rightarrow B \vartriangle C = A \setminus C)\big)$

Proof: Let $A$ be arbitrary. Let $B = A$. Now let $C$ be arbitrary, and suppose $C \subseteq A$. Let $x$ be arbitrary. Suppose $x \in B \vartriangle C = A \vartriangle C$. Then $x \in A \setminus C \cup C \setminus A$. Suppose $x \in C \setminus A$. Then $x \in C$ and $x \notin A$. But since $C \subseteq A$ and $x \in C$, $x \in A$. This contradicts the fact that $x \notin A$, so $x \notin C \setminus A$. Since $x \in A \setminus C \cup C \setminus A$, we can conclude that $x \in A \setminus C$. Now suppose $x \in A \setminus C$. Clearly $x \in A \setminus C \cup C \setminus A$, and $x \in A \vartriangle C = B \vartriangle C$. Since $x$ was arbitrary, $B \vartriangle C = A \setminus B$.

To show that $B$ is unique, let $B'$ be arbitrary such that $B' \subseteq A$ and $\forall C (C \subseteq A \rightarrow B' \vartriangle C = A \setminus C)$. Taking $C = \emptyset \subseteq A$, we have $B' \vartriangle \emptyset = A \setminus \emptyset$. So $B' \cup \emptyset \setminus (B' \cap \emptyset)=A$. It follows that $B' \cup \emptyset \setminus (B' \cap \emptyset)= B' \setminus \emptyset= B'=A = B$. $\square$

1

There are 1 best solutions below

4
On

It's OK. Here's a quicker option. On the one hand, by inspection $C\subseteq A\implies A\vartriangle C=A\setminus C$. On the other hand, if $B$ is a proper subset of $A$ then $C:=A\setminus B\implies B\vartriangle C=A\ne A\setminus C$, so $B=A$ is the unique solution.