Free category

Last updated

In mathematics, the free category or path category generated by a directed graph or quiver is the category that results from freely concatenating arrows together, whenever the target of one arrow is the source of the next.

Mathematics Field of study concerning quantity, patterns and change

Mathematics includes the study of such topics as quantity, structure, space, and change.

Directed graph type of graph

In mathematics, and more specifically in graph theory, a directed graph is a graph that is made up of a set of vertices connected by edges, where the edges have a direction associated with them.

In mathematics, a quiver is a directed graph where loops and multiple arrows between two vertices are allowed, i.e. a multidigraph. They are commonly used in representation theory: a representation V of a quiver assigns a vector space V(x) to each vertex x of the quiver and a linear map V(a) to each arrow a.

Contents

More precisely, the objects of the category are the vertices of the quiver, and the morphisms are paths between objects. Here, a path is defined as a finite sequence

where is a vertex of the quiver, is an edge of the quiver, and n ranges over the non-negative integers. For every vertex of the quiver, there is an "empty path" which constitutes the identity morphisms of the category.

The composition operation is concatenation of paths. Given paths

their composition is

. [1] [2]

Note that the result of the composition starts with the right operand of the composition, and ends with its left operand.

Examples

In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero elements, often called the empty string and denoted by ε or λ, as the identity element. The free monoid on a set A is usually denoted A. The free semigroup on A is the subsemigroup of A containing all elements except the empty string. It is usually denoted A+.

Properties

The category of small categories Cat has a forgetful functor U into the quiver category Quiv:

In mathematics, specifically in category theory, the category of small categories, denoted by Cat, is the category whose objects are all small categories and whose morphisms are functors between categories. Cat may actually be regarded as a 2-category with natural transformations serving as 2-morphisms.

In mathematics, in the area of category theory, a forgetful functor 'forgets' or drops some or all of the input's structure or properties 'before' mapping to the output. For an algebraic structure of a given signature, this may be expressed by curtailing the signature: the new signature is an edited form of the old one. If the signature is left as an empty list, the functor is simply to take the underlying set of a structure. Because many structures in mathematics consist of a set with an additional added structure, a forgetful functor that maps to the underlying set is the most common case.

U : CatQuiv

which takes objects to vertices and morphisms to arrows. Intuitively, U "[forgets] which arrows are composites and which are identities". [2] This forgetful functor is right adjoint to the functor sending a quiver to the corresponding free category.

Universal property

The free category on a quiver can be described up to isomorphism by a universal property. Let C : QuivCat be the functor that takes a quiver to the free category on that quiver (as described above), let U be the forgetful functor defined above, and let G be any quiver. Then there is a graph homomorphism I : GU(C(G)) and given any category D and any graph homomorphism F : GU(B), there is a unique functor F' : C(G) → D such that U(F')∘I=F, i.e. the following diagram commutes:

Up to Mathematical statement of uniqueness, except for an equivalent . structure (equivalence relation)

In mathematics, the phrase up to appears in discussions about the elements of a set, and the conditions under which subsets of those elements may be considered equivalent. The statement "elements a and b of set S are equivalent up to X" means that a and b are equivalent if criterion X is ignored. That is, a and b can be transformed into one another if a transform corresponding to X is applied.

In category theory, an abstract branch of mathematics, an equivalence of categories is a relation between two categories that establishes that these categories are "essentially the same". There are numerous examples of categorical equivalences from many areas of mathematics. Establishing an equivalence involves demonstrating strong similarities between the mathematical structures concerned. In some cases, these structures may appear to be unrelated at a superficial or intuitive level, making the notion fairly powerful: it creates the opportunity to "translate" theorems between different kinds of mathematical structures, knowing that the essential meaning of those theorems is preserved under the translation.

In various branches of mathematics, a useful construction is often viewed as the “most efficient solution” to a certain problem. The definition of a universal property uses the language of category theory to make this notion precise and to study it abstractly.

Free-category-ump.svg

The functor C is left adjoint to the forgetful functor U. [1] [2] [3]

See also

Related Research Articles

In category theory, a branch of mathematics, the abstract notion of a limit captures the essential properties of universal constructions such as products, pullbacks and inverse limits. The dual notion of a colimit generalizes constructions such as disjoint unions, direct sums, coproducts, pushouts and direct limits.

In mathematics, specifically category theory, adjunction is a relationship that two functors may have. Two functors that stand in this relationship are known as adjoint functors, one being the left adjoint and the other the right adjoint. Pairs of adjoint functors are ubiquitous in mathematics and often arise from constructions of "optimal solutions" to certain problems, such as the construction of a free group on a set in algebra, or the construction of the Stone-Čech compactification of a topological space in topology.

