Misplaced Pages

This is an old revision of this page, as edited by Paul August (talk | contribs) at 03:39, 20 July 2004 (→Definitions of sets: sp). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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, ${\displaystyle x\in A}$ says, in mathematical notation, that the element ${\displaystyle x}$ belongs to the set ${\displaystyle A}$. See more on terminology and notation below.

Definitions of sets

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.

Infinite sets

Infinite sets are sets which do not have n elements where n is a natural number. Infinite sets have an infinite number of elements, giving them a special property. The special property of infinite sets which makes them inherently different from finite sets is that you can remove n elements from infinite sets and the set that remains will have the same cardinality as before. For instance if you remove the numbers 1 to 1 million from the set of the natural numbers the set that remains will have the same cardinality as the set of the natural numbers. This is obviously not the case for finite sets, for if you remove n elements from a finite set the cardinality of that set will be reduced by n.

Intuitively one might think that the cardinalities of all infinite sets are equal. However, this is not the case. See below in this article, Cantor's theorem and Cantor's diagonal argument for more information on this topic.

Also, 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 ${\displaystyle A}$ and ${\displaystyle B}$ are sets and every ${\displaystyle x}$ in ${\displaystyle A}$ is also contained in ${\displaystyle B}$, then ${\displaystyle A}$ is said to be a subset of ${\displaystyle B}$, denoted ${\displaystyle A\subseteq B}$. Note that this includes the case where A=B. If at least one element in ${\displaystyle B}$ is not also in ${\displaystyle A}$, ${\displaystyle A}$ is called a proper subset of ${\displaystyle B}$, denoted ${\displaystyle A\subset B}$. Every set has as subsets itself, called the improper subset, and the empty set {} or ${\displaystyle \emptyset }$. The fact that an element ${\displaystyle x}$ belongs to the set ${\displaystyle A}$ is denoted ${\displaystyle x\in A}$.

The union of a collection of sets ${\displaystyle S={S_{1},S_{2},S_{3},\cdots }}$ is the set of all elements contained in at least one of the sets ${\displaystyle S_{1},S_{2},S_{3},\cdots }$

The intersection of a collection of sets ${\displaystyle T={T_{1},T_{2},T_{3},\cdots }}$ is the set of all elements contained in all of the sets.

These unions and intersections are denoted

${\displaystyle S_{1}\cup S_{2}\cup S_{3}\cup \cdots }$

and

${\displaystyle T_{1}\cap T_{2}\cap T_{3}\cap \cdots }$

respectively.

The set of all subsets of ${\displaystyle X}$ is called its power set and is denoted ${\displaystyle 2^{X}}$ or ${\displaystyle 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 ${\displaystyle |A|}$ for a set ${\displaystyle A}$ (for a finite set this is an ordinary number, for an infinite set it differentiates between different "degrees of infiniteness", named ${\displaystyle \aleph _{0}}$ (aleph zero), ${\displaystyle \aleph _{1},\aleph _{2}...}$).

The set of functions from a set A to a set B is sometimes denoted by B. 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

${\displaystyle A\times B=\{(a,b):a\in A{\mbox{ and }}b\in B\}}$

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

A+B = A&times{0} ${\displaystyle \cup }$ B&times{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 (${\displaystyle \mathbb {N} }$) often represents this set.
2. Integers appear as solutions for x in equations like x + a = b. A blackboard bold capital Z (${\displaystyle \mathbb {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 (${\displaystyle \mathbb {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 (${\displaystyle \mathbb {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 (${\displaystyle \mathbb {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 (${\displaystyle \mathbb {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-Fränkel axioms, whether or not the axiom of regularity is included) 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:

· · · ${\displaystyle \in x2\in x1\in x0}$

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 variants of ZFC without the axiom of regularity, the possibility of non-well-founded sets arises. When working in such a system, a set that is not necessarily well-founded is called a hyperset. Clearly, if A ∈ A, then A is a non-well-founded 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 hypersets 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 hyperset domain 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.

• Mathematics
• Set theory