MATH.7:5.2 - Sets represented by bit vectors

Let X be the subsets of {a,b,c}. Map a subset to its membership vector in {0,1}^3; for example, {a,c} maps to (1,0,1). Decode by selecting the positions marked 1. These maps are inverse on all eight subsets and all eight vectors.

Take symmetric difference as the source operation: an element belongs to S△T when it belongs to exactly one of S and T. Its transported operation is coordinatewise XOR, whose output bit is 1 exactly when the two input bits differ. The empty set becomes (0,0,0).

For S={a,c} and T={b,c}, symmetric difference gives {a,b}. In coordinates:

(1,0,1) XOR (0,1,1) = (1,1,0).

Decoding returns {a,b}. This gives a way to perform the set operation in a binary representation and recover its result. The inverse map and operation formula explain why the method works for every subset pair; the eight-by-eight table is a finite check if needed.

If the next question asks for union instead, derive its operation: coordinatewise OR. Reusing XOR would discard an element present in both inputs. The same bijection supports both operations once each is defined.