nLab
structured set

Structured sets

Idea

A structured set is, of course, a set equipped with extra structure. It is not the individual structured set that matters so much as the category of sets with a particular sort of structure.

Definitions

Abstract

Very abstractly, we may define a structured set as an object of any concrete category, that is an object of any category CC equipped with a faithful functor U:CSetU\colon C \to Set to the category of sets. (Some authors require that UU be representable for a concrete category, but we do not need that here.) Given two structured sets XX and YY (in the same category CC), a function f:U(X)U(Y)f\colon U(X) \to U(Y) between their underlying sets preserves the structure if it lies in the image of UU, that is if there exists a (necessarily unique since UU is faithful) morphism f˜:XY\tilde{f}\colon X \to Y in CC such that U(f˜)=fU(\tilde{f}) = f.

Concrete

More concretely, we may define a type of structure on sets as an operation TT that, to any set AA, assigns a set T(A)T(A) of TT-structures on AA. At minimum, we should have T(A)T(B)T(A) \cong T(B) whenever ABA \cong B (where \cong is isomorphism in SetSet), so that the concept is structural. But for good behaviour, we actually want something more coherent; we want an additional operation that, to any bijection f:ABf\colon A \to B, assigns a bijection T(f):T(A)T(B)T(f)\colon T(A) \to T(B), such that:

  • T(id A)=id T(A)T(\id_A) = \id_{T(A)},
  • T(fg)=T(f)T(g)T(f g) = T(f) T(g).

In other words, T:Set Set T\colon Set_\cong \to Set_\cong (or equivalently T:Set SetT\colon Set_\cong \to Set) is a functor from the underlying groupoid of SetSet to itself (or equivalently to all of SetSet). In particular, any automorphism of a single set AA defines an automorphism of the TT-structures on AA, giving an action of the symmetric group S AS_A on T(A)T(A).

(Compare the notion of structure type from combinatorics, which is a set-valued functor on the groupoid of finite sets. Every combinatorial structure type can be interpreted as a type of structure, where only finite sets are capable of supporting the structure.)

Given a type TT of structure on sets, we define a TT-structured set to be a set AA equipped with an element of T(A)T(A). Given TT-structured sets X=(A,σ)X = (A,\sigma) and Y=(B,τ)Y = (B,\tau), a bijection f:ABf\colon A \to B preserves the TT-structure on XX and YY if T(f)(σ)=τT(f)(\sigma) = \tau.

In general, there is no notion of whether an arbitrary function f:ABf\colon A \to B preserves TT-structure, although such a notion may be defined in many cases. So to get a concrete construction of a concrete category, we specify whatever morphisms we like, subject to the restriction that they form a category and have the correct core given above.

Bourbaki's theory of structure, while not described in category-theoretic terms, is essentially the above.

Conversions

Morally, either of the abstract and concrete versions can be converted into the other. Technically, there are some restrictions.

Abstract to concrete

Given a category CC and a faithful functor U:CSetU\colon C \to Set, we may define a type TT of structure on sets as follows:

For each set AA, consider the essential fibre of UU over AA, the collection of pairs (X,f)(X,f) where XX is an object of CC and f:U(X)Af\colon U(X) \to A is a bijection. We consider two such pairs (X,σ)(X,\sigma) and (Y,τ)(Y,\tau) to be equivalent if there is an isomorphism h:XYh\colon X \to Y in CC such that U(h);τ=σU(h) ; \tau = \sigma. (Because UU is faithful, any such hh must be unique.) Define T(A)T(A) to be the quotient set of the essential fibre modulo this equivalence relation. That is, a TT-structure on AA is an equivalence class [(X,σ)][(X,\sigma)].

Given a bijection f:ABf\colon A \to B, we must define T(f):T(A)T(B)T(f)\colon T(A) \to T(B). So given (X,σ)(X,\sigma) as above, let T(f)T(f) map [(X,σ)][(X,\sigma)] to [(X,σ;f)][(X,\sigma;f)] in T(B)T(B). It's easy to check that this is well defined as a function from T(A)T(A) to T(B)T(B); we can also check that this makes TT into a functor and that the abstract and concrete definitions of whether a bijection preserves TT-structure agree.

