Set

This article is about sets in mathematics. For other meanings, see Set (disambiguation).

The concept of sets, first set forth rigorously by the mathematician Georg Cantor who in the nineteenth century developed set theory, one of the central unifying ideas of mathematics, has been since the late twentieth century included in the mathematics curriculum at the elementary school level. Loosely defined, a set is a collection of objects called elements, for example, a flock of birds, a school of fish, a murder of crows, etc.

Ways of describing a set

A set may be described by words, for example, "the counties in the San Luis Valley of Colorado" or "all even numbers between 1 and 191". Another way to describe a set is by listing the elements, {Alamosa, Conejos, Costilla, Mineral, Rio Grande, Saguache} or {2, 4, 6,..., 188, 190}. When a list is long, it is customary notation to list the first three elements followed by three dots then the last two elements. In customary mathematical notation sets are named using uppercase letters; elements of sets are denoted by lowercase letters. For example,   says, in mathematical notation, that the element x belongs to the set A. See more on terminology and notation below.

Definition

In mathematics, a set is a collection of elements such that two sets are equal if, and only if, every element of one is also an element of the other. It does not matter in what order, or how many times, the elements are listed in the collection.

By contrast, a collection of elements in which multiplicity but not order is relevant is called a multiset. Other related concepts are described below.

If a set has n elements, where n is a natural number (possibly 0), then the set is said to be a finite set with cardinality n; otherwise it is said to be an infinite set. However, another definition of an infinite set is as follows. An infinite set is a set where you can remove n elements and the set will still have the same cardinality(size) as before you removed n elements. For instance, if you remove all the numbers from 1 to 1 million from the set of the naturals, the set will still have the same cardinality compared to the original set of naturals. This is not the case for finite sets, of course. Removal of n elements from a finite set will decrease its cardinality by n. Since all empty sets (i.e., sets with no elements) are equal to each other, it is permissible to speak of a set with no elements as the empty set.

For a discussion of the properties and axioms concerning the construction of sets, see the articles on naïve set theory and axiomatic set theory. Here we give only a brief overview of the concept.

Introduction

Sets are one of the basic concepts of mathematics. A set is, more or less, just a collection of entities, called its elements. Standard notation uses braces around the list of elements, as in:

{red, green, blue}

{red, red, blue, red, green, red, red, green, red, red, blue}

{x : x is an additive primary color}

All three lines above denote the same set. As you see, it is possible to describe one and the same set in different ways: either by listing all its elements (best for small finite sets) or by giving a defining property of all its elements.

Set terminology

If A and B are sets and every x in A is also contained in B, then A is said to be a subset of B, denoted  . Note that this includes the case where A=B. If at least one element in B is not also in A, A is called a proper subset of B, denoted  . Every set has as subsets itself, called the improper subset, and the empty set {} or  . The fact that an element x belongs to the set A is denoted  .

The union of a collection of sets   is the set of all elements contained in at least one of the sets  

The intersection of a collection of sets   is the set of all elements contained in all of the sets.

These unions and intersections are denoted

and

respectively.

The set of all subsets of X is called its power set and is denoted 2^X or P(X). This power set is a Boolean algebra under the operations of union and intersection.

If there is a one-to-one correspondence between the elements of two sets, the two sets are said to have the same cardinality. Cantor’s theorem. states that the cardinality of the power set of a set A is strictly greater than the cardinality of A itself.

The ‘number of elements’ in a certain set is called the cardinal number of the set and denoted | A | for a set A (for a finite set this is an ordinary number, for an infinite set it differentiates between different "degrees of infiniteness", named   (aleph zero),  ).

The set of functions from a set A to a set B is sometimes denoted by B^A. It is a generalisation of the power set in which 2 could be regarded as the set {0,1} (see natural number).

The cartesian product of two sets A and B is the set of ordered pairs

The sum or disjoint union of two sets A and B is the set

A+B = A×{0}   B×{1}.

Examples of sets of numbers

Note: In this section, a, b, and c are natural numbers, and r and s are real numbers.

1. Natural numbers are used for counting. A blackboard bold capital N ( ) often represents this set.
2. Integers appear as solutions for x in equations like x + a = b. A blackboard bold capital Z ( ) often represents this set (for the German Zahlen, meaning numbers, because I is used for the set of imaginary numbers).
3. Rational numbers appear as solutions to equations like a + bx = c. A blackboard bold capital Q ( ) often represents this set (for quotient, because R is used for the set of real numbers).
4. 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 ( ) or a Q with an overline often represents this set.
5. Real numbers include the algebraic numbers as well as the transcendental numbers, which can’t appear as solutions to polynomial equations with rational coefficents. A blackboard bold capital R ( ) often represents this set.
6. Imaginary numbers appear as solutions to equations such as x² + r = 0 where r > 0.
7. 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 ( ) often represents this set.

Special remarks about terminology

Care must be taken with verbal descriptions of sets. One can describe in words a set whose existence is paradoxical. If one assumes such a set exists, an apparent paradox or antinomy may occur. Axiomatic set theory was created to avoid these problems.

For example, suppose we call a set well-behaved if it doesn't contain itself as an element. Now consider the set S of all well-behaved sets. Is S itself well-behaved? There is no consistent answer; this is Russell’s paradox.

In axiomatic set theory, the set S is either not allowed (in the case of the Zermelo-Frankel axioms) or is considered to be a proper class (in the case of the von Neumann-Bernays-Gödel axioms), and we have no paradox.

Well-foundedness

In 1917, Dmitry Mirimanov (also spelled Mirimanoff) introduced the concept of well-foundedness:

a set, x0, is well-founded iff it has no infinite descending membership sequence:

· · ·  

In Zermelo-Fraenkel set theory (ZFC), there is no infinite descending ∈-sequence by the axiom of regularity. A proof is given here. In fact, the axiom of regularity is often called the foundation axiom since it can be proved within ZFC- (that is, ZFC without the axiom of regularity) that well-foundedness implies regularity.

Hypersets

In ZFC without the axiom of regularity, the possibility of non-well-founded sets arises. Such sets, if they exist, are also called hypersets. Clearly, if A ∈ A, then A is a hyperset.

In 1988, Peter Aczel published an influential work, Non-Well-Founded Sets. The theory of hypersets has been applied in computer science (process algebra and final semantics), linguistics (situation theory), and philosophy (work on the Liar Paradox).

Three distinct anti-foundation axioms are well-known:

1. AFA (‘Anti-Foundation Axiom’) — due to M. Forti and F. Honsell;
2. FAFA (‘Finsler’s AFA’) — due to P. Finsler;
3. SAFA (‘Scott’s AFA’) — due to Dana Scott.

The first of these, AFA, is based on accessible pointed graphs (apg) and states that two sets are equal if and only if they can be pictured by the same apg. Within this framework, it can be shown that the so-called Quine atom, formally defined by Q={Q}, exists and is unique.

It is worth emphasizing that hyperset theory is an extension of classical set theory rather than a replacement: the well-founded sets within a domain in which hypersets also exist conform to classical set theory.

Related concepts

In mathematics, the general term for an indexed collection of elements is family. A well-known example of a family is a sequence.

In computer science:

• a list is a data structure closely corresponds to sequences and which is often used to represent sets;
• a bag is a finite multiset.