You may also like

problem icon

Cube Net

How many tours visit each vertex of a cube once and only once? How many return to the starting point?

problem icon

Binary Sequences

Show that the infinite set of finite (or terminating) binary sequences can be written as an ordered list whereas the infinite set of all infinite binary sequences cannot.

problem icon

Binomial Coefficients

An introduction to the binomial coefficient, and exploration of some of the formulae it satisfies.

Groups of Sets

Stage: 5 Challenge Level: Challenge Level:2 Challenge Level:2

Thanks Jack from Pate's School, Yosef from Yeshivat Rambam High School, Baltimore, Andrei from Tudor Vianu National College, Bucharest, Romania and Curt from Reigate College for your solutions.

The binary operation $*$ for combining sets is defined as $A*B =(A\cup B) - (A\cap B)$.

To prove that $G$, consisting of the set of all subsets of a set $S$ (including the empty set and the set $S$ itself), together with the binary operation $*$, forms a group (assuming that the associative property is satisfied) it has to be shown that $G$ is closed, it contains an identity element and for each element in $G$ there is an inverse element contained in $G$.
Set diagram If $A$ and $B$ are two subsets of the set $S$, then $A*B =(A\cup B) - (A\cap B)$ is also a set, and $(A\cup B) - (A\cap B)$ is the subset of $S$ shown in colour in Andrei's diagram. Hence the closure property is satisfied.

The union of any set $A$ and the empty set $\phi$, is $A$, and there is no intersection between $A$ and $\phi$ as $\phi$ contains no elements to intersect.

$$\eqalign{ A*\phi &= (A\cup \phi)-(A\cap \phi)\cr &= A - \phi \cr &= A}.$$

Therefore $\phi$ is the identity element.

The intersection of a set with itself is itself, and the union of a set with itself is itself, for any set $A$, that is

$$\eqalign{ A*A &= (A\cup A) - (A\cap A) \cr &= A - A \cr &= \phi }.$$

Therefore the inverse of any element is itself, each element of $G$ is self inverse.

The fourth property, associativity, was assumed so we have shown $G$ is a group.

To solve $\{1,2,4\}*X=\{3,4\}$, rewrite it as $A*X=B$, where the solution is $X=A^{-1}*B$. We consider the set of all subsets of the natural numbers and note that this is an example of the group discussed above. Hence as the element $\{1,2,4\}$ is self inverse:

$$\eqalign{ X &= \{1,2,4\}*\{3,4\} \cr &= \{1,2,4\}\cup\{3,4\}- \{1,2,4\}\cap \{3,4\} \cr &= \{1,2,3,4\} - \{4\} \cr &= \{1,2,3\} }.$$ Check: $$\eqalign{ \{1,2,4\}*\{1,2,3\}&= \{1,2,4\}\cup\{1,2,3\} - \{1,2,4\}\cap\{1,2,3\}\cr &=\{1,2,3,4\}- \{1,2\} \cr &= \{3,4\} .}$$