Set (mathematics)

From Citizendium, the Citizens' Compendium
Jump to: navigation, search
This article is developing and not approved.
Main Article
Talk
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
 
This editable Main Article is under development and not meant to be cited; by editing it you can help to improve it towards a future approved, citable version. These unapproved articles are subject to a disclaimer.

Informally, a set is thought of as any collection of distinct elements. They may be defined in two ways: by enumeration of their members (a definition by extension), for example by identifying a room of students by listing their names, or by a defining property (a definition by intension), for example, by speaking of the set of all students in Room 101.[1]

Sets are axiomatized and investigated in general by a branch of mathematics known as set theory. In particular, set theory studies what conditions must apply to a defining property in order that the elements with that property in fact form a set. (Some choices of property lead to paradoxes,[2] and this topic still is not fully resolved.) The very existence of various sets introduced below is addressed by set theory, for example by the Zermelo-Fraenkel axioms.[3]

Introduction

The basic property of sets is that they are solely determined by the elements they contain (this is called extensionality). Thus, we can identify sets by listing their elements. For instance, we can talk about the set that has as its elements the numbers 1, 2 and 3. This set is denoted {1, 2, 3}.

A consequence of this basic property is that a set cannot contain an element twice. The set {1, 2, 2, 3} contains the elements 1, 2 and 3 and is thus the same as the set {1, 2, 3}. This is the difference between sets and multisets; when considered as multisets, {1, 2, 2, 3} and {1, 2, 3} are taken as different.

Because only the members matter, the order in which the elements are listed does not matter. The sets {1, 2, 3} and {3, 2, 1} have the same elements and thus these two sets are equal. However, there are many contexts in which we want to consider structures that have elements in a certain order and these elements may be the same. Such a structure is called a tuple or a sequence or an ordered set. The tuple containing the elements 1, 2 and 3 (in that order) is different from the tuple containing the elements 3, 2 and 1. These tuples are denotes (1, 2, 3) and (3, 2, 1) respectively, with round brackets (or angle brackets) instead of curly brackets to emphasize the difference between tuples and sets.

Despite the intuitive definition, a set is usually not defined formally in terms of other mathematical objects; rather it is defined by the laws (called axioms) that is satisfies. For instance, one commonly requires that no set may be an element of itself. Because sets are defined by themselves, they are fundamental structures in mathematics and logic. Mathematicians have found ways to define many mathematical objects, such as the real numbers, in terms of sets.

The number of elements that a set contains does not have to be finite. Sets that contain a finite number of elements are called finite sets. Sets that contain an infinite number of elements are called infinite sets. The number of elements that a finite set contains is called that set's cardinality. The concept of cardinality can also be applied to infinite sets, though the concept is less intuitive, and relies upon bijections between sets.

Notation and terminology

Some sets can be denoted by a list of objects separated with commas, enclosed with curly brackets. As mentioned before, {1, 2, 3} is the set of the numbers 1, 2, and 3. We say that 1, 2, and 3 are its members or its elements. The set with no elements at all is called the empty set, denoted by ∅ = { }.

There are many other ways to write out sets. For example,

A = {x | 1 < x < 10, x is a natural number}

can be read as follows: A is the set of all x, where x is between 1 and 10, and x is a natural number. A could also be written as:

A = {2, 3, 4, 5, 6, 7, 8, 9}

Membership in a set is expressed with the ∈ symbol. To say that the set A contains the 2 as an element (or that 2 is an element of A), we write

2 ∈ A

The cardinality of a set is expressed by placing bars around the name of the set. For example, one would express the cardinality of the above set as such:

|A| = 8

Subsets

A set A is a subset of another set B if each element of A is an element of B. One says "A is contained in B" and writes AB, alternatively that "B contains A" or BA. If AB and BA, then A = B. Set A is a proper subset of set B if AB and AB. Sometimes, for emphasis, the notation AB is used when the possibility that A=B is allowed, and AB is reserved for the case when A=B is excluded.[4] If A is a subset of B, then B is a superset of A.

Set of sets

A set whose elements are also sets is called a set of sets. An important example is the set called the power set, a set whose elements consist of all the subsets of a set. (It may be observed for a set that is not expressed in the form of an explicit list of all its elements, there may be some complexity in discussing its subsets.) If A is a set, the power set of A often is denoted as ℘(A) or P(A) or .

One might simplemindedly imagine labeling some individual subset of A as Ai with some index i from an index set I, and then referring to the collection of these subsets {Ai|i∈I} as a family of subsets of A. In a more elaborate formulation of this notion, one defines a family of subsets in terms of the set of all subsets of A, ℘(A), and a labeling scheme for designating each of the subsets in ℘(A) as Ai with some iI, using a mapping function f, itself called the family. Then the set {Ai} is called a family of subsets of A, and of course, depends upon the labeling family function f.[5]

A famous letter from Cantor to Dedekind in 1899 pointed out that the notion of a "set of all sets" leads to a contradiction (it cannot include its own power set).[6] Some sets include themselves (so-called impredicative definitions), and some do not: The set of all ideas is an idea. The set of all wikis is not a wiki. Impredicative definitions underlie paradoxes.

Union, intersection, difference

(PD) Image: John R. Brews
Set A is the interior of the blue circle (left), set B is the interior of the red circle (right). The sets designated on the left are colored orange.