Technicality: If CC is a large category, then T(A)T(A) might be a proper class instead of a set. In this case, we can pass to a larger universe; it is not essential for T:Set SetT\colon Set_\cong \to Set that both copies of SetSet be the same size. But for the above description to make sense as it is, we must require that UU have essentially small fibres.

Concrete to abstract

Given a type TT of structure on sets, we cannot quite reconstruct the category CC, but we can reconstruct its core C C_\cong. That is, we can say what the objects and isomorphisms of CC are, if not the morphisms of CC in general.

An object of CC is simply a pair (A,σ)(A,\sigma) consisting of a set AA and an element σ\sigma of T(A)T(A). Given two such objects, an isomorphism from (A,σ)(A,\sigma) to (B,τ)(B,\tau) is simply a structure-preserving map from AA to BB, that is a bijection f:ABf\colon A \to B such that T(f)(σ)=τT(f)(\sigma) = \tau. Then it is straightforward to check that this defines a groupoid C C_\cong. This groupoid, the groupoid of TT-structured sets, is naturally equipped with a faithful forgetful functor U:C SetU\colon C_\cong \to Set, given by U(A,σ)AU(A,\sigma) \coloneqq A.

While defining isomorphisms of structured sets is an exact science, choosing more general morphisms of structured sets is something of an art. In principle, we may define a (not the!) category of TT-structured sets by picking, for each (A,σ)(A,\sigma) and (B,τ)(B,\tau), a collection Hom σ,τ(A,B)Hom_{\sigma,\tau}(A,B) of functions from AA to BB, such that:

  • whenever fHom σ,τ(A,B)f \in Hom_{\sigma,\tau}(A,B) and gHom τ,υ(B,C)g \in Hom_{\tau,\upsilon}(B,C), then f;gHom σ,υ(A,C)f ; g \in Hom_{\sigma,\upsilon}(A,C);

  • the identity map on AA belongs to Hom σ,σ(A,A)Hom_{\sigma,\sigma}(A,A); and

  • a bijection ff from AA to BB is an isomorphism (as defined above) if and only if both fHom σ,τ(A,B)f \in Hom_{\sigma,\tau}(A,B) and f 1Hom τ,σ(B,A)f^{-1} \in Hom_{\tau,\sigma}(B,A).

The last condition states precisely that the underlying groupoid of any concrete category of TT-structured sets is the groupoid of TT-structured sets.

Any category of TT-structured sets is still (like the groupoid of such sets) a concrete category.

Back and forth

If we start with a type TT of structures on sets, construct from this a groupoid C C_\cong and a faithful functor U:C SetU\colon C_\cong \to Set and then construct from this another type TT' of structures, then TT' will be equivalent to TT in the sense that there is a natural isomorphism between them as functors from Set Set_\cong to SetSet.

If we start with a category CC and a faithful functor U:CSetU\colon C \to Set, construct from this a type of structures T:Set SetT\colon Set_\cong \to Set, and then construct from this a groupoid C C_\cong with a faithful functor U:C SetU\colon C_\cong \to Set, then C C_\cong will in fact be the core of CC, with U:C SetU\colon C_\cong \to Set to restriction of U:CSetU\colon C \to Set to this core, up to equivalence of categories.

(Do we need proofs?)

Thus the abstract and concrete approaches to structured sets are equivalent, except that the concrete approach does not include a specification of what are the noninvertible morphisms between structured sets.

Examples

Almost everything in contemporary mathematics is an example of a structured set; here we list only a few representative ones (and perhaps also some exceptions).

Structured objects

Given any category SS whatsoever, we may define a type of structure on objects of SS as a functor T:S SetT\colon S_\cong \to Set to SetSet from the underyling groupoid of SS. Then any faithful functor U:CSU\colon C \to S whatsoever defines a type of structure on objects of SS (at least if its fibres are essentially small), in the same way as a concrete category defines a type of structure on sets. Indeed, we say that UU presents the objects of CC as objects of SS with extra structure.

See also

Revised on August 27, 2012 23:55:31 by Toby Bartels (98.19.40.130)