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

From Wikibooks, open books for an open world
Jump to navigation Jump to search

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[edit]

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 Extensionality[edit]

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 set[edit]

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