Mathematical Proof and the Principles of Mathematics/Sets/Elements and subsets

As we mentioned earlier, the basic concepts of set theory are left undefined. In fact the term 'set' simply means 'object', since all the objects in set theory are sets.

Elements of sets

The concept of membership in a set is fundamental, and we take as our Axiom 0 that this relationship exists. As with the '=' relation, we reserve a symbol '∈' for this relation:

Axiom S0: There is a relation '∈', defined on the universe of discourse, written $x\in y$ and read "x is an element of y," "x is in y," "x is contained in y," or "y contains x." (The last two phrases are ambiguous and should be used with care.)

The '∉' relation is defined in terms of '∈':

Definition SE1: Write $x\notin y,$ when not $x\in y.$

We can also define the reverse relation, though this isn't used much in practice.

Definition SE2: Write $x\ni y,$ when $y\in x.$

Subsets

The next axiom establishes when two sets are equal, but it's more convenient to first define what it means for a set to be a subset of another. We write $y\subseteq z,$ and say, "y is a subset of z," to mean all the elements of a set y are in a set z. Formally:

Definition SE3: Write $y\subseteq z,$ when for all x, $x\in y$ implies $x\in z.$

The symbols $y\subseteq z$ are read "y is a subset of z," "y is contained in z," or, "z contains y." (The last two phrases are also used in Axiom S0 to mean something else, which is why they are ambiguous. Rely on context to figure out what is meant in each case.)

Intuitively, $y\subseteq z$ means $y$ can be obtained from $z$ by removing zero or more of its elements, or that $z$ can be obtained from $y$ by adding zero or more elements. To prove one set is a subset of another, say $b\subseteq c$, start by choosing an arbitrary $a$, then assume $a\in b$ and derive $a\in c$. We already have two theorems whose proofs we leave as exercises.

As an example, consider the sets $A=\{1,2\}$ and $B=\{1,2,3\}$. We have that $A\subseteq B$ since all the elements of A are in B, but it's false that $B\subseteq A$ because 3 is in B but not A.

Theorem SE1: For all $x$, $x\subseteq x$.

Theorem SE2: For all $x$, $y$ and $z$, $x\subseteq y$ and $y\subseteq z$ imply $x\subseteq z$.

As with the '∈' relations, we can define variations on the '⊆' relation:

Definition SE4: Write $x\nsubseteq y,$ when not $x\subseteq y.$

Definition SE5: Write $x\supseteq y,$ when $y\subseteq x.$

Theorem SE3: $y\nsubseteq z$ if for some $x$, $x\in y$ and $x\notin z$.

The Axiom of Extensionality

As we mentioned in the history section of this chapter, a set is meant to be bag of objects with no internal organization or structure. In other words, all we require for two sets to be the same is that they have the same elements. This contrasts with ordered pairs, which we'll soon define formally, where the ordered pair depends on which order the elements occur. For example the ordered pair (1, 2) is not the same as the ordered pair (2, 1), but the set {1, 2} is the same as the set {2, 1}.

We can capture this idea informally by declaring

Two sets are equal if and only if they contain exactly the same elements.

More formally, we have the axiom:

Axiom S1 (Axiom of Extensionality): For all $x$ and $y$, $x\subseteq y$ and $y\subseteq x$ imply $x=y$.

Let's break this down to check that it matches the intuitive description from the previous paragraph. The condition $x\subseteq y$ basically says every element of $x$ is also in $y$, and the condition $y\subseteq x$ says every element of $y$ is also in $x$. When you put them together it says $x$ and $y$ have the same elements, and since a set is determined by its elements $x$ and $y$ must be the same thing.

Some authors take this axiom to be a definition of equality (at least for sets), which we could do as well if equality hadn't already been declared a fundamental concept. Note that even if equality were defined this way, we would still need the axiom substitution.

The Axiom of Extensionality provides a procedure for showing two sets are equal. To show $y=z$, first show $x\in y$ implies $x\in z$ and then show $x\in z$ implies $x\in y$. To show two sets y and z are not equal, it is enough to exhibit an x which is in y but not z or which is in z but not y.

For example, let $A=\{1\}$ and $B=\{1,1\}$. If x is an element of A then x=1, which is in the list 1, 1, so x is an element of B. On the other hand, if x is an element of B then x=1 or x=1, which implies x=1, and so x is an element of A. Therefore A=B.

As an example of two sets which are not equal, take $A=\{1,2,3\}$ and $B=\{1,2\}$. Then $A\neq B$ since $3\in A$ but $3\notin B$.

If we wish to say that x is a subset of y and exclude the possibility that x and y are equal, then say x is a proper subset of y. In symbols:

Definition SE4: Write $y\subset z,$ when $y\subseteq z$ and $y\neq z$.

The relations $\subseteq$ and $\subset$ are known as inclusion relations.

The empty set

So far, we have only discussed when two sets are the same, or one a subset of another; we haven't actually shown that any sets exists. In fact, the axioms we've given until now all hold for an empty universe, so we'll need another axiom to ensure the universe has something in it.

The Axiom of Existence tells us that there exists at least one set, specifically a set with no elements. This axiom is a starting point to bootstrap set theory since it provides us with a first set. The fact that it has no elements allows us to avoid the issue that no other sets have been defined yet.

Informally, the axiom states:

There exists a set that contains no elements.

More formally:

Axiom S2 (Existence of an empty set): For some $x$, for all $y$, $y\notin x$.

Note that the axiom just states that there exists at least one empty set. It doesn't state that there is only one such set. We still have some work to do before we can define 'the' empty set and give a name to it. Recall that the requirements for a definition are existence and uniqueness for the predicate in question.

First we define the predicate $Empty(x)$ to mean

For all $y$, not $y\in x$

then Axiom S1 simply spells out existence for this predicate, in other words:

For some x, $Empty(x)$

To prove uniqueness, we need to prove:

Theorem SE4: $Empty(x)$ and $Empty(y)$ imply $x=y$

We leave the proof as an exercise with a hint: Prove each set is a subset of the other and apply Axiom S1.

Since there is exactly one empty set, we can call it the empty set and define a symbol for it, namely $\varnothing$. We can also denote it $\{\}$. Formally:

Definition SE5: The empty set, denoted ∅ or {}, is defined to the set for which

For all $y$, not $y\in \varnothing$.

Note that the symbol ∅ looks similar to, but is actually different from the letter ø used in certain Nordic languages.

Theorem SE6: For all $x$, $\varnothing \subseteq x$.

The proof is left as an exercise. If you think of $x\subseteq y$ as meaning $x$ is smaller than $y$ in some sense, then ∅ is the smallest set. It's natural to ask if there is a largest set, but the answer is no. In order to prevent problems such as Russell's paradox, described in the chapter introduction, such a set cannot exist.

Theorem SE7: For all $x$, not $x=\varnothing$ implies for some $y$, $y\in x$

Again, the proof is left as an exercise.