Also found in: Dictionary, Thesaurus, Medical, Legal, Financial, Wikipedia.
the study of the general properties of sets (mainly, of infinite sets). The concept of a set, or aggregate, is one of the simplest mathematical concepts. The concept is not defined, but it can be clarified by means of examples. Thus we may speak of the set of all books in a given library, the set of all points on a given line, and the set of all solutions of a given equation; the books in the library, the points on the line, and the solutions of the equation are the elements of the corresponding sets. To define a set, it is sufficient to indicate the characteristic property of its elements, that is, the property of all the elements of this set and only these elements. It may happen that no object possesses a given property. It is then said that this property defines the empty set. We write x ∊ M (read: x belongs to the set M) to indicate that a given object jc is an element of a set M.
Subsets. If every element of a set A is also an element of a set B, then A is said to be a subset, or part, of B. We write A ⊆ B or B ⊇ A. In particular, B is itself a subset of B. The empty set is defined to be a subset of every set. Every nonempty subset A of a given set B, other than B, is said to be a proper subset of B.
Cardinality of sets. The first problem that arose in treating infinite sets was whether it was possible to compare them quantitatively. The answer to this and similar problems was given in the late 1870’s by G. Cantor, who laid the foundations of set theory as a mathematical science. The possibility of a comparative quantitative estimate of sets is based on the concept of a one-to-one correspondence between two sets. Suppose that some rule or law associates to every element of a set A a definite element of B. If every element of B turns out to correspond to one and only one element of A, then we say that a one-to-one correspondence has been established between A and B. Clearly, a one-to-one correspondence can be established between two finite sets if and only if they have the same number of elements. As a generalization of this fact, the quantitative equivalence of two infinite sets is defined as the possibility of establishing a one-to-one correspondence between the sets.
Even before the creation of set theory, B. Bolzano had precisely formulated the concept of a one-to-one correspondence. Also, Bolzano had no doubts about the the existence of infinities of different orders. However, not only did he not make the concept of a one-to-one correspondence the basis for establishing the quantitative equivalence of sets, but he absolutely opposed it. Bolzano balked at putting an infinite set in one-to-one correspondence with a proper subset of itself. (For example, if we associate to each natural number n the number 2n, then we obtain a one-to-one correspondence between the set of all natural numbers and the set of all even natural numbers.) Rather than use infinite sets and reject the axiom that the part is less than the whole, Bolzano abandoned one-to-one correspondence as a criterion for the equivalence of sets, and thus remained outside the mainstream of the development of set theory. It is easy to prove that every infinite set M contains a proper subset equivalent to M, whereas no such proper subset can be found in any finite set. Therefore, the existence of a proper subset equivalent to the entire set can be taken as a definition of an infinite set (J. Dedekind).
Only three cases are possible for two infinite sets A and B: (1) a proper subset of A is equivalent to B, but no proper subset of B is equivalent to A or, (2) conversely, a proper subset of B is equivalent to A but no proper subset of A is equivalent to B, or, finally, (3) a proper subset of A is equivalent to B and a proper subset of B is equivalent to A. It has been proved that in the last case A and B are equivalent (the Cantor-Bernstein theorem). In the first case we say that the cardinality of A is greater than the cardinality of B; in the second case we say that the cardinality of B is greater than that of A. The a priori possible fourth case —that no proper subset of A is equivalent to B and no proper subset of B is equivalent to A —cannot occur (for infinite sets).
The importance of the concept of the cardinality of a set lies in the existence of nonequivalent infinite sets. For example, the set of all subsets of a given set M has cardinality greater than M A set equivalent to the set of all natural numbers is said to be a countable set. The cardinality of countable sets is the smallest cardinality that an infinite set can have. Every infinite set contains a countable proper subset. Cantor proved that the set of all rational numbers and even of all algebraic numbers is countable, whereas the set of all real numbers is uncountable. This was a new proof of the existence of transcendental numbers, that is, real numbers that are not roots of an algebraic equation with integral coefficients (and even of the uncountability of the set of these numbers). The cardinality of the set of all real numbers is said to be the cardinality of the continuum. The set of all subsets of a countable set, the set of all complex numbers, and, consequently, the set of all points in the plane, the set of all points in three- and, more generally, in n -dimensional space for any n are all equivalent to the set of all real numbers. Cantor advanced the hypothesis (called the continuum hypothesis) that every set consisting of real numbers is finite, countable, or equivalent to the set of all real numbers. For the hypothesis and important related results seeCONTINUUM PROBLEM.
Mappings of sets. In set theory the analytic concept of a function and the geometric concept of a mapping or transformation of a figure are combined into the general concept of a mapping of one set into another. Suppose two sets X and Y are given and let us associate to every element x ∊ X an element y = f(x) of set Y. Then we say that there exists a mapping of X into Y, or that there exists a function with inputs x in X and outputs y in Y. For every x ∊ X, the element y = f(x) of Y is said to be the image of x under/or the value of/for a given value of its argument jc.
EXAMPLES. (1) Suppose a square with vertices (0,0), (0,1), (1,0), and (1, 1) is given in a plane with rectangular coordinate system. Project the square on, say, the x-axis. This projection is a mapping of the set X of all points of the square onto the set Y of all points of its base. The image of a point (x, y) is the point(x, 0).
(2) Suppose X is the set of real numbers. The correspondence y = f(x) = x3, x ∊ X, is a mapping of X onto itself.
(3) Suppose X is the set of all real numbers. The correspondence y = f(x) = arc tan x, x ∊ X, is a mapping of X onto the interval (-π/2, π/2).
A one-to-one correspondence between sets X and Y is a map-ping of X into y such that every element of Y is the image of one and only one element of X. The mappings in examples (2) and (3) are one-to-one, while that in (1) is not one-to-one.
Operations on sets. The sum, or union, of two, three, or, in general, an arbitrary finite or infinite collection of sets is the set of all objects each of which is an element of at least one of the given constituent sets. The intersection of two, three, or, in general, any finite or infinite collection of sets is the set of all the elements common to all the given sets. The intersection of even two nonempty sets can be empty. The difference between a set B and a set A is the set of all elements of B that are not elements of A. The difference between a set B and its subset A is said to be the complement of A in B.
The operations of addition and intersection of sets satisfy associative and commutative laws. Moreover, the operation of intersection is distributive with respect to addition and subtraction. The result of applying these operations to subsets of a set M is a subset of M. This is not true of the Cartesian product of sets and of the operation of “raising to a power.” The Cartesian product X × Y of sets X and Y is the set of all pairs (x, y), x ∈ and y ∊ Y, and Yx, Y raised to the power X, is the set of all mappings of X into Y. It is possible to define the Cartesian product of any collection of sets so that when the factors coincide it becomes the operation of raising to a power. If £ and r\ are the cardinalities of X and Y, then ξ ⋅ η ηξ and rf are defined as the cardinalities of the sets X × Fand Yx, respectively, which in the case of finite sets agrees with multiplication and raising to a power of natural numbers. The sum of cardinal numbers ξ and η is defined as the cardinal number of the sum of pairwise disjoint sets whose cardinal numbers are ξ and η.
Ordered sets. A set X is said to be ordered if for some pairs x1, x2 of elements of X there is defined a transitive rule of precedence (succession), expressed as “the element x1 precedes the element x2, x1 < x2,” or, “the element x1 is followed by the element x2, x2 > x1” The transitivity condition means that if x < x1 and x1 < x2, then x < x2 A set with an order relation is said to be “partially ordered.” Sometimes, we speak of an “ordered set” instead of a “partially ordered set” (Bourbaki). However, an ordered set is usually a partially ordered set in which the ordering satisfies the following additional (”linear ordering”) requirements: (1) no element precedes itself, and (2) for any two different elements x and x\t one precedes the other, that is, either x1 < x1 or x1 < x.
EXAMPLES. (1) Every set M whose elements are sets x is “partially ordered ’by inclusion’”: x < x1 if x ⊂ x1.
(2) Any set of functions f defined on the number line is partially ordered if we set f1 < f2 if and only if f2(x) ≦= f2(x) for every real number x.
(3) Every set of real numbers is linearly ordered; the smaller of two numbers is assumed to precede the larger.
Two ordered sets are said to be similar, or to be of the same ordinal type, if an order-preserving one-to-one correspondence can be established between them. An element of an ordered set is said to be the first element if it precedes all the remaining elements in this ordered set. The last element is similarly defined. Examples include the following. In the ordered set of all real numbers, there is neither a first nor a last element; in the ordered set of all nonnegative numbers, zero is the first element, while no last element exists; in the ordered set of all real numbers x satisfying the inequalities a ≦ x ≦ b, the number a is the first element and b is the last element.
An ordered set is said to be well-ordered if it, and each of its proper subsets, has a first element. The ordinal types of well-ordered sets are called ordinal numbers. If a well-ordered set is finite, then its ordinal number is the usual ordinal number of elementary arithmetic. The ordinal types of infinite well-ordered sets are called transfinite numbers.
Point sets. Point set theory—that is, in the original sense of the word, the theory of sets whose elements are real numbers (points of the number line) as well as points of two- , three- , and, in general n -dimensional space—was founded by Cantor, who established the concept of a limit point of a set and such related concepts as a closed set. Further development of point set theory led to the concepts of metric space and topological space; these spaces are studied in general topology.
Descriptive set theory is a highly self-contained discipline. Founded by the French mathematicians R. Baire (L. R. Baire) and H. Lebesgue in the course of classifying discontinuous functions (1905), descriptive set theory began with the study and classification of Borel sets (5-sets). Borel sets are defined as sets that can be constructed, starting from closed sets, by applying the operations of addition and intersection in any order, but each time to a finite or countable number of sets. Lebesgue proved that such sets and only such sets can be obtained as point sets in which a real function f(x) that occurs in a Baire classification vanishes or, more generally, satisfies a condition of the form a < f(x) < b.
Further development of descriptive set theory was carried out chiefly by Russian and Polish mathematicians, particularly those of the Moscow school founded by N. N. Luzin (P. S. Aleksandrov, M. la. Suslin, M. A. Lavrent’ev, A. N. Kolmogorov, and P. S. Novikov). Aleksandrov proved a theorem (1916) stating that every uncountable Borel set has the cardinality of the continuum. The apparatus of this proof was used by Suslin to construct the theory of A -sets, which includes 5-sets as a special case; up until then, it had been assumed that ^-sets were, essentially, the only sets that could be encountered in analysis. Suslin showed that the complement M of an /4-set is itself an .4-set if and only if M is a Borel set (the complement of a Borel set is always a Borel set). The ,4-sets turned out to be the continuous images of the set of all irrational numbers. For many years the theory of A -sets remained at the center of descriptive set theory. Then Luzin arrived at a general definition of projective sets, which can be obtained from the set of all irrational numbers by repeated application of the operation of subtraction and continuous mapping. Novikov and others also worked on the theory of /4-sets and projective sets. Descriptive set theory is closely related to investigations on the foundations of mathematics, particularly the effective definability of mathematical objects and the solvability of mathematical problems.
Importance of set theory. Set theory has had a very great effect on the development of modern mathematics. First, set theory has been the foundation for a number of new mathematical disciplines, including the theory of functions of a real variable, general topology, general algebra, and functional analysis. Second, set-theoretic methods are gradually finding greater use in the classical branches of mathematics. Thus, in mathematical analysis, for example, set-theoretic methods are widely used in the qualitative theory of differential equations, the calculus of variations, and probability. Finally, set theory has had a profound effect on the understanding of the very subject of mathematics and of its major branches, such as geometry. By means of set theory it was possible to give a precise definition of the concept of isomorphism between systems of objects connected by relations and to arrive at the insight that every mathematical theory in its pure and abstract form studies a system of objects only “up to isomorphism,” that is, any mathematical theory can be ap-plied without any changes to any system of objects isomorphic to the system that the theory was initially created to study.
In questions on the foundations of mathematics, that is, the rigorous and logically faultless development of mathematical theories, set theory itself requires the justification of the methods of reasoning used in it. Moreover, all the logical difficulties associated with justifying the mathematical theory of infinity become only more acute when we consider them from the point of view of general set theory.
REFERENCESLuzin, N. N. Teoriia funktsii deistviteVnogo peremennogo, 2nd ed. Moscow, 1948.
Aleksandrov, P. S. Vvedenie v obshchuiu teoriiu mnozhestv i funktsii. Moscow-Leningrad, 1948.
Hausdorff, F. Teoriia mnozhestv. Moscow-Leningrad, 1937. (Translated from German.)
P. S. ALEKSANDROV
set theory[′set ‚thē·ə·rē]
Mathematicians began to realise toward the end of the 19th century that just doing "the obvious thing" with sets led to embarrassing paradoxes, the most famous being Russell's Paradox. As a result, they acknowledged the need for a suitable axiomatisation for talking about sets. Numerous such axiomatisations exist; the most popular among ordinary mathematicians is Zermelo Fr?nkel set theory.
The beginnings of set theory.
set theoryThe branch of mathematics or logic that is concerned with sets of objects and rules for their manipulation. UNION, INTERSECT and COMPLEMENT are its three primary operations and they are used in relational databases as follows.
Given a file of Americans and a file of golfers, UNION would create a file of all Americans and golfers. INTERSECT would create a file of American golfers, and COMPLEMENT would create a file of golfers who are not Americans, or of Americans who are not golfers. See fuzzy logic.