Binary Operations on Subsets--Two Questions

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:

1. 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
2. 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!

-

2 Answers

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.

-
Many thanks Hayden! I am glad to know now about Cayley Tables. They are useful. – mcmahon.an Mar 4 '13 at 4:25
Quick follow-ups...1) The order of the value of the Cayley table diagonal doesn't matter, so the negations of P and Q should also fit the bill for idempotent operations, right? 2) The book I am reading tells me that at least the subsets of a set under "Symmetric Difference" form a group, so your second answer confuses me. I apologize if the original wording was difficult. Note: the text is by DL Johnson: Elements of Logic via Numbers and Sets – mcmahon.an Mar 4 '13 at 4:33
It depends on how you're looking at the order. If we're looking at the i,i entry of the cayley table, then it needs to be such that $x_i\oplus x_i=x_i$ for whatever operation $\oplus$ you're using. Thus, keeping the places of 0 and 1 fixed, the diagonals will always have to be the same for all idempotent truth functions. The negations of P and Q wouldn't be, as $\neg 1=0$ and $\neg 0=1$. As far as the second point, you are indeed correct. I missed that the symmetric difference does indeed have an identity, and stopped checking properties after that. The answer has been updated as such. – Hayden Mar 4 '13 at 5:37

For 1, True and False are also idempotent

-
Thanks, but I don't understand this. If this is the definition of idempotence:"Whenever the operands of the operation are the same, the connective gives the operand as the result", how can either True or False have the property? In the case of True, input 0 and 0 as operands and you get 1; in the case of False, input 1 and 1 as operands and you get 0...Forgive me, but what have I missed here? Many thanks – mcmahon.an Mar 4 '13 at 5:20
I had seen idempotence in the sense of matrices, $A^2=A$ so when you apply the operation twice you get the same result. But in Boolean logic it is different. – Ross Millikan Mar 4 '13 at 5:47
I see. Fascinating. Thanks all the same! – mcmahon.an Mar 4 '13 at 5:55