Set (mathematics)

This article is about sets themselves. For the branches of mathematics studying sets, see Naive set theory and Set theory. For the category of sets, see Set (category theory).

In mathematics, a set is a collection of different things; the things are called elements or members of the set and are typically mathematical objects: numbers, symbols, points in space, lines, other geometric shapes, variables, functions, or even other sets.

File:Example of a set.svg

A set of polygons in an Euler diagram

File:Example of a set rearranged.svg

This set equals the one above since they have the same elements.

Mathematics typically does not define precisely what constitutes a "set" or "collection", because such a definition would have to be in terms of something else previously defined. Instead, sets serve as foundational objects whose behavior is described by axioms modeled on intuition about collections, and then essentially all other mathematical objects are rigorously defined in terms of sets.

Set theory studies possible axiom systems and their consequences. Since the first half of the 20th century, ZFC (Zermelo–Fraenkel set theory with the axiom of choice) has been the axiom system most commonly used.

Context

Before the end of the 19th century, sets were not studied specifically, and they were not clearly distinguished from sequences. Most mathematicians considered infinity as potential—meaning that it is the result of an endless process—and were reluctant to consider infinite sets. For example, a line was considered not as a set of points, but as a locus where a point may be located.

The mathematical study of infinite sets began with Georg Cantor (1845–1918). This provided some counterintuitive statements and paradoxes. For example, the number line has an infinite number of elements that is strictly larger than the infinite number of natural numbers, and any line segment has the same number of elements as the whole line. Assuming the existence of a set of all sets led to a contradiction, Russell's paradox. This led to the foundational crisis of mathematics, and to proposed resolutions. One of these, Zermelo–Fraenkel set theory, has been generally adopted as a foundation of set theory and all mathematics, though much of mathematics does not require its full power.

Meanwhile, sets started to be widely used in all mathematics. In particular, algebraic structures and mathematical spaces are typically defined in terms of sets. Also, many older mathematical results are restated in terms of sets. For example, Euclid's theorem is often stated as "the set of the prime numbers is infinite". This wide use of sets in mathematics was prophesied by David Hilbert when saying: "No one will drive us from the paradise that Cantor created for us."

The object of this article is to summarize the manipulation rules and properties of sets that are commonly used in mathematics, without reference to a specific logical framework. For the branch of mathematics that studies sets, see Set theory; for an informal presentation of the corresponding logical framework, see Naive set theory; for a more formal presentation, see Axiomatic set theory and Zermelo–Fraenkel set theory.

Basic notions

In mathematics, a set is a collection of different things, called elements or members of the set. A set may also be called a collection or family, especially when its elements are themselves sets; this may avoid confusion between the set and its members. A set may be specified either by listing its elements or by giving a property that characterizes its elements, such as for the set of the prime numbers or the set of all students in a given class.

If Template:Tmath is an element of a set Template:Tmath, one says that Template:Tmath belongs to Template:Tmath or is in Template:Tmath, and one writes Template:Tmath. The statement "Template:Tmath is not in Template:Tmath" is written as Template:Tmath. For example, if Template:Tmath is the set of all integers, then Template:Tmath and Template:Tmath. The axiom of extensionality states that two sets are equal if and only if they have the same elements.

There exists a set with no elements, and extensionality implies that there is only one such set. It is called the empty set (or null set) and is denoted Template:Tmath, Template:Tmath, or Template:Tmath.

A singleton is a set with exactly one element. If Template:Tmath is this element, the singleton is denoted Template:Tmath. The sets Template:Tmath and Template:Tmath are different, because the former has one element (namely, Template:Tmath) and the latter has no elements at all.

A set is finite if there exists a natural number Template:Tmath such that the first Template:Tmath natural numbers can be put in bijection (one-to-one correspondence) with the elements of the set. In this case, one says that Template:Tmath is the number of elements of the set. A set is infinite if such an Template:Tmath does not exist. The empty set is a finite set with Template:Tmath elements.

ℕ ⊊ ℤ ⊊ ℚ ⊊ ℝ

The standard number systems of natural numbers, integers, rational numbers, and real numbers are infinite sets.

