# Max length of meaningful combinations of union and intersection of three sets.

Given three sets: $X, Y, Z$ and the two set operations: union and intersection. What is the maximum length of a 'formula' which is not reducible to a shorter formula.

Eg. the formula $(X \cap Y) \cup X$ can be reduced to the formula $X$.

However the formula $Y \cap(X \cup Z)$ is not reducible in length.

I've been thinking about this problem for a while now, but can't seem to get past a length of 3. (the length being the amount of set symbols).

All possible combinations (I think):

$$X$$

$$Y$$

$$Z$$

$$X \cup Y$$

$$Y \cup Z$$

$$X \cup Z$$

$$X \cap Y$$

$$Y \cap Z$$

$$X \cap Z$$

$$(X \cap Y) \cup Z$$

$$(Y \cap Z) \cup X$$

$$(Z \cap X) \cup Y$$

$$(X \cup Y) \cap Z$$

$$(Z \cup X) \cap Y$$

$$(Y \cup Z) \cap X$$

$$X \cap Y \cap Z$$

$$X \cup Y \cup Z$$

$$\{(X \cup Z) \cap Y\} \cup (X \cap Z)$$

Venn says:

• Note that by using only union and intersection operations it is impossible to get rid of the $X \cap Y \cap Z$ region. – Maazul Apr 30 '13 at 20:21
• Thank you very much! This is a great help! – 13Tazer31 May 1 '13 at 15:38