Given a nonempty set S, we select a fixed subset $S_0\subseteq S$ and use it to define two functions on the set of all subsets of $S$:

  1. $f(A)=A\cup S_0$

  2. $g(A)=A\setminus S_0$

For what choices of $S_0$ do these functions commute?

  1. Only for $S_0=\varnothing$? or
  2. Only for $S_0=S$? or
  3. For all $S_0$?
  • 1
    $\begingroup$ You have three options. Test each option with an example. $\endgroup$ – Newb Dec 23 '13 at 21:58
  • $\begingroup$ first option: f(A)=A , g(A) = A $\endgroup$ – tim Dec 23 '13 at 22:03
  • $\begingroup$ second option: f(A) = A ∪ S, g(A) = A / S, i am confused this with the third option actually, $\endgroup$ – tim Dec 23 '13 at 22:04


Recall that the functions commute if for every $A$, $f(g(A))=g(f(A))$, that is $$(A\cup S_0)\setminus S_0=(A\setminus S_0)\cup S_0.$$

The choices for which the functions don't commute can be found by testing the case where $S=\{a,b,c\}$. The choice where the functions do commute is easily provable.

| cite | improve this answer | |
  • $\begingroup$ thank you for the detailed answer, i followed your explanation, the answer would be the first one, is that correct? thank you $\endgroup$ – tim Dec 23 '13 at 22:06
  • $\begingroup$ Yes, the first one is true, the others false. $\endgroup$ – Asaf Karagila Dec 23 '13 at 22:22

$gf(A)=g(A\cup S_0)=(A\cup S_0)\setminus S_0=A\setminus S_0$

$fg(A)=(A\setminus S_0)\cup S_0=A$

1 -true

| cite | improve this answer | |
  • 1
    $\begingroup$ Your calculation of $fg(A)$ is false. $A=\varnothing$ and $S_0\neq\varnothing$ gives $fg(A)=S_0\neq A$. $\endgroup$ – Asaf Karagila Dec 23 '13 at 22:11

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.