The natural numbers form an infinite set, commonly denoted Template:Tmath. Other examples of infinite sets include the integers (Template:Tmath), the rational numbers (Template:Tmath), the real numbers (Template:Tmath), nonzero real vector spaces, curves, and most other mathematical spaces.

Specifying a set

Extensionality implies that to specify a set, it suffices either to list its elements or to provide a property that characterize the set's elements among the elements of a possibly larger set.

Roster notation

Roster or enumeration notation is a notation introduced by Ernst Zermelo in 1908 that specifies a set by listing its elements between braces, separated by commas. For example, one sees that Template:Tmath and Template:Tmath denote sets and not tuples because of the enclosing braces.

The notations Template:Tmath for the empty set and Template:Tmath for a singleton are examples of roster notation.

When specifying a set, all that matters is whether each potential element is in the set or not, so a set does not change if elements are repeated or arranged in a different order. For example, $$\{1,2,3,4\}=\{4,2,1,3\}=\{4,2,4,3,1,3\}.$$

When there is a clear pattern for generating all set elements, one can use an ellipsis to abbreviate the notation; for example, $\{1,2,3,\ldots ,10\}$ is a shorthand for Template:Tmath. Ellipses in roster notation can also be used to describe some infinite sets; for example, the set of all integers can be denoted as $$\{\ldots ,-3,-2,-1,0,1,2,3,\ldots \}$$ or $$\{0,1,-1,2,-2,3,-3,\ldots \}.$$

Set-builder notation

Main article: Set-builder notation

Set-builder notation specifies a set as being the set of all elements that satisfy some logical formula. More precisely, if Template:Tmath is a logical formula depending on a variable Template:Tmath, which evaluates to true or false depending on the value of Template:Tmath, then $$\{x\mid P(x)\}$$ or $$\{x:P(x)\}$$ denotes the set of all Template:Tmath for which Template:Tmath is true. For example, a set Template:Tmath can be specified as follows: $$F=\{n\mid n{\text{ is an integer, and }}0\leq n\leq 19\}.$$ In this notation, the vertical bar "|" is read as "such that", and the whole formula can be read as "Template:Tmath is the set of all Template:Tmath such that Template:Tmath is an integer in the range from 0 to 19 inclusive".

Some logical formulas, such as Template:Tmath or Template:Tmath cannot be used in set-builder notation because there is no set for which the elements are characterized by the formula. There are several ways for avoiding the problem. One may prove that the formula defines a set; this is often almost immediate, but may be very difficult.

One may also introduce a larger set Template:Tmath that must contain all elements of the specified set, and write the notation as $$\{x\mid x\in U{\text{ and ...}}\}$$ or $$\{x\in U\mid {\text{ ...}}\}.$$

One may also define Template:Tmath once for all and take the convention that every variable that appears on the left of the vertical bar of the notation represents an element of Template:Tmath. This amounts to saying that Template:Tmath is implicit in set-builder notation. In this case, Template:Tmath is often called the domain of discourse or a universe.

For example, with the convention that a lower case Latin letter may represent a real number and nothing else, the expression $$\{x\mid x\not \in \mathbb {Q} \}$$ is an abbreviation of $$\{x\in \mathbb {R} \mid x\not \in \mathbb {Q} \},$$ which defines the irrational numbers.

Subsets

Main article: Subset

A subset of a set Template:Tmath is a set Template:Tmath such that every element of Template:Tmath is also an element of Template:Tmath. The following are different ways of expressing the same thing:

• Template:Tmath is a subset of Template:Tmath,
• Template:Tmath,
• Template:Tmath is contained in Template:Tmath,
• Template:Tmath,
• Template:Tmath is a superset of Template:Tmath,
• Template:Tmath contains Template:Tmath,
• Template:Tmath.

The relationship between sets established by ⊆ is called inclusion or containment.

A set Template:Tmath is a proper subset of a set Template:Tmath if Template:Tmath and Template:Tmath; to denote this, one writes Template:Tmath, or Template:Tmath. Likewise, one may write Template:Tmath or Template:Tmath.

The notation Template:Tmath often means Template:Tmath, but some authors use Template:Tmath to mean Template:Tmath. To avoid ambiguity, one can write Template:Tmath or Template:Tmath, depending on what is intended.

