Set (mathematics)

In mathematics, a set is a collection of different^[1] things;^[2]^[3]^[4] these things are called elements or members of the set and are typically mathematical objects of any kind: numbers, symbols, points in space, lines, other geometrical shapes, variables, or even other sets.^[5] A set may have a finite number of elements or be an infinite set. There is a unique set with no elements, called the empty set; a set with a single element is a singleton.

This article is about what mathematicians call "intuitive" or "naive" set theory. For a more detailed account, see Naive set theory. For a rigorous modern axiomatic treatment of sets, see Set theory.

Sets are uniquely characterized by their elements; this means that two sets that have precisely the same elements are equal (they are the same set).^[6] This property is called extensionality. In particular, this implies that there is only one empty set.

Sets are ubiquitous in modern mathematics. Indeed, set theory, more specifically Zermelo–Fraenkel set theory, has been the standard way to provide rigorous foundations for all branches of mathematics since the first half of the 20th century.^[5]

An uses a rule to determine membership. Semantic definitions and definitions using set-builder notation are examples.

intensional definition

An describes a set by listing all its elements.^[19] Such definitions are also called enumerative.

extensional definition

An is one that describes a set by giving examples of elements; a roster involving an ellipsis would be an example.

ostensive definition

The set of all humans is a proper subset of the set of all mammals.

{1, 3} ⊂ {1, 2, 3, 4}.

{1, 2, 3, 4} ⊆ {1, 2, 3, 4}.

If every element of set A is also in B, then A is described as being a subset of B, or contained in B, written A ⊆ B,^[31] or B ⊇ A.^[32] The latter notation may be read B contains A, B includes A, or B is a superset of A. The relationship between sets established by ⊆ is called inclusion or containment. Two sets are equal if they contain each other: A ⊆ B and B ⊆ A is equivalent to A = B.^[20]

If A is a subset of B, but A is not equal to B, then A is called a proper subset of B. This can be written A ⊊ B. Likewise, B ⊋ A means B is a proper superset of A, i.e. B contains A, and is not equal to A.

A third pair of operators ⊂ and ⊃ are used differently by different authors: some authors use A ⊂ B and B ⊃ A to mean A is any subset of B (and not necessarily a proper subset),^[33]^[24] while others reserve A ⊂ B and B ⊃ A for cases where A is a proper subset of B.^[31]

Examples:

The empty set is a subset of every set,^[26] and every set is a subset of itself:^[33]

$\mathbf {N}$ or $\mathbb {N}$ , the set of all : $\mathbf {N} =\{0,1,2,3,...\}$ (often, authors exclude $0$ );^[34]

natural numbers

$\mathbf {Z}$ or $\mathbb {Z}$ , the set of all (whether positive, negative or zero): $\mathbf {Z} =\{...,-2,-1,0,1,2,3,...\}$ ;^[34]

integers

$\mathbf {Q}$ or $\mathbb {Q}$ , the set of all (that is, the set of all proper and improper fractions): $\mathbf {Q} =\left\{{\frac {a}{b}}\mid a,b\in \mathbf {Z} ,b\neq 0\right\}$ . For example, $- 7 / 4 \in Q$ and $5 = 5 / 1 \in Q$ ;^[34]

rational numbers

$\mathbf {R}$ or $\mathbb {R}$ , the set of all , including all rational numbers and all irrational numbers (which include algebraic numbers such as ${\sqrt {2}}$ that cannot be rewritten as fractions, as well as transcendental numbers such as $π$ and $e$ );^[34]

real numbers

$\mathbf {C}$ or $\mathbb {C}$ , the set of all : $C = {a + bi | a, b \in R}$ , for example, $1 + 2 i \in C$ .^[34]

complex numbers

There are sets of such mathematical importance, to which mathematicians refer so frequently, that they have acquired special names and notational conventions to identify them.

Many of these important sets are represented in mathematical texts using bold (e.g. $\mathbf {Z}$ ) or blackboard bold (e.g. $\mathbb {Z}$ ) typeface.^[34] These include