The union or sum of two sets A and B, written A B, is the set with elements that appear in A or B or both. That is:

The intersection or product of A and B, written AB is the set with elements that appear in both set A and in set B. That is:

The difference of two sets A and B, written AB, is the set with elements of A that are not elements of B. It also is called the relative complement of B in set A. That is:

The absolute complement of A, denoted ~A, is the set of all elements not contained in A:

which suggests there exists a broader universal set U that includes A and all other sets under discussion. Evidently it holds that:

These notions are visualized in the Venn diagram of the figure, in which the circles represent subsets A and B of the universal set U, the rectangle.[7] It is usual to consider the rims of the circles as containing no points of their own, but simply identifying the separation of the sets A and B from not A (~A) and not B (~B). If the rims are considered to have points of their own, minutiae of interpretation are introduced, as discussed in a footnote below.[8]

The union and the intersection are commutative, that is:

and associative:

Two sets A and B are said to be disjoint if AB = ∅. Also of interest are the absorption law:

and the distributive law:

Other relations involving set operations between multiple sets A, B, C ... are known.[9]

Cartesian products

The Cartesian product or direct product of two sets A and B is the set defined by:

This definition can be extended to any number of sets. The couple (a, b) is called an ordered pair, because the order of the two entries is significant, indicating which set the element comes from. The set A × B = ∅ if and only if either A = ∅ or B = ∅.

Mappings or functions

Given two sets A and B, a mapping (or map) also called a function or transformation from A into B, is a rule associating each element of A to an element of B. Common notations for a mapping f are:

where the element aA is associated by the mapping f to an element bB, that is:

and b is called the image of a in B under f. The set A is called the domain of the mapping f, and the subset of B consisting of all the image points is the image (or sometimes range) of f, denoted as the subset of B given by:

The set B to which A is mapped is called the co-domain. Evidently, the image is a subset of the co-domain.

  • If the mapping f : A→B satisfies f(A) = B, then f is surjective; we say f maps A onto B, and the image equals the co-domain.
  • The mapping f is injective (or one-to-one) if a1 ≠ a2 means f(a1) ≠ f(a2) for all a1,a2 ∈ A.
  • A bijective function (or invertible function) is one which is both surjective and injective (onto and one-to-one).

Two functions f and g are equal if they have the same domain A, the same co-domain B, and if f(a) = g(a) for all aA.

Some special sets

Some sets that are ubiquitous in the mathematical literature have special symbols:

Among other such well known sets are the fibonacci numbers, even numbers, odd numbers, quaternions, octonions and the Hamiltonian integers.

Some examples of sets

  • The set consisting of all tuples (a,b), where a is any real number and ditto for b. This set is known as × or 2.
  • The three element set {Red, Yellow, Green}.
  • The set consisting of the two elements Brake, Accelerate.
  • The set consisting of all tuples (a,b) where a is any element in the set {Red, Yellow, Green} and b is any element in the set {Brake, Accelerate}.
  • The set of all functions from the set {Red, Yellow, Green} to the set {Brake, Accelerate}.

References

  1. Bertrand Russell (1920). Introduction to mathematical philosophy, 2nd ed. Allen & Unwin, p. 12. 
  2. For a brief discussion, see Morris Kline (1990). “§2: The paradoxes of set theory”, Mathematical thought from ancient to modern times, Volume 3. Oxford University Press, pp. 1183 ff. ISBN 0195061373. 
  3. For example, see Thomas J. Jech (1978). “Chapter 1: Axioms of set theory - Axioms of Zermelo-Fraenkel”, Set theory. Academic Press, pp. 1 ff. ISBN 0123819504. 
  4. For example see G Shanker Rao (2002). “2.3: Subsets”, Discrete Mathematical Structures. New Age International, pp. 40 ff. ISBN 8122414249. 
  5. See Paul Richard Halmos (1998). “Section 9: Families”, Naive set theory, Reprint of 1960 ed. Springer, pp. 34 ff. ISBN 9780387900926. 
  6. See Edward Craig (1998). “Paradoxes of set and property; §3 Cantor: side-stepping the paradoxes”, Routledge Encyclopedia of Philosophy, Volume 1. Taylor & Francis, p. 215. ISBN 0415073103. 
  7. See, for example, N. Chandrasekaran, M. Umaparvathi. “§1.3.3 Representation by Venn diagrams”, Discrete Mathematics. PHI Learning Pvt. Ltd., p. 11. ISBN 812033938X. 
  8. If we suppose the perimeters of the circles to contain no points, no complication occurs. If, on the other hand, we consider them to have non-zero width, the figure contains four sets (besides the universal set), set A (white) of points interior to the blue circle, set B (also white) of points interior to the red circle, set RimA (blue) and set RimB (red). These sets are not disjoint when the two circles overlap, for example, as they do in the figure. As an instance, in the depicted union AB, the red rim enters the interior of the blue circle. These points in set RimB that are also inside the blue circle are also in set A. They have dual identity, and can be taken either as red or as white points. To make this point, the dual-identity points of the perimeters are shown dashed, with the dashes and spaces colored to represent both identities.
  9. See, for example, John L Kelley (1985). “Chapter 0: Preliminaries”, General topology, 2nd ed. Birkhäuser, pp. 1 ff. ISBN 0387901256. 

Editing note: For guidance in formatting of footnotes as done in this article, see CZ:List-defined references.