Examples

• The set of all humans is a proper subset of the set of all mammals.
• Template:Tmath
• Template:Tmath

Properties of containment

• Two sets are equal if and only if they contain each other: Template:Tmath is equivalent to (Template:Tmath and Template:Tmath).
• The empty set is a subset of every set: Template:Tmath.

Basic operations

There are several standard operations that produce new sets from given sets, analogously to how addition and multiplication produce new numbers from given numbers. The operations that are considered in this section are those such that all elements of the produced sets belong to a previously defined set. These operations are commonly illustrated with Euler diagrams and Venn diagrams.

Intersection

File:Venn0001.svg

The intersection of A and B, denoted A ∩ B

The intersection of two sets Template:Tmath and Template:Tmath is a set denoted Template:Tmath whose elements are those elements that belong to both Template:Tmath and Template:Tmath. That is, $$A\cap B=\{x\mid x\in A\land x\in B\},$$ where Template:Tmath denotes the logical and.

Intersection is associative and commutative; this means that for proceeding a sequence of intersections, one may proceed in any order, without the need of parentheses for specifying the order of operations.

If Template:Tmath is a nonempty set of sets, its intersection, denoted ${\textstyle \bigcap _{A\in {\mathcal {S}}}A,}$ is the set whose elements are those elements that belong to all sets in Template:Tmath. That is, $$\bigcap _{A\in {\mathcal {S}}}A=\{x\mid (\forall A\in {\mathcal {S}})\;x\in A\}.$$ Example: If ${\mathcal {S}}=\{X,Y\}$, then ${\textstyle \bigcap _{A\in {\mathcal {S}}}A=X\cap Y}$.

Union

File:Venn0111.svg

The union of A and B, denoted A ∪ B

The union of two sets Template:Tmath and Template:Tmath is a set denoted Template:Tmath whose elements are those elements that belong to Template:Tmath or Template:Tmath or both. That is, $$A\cup B=\{x\mid x\in A\lor x\in B\},$$ where Template:Tmath denotes the logical or.

Union is associative and commutative.

If Template:Tmath is a set of sets, its union, denoted ${\textstyle \bigcup S=\bigcup _{A\in {\mathcal {S}}}A,}$ is the set whose elements are those elements that belong to at least one set in Template:Tmath. That is, $$\bigcup _{A\in {\mathcal {S}}}A=\{x\mid (\exists A\in {\mathcal {S}})\;x\in A\}.$$ Example: If ${\mathcal {S}}=\{X,Y\}$, then ${\textstyle \bigcup _{A\in {\mathcal {S}}}A=X\cup Y}$.

Set difference

File:Venn0100.svg

The set difference A \ B

The set difference of two sets Template:Tmath and Template:Tmath, is a set, denoted Template:Tmath or Template:Tmath, whose elements are those elements that belong to Template:Tmath, but not to Template:Tmath. That is, $$A\setminus B=\{x\mid x\in A\land x\not \in B\},$$ where Template:Tmath denotes the logical and.

File:Venn1010.svg

The complement of A in U

When Template:Tmath the difference Template:Tmath is also called the complement of Template:Tmath in Template:Tmath. When all sets that are considered are subsets of a fixed universal set Template:Tmath, the complement Template:Tmath is often called the absolute complement of Template:Tmath.

File:Venn0110.svg

The symmetric difference of A and B

The symmetric difference of two sets Template:Tmath and Template:Tmath, denoted Template:Tmath, is the set of those elements that belong to Template:Tmath or Template:Tmath but not to both: $$A\,\Delta \,B=(A\setminus B)\cup (B\setminus A).$$

Algebra of subsets

Main article: Algebra of sets

The set of all subsets of a set Template:Tmath is called the powerset of Template:Tmath, often denoted Template:Tmath. The powerset is an algebraic structure whose main operations are union, intersection, set difference, symmetric difference and absolute complement (complement in Template:Tmath).

The powerset is a Boolean ring that has symmetric difference as addition, intersection as multiplication, the empty set as additive identity, Template:Tmath as multiplicative identity, and the subset itself as the additive inverse.

