Category of sets
Encyclopedia
In the mathematical
field of category theory
, the category of sets, denoted as Set, is the category
whose objects
are sets. The arrows or morphism
s between sets A and B are all function
s from A to B. Care must be taken in the definition of Set to avoid set-theoretic paradoxes
.
Many other categories (such as the category of groups
, with group homomorphisms as arrows) add structure to the objects of the category of sets and/or restrict the arrows to functions of a particular kind.
s in Set are the surjective maps, the monomorphism
s are the injective maps, and the isomorphism
s are the bijective maps.
The empty set
serves as the initial object
in Set with empty function
s as morphisms. Every singleton is a terminal object, with the functions mapping all elements of the source sets to the single target element as morphisms. There are thus no zero objects in Set.
The category Set is complete and co-complete
. The product
in this category is given by the cartesian product
of sets. The coproduct is given by the disjoint union
: given sets Ai where i ranges over some index set I, we construct the coproduct as the union of Ai×{i} (the cartesian product with i serves to ensure that all the components stay disjoint).
Set is the prototype of a concrete category
; other categories are concrete if they "resemble" Set in some well-defined way.
Every two-element set serves as a subobject classifier
in Set. The power object of a set A is given by its power set, and the exponential object
of the sets A and B is given by the set of all functions from A to B. Set is thus a topos
(and in particular cartesian closed
).
Set is not abelian
, additive
or preadditive
. Its zero morphism
s are the empty functions ∅ → X.
Every not initial object in Set is injective
and (assuming the axiom of choice) also projective
.
the collection of all sets is not a set; this follows from the axiom of foundation. One refers to collections that are not sets as proper classes. One can't handle proper classes as one handles sets; in particular, one can't write that those proper classes belong to a collection (either a set or a proper class). This is a problem: it means that the category of sets cannot be formalized straightforwardly in this setting.
One way to resolve the problem is to work in a system that gives formal status to proper classes, such as NBG set theory. In this setting, categories formed from sets are said to be small and those (like Set) that are formed from proper classes are said to be large.
Another solution is to assume the existence of Grothendieck universe
s. Roughly speaking, a Grothendieck universe is a set which is itself a model of ZF(C) (for instance if a set belongs to a universe, its elements and its powerset will belong to the universe). The existence of Grothendieck universes (other than the empty set and the set
of all hereditarily finite set
s) is not implied by the usual ZF axioms; it is an additional, independent axiom, roughly equivalent to the existence of strongly inaccessible cardinals. Assuming this extra axiom, one can limit the objects of Set to the elements of a particular universe. (There is no "set of all sets" within the model, but one can still reason about the class U of all inner sets, i. e., elements of U.)
In one variation of this scheme, the class of sets is the union of the entire tower of Grothendieck universes. (This is necessarily a proper class, but each Grothendieck universe is a set because it is an element of some larger Grothendieck universe.) However, one does not work directly with the "category of all sets". Instead, theorems are expressed in terms of the category SetU whose objects are the elements of a sufficiently large Grothendieck universe U, and are then shown not to depend on the particular choice of U. As a foundation for category theory
, this approach is well matched to a system like Tarski-Grothendieck set theory
in which one cannot reason directly about proper classes; its principal disadvantage is that a theorem can be true of all SetU but not of Set.
Various other solutions, and variations on the above, have been proposed.
The same issues arise with other concrete categories, such as the category of groups
or the category of topological spaces
.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
field of category theory
Category theory
Category theory is an area of study in mathematics that examines in an abstract way the properties of particular mathematical concepts, by formalising them as collections of objects and arrows , where these collections satisfy certain basic conditions...
, the category of sets, denoted as Set, is the category
Category (mathematics)
In mathematics, a category is an algebraic structure that comprises "objects" that are linked by "arrows". A category has two basic properties: the ability to compose the arrows associatively and the existence of an identity arrow for each object. A simple example is the category of sets, whose...
whose objects
Category theory
Category theory is an area of study in mathematics that examines in an abstract way the properties of particular mathematical concepts, by formalising them as collections of objects and arrows , where these collections satisfy certain basic conditions...
are sets. The arrows or morphism
Morphism
In mathematics, a morphism is an abstraction derived from structure-preserving mappings between two mathematical structures. The notion of morphism recurs in much of contemporary mathematics...
s between sets A and B are all function
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
s from A to B. Care must be taken in the definition of Set to avoid set-theoretic paradoxes
Paradoxes of set theory
This article contains a discussion of paradoxes of set theory. As with most mathematical paradoxes, they generally reveal surprising and counter-intuitive mathematical results, rather than actual logical contradictions within modern axiomatic set theory....
.
Many other categories (such as the category of groups
Category of groups
In mathematics, the category Grp has the class of all groups for objects and group homomorphisms for morphisms. As such, it is a concrete category...
, with group homomorphisms as arrows) add structure to the objects of the category of sets and/or restrict the arrows to functions of a particular kind.
Properties of the category of sets
The epimorphismEpimorphism
In category theory, an epimorphism is a morphism f : X → Y which is right-cancellative in the sense that, for all morphisms ,...
s in Set are the surjective maps, the monomorphism
Monomorphism
In the context of abstract algebra or universal algebra, a monomorphism is an injective homomorphism. A monomorphism from X to Y is often denoted with the notation X \hookrightarrow Y....
s are the injective maps, and the isomorphism
Isomorphism
In abstract algebra, an isomorphism is a mapping between objects that shows a relationship between two properties or operations. If there exists an isomorphism between two structures, the two structures are said to be isomorphic. In a certain sense, isomorphic structures are...
s are the bijective maps.
The empty set
Empty set
In mathematics, and more specifically set theory, the empty set is the unique set having no elements; its size or cardinality is zero. Some axiomatic set theories assure that the empty set exists by including an axiom of empty set; in other theories, its existence can be deduced...
serves as the initial object
Initial object
In category theory, an abstract branch of mathematics, an initial object of a category C is an object I in C such that for every object X in C, there exists precisely one morphism I → X...
in Set with empty function
Empty function
In mathematics, an empty function is a function whose domain is the empty set. For each set A, there is exactly one such empty functionf_A: \varnothing \rightarrow A....
s as morphisms. Every singleton is a terminal object, with the functions mapping all elements of the source sets to the single target element as morphisms. There are thus no zero objects in Set.
The category Set is complete and co-complete
Complete category
In mathematics, a complete category is a category in which all small limits exist. That is, a category C is complete if every diagram F : J → C where J is small has a limit in C. Dually, a cocomplete category is one in which all small colimits exist...
. The product
Product (category theory)
In category theory, the product of two objects in a category is a notion designed to capture the essence behind constructions in other areas of mathematics such as the cartesian product of sets, the direct product of groups, the direct product of rings and the product of topological spaces...
in this category is given by the cartesian product
Cartesian product
In mathematics, a Cartesian product is a construction to build a new set out of a number of given sets. Each member of the Cartesian product corresponds to the selection of one element each in every one of those sets...
of sets. The coproduct is given by the disjoint union
Disjoint union
In mathematics, the term disjoint union may refer to one of two different concepts:* In set theory, a disjoint union is a modified union operation that indexes the elements according to which set they originated in; disjoint sets have no element in common.* In probability theory , a disjoint union...
: given sets Ai where i ranges over some index set I, we construct the coproduct as the union of Ai×{i} (the cartesian product with i serves to ensure that all the components stay disjoint).
Set is the prototype of a concrete category
Concrete category
In mathematics, a concrete category is a category that is equipped with a faithful functor to the category of sets. This functor makes it possible to think of the objects of the category as sets with additional structure, and of its morphisms as structure-preserving functions...
; other categories are concrete if they "resemble" Set in some well-defined way.
Every two-element set serves as a subobject classifier
Subobject classifier
In category theory, a subobject classifier is a special object Ω of a category; intuitively, the subobjects of an object X correspond to the morphisms from X to Ω. As the name suggests, what a subobject classifier does is to identify/classify subobjects of a given object according to which elements...
in Set. The power object of a set A is given by its power set, and the exponential object
Exponential object
In mathematics, specifically in category theory, an exponential object is the categorical equivalent of a function space in set theory. Categories with all finite products and exponential objects are called cartesian closed categories...
of the sets A and B is given by the set of all functions from A to B. Set is thus a topos
Topos
In mathematics, a topos is a type of category that behaves like the category of sheaves of sets on a topological space...
(and in particular cartesian closed
Cartesian closed category
In category theory, a category is cartesian closed if, roughly speaking, any morphism defined on a product of two objects can be naturally identified with a morphism defined on one of the factors. These categories are particularly important in mathematical logic and the theory of programming, in...
).
Set is not abelian
Abelian category
In mathematics, an abelian category is a category in which morphisms and objects can be added and in which kernels and cokernels exist and have desirable properties. The motivating prototype example of an abelian category is the category of abelian groups, Ab. The theory originated in a tentative...
, additive
Additive category
In mathematics, specifically in category theory, an additive category is a preadditive category C such that all finite collections of objects A1,...,An of C have a biproduct A1 ⊕ ⋯ ⊕ An in C....
or preadditive
Preadditive category
In mathematics, specifically in category theory, a preadditive category is a category that is enriched over the monoidal category of abelian groups...
. Its zero morphism
Zero morphism
In category theory, a zero morphism is a special kind of morphism exhibiting properties like those to and from a zero object.Suppose C is a category, and f : X → Y is a morphism in C...
s are the empty functions ∅ → X.
Every not initial object in Set is injective
Injective object
In mathematics, especially in the field of category theory, the concept of injective object is a generalization of the concept of injective module. This concept is important in homotopy theory and in theory of model categories...
and (assuming the axiom of choice) also projective
Projective module
In mathematics, particularly in abstract algebra and homological algebra, the concept of projective module over a ring R is a more flexible generalisation of the idea of a free module...
.
Foundations for the category of sets
In Zermelo–Fraenkel set theoryZermelo–Fraenkel set theory
In mathematics, Zermelo–Fraenkel set theory with the axiom of choice, named after mathematicians Ernst Zermelo and Abraham Fraenkel and commonly abbreviated ZFC, is one of several axiomatic systems that were proposed in the early twentieth century to formulate a theory of sets without the paradoxes...
the collection of all sets is not a set; this follows from the axiom of foundation. One refers to collections that are not sets as proper classes. One can't handle proper classes as one handles sets; in particular, one can't write that those proper classes belong to a collection (either a set or a proper class). This is a problem: it means that the category of sets cannot be formalized straightforwardly in this setting.
One way to resolve the problem is to work in a system that gives formal status to proper classes, such as NBG set theory. In this setting, categories formed from sets are said to be small and those (like Set) that are formed from proper classes are said to be large.
Another solution is to assume the existence of Grothendieck universe
Grothendieck universe
In mathematics, a Grothendieck universe is a set U with the following properties:# If x is an element of U and if y is an element of x, then y is also an element of U...
s. Roughly speaking, a Grothendieck universe is a set which is itself a model of ZF(C) (for instance if a set belongs to a universe, its elements and its powerset will belong to the universe). The existence of Grothendieck universes (other than the empty set and the set
of all hereditarily finite setHereditarily finite set
In mathematics and set theory, hereditarily finite sets are defined recursively as finite sets consisting of 0 or more hereditarily finite sets.-Formal definition:...
s) is not implied by the usual ZF axioms; it is an additional, independent axiom, roughly equivalent to the existence of strongly inaccessible cardinals. Assuming this extra axiom, one can limit the objects of Set to the elements of a particular universe. (There is no "set of all sets" within the model, but one can still reason about the class U of all inner sets, i. e., elements of U.)
In one variation of this scheme, the class of sets is the union of the entire tower of Grothendieck universes. (This is necessarily a proper class, but each Grothendieck universe is a set because it is an element of some larger Grothendieck universe.) However, one does not work directly with the "category of all sets". Instead, theorems are expressed in terms of the category SetU whose objects are the elements of a sufficiently large Grothendieck universe U, and are then shown not to depend on the particular choice of U. As a foundation for category theory
Category theory
Category theory is an area of study in mathematics that examines in an abstract way the properties of particular mathematical concepts, by formalising them as collections of objects and arrows , where these collections satisfy certain basic conditions...
, this approach is well matched to a system like Tarski-Grothendieck set theory
Tarski-Grothendieck set theory
Tarski–Grothendieck set theory is an axiomatic set theory that was introduced as part of the Mizar system for formal verification of proofs. Its characteristic axiom is Tarski's axiom . The theory is a non-conservative extension of Zermelo–Fraenkel set theory...
in which one cannot reason directly about proper classes; its principal disadvantage is that a theorem can be true of all SetU but not of Set.
Various other solutions, and variations on the above, have been proposed.
The same issues arise with other concrete categories, such as the category of groups
Category of groups
In mathematics, the category Grp has the class of all groups for objects and group homomorphisms for morphisms. As such, it is a concrete category...
or the category of topological spaces
Category of topological spaces
In mathematics, the category of topological spaces, often denoted Top, is the category whose objects are topological spaces and whose morphisms are continuous maps. This is a category because the composition of two continuous maps is again continuous...
.