Each of the above sets of numbers has an infinite number of elements. Each is a subset of the sets listed below it.

Sets of positive or negative numbers are sometimes denoted by superscript plus and minus signs, respectively. For example, $\mathbf {Q} ^{+}$ represents the set of positive rational numbers.

(or one-to-one) if it maps any two different elements of $A$ to different elements of $B$ ,

injective

(or onto) if for every element of $B$ , there is at least one element of $A$ that maps to it, and

surjective

(or a one-to-one correspondence) if the function is both injective and surjective — in this case, each element of $A$ is paired with a unique element of $B$ , and each element of $B$ is paired with a unique element of $A$ , so that there are no unpaired elements.

bijective

A function (or mapping) from a set $A$ to a set $B$ is a rule that assigns to each "input" element of $A$ an "output" that is an element of $B$ ; more formally, a function is a special kind of relation, one that relates each element of $A$ to exactly one element of $B$ . A function is called

An injective function is called an injection, a surjective function is called a surjection, and a bijective function is called a bijection or one-to-one correspondence.

The of $A$ is the set of all elements (of $U$ ) that do not belong to $A$ . It may be denoted $A c$ or $A'$ . In set-builder notation, $A^{\text{c}}=\{a\in U:a\notin A\}$ . The complement may also be called the absolute complement to distinguish it from the relative complement below. Example: If the universal set is taken to be the set of integers, then the complement of the set of even integers is the set of odd integers.

complement

Suppose that a universal set $U$ (a set containing all elements being discussed) has been fixed, and that $A$ is a subset of $U$ .

Given any two sets $A$ and $B$ ,

Examples:

The operations above satisfy many identities. For example, one of De Morgan's laws states that $(A \cup B)' = A' \cap B'$ (that is, the elements outside the union of $A$ and $B$ are the elements that are outside $A$ and outside $B$ ).

The cardinality of $A \times B$ is the product of the cardinalities of $A$ and $B$ . (This is an elementary fact when $A$ and $B$ are finite. When one or both are infinite, multiplication of cardinal numbers is defined to make this true.)

The power set of any set becomes a Boolean ring with symmetric difference as the addition of the ring and intersection as the multiplication of the ring.

Applications[edit]

Sets are ubiquitous in modern mathematics. For example, structures in abstract algebra, such as groups, fields and rings, are sets closed under one or more operations.

One of the main applications of naive set theory is in the construction of relations. A relation from a domain $A$ to a codomain $B$ is a subset of the Cartesian product $A \times B$ . For example, considering the set $S = {rock, paper, scissors}$ of shapes in the game of the same name, the relation "beats" from $S$ to $S$ is the set $B = {(scissors,paper), (paper,rock), (rock,scissors)}$ ; thus $x$ beats $y$ in the game if the pair $(x, y)$ is a member of $B$ . Another example is the set $F$ of all pairs $(x, x 2)$ , where $x$ is real. This relation is a subset of $R \times R$ , because the set of all squares is subset of the set of all real numbers. Since for every $x$ in $R$ , one and only one pair $(x,...)$ is found in $F$ , it is called a function. In functional notation, this relation can be written as $F (x) = x 2$ .

shows that the "set of all sets that do not contain themselves", i.e., {x | x is a set and x ∉ x}, cannot exist.

Russell's paradox

shows that "the set of all sets" cannot exist.

Cantor's paradox

(1979). Georg Cantor: His Mathematics and Philosophy of the Infinite. Boston: Harvard University Press. ISBN 0-691-02447-2.

Dauben, Joseph W.

(1960). Naive Set Theory. Princeton, N.J.: Van Nostrand. ISBN 0-387-90092-6.

Halmos, Paul R.

Stoll, Robert R. (1979). Set Theory and Logic. Mineola, N.Y.: . ISBN 0-486-63829-4.

Dover Publications

Velleman, Daniel (2006). How To Prove It: A Structured Approach. . ISBN 0-521-67599-5.

Cambridge University Press

The dictionary definition of set at Wiktionary

(in German)