Naive set theory
|
|
Naive set theory1 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 certain axioms. Sets are of great importance in mathematics; in fact, in modern formal treatments, every mathematical object (numbers, relations, functions, etc.) is defined in terms of sets.
| Contents |
Introduction
Naive set theory was created at the end of the 19th century 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. Today, when mathematicians talk about "set theory" as a field, they usually mean axiomatic set theory, but when they talk about set theory as a mere tool to be applied to other mathematical fields, they usually mean naive set theory.
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. Sets are defined informally and a few of their properties are investigated. 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 no attempt is made to justify every statement on such a basis.
Sets, membership and equality
In naive set theory, a set is described as a well-defined collection of objects. These objects are called the elements or members of the set. Objects can be anything: numbers, people, other sets, etc. For instance, 4 is a member of the set of all even integers. As can be seen from this example, sets are allowed to have an infinite number of elements.
If x is a member of A, then it is also said that x belongs to A, or that x is in A. In this case, we write x ∈ A. (The symbol "<math>\in<math>" is a derivation from the Greek letter epsilon, "ε", introduced by Peano in 1888.) The symbol <math>\notin<math> is sometimes used to write x ∉ A, or "x is not in A".
Two sets A and B are defined to be equal when they have precisely the same elements, that is, if every element of A is an element of B and every element of B is an element of A. (See axiom of extensionality.) 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, often denoted <math>\varnothing<math>: 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 (multiplicity) of elements is irrelevant; 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, but this example would usually be read by mathematicians as "the set containing the single element dogs".
An extreme (but correct) example of this notation is {}, which denotes the empty set.
We can also use the notation {x : P(x)} (or sometimes {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 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 also 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 a proper subset.
If A is a subset of B, then one can also say that B is a superset of A, 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 U.S. 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.
It follows immediately from the definition of equality of sets above, that given two sets A and B, A = B iff A ⊆ B and B ⊆ A. In fact this is often given as the definition of equality.
The set of all subsets of a given set A is called the power set of A and is denoted by <math>2^A<math> or <math>P(A)<math>. If the set A has n elements, then <math>P(A)<math> will have <math>2^n<math> elements. Note that the empty set is a subset of every set.
Universal sets and absolute complements
In certain contexts we may consider all sets under consideration as being subsets of some given universal set. For instance, if we are investigating properties of the real numbers R (and subsets of R), then we may take R 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
- AC := {x ∈ U : ¬(x ∈ A)},
where ¬ is the logical not operator. In other words, AC (sometimes simply A') is the set of all members of U which are not members of A. Thus with A, B and C defined 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.
Unions, intersections, 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 {}.
For any set A, the power set <math>P(A)<math> is a Boolean algebra under the operations of union and intersection.
Ordered pairs and Cartesian products
Intuitively, an ordered pair is simply a collection of two objects such that one can be distinguished as the first element and the other as the second element, and having the fundamental property that, two ordered pairs are equal if and only if their first elements are equal and their second elements are equal.
Formally, an ordered pair with first coordinate a, and second coordinate b, usually denoted by (a, b), is defined as the set {{a}, {a, b}}.
It follows that, two ordered pairs (a,b) and (c,d) are equal if and only if a = c and b = d.
Alternatively, an ordered pair can be formally thought of as a set {a,b} with a total order.
(The notation (a, b) is also used to denote an open interval on the real number line, but the context should make it clear which meaning is intended.)
If A and B are sets, then the Cartesian product (or simply product) is defined 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 coordinate is an element of A and whose second coordinate 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 R2 := R × R represents the Euclidean plane and R3 := R × R × R represents three-dimensional Euclidean space.
Some important sets
Note: In this section, a, b, and c are natural numbers, and r and s are real numbers.
- Natural numbers are used for counting. A blackboard bold capital N (<math>\mathbb{N}<math>) often represents this set.
- Integers appear as solutions for x in equations like x + a = b. A blackboard bold capital Z (<math>\mathbb{Z}<math>) often represents this set (for the German Zahlen, meaning numbers, because I is used for the set of imaginary numbers).
- Rational numbers appear as solutions to equations like a + bx = c. A blackboard bold capital Q (<math>\mathbb{Q}<math>) often represents this set (for quotient, because R is used for the set of real numbers).
- Algebraic numbers appear as solutions to polynomial equations (with integer coefficients) and may involve radicals and certain other irrational numbers. A blackboard bold capital A (<math>\mathbb{A}<math>) or a Q with an overline often represents this set.
- Real numbers include the algebraic numbers as well as the transcendental numbers, which cannot appear as solutions to polynomial equations with rational coefficients. A blackboard bold capital R (<math>\mathbb{R}<math>) often represents this set.
- Imaginary numbers appear as solutions to equations such as x2 + r = 0 where r > 0. A blackboard bold capital I (<math>\mathbb{I}<math>) often represents this set.
- Complex numbers are the sum of a real and an imaginary number: r + si. Here both r and s can equal zero; thus, the set of real numbers and the set of imaginary numbers are subsets of the set of complex numbers. A blackboard bold capital C (<math>\mathbb{C}<math>) often represents this set.
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}.
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.
See also
References
- Paul Halmos, Naive set theory. Princeton, NJ: D. Van Nostrand Company, 1960. Reprinted by Springer-Verlag, New York, 1974. ISBN 0-387-90092-6 (Springer-Verlag edition).
External links
- Beginnings of set theory (http://www-groups.dcs.st-and.ac.uk/~history/HistTopics/Beginnings_of_set_theory.html) page at St. Andrews
- Earliest Known Uses of Some of the Words of Mathematics (S) (http://members.aol.com/jeff570/s.html) (at Jeff Miller's website -- recommended)
Footnote
1 Concerning the origin of the term "naive set theory", Jeff Miller [1] (http://members.aol.com/jeff570/s.html) has this to say: "Naïve set theory (contrasting with axiomatic set theory) was used occasionally in the 1940s and became an established term in the 1950s. It appears in Hermann Weyl's review of P. A. Schilpp (ed) The Philosophy of Bertrand Russell in the American Mathematical Monthly, 53., No. 4. (1946), p. 210 and Laszlo Kalmar's review of The Paradox of Kleene and Rosser in Journal of Symbolic Logic, 11, No. 4. (1946), p. 136. (JSTOR)." The term was later popularized by Paul Halmos' book, Naive Set Theory (1960).ca:Teoria de conjunts de:Mengenlehre es:Teoría de conjuntos fr:Théorie naïve des ensembles he:תורת הקבוצות הנאיבית nl:Verzameling pt:Teoria dos conjuntos zh:朴素集合论