The powerset is also a Boolean algebra for which the join Template:Tmath is the union Template:Tmath, the meet Template:Tmath is the intersection Template:Tmath, and the negation is the set complement.

As for every Boolean algebra, the powerset is also a partially ordered set for set inclusion. It is also a complete lattice.

The axioms of these structures induce many identities relating subsets, which are detailed in the linked articles.

Functions

Main article: Function (mathematics)

A function Template:Tmath from a set Template:Tmath to a set Template:Tmath is a rule that assigns to each element of Template:Tmath a unique element of Template:Tmath. For example, the square function maps each real number Template:Tmath to Template:Tmath.

The notation Template:Tmath denotes a function Template:Tmath from Template:Tmath to Template:Tmath. The result of applying Template:Tmath to an element Template:Tmath of Template:Tmath is denoted $f(a)$; it is called the value of Template:Tmath at Template:Tmath, or the image of Template:Tmath under Template:Tmath. The set Template:Tmath is called the domain of Template:Tmath, and Template:Tmath is called the codomain of Template:Tmath.

The graph of a function Template:Tmath is the set of all ordered pairs Template:Tmath as Template:Tmath ranges over all elements of Template:Tmath. It is a subset of the Cartesian product Template:Tmath defined below. For example, the graph of the square function is a parabola in Template:Tmath; it contains points such as Template:Tmath and Template:Tmath.

Once the domain and codomain are specified, the graph of Template:Tmath contains the same information as Template:Tmath itself. This point of view allows one to formally define 'function' in terms of sets. Specifically, a function from Template:Tmath to Template:Tmath is a triple Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (A,B,G)} of sets with Template:Tmath such that for every element Template:Tmath in Template:Tmath, there exists a unique element Template:Tmath in Template:Tmath such that Template:Tmath. (For functions from Template:Tmath to Template:Tmath especially, the condition on Template:Tmath is called the vertical line test.)

Indexed families

Intuitively, an indexed family is a set whose elements are labelled with the elements of another set, the index set. These labels allow the same element to occur several times in the family.

Formally, an indexed family is a function that has the index set as its domain. Generally, the usual functional notation Template:Tmath is not used for indexed families. Instead, the element of the index set is written as a subscript of the name of the family, such as in Template:Tmath.

When the index set is Template:Tmath, an indexed family is called an ordered pair. When the index set is the set of the Template:Tmath first natural numbers, an indexed family is called an Template:Tmath-tuple. When the index set is the set of all natural numbers an indexed family is called a sequence.

In all these cases, the natural order of the natural numbers allows omitting indices for explicit indexed families. For example, Template:Tmath denotes the 3-tuple Template:Tmath such that Template:Tmath.

The above notations Template:Tmath and Template:Tmath are commonly replaced with a notation involving indexed families, namely Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \bigcup_{i\in \mathcal I} A_i=\{x\mid (\exists i\in \mathcal I)\; x\in A_i\}} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \bigcap_{i\in \mathcal I} A_i=\{x\mid (\forall i\in \mathcal I)\; x\in A_i\}.}

The formulas of the above sections are special cases of the formulas for indexed families, where Template:Tmath and Template:Tmath. The formulas remain correct, even in the case where Template:Tmath for some Template:Tmath, since Template:Tmath.

External operations

In Template:Alink, all elements of sets produced by set operations belong to previously defined sets. In this section, other set operations are considered, which produce sets whose elements can be outside all previously considered sets. These operations are Cartesian product, disjoint union, set exponentiation and power set.

Cartesian product

Main article: Cartesian product

Given sets Template:Tmath and Template:Tmath, their Cartesian product (or simply product), denoted Template:Tmath, is the set of all ordered pairs Template:Tmath such that Template:Tmath and Template:Tmath; that is, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A\times B = \{(a,b) \mid a\in A \text{ and } b\in B\}.} The definition makes sense even if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A=B} .

One can likewise define Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A \times B \times C} as a set of ordered triples Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (a,b,c)} , and likewise for any finite number of sets.

In fact, the number of sets does not have to be finite. Given any indexed family of sets Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (A_i)_{i \in I}} , the product Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \prod_{i \in I} A_i} is the set of all indexed families of elements Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (a_i)_{i \in I}} such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_i \in A_i} for each Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i \in I} . The axiom of choice implies that any product of nonempty sets is nonempty.

