Naive set theory

Naive set theory is distinguished from axiomatic set theory by the fact that the former regards sets as collections of objects, called the elements or members of the set, whereas the latter regards sets only as that which satisfies the axioms. Sets are of great importance in mathematics; in fact, in the modern formal treatment, the whole machinery of pure mathematics (numbers, relations, functions, etc.) is defined in terms of sets.

Naive set theory was developed at the end of the 19th century (principally by Georg Cantor) in order to allow mathematicians to work with infinite sets consistently.

As it turned out, assuming that one could perform any operations on sets without restriction led to paradoxes such as Russell's paradox. In response, axiomatic set theory was developed to determine precisely what operations were allowed and when. Indeed, when research mathematicians talk about "set theory" today, they usually mean axiomatic set theory.

However, axiomatic set theory can be quite abstruse and yet has little effect on ordinary mathematics. Thus, it is useful to study sets in the original naive sense in order to develop facility for working with them. Furthermore, a firm grasp of naive set theory is important as a first stage in understanding the motivation for the axiomatic theory.

This article develops the naive theory. We begin by defining sets informally and investigating a few of their properties. Links in this article to specific axioms of set theory point out some of the relationships between the informal discussion here and the formal axiomatization of set theory, but we make no attempt to justify every statement on such a basis.

Table of contents 1 Sets, membership and equality 2 Specifying sets 3 Subsets 4 Universal sets and absolute complements 5 Intersections, unions, and relative complements 6 Cartesian products 7 Paradoxes 8 External links

Sets, membership and equality

In naive set theory, a set is described as a collection of objects. Those objects that belong to a set are called its members. As objects we allow anything: numbers, people, other sets... For instance, 4 is a member of the set of all even integers. As you see, we allow sets to be infinite.

If x is a member of A, then we also say that x is an element of A, or that x belongs to A, or that x is in A, or that A owns x. In this case, we write x ∈ A. (The symbol "∈" is a derivation of the Greek letter Epsilon, "ε".)

We define two sets to be equal when they have precisely the same elements. (See Axiom of extension.) Thus a set is completely determined by its elements; the description is immaterial. For example, the set with elements 2, 3, and 5 is equal to the set of all prime numbers less than 6. If A and B are equal, then this is denoted symbolically as A = B (as usual).

We also allow for an empty set, a set without any members at all. Since a set is determined completely by its elements, there can only be one empty set. (See Axiom of empty set.)

Specifying sets

The simplest way to describe a set is to list its elements between curly braces. Thus {1,2} denotes the set whose only elements are 1 and 2. (See Axiom of pairing.) Note the following points:

• Order of elements is immaterial; for example, {1,2} = {2,1}.
• Repetition of elements is irrelevent; for example, {1,2,2} = {1,1,1,2} = {1,2}.

(These are consequences of the definition of equality in the previous section.) This notation can be informally abused[?] by saying something like {dogs} to indicate the set of all dogs. An extreme example of this notation is {}, which denotes the empty set.

We can also use the notation {x : P(x)} to denote the set containing all objects for which the condition P holds. For example, {x : x is a real number} denotes the set of real numbers, {x : x has blonde hair} denotes the set of everything with blonde hair, and {x : x is a dog} denotes the set {dogs} of all dogs.

This notation is called "set builder notation" (or "set comprehension", particularly in the context of Functional programming). Some variants of set builder notation are:

• {x ∈ A : P(x)} denotes the set of all x that are already members of A such that the condition P holds for x. For example, if Z is the set of integers, then {x ∈ Z : x is even} is the set of all even integers. (See Axiom of specification.)
• {F(x) : x ∈ A} denotes the set of all objects obtained by putting members of the set A into the formula F. For example, {2x : x ∈ Z} is again the set of all even integers. (See Axiom of replacement.)
• {F(x) : P(x)} is the most general form of set builder notation. For example, {x's owner : x is a dog} is the set of all dog owners.

Subsets

Given two sets A and B we say that A is a subset of B, if every element of A is automatically an element of B. Notice that in particular, B is a subset of itself; a subset of B that isn't equal to B is called proper.

If A is a subset of B, then one can also say that B is a superset of A, or that A is contained in B, or that B contains A. In symbols, A ⊆ B means that A is a subset of B, and B ⊇ A means that B is a superset of A. Some authors use the symbols "⊂" and "⊃" for subsets, and others use these symbols only for proper subsets. In this encyclopedia, "⊆" and "⊇" are used for subsets while "⊂" and "⊃" are reserved for proper subsets.

As an illustration, let A be the set of real numbers, let B be the set of integers, let C be the set of odd integers, and let D be the set of current or former US Presidents. Then C is a subset of B, B is a subset of A, and C is a subset of A. Note that not all sets are comparable in this way. For example, it is not the case either that A is a subset of D nor that D is a subset of A.

The sets A, B and C above illustrate the

PROPOSITION 1: Given any three sets A, B and C, if A is a subset of B and B is a subset of C, then A is a subset of C.

The proof is an easy exercise.

It is also the case that

PROPOSITION 2: Two sets A and B are equal if and only if A is a subset of B and B is a subset of A.

Notice that one of the examples of set builder notation above, {x ∈ A : P(x)}, is specifically designed to construct a subset of A.

We also have

PROPOSITION 3: The empty set is a subset of every set.

Proof: Given any set A, we wish to prove that {} is a subset of A. This involves showing that all elements of {} are elements of A. But there are no elements of {}. For the experienced mathematician, the inference "{} has no elements, so all elements of {} are elements of A" is immediate, but it may be more troublesome for the beginner. Since {} has no members at all, how can "they" be members of anything else? It may help to think of it the other way around. In order to prove that {} was not a subset of A, we would have to find an element of {} which was not also an element of A. Since there are no elements of {}, this is impossible and hence {} is indeed a subset of A.

These proposition show that ⊆ is a partial order on the class of all sets, and {} is a bottom element[?]. (See Paradoxes below for more on the class of all sets.)

Universal sets and absolute complements

In certain contexts we may consider all of our sets as being subsets of some given universal set. For instance, if we are investigating properties of real numbers (and sets of reals), then we may take R, the set of all reals, as our universal set. It is important to realise that a universal set is only temporarily defined by the context; there is no such thing as a "universal" universal set, "the set of everything" (see Paradoxes below).

Given a universal set U and a subset A of U, we may define the complement of A (in U) as

A' := {x ∈ U : not(x ∈ A)},

i.e., the set of all members of U which are not members of A. Thus with A, B and C as in the section on subsets, if B is the universal set, then C' is the set of even integers, while if A is the universal set, then C' is the set of all real numbers that are either even integers or not integers at all.

The collection {A : A ⊆ U} of all subsets of a given universe U is called the power set of U. (See Axiom of power set.) It is denoted P(U); the "P" is sometimes in a fancy font.

Intersections, unions, and relative complements

Given two sets A and B, we may construct their union. This is the set consisting of all objects which are elements of A or of B or of both (see Axiom of union). It is denoted by A ∪ B. The intersection of A and B is the set of all objects which are both in A and in B. It is denoted by A ∩ B. Finally, the relative complement of B relative to A, also known as the set theoretic difference of A and B, is the set of all objects that belong to A but not to B. It is written as A \ B. Symbolically, these are respectively

A ∪ B := {x : (x ∈ A) or (x ∈ B)};

A ∩ B := {x : (x ∈ A) and (x ∈ B)} = {x ∈ A : x ∈ B} = {x ∈ B : x ∈ A};

A \ B := {x : (x ∈ A) and not(x ∈ B) } = {x ∈ A : not(x ∈ B)}.

Notice that A doesn't have to be a subset of B for B \ A to make sense; this is the difference between the relative complement and the absolute complement from the previous section.

To illustrate these ideas, let A be the set of left-handed people, and let B be the set of people with blond hair. Then A ∩ B is the set of all left-handed blond-haired people, while A ∪ B is the set of all people who are left-handed or blond-haired or both. A \ B, on the other hand, is the set of all people that are left-handed but not blond-haired, while B \ A is the set of all people that have blond hair but aren't left-handed.

Now let E be the set of all human beings, and let F be the set of all living things over 1000 years old. What is E ∩ F in this case? No human being is over 1000 years old, so E ∩ F must be the empty set {}.

We list without proof several simple properties of these operations. These properties can be visualized with Venn diagrams.

PROPOSITION 4: For any sets A, B, and C:

• A ∩ A = A;
• A ∪ A = A;
• A \ A = {};
• A ∩ B = B ∩ A;
• A ∪ B = B ∪ A;
• (A ∩ B) ∩ C = A ∩ (B ∩ C);
• (A ∪ B) ∪ C = A ∪ (B ∪ C);
• C \ (A ∩ B) = (C \ A) ∪ (C \ B);
• C \ (A ∪ B) = (C \ A) ∩ (C \ B);
• C \ (B \ A) = (A ∩ C) ∪ (C \ B);
• (B \ A) ∩ C = (B ∩ C) \ A = B ∩ (C \ A);
• (B \ A) ∪ C = (B ∪ C) \ (A \ C);
• A ⊆ B if and only if A ∩ B = A;
• A ⊆ B if and only if A ∪ B = B;
• A ⊆ B if and only if A \ B = {};
• A ∩ B = {} if and only if B \ A = B;
• A ∩ B ⊆ A ⊆ A ∪ B;
• A ∩ {} = {};
• A ∪ {} = A;
• {} \ A = {};
• A \ {} = A.

PROPOSITION 5: For any universal set U and subsets A, B, and C of U:

• A'' = A;
• B \ A = A' ∩ B;
• (B \ A)' = A ∪ B';
• A ⊆ B if and only if B' ⊆ A';
• A ∩ U = A;
• A ∪ U = U;
• U \ A = A';
• A \ U = {}.

We can also prove the distributive laws:

PROPOSITION 6: For any sets A, B, and C:

(a) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C);

