I have two questions about the properties of binary set operations that I am having difficulty arriving at answers that I completely trust (though I am sure they are not difficult questions). Here they are:
- Of the 16 binary operations on subsets satisfy the idempotent law? -Clearly the answer is at least 2, but binary operations P and Q are idempotent as well, correct? Compare this
- Under how many of the 16 binary operations on the subsets of a set do the latter form a group? -I am not really sure how to solve this question.
Many thanks in advance!
You link to binary logic functions, so I will answer with regards to those (you can generalize to general sets without much issue; the pictures help with this)
An operation that is idempotent (that is, for an operation $\oplus$, $x\oplus x=x$) will have the diagonal of the Cayley Table (a generalization of the multiplication table) equal to its value, so that by applying this to these operations, we see that only disjunction (or), conjunction (and), alternative denial (nand), joint denial (nor) (along with the trivially idempotent $P$ and $Q$ operators) are idempotent.
To answer the second question, the operations would need to be closed (all of these operations are closed), have an (unique) identity (conjunction ($x\wedge 1 =x$), disjunction ($x\vee 0=x$), symmetric difference ($x\oplus 0=x$), biconditional ($x\leftrightarrow 1=x$) are the only ones with this property), are associative (the above are all associative), and have inverses (for conjunction: if $x=1$, then $x^{-1}=1$ is an inverse for $\wedge$, but if $x=0$, then there is no $x^{-1}$ such that $x\wedge x^{-1}=1$, so there is no inverse; for disjunction, the identity is not unique, as $1\vee x=1$ for all $x$, so that $x=1$ has no inverse; for symmetric difference, if $x=1$, then $x^{-1}=1$, and if $x=0$, then $x^{-1}=0$; for biconditional, if $x=1$, then $x^{-1}=1$, and if $x=0$, then $x^{-1}=0$).
Thus, at least the symmetric difference and biconditional form groups.