this is from Velleman's How To Prove It, exercise 4.6.14.b. The exercise reads as in the title and $A\vartriangle Y$ is the symmetric difference between $X$ and $Y$, so $X\vartriangle Y = (X \setminus Y) \cup (Y \setminus X)$. I have written a proof and would appreciate it if someone could check it. To prove uniqueness I use the equivalence $\exists !xP(x) \equiv \exists x(P(x)\wedge \forall y (P(y) \to y=x))$. Are there any other ways to prove it besides using proof by contradiction twice? Maybe using identities on the symmetric difference operation? Maybe using the equivalence $\exists!xP\left(x\right)\equiv\exists xP\left(x\right)\wedge\forall y\forall z\left(\left(P\left(y\right)\wedge P\left(z\right)\right)\to y=z\right)$? By the way, the relation $R$ is proven to be an equivalence relation in exercise 4.6.14.a.

Suppose $B \subseteq A$, and define a relation $R$ on $\mathscr{P}(A)$ as $$R=\left\{ \left(X,Y\right)\in\mathscr{P}\left(A\right)\times\mathscr{P}\left(A\right)\mid\left(X\vartriangle Y\right)\subseteq B\right\}.$$ Prove that for every $X\in\mathscr{P}\left(A\right)$, there is exactly one $Y\in\left[X\right]_{R}$ such that $Y\cap B=\varnothing$.

Let $Y=X\setminus B$. Then $X\vartriangle\left(X\setminus B\right)=\left(X\setminus\left(X\setminus B\right)\right)\cup\left(\left(X\setminus B\right)\setminus X\right)=\left(X\cap B\right)\subseteq B$, so $Y\in\left[X\right]_{R}$. Since $\left(X\setminus B\right)\cap B=\varnothing$, $Y$ has the desired properties. To see that $Y$ is unique, suppose $Z$ is an arbitrary set such that $Z\in\left[X\right]_{R}$ and $Z\cap B=\varnothing$. We will prove that $Z=X\setminus B=Y$.

Let $x\in Z$ and, seeking a contradiction, suppose $x\notin X$. Then $x\in X \vartriangle Z$. Since $Z\in\left[X\right]_{R}$, $Z\vartriangle X\subseteq B$, so $x\in B$. But $Z\cap B=\varnothing$, so $x\notin B$ and thus we can conclude that $x\in X$. Hence $x\in X\setminus B$, and since $x$ was an arbitrary element of $Z$, it follows that $Z\subseteq X\setminus B$.

Now let $x\in X\setminus B$ and, seeking a contradiction once more, suppose $x\notin Z$. Then $x\in X\setminus Z$, so $x\in X\vartriangle Z\subseteq B$. But we know $x\notin B$, so it must be the case that $x\in Z$. Since $x$ was arbitrary, $X\setminus B\subseteq Z$, and therefore $Z = X\setminus B = Y$.

  • $\begingroup$ It may be easier if you observe that $(X,Y)\in R \iff X$ \ $B=Y$ \ $B.$ So if $(X,Y)\in R$ and $Y \cap B=\phi$ then $Y=Y$ \ $B=X$ \ $B.$ It often pays to look for equivalent but perhaps simpler versions of a given def'n or hypothesis. $\endgroup$ – DanielWainfleet Feb 1 '17 at 22:22
  • $\begingroup$ This is exactly what I was looking for. That equivalence makes a lot of sense intuitively, but I wonder if proving it could also get a little verbose as my proof above. Do you know if the proof for it is simple, or was the equivalence just obvious to you? $\endgroup$ – MuchToLearn Feb 1 '17 at 23:49
  • $\begingroup$ I tried to picture what $X$ and $Y$ look like if $(X,Y)\in R.$ In particular what $X$ \ $B$ and $Y$ \ $B$ would be....I noticed that if $p\in (X$ \ $B)$ or $p\in (Y$ \ $B)$ then $p$ must belong to both $X$ \ $B$ and $Y$ \ $B,$ otherwise $p$ would belong to $X\Delta Y$ but not to $B$.... Without referring to members, we can say : $(X \backslash B)\Delta (Y\backslash B) = (X \Delta Y) \backslash B$ for any $X,Y,B.$... So if $(X,Y)\in R$ we have $\phi=(X\Delta Y)$ \ $B=(X$ \ $B)\Delta (Y$ \ $B),$ and this last expression is empty iff $X$ \ $B= Y$ \ $B.$ (Because $\phi =P\Delta Q\iff P=Q.$) $\endgroup$ – DanielWainfleet Feb 2 '17 at 4:47
  • $\begingroup$ Excellent. Would have accepted it as the answer. Thank you! $\endgroup$ – MuchToLearn Feb 2 '17 at 15:56
  • $\begingroup$ You are welcome. $\endgroup$ – DanielWainfleet Feb 3 '17 at 3:15

I think your proof is fine. Here is another way to express it, although it is essentially the same as yours. I don't know if it is any clearer, since justifying each step will end up re-doing what you have already done...

The first part of your first paragraph establishes $Y=X \setminus B$ satisfies $Y \in [X]_R$ and $Y \cap B = \varnothing$.

It remains to prove the converse: if some arbitrary $Y$ satisfies $Y \in [X]_R$ and $Y \cap B = \varnothing$, then $Y=X \setminus B$.

Note that $X \triangle Y = (X \setminus Y) \cup (Y \setminus X) \subseteq B$ and $Y \cap B = \varnothing$ together imply $Y \setminus X = \varnothing$. Thus $Y \subseteq X$. Combining this with $Y \cap B = \varnothing$ yields $Y \subseteq X \setminus B$.

Thus, $$B = X \setminus (X \setminus B) \subseteq X \setminus Y = X \triangle Y \subseteq B,$$ so all these subsets are actually equalities, yielding $Y=X \setminus B$.


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.