Set

This article is about sets in mathematics. See also

• Set (god) for the figure from ancient Egyptian mythology.
• Set game for the card game.
• Set (computer science) as datatype that is a collection of values.
• Set (drama) discusses dramatic sets
• Small appliance discusses appliances such as TV sets
• Musical set theory for tone row

---

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. Since all empty sets are equal to each other, it is permissible to speak of a set with no elements as the empty set.

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. More generally, 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 set of all subsets of a set A is strictly greater than the cardinality of A itself.

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

Table of contents

1 Introduction 2 Set Terminology 3 Examples of Sets of Numbers 4 Special Remarks About Terminology 5 Well-Foundedness 6 Hypersets

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; and it does not matter in what order, or how many times, the elements are listed, if a list is given.

By contrast, a collection of elements in which multiplicity is relevant is called a multiset. In computer science, a finite multiset is called a bag, and a collection of elements in which the order of presentation is relevant is called a list.

Set Terminology

If and are sets and every in is also contained in , then is said to be a subset of , denoted . If at least one element in is not also in , is called a proper subset of , denoted . Every set has as subsets itself, called the improper subset, and the empty set {} or . The fact that an element belongs to the set 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 "number of elements" in a certain set is called the cardinal number of the set and denoted for a set (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 all subsets of is called its power set and is denoted or . This power set is a Boolean algebra under the operations of union and intersection.

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

The sum of two sets A and B is the set

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

Examples of Sets of Numbers

1. Natural numbers which are used for counting the members of sets.
2. Integers which appear as solutions to equations like x + a = b.
3. Rational numbers which appear as solutions to equations like a + bx = c.
4. Algebraic numbers which can appear as solutions to polynomial equations (with integer coefficients) and may involve radicals and certain other irrational numbers.
5. Real numbers which include transcendental numbers (which can't appear as solutions to polynomial equations with rational coefficents) as well as the algebraic numbers.
6. Complex numbers which provide solutions to equations such as x² + 1 = 0.

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-Godel 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 if and only if it has no infinite descending membership sequence:

· · · ∈ x2 ∈ x1 ∈ 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 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, i.e. 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.