Set exponentiation

Main article: Set exponentiation

Given two sets Template:Tmath and Template:Tmath, the set exponentiation, denoted Template:Tmath, is the set that has as elements all functions from Template:Tmath to Template:Tmath.

Equivalently, Template:Tmath can be viewed as the Cartesian product of a family, indexed by Template:Tmath, of sets that are all equal to Template:Tmath. This explains the terminology and the notation, since exponentiation with integer exponents is a product where all factors are equal to the base.

Power set

Main article: Power set

The power set of a set Template:Tmath is the set that has all subsets of Template:Tmath as elements, including the empty set and Template:Tmath itself. It is often denoted Template:Tmath. For example, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal P(\{1,2,3\})=\{\emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}\}.}

There is a natural one-to-one correspondence (bijection) between the subsets of Template:Tmath and the functions from Template:Tmath to Template:Tmath; this correspondence associates to each subset the function that takes the value Template:Tmath on the subset and Template:Tmath elsewhere. Because of this correspondence, the power set of Template:Tmath is commonly identified with set exponentiation: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal P(E)=\{0,1\}^E.} In this notation, Template:Tmath is often abbreviated as Template:Tmath, which gives Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal P(E)=2^E.} In particular, if Template:Tmath has Template:Tmath elements, then Template:Tmath has Template:Tmath elements.

Disjoint union

Main article: Disjoint union

The disjoint union of two or more sets is similar to the union, but, if two sets have elements in common, these elements are considered as distinct in the disjoint union. This is obtained by labelling the elements by the indexes of the set they are coming from.

The disjoint union of two sets Template:Tmath and Template:Tmath is commonly denoted Template:Tmath and is thus defined as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A\sqcup B=\{(a,i)\mid (i=1 \land a\in A)\lor (i=2 \land a\in B\}.}

If Template:Tmath is a set with Template:Tmath elements, then Template:Tmath has Template:Tmath elements, while Template:Tmath has Template:Tmath elements.

The disjoint union of two sets is a particular case of the disjoint union of an indexed family of sets, which is defined as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \bigsqcup_{i \in \mathcal I}=\{(a,i)\mid i\in \mathcal I \land a\in A_i\}.}

The disjoint union is the coproduct in the category of sets. Therefore the notation Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \coprod_{i \in \mathcal I}=\{(a,i)\mid i\in \mathcal I \land a\in A_i\}} is commonly used.

Internal disjoint union

Given an indexed family of sets Template:Tmath, there is a natural map Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \bigsqcup_{i\in \mathcal I} A_i&\to \bigcup_{i\in \mathcal I} A_i\\ (a,i)&\mapsto a , \end{align}} which consists in "forgetting" the indices.

This map is always surjective; it is bijective if and only if the Template:Tmath are pairwise disjoint, that is, all intersections of two sets of the family are empty. In this case, Template:Tmath and Template:Tmath are commonly identified, and one says that their union is the disjoint union of the members of the family.

If a set is the disjoint union of a family of subsets, one says also that the family is a partition of the set.

Cardinality

Main articles: Cardinality and Cardinal number

Informally, the cardinality of a set Template:Tmath, often denoted Template:Tmath, is the number of its members. This number is the natural number Template:Tmath when there is a bijection between the set that is considered and the set Template:Tmath of the first Template:Tmath natural numbers. The cardinality of the empty set is Template:Tmath. A set with the cardinality of a natural number is called a finite set, which applies in both cases. Otherwise, one has an infinite set.

The fact that natural numbers measure the cardinality of finite sets is the basis of the concept of natural number, and predates for several thousands years the concept of sets. A large part of combinatorics is devoted to the computation or estimation of the cardinality of finite sets.

Infinite cardinalities

The cardinality of an infinite set is commonly represented by a cardinal number, exactly as the number of elements of a finite set is represented by a natural numbers. The definition of cardinal numbers is too technical for this article; however, many properties of cardinalities can be dealt without referring to cardinal numbers, as follows.

