Set theory

1 Basic concepts

Set theory begins with the idea of a set, a collection of distinct objects treated as a single object of study. The elements of a set may be numbers, letters, geometric figures, or other mathematical entities. Because the notion is so general, set theory provides a common vocabulary for describing many areas of mathematics.

1.1 Sets and elements

A set is usually written with braces, such as {1, 2, 3}. The objects inside are called elements or members. The order of listing does not matter, and repeated listings do not change the set. Thus {1, 2, 3} is the same set as {3, 2, 1}, and {1, 1, 2, 3} represents the same collection.

Sets may be finite or infinite. A finite set has a limited number of elements, while an infinite set continues without end. Common examples include the set of natural numbers and the set of points on a line.

1.2 Membership and equality

Membership is expressed by writing an element in a set, as in 2 ∈ {1, 2, 3}. Nonmembership is written with the symbol ∉. These relations describe whether an object belongs to a collection.

Two sets are equal when they contain exactly the same elements. This means that set equality depends only on membership, not on how the set is presented. For example, {a, b} and {b, a} are equal because each has the same members.

1.3 Common set operations

Set operations combine or compare sets to form new ones. These operations are central to mathematical reasoning, since they describe how collections overlap, differ, or expand into larger structures.

1.3.1 Union

The union of two sets consists of all elements that appear in either set. If A and B are sets, their union is written A ∪ B. This operation gathers elements from both collections without duplicating them.

1.3.2 Intersection

The intersection of two sets contains only the elements common to both. It is written A ∩ B. When two sets have no elements in common, their intersection is the empty set.

1.3.3 Difference and complement

The difference A \ B consists of elements in A that are not in B. This operation is useful for isolating parts of a set after removing another. The complement of a set is defined relative to a larger surrounding set, often called the universe, and contains all elements outside the given set but within that universe.

1.4 Subsets and power sets

A set A is a subset of B if every element of A is also an element of B. This relation is written A ⊆ B. If A is a subset of B and not equal to B, it is called a proper subset.

The power set of a set A is the set of all subsets of A. It is written P(A). Even for a small set, the power set can be much larger than the original set, since it includes the empty set, single-element subsets, and all other combinations.

2 Relations and functions

Set theory also provides a framework for describing connections between elements of sets. Relations and functions are built from ordered pairs and are used throughout mathematics to model correspondence, structure, and transformation.

2.1 Ordered pairs

An ordered pair is a pair of objects in which position matters. The pair (a, b) is generally different from (b, a) unless a and b are the same. Ordered pairs are used to represent points, relations, and function values.

2.2 Relations

A relation is a set of ordered pairs. If an ordered pair (a, b) belongs to a relation, one says that a is related to b in that relation. Relations can encode comparisons, connections, or other patterns among objects.

2.2.1 Equivalence relations

An equivalence relation is a relation that is reflexive, symmetric, and transitive. Such a relation partitions a set into equivalence classes, grouping together elements that are regarded as equivalent under some criterion. Common examples arise from congruence or from having the same remainder in arithmetic.

2.2.2 Partial orders

A partial order is a relation that is reflexive, antisymmetric, and transitive. It describes a hierarchy in which not every pair of elements must be comparable. Subset inclusion is a standard example of a partial order.

2.3 Functions

A function assigns each element of one set to exactly one element of another set. The first set is called the domain, and the target set is called the codomain. Functions are among the most important structures in mathematics because they express dependence and transformation.

2.3.1 Injective, surjective, and bijective functions

An injective function maps distinct inputs to distinct outputs. A surjective function reaches every element of the codomain. A bijective function is both injective and surjective, establishing a perfect pairing between two sets.

2.3.2 Images and preimages

The image of a set under a function is the set of all outputs obtained from elements of that set. The preimage of a subset of the codomain is the collection of all inputs that map into it. These concepts help describe how functions transport structure from one set to another.

3 Construction of number systems

Set theory offers a precise way to build the familiar number systems from simple starting points. This approach shows how arithmetic objects can be defined in terms of sets and relations rather than taken as primitive.

3.1 Natural numbers

The natural numbers can be represented by sets arranged in increasing order, each number corresponding to the set of all smaller numbers. This provides a basis for defining counting and induction within set theory. The construction makes the natural numbers part of a cumulative hierarchy.

3.2 Integers

The integers extend the natural numbers by including zero and negative numbers. In set-theoretic constructions, integers are often represented by equivalence classes of pairs of natural numbers, capturing the idea of subtraction. This allows arithmetic to be developed in a rigorous way.

3.3 Rational numbers