(b) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).

Proof: We shall prove (a) and leave (b) as an exercise. Each side of equation (a) defines a set and we wish to prove that these sets are equal. By Proposition 2, a possible strategy is to show that each side is a subset of the other.

1. Pick any element x of the left-hand side (LHS). Then, by definition of ∩, x is in A and x is in B ∪ C; that is, x is in A and either x is in B or x is in C (or both). In the first case, x is both in A and in B, so it's in A ∩ B and a fortiori in (A ∩ B) ∪ (A ∩ C). In the second case, x is both in A and in C and so again it's in (A ∩ B) ∪ (A ∩ C). Thus in either case, x is in (A ∩ B) ∪ (A ∩ C). We have shown that every element of the LHS is automatically in the RHS. But this is precisely what we mean by saying that the LHS is a subset of the RHS.
2. Pick any element x of the RHS. Then x is in A ∩ B or x is in A ∩ C (or both). In the first case, x is in A and x is in B; in the second, x is in A and x is in C. In either case, x is in A. Also in the first case x is in B and hence in B ∪ C; in the second case, x is in C and thus again in B ∪ C. We have proved that whatever x is, if it is a member of the RHS, then it is both in A and in B ∪ C and hence by definition is in A ∩ (B ∪ C). We have proved that the RHS is a subset of the LHS.

By Proposition 2, (1) and (2) together prove that LHS = RHS, as required.

The above propositions show that the power set P(U) is a Boolean lattice.

Cartesian products

Given objects a and b the ordered pair containing a and b is denoted (a,b). For the time being we shall take this as a primitive notion (but see also Ordered pair). That is, we shall assume that (a,b) has the property that if (a,b) = (x,y), then a = x and b = y. The objects a and b are called respectively the first and second components of (a,b). Now, given two sets A and B, we define their Cartesian product to be

A × B = {(a,b) : a is in A and b is in B}.

That is, A × B is the set of all ordered pairs whose first component is an element of A and whose second component is an element of B.

We can extend this definition to a set A × B × C of ordered triples, and more generally to sets of ordered n-tuples for any positive integer n. It is even possible to define infinite Cartesian products, but to do this we need a more recondite definition of the product.

Cartesian products were first developed by René Descartes in the context of analytic geometry. If R denotes the set of all real numbers, then R² := R × R represents the Euclidean plane and R³ := R × R × R represents three-dimensional Euclidean space.

Paradoxes

We referred earlier to the need for a formal, axiomatic approach. What problems arise in the treatment we have given? The problems relate to the formation of sets. One's first intuition might be that we can form any sets we want, but this view leads to inconsistencies. For any set we can ask whether x is a member of itself. Define

Z = {x : x is not a member of x}.

Thus for every object x, x belongs to Z if and only if x does not belong to x. Now for the problem: is Z a member of Z? If yes, then by the defining quality of Z, Z is not a member of itself, i.e., Z is not a member of Z. This forces us to declare that Z is not a member of Z. Then Z is not a member of itself and so, again by definition of Z, Z is a member of Z. Thus both options lead us to a contradiction and we have an inconsistent theory. Axiomatic developments place restrictions on the sort of sets we are allowed to form and thus prevent problems like our set Z from arising. (This particular paradox is Russell's paradox.)

The penalty is a much more difficult development. In particular, it is problematic to speak of a set of everything, or to be (possibly) a bit less ambitious, even a set of all sets. In fact, in the standard axiomatisation of set theory, there is no set of all sets. In areas of mathematics that seem to require a set of all sets (such as category theory), one can sometimes make do with a universal set so large that all of ordinary mathematics can be done within it (see Universe (mathematics)[?]). Alternatively, one can make use of proper classes. Or, one can use a different axiomatisation of set theory, such as W. V. Quine's New Foundations[?], which allows for a set of all sets and avoids Russell's paradox in another way. The exact resolution employed rarely makes an ultimate difference.

External links

• Beginnings of set theory (http://www-groups.dcs.st-and.ac.uk/~history/HistTopics/Beginnings_of_set_theory) page at St. Andrews