Two sets Template:Tmath and Template:Tmath have the same cardinality if there exists a one-to-one correspondence (bijection) between them. This is denoted Template:Tmath, and would be an equivalence relation on sets, if a set of all sets would exist.

For example, the natural numbers and the even natural numbers have the same cardinality, since multiplication by two provides such a bijection. Similarly, the interval Template:Tmath and the set of all real numbers have the same cardinality, a bijection being provided by the function Template:Tmath.

Having the same cardinality of a proper subset is a characteristic property of infinite sets: a set is infinite if and only if it has the same cardinality as one of its proper subsets. So, by the above example, the natural numbers form an infinite set.

Besides equality, there is a natural inequality between cardinalities: a set Template:Tmath has a cardinality smaller than or equal to the cardinality of another set Template:Tmath if there is an injection from Template:Tmath to Template:Tmath. This is denoted Template:Tmath.

Schröder–Bernstein theorem implies that Template:Tmath and Template:Tmath imply Template:Tmath. Also, one has Template:Tmath, if and only if there is a surjection from Template:Tmath to Template:Tmath. For every two sets Template:Tmath and Template:Tmath, one has either Template:Tmath or Template:Tmath. So, inequality of cardinalities is a total order.

The cardinality of the set Template:Tmath of the natural numbers, denoted Template:Tmath, is the smallest infinite cardinality. This means that if Template:Tmath is a set of natural numbers, then either Template:Tmath is finite or Template:Tmath.

Sets with cardinality less than or equal to Template:Tmath are called countable sets; these are either finite sets or countably infinite sets (sets of cardinality Template:Tmath); some authors use "countable" to mean "countably infinite". Sets with cardinality strictly greater than Template:Tmath are called uncountable sets.

Cantor's diagonal argument shows that, for every set Template:Tmath, its power set (the set of its subsets) Template:Tmath has a greater cardinality: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |S|<\left|2^S \right|.} This implies that there is no greatest cardinality.

Cardinality of the real numbers

The cardinality of set of the real numbers is called the cardinality of the continuum and denoted Template:Tmath. (The term "continuum" referred to the real line before the 20th century, when the real line was not commonly viewed as a set of numbers.)

Since, as seen above, the real line Template:Tmath has the same cardinality of an open interval, every subset of Template:Tmath that contains a nonempty open interval also has the cardinality Template:Tmath.

One has Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathfrak c = 2^{\aleph_0},} meaning that the cardinality of the real numbers equals the cardinality of the power set of the natural numbers. In particular, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathfrak c > \aleph_0.}

When published in 1878 by Georg Cantor, this result was so astonishing that it was rejected by mathematicians, and several decades were needed before its common acceptance.

It can be shown that Template:Tmath is also the cardinality of the entire plane, and of any finite-dimensional Euclidean space.

The continuum hypothesis, a conjecture formulated by Georg Cantor in 1878, states that there is no set with cardinality strictly between Template:Tmath and Template:Tmath. In 1963, Paul Cohen proved that the continuum hypothesis is independent of the axioms of Zermelo–Fraenkel set theory with the axiom of choice. This means that if the most widely used set theory is consistent (that is not self-contradictory), then the same is true for both the set theory with the continuum hypothesis added as a further axiom, and the set theory with the negation of the continuum hypothesis added.

Axiom of choice

Main article: Axiom of choice

Informally, the axiom of choice says that, given any family of nonempty sets, one can choose simultaneously an element in each of them. Formulated this way, acceptability of this axiom sets a foundational logical question, because of the difficulty of conceiving an infinite instantaneous action. However, there are several equivalent formulations that are much less controversial and have strong consequences in many areas of mathematics. In the present days, the axiom of choice is thus commonly accepted in mainstream mathematics.

A more formal statement of the axiom of choice is: the Cartesian product of every indexed family of nonempty sets is non empty.

Other equivalent forms are described in the following subsections.

Zorn's lemma

Main article: Zorn's lemma

Zorn's lemma is an assertion that is equivalent to the axiom of choice under the other axioms of set theory, and is easier to use in usual mathematics.

Let Template:Tmath be a partial ordered set. A chain in Template:Tmath is a subset that is totally ordered under the induced order. Zorn's lemma states that, if every chain in Template:Tmath has an upper bound in Template:Tmath, then Template:Tmath has (at least) a maximal element, that is, an element that is not smaller than another element of Template:Tmath.

