# XOR in set theory

1. Mar 17, 2014

### Jhenrique

First: relating some ideia of set theory and binary logic, like:

U = 1
Ø = 0

thus, some identities appears:

U ∪ U = U
U ∪ Ø = U
Ø ∪ U = U
Ø ∪ Ø = Ø

U ∩ U = U
U ∩ Ø = Ø
Ø ∩ U = Ø
Ø ∩ Ø = Ø

1 + 1 = 1
1 + 0 = 1
0 + 1 = 1
0 + 0 = 0

1 × 1 = 1
1 × 0 = 0
0 × 1 = 0
0 × 0 = 0

So, the conclusion is that the operation of Union is analogous to AND, and the Intersection is analogous to OR.

But, one thing no is clear for me yet: and the binary operation XOR, XOR have a analogue in set theory?

2. Mar 17, 2014

### D H

Staff Emeritus
XOR is the same as "not equals", and sets can be compared for equality (or lack thereof).

3. Mar 17, 2014

### Jhenrique

Wait... binary operations shouldn't be compared with set operations ?

4. Mar 17, 2014

### D H

Staff Emeritus
Huh?

The other way around. Union is analogous to OR, intersection to AND.

Symmetric difference, perhaps.

Don't get too carried away with analogies. There are sixteen functions that map a pair of booleans to a boolean.

5. Mar 17, 2014

### Jhenrique

I compared AND with Union and OR with Intersection. AND, OR, Union and Intersection are all operations. I think strange to compare XOR (an operation) with the ideia of "not equals" (that isn't an operation).

6. Mar 17, 2014

### D H

Staff Emeritus
And that was an erroneous comparison. Look at your own opening post. Anything AND false is false. The intersection between any set and the null set is the null set. AND is analogous to set intersection, not set union. Similarly, OR is analogous to set union, not set intersection.

Of course "not equals" is an operation. There's even a special symbol for it: ≠. Boolean not equals and boolean exclusive or have the exactly same truth tables. They are the same operation in boolean algebra.

7. Mar 17, 2014

### micromass

Staff Emeritus
I would say the equivalent to XOR is the operation

$$A\Delta B = \{x~\vert~(x\in A)~\mathrm{XOR}~(x\in B)\}$$

Thus we see easily that this is

$$A\Delta B = (A\cup B)\setminus (A\cap B)$$

This is called the symmetric difference.

8. Mar 17, 2014

### D H

Staff Emeritus
That's what I said in post #4.

9. Mar 17, 2014

### Jhenrique

OH YEAH!!! I was wrong! AND is to Intersection so like OR is to Union.

"symmetric difference"... huh... very interesting!