Allegory (category theory)

Allegory (category theory)

In mathematics, in the subject of category theory, an allegory is a category that has some of the structure of the category of sets and binary relations between them. Allegories can be used as an abstraction of categories of relations, and in this sense the theory of allegories is a generalization of relation algebra to relations between different sorts. Allegories are also useful in defining and investigating certain constructions in category theory, such as exact completions.

Precisely, an allegory is a category in which
* every morphism "R":"X→Y" is associated with an anti-involution, i.e. a morphism "R"°:"Y→X"; and
* every pair of morphisms "R","S":"X"→"Y" with common domain/codomain is associated with an intersection, i.e. a morphism "R"∩"S":"X"→"Y"all such that
* intersections are idempotent ("R"∩"R"="R"), commutative ("R"∩"S"="S"∩"R"), and associative ("R"∩"S")∩"T"="R"∩("S"∩"T");
* anti-involution distributes over composition (("RS")°="S"°"R"°) and intersection (("R"∩"S")°="S"°∩"R"°);
* composition is semi-distributive over intersection ("R"("S"∩"T")⊆"RS"∩"RT", ("R"∩"S")"T")⊆"RT"∩"ST"); and
* the modularity law is satisfied: ("RS"∩"T"⊆("R"∩"TS"°)"S").Here, we are abbreviating using the order defined by the intersection: "R"⊆"S" means "S"="R"∩"S".

In this article we adopt the convention that morphisms compose from right to left, so "RS" means "first do "S", then do "R".

A first example of an allegory is Rel(Set). The objects of this allegory are sets, and a morphism "X→Y" is a binary relation between "X" and "Y". Composition of morphisms is composition of relations; intersection of morphisms is intersection of relations.

Regular categories and allegories

Allegories of relations in regular categories

In a category "C", a relation between objects "X", "Y" is a span of morphisms "X←R→Y" that is jointly-monic. Two such spans "X←S→Y" and "X←T→Y" are considered equivalent when there is an isomorphism between S and T that make everything commute, and strictly speaking relations are only defined up to equivalence (one may formalise this either using equivalence classes or using bicategories). If the category "C" has products, a relation between "X" and "Y" is the same thing as a monomorphism into "X"×"Y" (or an equivalence class of such). In the presence of pullbacks and a proper factorization system, one can define the composition of relations. The composition of "X←R→Y←S→Z" is found by first pulling back the cospan "R→Y←S" and then taking the jointly-monic image of the resulting span "X←R←·→S→Z".

Composition of relations will be associative if the factorization system is appropriately stable. In this case one can consider a category Rel("C"), with the same objects as "C", but where morphisms are relations between the objects. The identity relations are the diagonals "X"→"X"×"X".

Recall that a regular category is a category with finite limits and images in which covers are stable under pullback. A regular category has a stable regular epi/mono factorization system. The category of relations for a regular category is always an allegory. Anti-involution is defined by turning the source/target of the relation around, and intersections are intersections of subobjects, computed by pullback.

Maps in allegories, and tabulations

A morphism "R" in an allegory "A" is called a map if it is entire (1⊆"R"°"R") and deterministic ("RR"°⊆1). Another way of saying this: a map is a morphism that has a right adjoint in "A", when "A" is considered, using the local order structure, as a 2-category. Maps in an allegory are closed under identity and composition. Thus there is a subcategory Map("A") of "A", with the same objects but only the maps as morphisms. For a regular category "C", there is an isomorphism of categories "C"≅Map(Rel("C")). In particular, a morphism in Map(Rel(Set)) is just an ordinary set function.

In an allegory, a morphism "R:X→Y" is tabulated by a pair of maps "f":"Z→X", "g":"Z→Y" if "gf"°=R and "f"°"f"∩"g"°"g"=1. An allegory is called tabular if every morphism has a tabulation. For a regular category "C", the allegory Rel("C") is always tabular. On the other hand, for any tabular allegory "A", the category Map("A") of maps is a locally regular category: it has pullbacks, equalizers and images that are stable under pullback. This is enough to study relations in Map("A") and, in this setting, "A"≅Rel(Map("A")).

Unital allegories and regular categories of maps

A unit in an allegory is an object "U" for which the identity is the largest morphism "U→U", and such that from every other object there is an entire relation to "U". An allegory with a unit is called unital. Given a tabular allegory "A", the category Map("A") is a regular category (it has a terminal object) if and only if "A" is unital.

More sophisticated kinds of allegory

Additional properties of allegories can be axiomatized. Distributive allegories have a union-like operation that is suitably well-behaved, and division allegories have a generalization of the division operation of relation algebra. Power allegories are distributive division allegories with additional powerset-like structure. The connection between allegories and regular categories can be developed into a connection between power allegories and toposes.

References

* cite book
author = Peter Freyd, Andre Scedrov
title = Categories, Allegories
publisher = North-Holland
series = Mathematical Library Vol 39
year = 1990
isbn = 978-0-444-70368-2

* cite book
author = Peter Johnstone
title = Sketches of an Elephant: A Topos Theory Compendium
publisher = OUP
series = Oxford Science Publications
year = 2003
isbn = 019852496X


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Category of relations — In mathematics, the category Rel has the class of sets as objects and binary relations as morphisms.A morphism (or arrow) R : A → B in this category is a relation between the sets A and B , so nowrap| R ⊆ A × B .The composition of two relations R …   Wikipedia

  • Regular category — In category theory, a regular category is a category with finite limits and coequalizers of kernel pairs, satisfying certain exactness conditions. In that way, regular categories recapture many properties of abelian categories, like the existence …   Wikipedia

  • Jesus myth theory — The Resurrection of Christ by Noel Coypel (1700). Jesus myth theorists see this as one of a number of stories about dying and rising gods. Description The …   Wikipedia

  • List of mathematics articles (A) — NOTOC A A Beautiful Mind A Beautiful Mind (book) A Beautiful Mind (film) A Brief History of Time (film) A Course of Pure Mathematics A curious identity involving binomial coefficients A derivation of the discrete Fourier transform A equivalence A …   Wikipedia

  • Relation algebra — is different from relational algebra, a framework developed by Edgar Codd in 1970 for relational databases. In mathematics, a relation algebra is a residuated Boolean algebra supporting an involutary unary operation called converse. The… …   Wikipedia

  • Philosophy of mathematics — The philosophy of mathematics is the branch of philosophy that studies the philosophical assumptions, foundations, and implications of mathematics. The aim of the philosophy of mathematics is to provide an account of the nature and methodology of …   Wikipedia

  • List of philosophy topics (A-C) — 110th century philosophy 11th century philosophy 12th century philosophy 13th century philosophy 14th century philosophy 15th century philosophy 16th century philosophy 17th century philosophy 18th century philosophy 19th century philosophy220th… …   Wikipedia

  • Analogy — is both the cognitive process of transferring information from a particular subject (the analogue or source) to another particular subject (the target), and a linguistic expression corresponding to such a process. In a narrower sense, analogy is… …   Wikipedia

  • literature — /lit euhr euh cheuhr, choor , li treuh /, n. 1. writings in which expression and form, in connection with ideas of permanent and universal interest, are characteristic or essential features, as poetry, novels, history, biography, and essays. 2.… …   Universalium

  • BIBLE — THE CANON, TEXT, AND EDITIONS canon general titles the canon the significance of the canon the process of canonization contents and titles of the books the tripartite canon …   Encyclopedia of Judaism

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”