In most uses of Zorn's lemma, Template:Tmath is a set of sets, the order is set inclusion, and the upperbound of a chain is taken as the union of its members.

An example of use of Zorn's lemma, is the proof that every vector space has a basis. Here the elements of Template:Tmath are linearly independent subsets of the vector space. The union of a chain of elements of Template:Tmath is linearly independent, since an infinite set is linearly independent if and only if each finite subset is, and every finite subset of the union of a chain must be included in a member of the chain. So, there exist a maximal linearly independent set. This linearly independent set must span the vector space because of maximality, and is therefore a basis.

Another classical use of Zorn's lemma is the proof that every proper ideal—that is, an ideal that is not the whole ring—of a ring is contained in a maximal ideal. Here, Template:Tmath is the set of the proper ideals containing the given ideal. The union of chain of ideals is an ideal, since the axioms of an ideal involve a finite number of elements. The union of a chain of proper ideals is a proper ideal, since otherwise Template:Tmath would belong to the union, and this implies that it would belong to a member of the chain.

Transfinite induction

Main articles: Well-order and Transfinite induction

The axiom of choice is equivalent with the fact that a well-order can be defined on every set, where a well-order is a total order such that every nonempty subset has a least element.

Simple examples of well-ordered sets are the natural numbers (with the natural order), and, for every Template:Tmath, the set of the Template:Tmath-tuples of natural numbers, with the lexicographic order.

Well-orders allow a generalization of mathematical induction, which is called transfinite induction. Given a property (predicate) Template:Tmath depending on a natural number, mathematical induction is the fact that for proving that Template:Tmath is always true, it suffices to prove that for every Template:Tmath, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (m<n \implies P(m)) \implies P(n).} Transfinite induction is the same, replacing natural numbers by the elements of a well-ordered set.

Often, a proof by transfinite induction easier if three cases are proved separately, the two first cases being the same as for usual induction:

• Template:Tmath is true, where Template:Tmath denotes the least element of the well-ordered set
• Template:Tmath, where Template:Tmath denotes the successor of Template:Tmath, that is the least element that is greater than Template:Tmath
• Template:Tmath, when Template:Tmath is not a successor.

Transfinite induction is fundamental for defining ordinal numbers and cardinal numbers.

See also

• Algebra of sets
• Alternative set theory
• Category of sets – Category whose objects are sets and whose morphisms are functions
• Class (set theory) – Collection of sets in mathematics that can be defined based on a property of its members
• Family of sets
• Fuzzy set – Sets whose elements have degrees of membership
• Mathematical logic – Subfield of mathematics
• Mereology
• Principia Mathematica – 3-volume treatise on mathematics, 1910–1913
• Set theory – Branch of mathematics that studies sets

References

• Dauben, Joseph W. (1979). Georg Cantor: His Mathematics and Philosophy of the Infinite. Boston: Harvard University Press. ISBN 0-691-02447-2.
• Halmos, Paul R. (1960). Naive Set Theory. Princeton, N.J.: Van Nostrand. ISBN 0-387-90092-6.
• Stoll, Robert R. (1979). Set Theory and Logic. Mineola, N.Y.: Dover Publications. ISBN 0-486-63829-4.
• Velleman, Daniel (2006). How To Prove It: A Structured Approach. Cambridge University Press. ISBN 0-521-67599-5.
• Gödel, Kurt (9 November 1938). "The Consistency of the Axiom of Choice and of the Generalized Continuum-Hypothesis". Proceedings of the National Academy of Sciences of the United States of America. 24 (12): 556–557. Bibcode:1938PNAS...24..556G. doi:10.1073/pnas.24.12.556. PMC 1077160. PMID 16577857.
• Cohen, Paul (1963b). "The Independence of the Axiom of Choice" (PDF). Stanford University Libraries. Archived (PDF) from the original on 2022-10-09. Retrieved 2019-03-22.

External links

• Template:Wiktionaryinline
• Cantor's "Beiträge zur Begründung der transfiniten Mengenlehre" (in German)