Rational numbers can be built from pairs of integers representing fractions. Different pairs may represent the same rational number, such as 1/2 and 2/4, so an equivalence relation is used to identify them. This construction formalizes division by nonzero integers.

3.4 Real numbers

The real numbers complete the rational numbers by including limits of sequences and numbers such as the square root of 2 and π. Set-theoretic approaches construct the real line through equivalence classes of sequences, Dedekind cuts, or related methods. These constructions support analysis and continuous mathematics.

3.5 Set-theoretic constructions

Set-theoretic construction seeks to define complex mathematical objects using only sets and simple operations. Once number systems are encoded in this way, many further structures can be developed uniformly. This approach is one reason set theory is regarded as foundational.

4 Cardinality

Cardinality measures the size of a set, meaning how many elements it contains. For finite sets, cardinality is straightforward, but for infinite sets it requires more refined notions of comparison.

4.1 Finite and infinite sets

A finite set has a definite count of elements. An infinite set has no such final count. Set theory distinguishes different kinds of infinity by comparing the sizes of infinite collections.

4.2 Countable sets

A set is countable if its elements can be listed in a sequence, possibly without end, so that each element appears at some position in the list. The natural numbers are the standard example. Some infinite sets, including the integers and rational numbers, are countable despite their infinite extent.

4.3 Uncountable sets

An uncountable set cannot be listed in sequence in this way. The real numbers form the most familiar example. Uncountability shows that not all infinities are the same size.

4.4 Comparing sizes of sets

Set theorists compare sizes by looking for injections, surjections, and bijections between sets. If two sets can be matched by a bijection, they have the same cardinality. This method extends the idea of counting to infinite collections.

4.4.1 Cantor's theorem

Cantor's theorem states that a set always has a strictly smaller cardinality than its power set. As a result, there is no largest set size in the ordinary sense. This theorem is a central result in the theory of infinite sets.

4.4.2 The continuum

The continuum usually refers to the cardinality of the real numbers. It is larger than the cardinality of the natural numbers and serves as a standard benchmark for uncountable size. The continuum is one of the most studied cardinalities in set theory.

5 Ordinals and transfinite numbers

Ordinals describe order type rather than simple size. They extend counting to well-ordered collections, including infinite ones, and provide a language for transfinite processes.

5.1 Well-ordered sets

A well-ordered set is one in which every nonempty subset has a least element. This property allows induction and recursion to be carried out in broad generality. Many ordinal concepts are modeled on well-ordering.

5.2 Ordinal numbers

Ordinal numbers record positions in a well-ordered sequence. They generalize the finite counting numbers and include infinite ordinals such as ω, the first infinite ordinal. Unlike cardinal numbers, ordinals reflect arrangement as well as quantity.

5.3 Transfinite induction

Transfinite induction extends ordinary induction to well-ordered sets of arbitrary length. To prove a statement for all ordinals, one shows it for a base case, then for successors, and finally for limit ordinals. This method is essential in advanced set theory.

5.4 Ordinal arithmetic

Ordinal arithmetic defines addition, multiplication, and exponentiation for ordinals. These operations behave differently from arithmetic on ordinary numbers because order matters. For example, ordinal addition is not commutative, reflecting the directional nature of sequence.

6 Axiomatic set theory

Axiomatic set theory provides a formal system of rules that specifies which sets exist and how they may be formed. The purpose of axiomatization is to make set theory precise, avoid contradictions, and support proof.

6.1 Motivation for axioms

Early naive approaches to sets allowed unrestricted formation of collections and led to paradoxes. Axioms were introduced to restrict set formation in controlled ways. This made the theory suitable as a foundation for mathematics.

6.2 Zermelo-Fraenkel set theory

Zermelo-Fraenkel set theory, usually abbreviated ZF, is the most widely used axiomatic framework for set theory. It includes a collection of axioms governing existence, equality, membership, and construction of sets. When combined with the axiom of choice, it is known as ZFC.

6.2.1 Extensionality

The axiom of extensionality states that two sets are equal if they have the same elements. It formalizes the principle that a set is determined entirely by membership. This axiom underlies the identity of sets throughout the theory.

6.2.2 Empty set

The empty set has no elements and serves as the starting point for many constructions. Its existence is guaranteed by the axioms. From it, more complex sets can be built.

6.2.3 Pairing and union

The axiom of pairing ensures that for any two sets, there is a set containing exactly those two as elements. The axiom of union allows one to combine the elements of a set of sets into a single set. Together, these axioms support the formation of many common collections.

6.2.4 Power set and separation

