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 setsEdit

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   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   when not  

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

Definition SE2: Write   when  


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   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   when for all x,   implies  

The symbols   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,   means   can be obtained from   by removing zero or more of its elements, or that   can be obtained from   by adding zero or more elements. To prove one set is a subset of another, say  , start by choosing an arbitrary  , then assume   and derive  . We already have two theorems whose proofs we leave as exercises.

As an example, consider the sets   and  . We have that   since all the elements of A are in B, but it's false that   because 3 is in B but not A.

Theorem SE1: For all  ,  .
Theorem SE2: For all  ,   and  ,   and   imply  .

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

Definition SE4: Write   when not  
Definition SE5: Write   when  
Theorem SE3:   if for some  ,   and  .

The Axiom of ExtensionalityEdit

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   and  ,   and   imply  .

Let's break this down to check that it matches the intuitive description from the previous paragraph. The condition   basically says every element of   is also in  , and the condition   says every element of   is also in  . When you put them together it says   and   have the same elements, and since a set is determined by its elements   and   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  , first show   implies   and then show   implies  . 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   and  . 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   and  . Then   since   but  .

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   when   and  .

The relations   and   are known as inclusion relations.

The empty setEdit

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  , for all  ,  .

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   to mean

For all  , not  

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

For some x,  

To prove uniqueness, we need to prove:

Theorem SE4:   and   imply  

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  . We can also denote it  . Formally:

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

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

Theorem SE6: For all  ,  .

The proof is left as an exercise. If you think of   as meaning   is smaller than   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  , not   implies for some  ,  

Again, the proof is left as an exercise.

History · Pairs