Set operations

I've already told you what the union of two sets is. To remind you, if $x$ and $y$ are sets, then $x\cup y$ is the set whose elements are exactly all the elements of $x$ together with all the elements of $y$. We established existence of this union set by appealing to the Axiom of Union. Two other basic set operations that you've probably heard about are intersection $\cap$ and set difference/minus $-$. However, these two are a bit different from the union and their existence follows from the Axiom of Comprehension.

Let $x$ and $y$ be two sets. Their intersection should consist exactly of those sets which belong to both $x$ and $y$. We can say this also in another way: the elements of the intersection of $x$ and $y$ are exactly those elements of $x$ which are also elements of $y$. Maybe you've caught onto what I'm trying to suggest: the intersection of $x$ and $y$ is the set

$$x\cap y:=\{z\in x:P_y(z)\}$$

where $P_y(z)$ is the property asserting "$z$ belongs to $y$". We said last time that we can form new sets in this way, so we get basically for free that the intersection exists and is unique, or in other words, it is correctly defined. (Just in case the symbol := confuses you, it means "equal by definition" or "the left side is defined to be the right side".)

The set difference $x-y$ is defined similarly, as it is simply the set of all elements of $x$ which are NOT elements of $y$. In mathematical notation,

$$x-y:=\{z\in x:z\notin y\}.$$

In both the cases of intersection and difference, we get these sets by shrinking one of the two sets. However, in the case of the union, we needed to increase both sets which appear in the union. This is the reason why we can't use Comprehension to get unions and we need a whole new axiom. That being said, the union is still closely related to intersection and difference, which I'll try to briefly sketch to you.

Before I continue, I need to tell you what is a subset. This should be self-explanatory, but let me say it anyway: "$x$ is a subset of $y$" means that every element of $x$ is also an element of $y$. Intuitively, $y$ is "bigger" in so much that it might contain additional elements to those of $x$. However, note that if $x=y$, then $x$ is also a subset of $y$. The fact that $x$ is a subset of $y$ is denoted by $x\subseteq y$. Let me list some facts about this relation.

1. If $x=y$, then $x\subseteq y$.
2. If $x\subseteq y$ and $y\subseteq x$, then $x=y$.
3. $\mathrm{\varnothing }\subseteq \{\mathrm{\varnothing }\}$, but $\mathrm{\varnothing }\ne \{\mathrm{\varnothing }\}$.
4. In fact, the empty set is a subset of EVERY set.

The point here is that $x\subseteq y$ means that "every element of $x$ is also an element of $y$", while $x=y$ means "every element of $x$ is also an element of $y$ and every element of $y$ is also an element of $x$" (which is just a reformulation of the Axiom of Extensionality). The empty set is a subset of every set because it has no elements, while we've already explained why $\mathrm{\varnothing }\ne \{\mathrm{\varnothing }\}$.

Now, let's say that $U$ is some set that contains everything that we consider relevant for the moment. We'll be interested in subsets of $U$. If $X$ and $Y$ are two such subsets, then there are three operations that we might do with those subsets: we can take $X\cup Y$, we can take $X\cap Y$, and we can take $X-Y$. There is also a way to compere these two subsets, since it might be the case that $X\subseteq Y$ or that $Y\subseteq X$ or that neither is true. In addition to all this, there are two special subsets of $U$ distinguished among the others, namely $\mathrm{\varnothing }$ and $U$. They are special for example in the sense that for all $X$ that we are considering, it is true that $\mathrm{\varnothing }\subseteq X\subseteq U$. In other words, $\mathrm{\varnothing }$ is the smallest set and $U$ is the largest set with respect to $\subseteq$. There is also a notion of the complement of $X$, which we denote by $X^{\complement }$ and define to be the set of all elements of $U$ which do not belong to $X$, that is $X^{\complement }=U-X$. Here are some pictures that I drew in Paint.

There is a very particular structure corresponding to the situation described above. This structure is called Boolean algebra and its rules say a lot about algebraic connections between the operations $\cup ,\cap ,-$. I leave this for the next post.