The power set axiom guarantees that the set of all subsets of a given set exists. Separation allows the formation of subsets defined by a property, provided one starts from an already existing set. These axioms control set formation without permitting unrestricted comprehension.

6.2.5 Replacement and infinity

Replacement states that the image of a set under a definable rule is also a set, which is crucial for constructing large objects. The axiom of infinity ensures the existence of an infinite set, enabling the development of number systems and transfinite constructions.

6.3 Choice and related principles

Some arguments in set theory require the ability to make selections from many sets at once. Principles of choice provide this ability and have consequences across mathematics.

6.3.1 Axiom of choice

The axiom of choice asserts that given a collection of nonempty sets, one can choose one element from each set. This principle is independent of the basic ZF axioms and has deep implications for algebra, topology, and analysis.

6.3.2 Equivalent forms

The axiom of choice is equivalent to several important statements, including Zorn's lemma and the well-ordering principle. These equivalent forms are often used in different areas depending on which is most convenient for a proof.

6.4 Alternative axiom systems

Besides ZF and ZFC, other axiom systems have been proposed to manage sets and classes in different ways. Some emphasize predicativity or restrict certain infinite constructions, while others incorporate classes more directly. These alternatives are studied for their logical and foundational properties.

7 Paradoxes and consistency

The development of set theory was strongly shaped by paradoxes discovered in early naive formulations. These contradictions showed that not every seemingly reasonable set-building rule is safe.

7.1 Early paradoxes

Early paradoxes demonstrated that unrestricted comprehension can produce impossible objects. They motivated the search for a more disciplined foundation. Two of the best known are Russell's paradox and the Burali-Forti paradox.

7.1.1 Russell's paradox

Russell's paradox considers the set of all sets that do not contain themselves. Asking whether this set contains itself leads to a contradiction. The paradox showed that naive self-reference must be handled with care.

7.1.2 Burali-Forti paradox

The Burali-Forti paradox arises from attempting to form the set of all ordinal numbers. Such a collection cannot be a set, because its existence would lead to a contradiction concerning the order type of all ordinals. This paradox revealed limits on totalizing infinite hierarchies.

7.2 Responses to paradoxes

The main response to paradoxes was to replace naive set theory with axiomatic systems that restrict set formation. By limiting how sets are defined, these systems avoid self-referential contradictions. Types, classes, and stratified hierarchies were among the ideas developed in response.

7.3 Relative consistency and independence

A statement is independent of a theory if it can neither be proved nor disproved from the axioms, assuming the axioms themselves are consistent. Relative consistency results show that one system is consistent if another is. Such results are important in understanding the strength and limitations of axiomatic set theories.

8 Classes and large-scale set theory

As set theory grows, some collections become too large to be sets in the usual sense. Classes and hierarchical constructions help describe these broader structures.

8.1 Proper classes

A proper class is a collection too large to be a set. Examples often include the collection of all sets or the collection of all ordinals. Proper classes are useful for talking about totalities that cannot themselves be treated as elements of a set.

8.2 Von Neumann universe

The von Neumann universe is a cumulative hierarchy built in stages. Each level is formed from the power set of earlier levels, creating an expanding structure that contains sets of increasing complexity. This universe is central to standard set-theoretic foundations.

8.3 Large cardinals

Large cardinals are infinite cardinals with strong properties extending far beyond ordinary infinite sizes. They often require additional axioms beyond ZF or ZFC. These notions play a major role in modern set theory because they reveal deep structure in the hierarchy of infinities.

8.4 Hierarchies and ranks

Rank assigns to each set a level in the cumulative hierarchy based on the ranks of its elements. This provides a way to measure how deeply a set is built from earlier stages. Hierarchical descriptions help organize the universe of sets and analyze definability.

9 Applications and influence

Set theory is not only a foundation for mathematics but also a practical language for organizing many branches of the subject. Its ideas shape how mathematicians define objects, compare structures, and build proofs.

9.1 Foundations of mathematics

Set theory supplies a unified framework in which many mathematical concepts can be defined. Numbers, functions, sequences, and spaces can all be expressed in set-theoretic terms. This makes it a common basis for formal reasoning.

9.2 Use in logic and computer science

In logic, set theory supports formal semantics, model theory, and the study of proof systems. In computer science, it influences data structures, specification languages, and reasoning about computation. Its emphasis on precise structure makes it valuable in both fields.

9.3 Influence on topology, analysis, and algebra

Many mathematical disciplines rely on set-theoretic language. Topology uses sets to define open and closed collections, analysis uses them for limits and completeness, and algebra uses them to describe groups, rings, and vector spaces. Set theory therefore underlies both abstract theory and concrete mathematical practice.