An exact sequence is a concept in mathematics, especially in group theory, ring and module theory, homological algebra, as well as in differential geometry. An exact sequence is a sequence, either finite or infinite, of objects and morphisms between them such that the image of one morphism equals the kernel of the next.

In category theory, a category is considered 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 that their internal language is the simply typed lambda calculus. They are generalized by closed monoidal categories, whose internal language, linear type systems, are suitable for both quantum and classical computation.

In mathematics, the idea of a free object is one of the basic concepts of abstract algebra. It is a part of universal algebra, in the sense that it relates to all types of algebraic structure. It also has a formulation in terms of category theory, although this is in yet more abstract terms. Examples include free groups, tensor algebras, or free lattices. Informally, a free object over a set A can be thought of as being a "generic" algebraic structure over A: the only equations that hold between elements of the free object are those that follow from the defining axioms of the algebraic structure.

In category theory, a branch of mathematics, the functors between two given categories form a category, where the objects are the functors and the morphisms are natural transformations between the functors. Functor categories are of interest for two main reasons:

In mathematics, particularly category theory, a representable functor is a functor of a special form from an arbitrary category into the category of sets. Such functors give representations of an abstract category in terms of known structures allowing one to utilize, as much as possible, knowledge about the category of sets in other settings.

In mathematics, the derived categoryD(A) of an abelian category A is a construction of homological algebra introduced to refine and in a certain sense to simplify the theory of derived functors defined on A. The construction proceeds on the basis that the objects of D(A) should be chain complexes in A, with two such chain complexes considered isomorphic when there is a chain map that induces an isomorphism on the level of homology of the chain complexes. Derived functors can then be defined for chain complexes, refining the concept of hypercohomology. The definitions lead to a significant simplification of formulas otherwise described by complicated spectral sequences.

In mathematics, a triangulated category is a category together with the additional structure of a "translation functor" and a class of "distinguished triangles". Prominent examples are the derived category of an abelian category and the stable homotopy category of spectra, both of which carry the structure of a triangulated category in a natural fashion. The distinguished triangles generate the long exact sequences of homology; they play a role akin to that of short exact sequences in abelian categories.

Fibred categories are abstract entities in mathematics used to provide a general framework for descent theory. They formalise the various situations in geometry and algebra in which inverse images of objects such as vector bundles can be defined. As an example, for each topological space there is the category of vector bundles on the space, and for every continuous map from a topological space X to another topological space Y is associated the pullback functor taking bundles on Y to bundles on X. Fibred categories formalise the system consisting of these categories and inverse image functors. Similar setups appear in various guises in mathematics, in particular in algebraic geometry, which is the context in which fibred categories originally appeared. Fibered categories are used to define stacks, which are fibered categories with "descent". Fibrations also play an important role in categorical semantics of type theory, and in particular that of dependent type theories.

This is a glossary of properties and concepts in category theory in mathematics.

In category theory, a discipline within mathematics, the nerveN(C) of a small category C is a simplicial set constructed from the objects and morphisms of C. The geometric realization of this simplicial set is a topological space, called the classifying space of the categoryC. These closely related objects can provide information about some familiar and useful categories using algebraic topology, most often homotopy theory.

In category theory, a branch of mathematics, a diagram is the categorical analogue of an indexed family in set theory. The primary difference is that in the categorical setting one has morphisms that also need indexing. An indexed family of sets is a collection of sets, indexed by a fixed set; equivalently, a function from a fixed index set to the class of sets. A diagram is a collection of objects and morphisms, indexed by a fixed category; equivalently, a functor from a fixed index category to some category.

In mathematics, the category of rings, denoted by Ring, is the category whose objects are rings and whose morphisms are ring homomorphisms. Like many categories in mathematics, the category of rings is large, meaning that the class of all rings is proper.

In mathematics, a topos is a category that behaves like the category of sheaves of sets on a topological space. Topoi behave much like the category of sets and possess a notion of localization; they are in a sense a generalization of point-set topology. The Grothendieck topoi find applications in algebraic geometry; the more general elementary topoi are used in logic.

References

  1. 1 2 3 4 Awodey, Steve (2010). Category theory (2nd ed.). Oxford: Oxford University Press. pp. 20–24. ISBN   0199237182. OCLC   740446073.
  2. 1 2 3 4 Mac Lane, Saunders (1978). Categories for the Working Mathematician (Second ed.). New York, NY: Springer New York. pp. 49–51. ISBN   1441931236. OCLC   851741862.
  3. "free category in nLab". ncatlab.org. Retrieved 2017-09-12.