Homomorphisms as structure-preserving maps

[Hurkyl]

It's interesting you choose fiber bundles as an example. If you generalize to all bundles, the construction is purely formal -- it's called the "slice category" and makes sense for any category whatsoever.

Of course, I believe the slice category was originally inspired by the construction of bundles. But for a kind of "good" category, slicing turns out to be a special case of a particularly natural sort of construction.

 

[Fredrik]

Do "slice categories" go by some other name? I bought Goldblatt's "Topoi" book, but I can't find it in the index.

 

[Hurkyl]

How about "comma category"?

 

[Fredrik]

Pages 34-36:

If X is a category, the corresponding "arrow category", X^→ has the arrows of X as objects. The arrows of X^→ are pairs of arrows of X. For example, if f:A→B and g:C→D are arrows of X and therefore objects of X^→, an arrow from f to g is a pair (h:A→C, k:B→D) of arrows in X, such that k\circ f=g\circ h.

A comma category is pretty much the same thing, except that all the arrows have the same domain, or the same codomain. If X is a category, the objects of the comma category X↓A are the arrows of X that have codomain A, and an arrow in X↓A from f:B→A to g:C→A is an arrow h:B→C in X such that g\circ h=f.

The objects of the comma category X↑A are the arrows of X that have domain A, and an arrow in X↑A from f:A→B to g:A→C is an arrow h:B→C in X such that h\circ f=g.

 

[Hurkyl]

The downarrow version is the slice category. (I've heard the uparrow one called the coslice category)

If T is the category of spaces, then T/X is precisely the category of bundles over X. The fiber bundles are a full subcategory therein.

I know, but model theory does.

Not really -- it has the same problem. Model theory tells you what the homomorphism are if and only if the particular structure you are interested in is "models of a particular theory" -- and even then you have to know which theory.

An interesting example are these two alledged theories of monoids:

Theory 1: A monoid consists of a set X with a binary operator * such that

• a*(b*c) = (a*b)*c
• There exists an element e such that e*a = a*e = a

Theory 2: A monoid consists of a set X with a binary operator * and constant e such that

• a*(b*c) = (a*b)*c
• e*a = a*e = a

Both theories define the class of monoids. However, they define different classes of homomorphisms. As a particular example, consider the multiplicative monoid (Z,*) of integers. The function f(x)=0 is a homomorphism of models of the first theory, but not of the second theory.

A similar example is notorious in ring theory -- if a ring has a multiplicative unit, does a homomorphism have to map it to a multiplicative unit? Differing conventions give different answers.



It's common to define structures to be models of a particular choice of first-order theory. If you do so, then obviously model theory tells you what the homomorphisms are.

Of course, the same is true of category theory. If you define structures as "objects in a category", then obviously category theory tells you what the homomorphism are.




Incidentally, I'm reminded of the situation of "modules over a graded ring". I don't know the history well so I might be telling it wrong, but as I understood it, at one time there were several possibilities for what precisely that should mean. It wasn't until the theory of Abelian categories was applied to module theory that things became obvious.

 

[Fredrik]

If T is the category of spaces, then T/X is precisely the category of bundles over X. The fiber bundles are a full subcategory therein.

Do you mean topological spaces? Does "/X" mean what I wrote as "↓X"? Don't we need to at least restrict it to only include epic arrows?

This is how I think of fiber bundles. Every surjection \pi:E\rightarrow B, partitions its domain into disjoint subsets of the form \pi^{-1}(b) with b\in B. This surjection is all we need to define a fiber bundle in the category of sets. If we add the requirements that E and B are topological spaces, and require that \pi is continuous, we get a fiber bundle in the category of topological spaces. And we can of course do something very similar with manifolds.

Are you distinguishing between "bundles" and "fiber bundles"? I suppose we could call what I just described "bundles" and reserve the term "fiber bundle" for those cases when all the \pi^{-1}(b) are isomorphic. Is that what you're doing?

Not really -- it has the same problem. Model theory tells you what the homomorphism are if and only if the particular structure you are interested in is "models of a particular theory" -- and even then you have to know which theory.
...
It's common to define structures to be models of a particular choice of first-order theory. If you do so, then obviously model theory tells you what the homomorphisms are.

I understand that model theory is only guaranteed to answer the question when we've been given exact information about which symbols are to be considered part of the structure. But that covers a lot of cases, and it's not clear (to me) how far this can be generalized. I would be very surprised if it can't be generalized to at least include metric spaces and vector spaces, and I expect that it can also be generalized to manifolds and fiber bundles.

Of course, the same is true of category theory. If you define structures as "objects in a category", then obviously category theory tells you what the homomorphism are.

A part of the reason why I want to define structures as "sets with additional stuff" is...physics. For example, suppose that we're trying to define a new theory of physics, and that this specific theory is built up around a vector space. The theory is defined by a set of axioms that tells us how to interpret some of the mathematics as predictions about results of experiments. Now it would be interesting to find out which other vector spaces we could have used in the definition of the theory. If we define our isomorphisms as structure-preserving bijections, we're guaranteed that isomorphic structures will work equally well in the theory. If we define them by choosing some random bunch of functions that are consistent with the category theory requirements on "arrows", it's not at all clear that isomorphic objects in the category work equally well in the theory.

I'm aware that my approach wouldn't give us all the structures we could have used in the theory. For example, except for some issues with what coordinate systems we're allowed to use, SR works equally well with spacetime defined as a vector space instead of as a manifold. Structure-preserving maps don't tell us that, but then neither does category theory.

 

[Hurkyl]

Do you mean topological spaces? Does "/X" mean what I wrote as "↓X"? Don't we need to at least restrict it to only include epic arrows?

Yes, that's what I meant by /X. The general definition of "bundle" I'm familiar with does not restrict to epic arrows; certainly the slice category must not.

Are you distinguishing between "bundles" and "fiber bundles"? I suppose we could call what I just described "bundles" and reserve the term "fiber bundle" for those cases when all the \pi^{-1}(b) are isomorphic. Is that what you're doing?

That's the distinction I'm used to -- but with the added condition that a fiber bundle is also supposed to be locally trivial.

But that covers a lot of cases, and it's not clear (to me) how far this can be generalized. I would be very surprised if it can't be generalized to at least include metric spaces and vector spaces,

Universal algebra already covers vector spaces over a particular field: you just throw in all of the scalars as unary operators, and an axiom for every arithmetic relation between scalars.

"Essentially algebraic theories" cover the case when the ring of scalars is not fixed, giving the theory of "a module over a ring": it has two basic types: the type of module elements and the type of scalars.

If you want to restrict to "a vector space over a field" you, of course, need a non-algebraic axiom that says the ring is actually a field. But this is still an ordinary first-order theory with two types.

Pseudo-metric spaces are similarly easy to encode as an essentially algebraic theory, if you allow distances to lie in an arbitrary ordered ring. Then, you just say that you're only interested in models whose ring of distances happens to be the real numbers. First-order logic let's you add an axiom to insist on non-degeneracy. Infinitary or second-order logic would let you add axioms insisting the ring of distances really is the real numbers, if you insisted on such a thing.

If we define our isomorphisms as structure-preserving bijections, we're guaranteed that isomorphic structures will work equally well in the theory.

Hrm. I hope what follows isn't going off on a tangent!

For the record, in any case I can imagine, any bijection of sets gives a structure-preserving map of sets with structure -- you just use the bijection to translate the structure on the domain into a structure on the codomain.

e.g. Suppose I have a topological space X and a random bijection f:|X| -> S. I can define a topological space Y such that |Y|=S, and whose open sets are the f(U) where U is open in X. f then represents a homeomorphism X -> Y.

I assert that this implies there are only three interesting aspects of the notion of isomorphisms of sets with structure:

• What is the automorphism group of a particular set with structure? (i.e. what are its symmetries?)
• What are the isomorphism classes of structures on a particular set?
• Given an isomorphism class, what is its cardinality?

and any other question is a "trivial" fact, in the sense it is entirely about bijections of sets, and has nothing to do with any notion of added structure.

I'm not sure if this is useful for your purpose?

 

[Hurkyl]

It might not be a useful shift in perspective, but I claim that the category-theoretic translation of what you've been saying is that you are trying to find convenient ways to construct categories, or at least groupoids. (in a groupoid, everything is an isomorphism)

The kinds of constructions you've been focusing on, I think, all turn out to be ways to present a category T -- e.g. for a unviersal algebra, the arrows of T might consist of all formal functions modulo equational axioms -- and the "model theory" of T consists of saying that a structure is a kind of functor T --> Set, and homomorphisms of structures are natural transformations.

(If you unfold the definitions, the definition of functor turns formal functions into real functions obeying the axioms, and the definition of natural transformation says that a homomorphism must preserve the operations)


I think the benefit, if there is one, of changing perspective to "How do I write down a category?" is that it gives you the flexibility to construct them in other fashions -- e.g. by taking existing categories you're happy with, and from them building a new category.

Or, by allowing you to "forget" the forgetful functor that turns your structures into sets -- modifying structure can be awkward at times if you insist on representing everything by sets. And physicists are often in the business of trying to eliminate superfluous structure from the mathematical structures they create.

 

[Fredrik]

Universal algebra already covers vector spaces over a particular field: you just throw in all of the scalars as unary operators, and an axiom for every arithmetic relation between scalars.

I'm familiar with that idea, or at least the first part of it (one unary operation for each scalar), but it makes me uncomfortable because we seem to be talking about first-order logic with uncountably many symbols. I don't know if that's OK or not. It seems weird. I thought everything was supposed to be simple in these languages. The language of set theory has only one symbol in addition to the ones that all first-order languages have in common. The language of group theory has one or three, depending on convention. Do we really want the language of vector space theory to have one symbol for each real/complex number? Doesn't it make more sense to just have one symbol for the scalar multiplication function, and generalize the concept of structure/model to involve more than one set? (See below for some clarification of what I mean).

"Essentially algebraic theories" cover the case when the ring of scalars is not fixed, giving the theory of "a module over a ring": it has two basic types: the type of module elements and the type of scalars.

If you want to restrict to "a vector space over a field" you, of course, need a non-algebraic axiom that says the ring is actually a field. But this is still an ordinary first-order theory with two types.

Pseudo-metric spaces are similarly easy to encode as an essentially algebraic theory, if you allow distances to lie in an arbitrary ordered ring. Then, you just say that you're only interested in models whose ring of distances happens to be the real numbers. First-order logic let's you add an axiom to insist on non-degeneracy. Infinitary or second-order logic would let you add axioms insisting the ring of distances really is the real numbers, if you insisted on such a thing.

I don't really understand what you're saying here, but I think the natural way to define metric spaces as structures would be to just allow more than one set in the definition of structure/model. Instead of associating a n-place predicate symbol with a function from Xⁿ into X, we can associate it with a function from Xⁿ into Y.

Maybe there are logical reasons why we shouldn't do that, but at the moment, I suspect that the only reason I haven't seen this done in the books I've read parts of (Enderton, Rautenberg, Kunen) is that it would make it harder to explain first-order logic.

For the record, in any case I can imagine, any bijection of sets gives a structure-preserving map of sets with structure -- you just use the bijection to translate the structure on the domain into a structure on the codomain.

I'm thinking that a structure-preserving map always preserves the relations/operations associated with the symbols of the language, and that if we take them (or any kind of functions) as homomorphisms, the corresponding isomorphisms are always bijective. So when we're dealing with sets, a function is "my kind of isomorphism" if and only if it's bijective, since there are no relations/operations to preserve.

e.g. Suppose I have a topological space X and a random bijection f:|X| -> S. I can define a topological space Y such that |Y|=S, and whose open sets are the f(U) where U is open in X. f then represents a homeomorphism X -> Y.

I assert that this implies there are only three interesting aspects of the notion of isomorphisms of sets with structure:

• What is the automorphism group of a particular set with structure? (i.e. what are its symmetries?)
• What are the isomorphism classes of structures on a particular set?
• Given an isomorphism class, what is its cardinality?

and any other question is a "trivial" fact, in the sense it is entirely about bijections of sets, and has nothing to do with any notion of added structure.

I'm not sure if this is useful for your purpose?

I don't know. You seem to be saying just that any bijection is structure-preserving if we get to choose the structure of the codomain. I think I'm only interested in situations where the structure of the codomain has been specified in advance, and we're supposed to determine if the two sets with structures are equivalent.

 

[QuarkHead]

Well, this is an interesting thread. Mind if I stick in my two-pennyworth? If this has been covered already, or if the discussion has moved on under its own momentum, forgive me; I am just going by the OP and a sampling of the responses.

Suppose that \mathcal{C} is a category with X,\,\,Y,\,\,Z \in \mathcal{C}.

Further suppose that f:X \to Y, \,\, g: Y \to Z \in \mathcal{C}. Then, essentially by definition g \circ f: X \to Z.

By definition, for all X,\,\,Y \in \mathcal{C} there exist arrows id_X: X \to X \in \mathcal{C} such that id_X \circ f= f and id_Y:Y \to Y such that g \circ id_Y = g.

Let's take arrow composition as a closed operation (it is) and associative (it is). But we may not assume, in general, that for all f: X \to Y \in \mathcal{C} there exists f': Y \to X such that f' \circ f =f \circ f' = id_X, then I define the category of arrows f : X \to Y (generically) as a monoid; id est this category Arr has the structure of a monoid.

Now define the functor F: \mathcal{C} \to \mathcal{D} such that F(f \circ g) = F(f) \circ F(g) and F(id_X) = F_{id_X} which is no more (or less) than to say that the the functors that take Arr onto Arr is a generalized monoid homomorphism.

 

[Hurkyl]

I don't know. You seem to be saying just that any bijection is structure-preserving if we get to choose the structure of the codomain. I think I'm only interested in situations where the structure of the codomain has been specified in advance, and we're supposed to determine if the two sets with structures are equivalent.

I may be going too far afield so I'll just briefly sketch what's going on. (But I can go into more detail if you ask)

If you choosing a representative of each isomorphism class of sets, and you choose a specific bijection from each set to the representative of its class, you can reduce all questions about bijections to questions about the automorphism group of the representative.

Once we add structure to our sets, the above choices allow us to represent any set with structure by a structure on the representative -- and any isomorphism of sets with structure becomes an isomorphism of two (possibly different) structures on the representative set.

The entire group of bijections on the set S acts on the set of structures on S, and you can do your favorite group-theoretic things -- split structures into orbits (i.e. isomorphism classes), look at the stabilizer of a structure (i.e. its symmetry group), identify the elements of an isomorphism class with elements of a quotient of the group of bijections, and so forth.

 

[yossell]

V. interesting discussion, though I'm not following all of it.

it makes me uncomfortable because we seem to be talking about first-order logic with uncountably many symbols.

Such languages have little to do with anything one could speak or practically reason with - but they are formally well defined, though weird; since your primary interest is not linguistic but a desire to spell out an appropriate, mathematical notion of structure, perhaps you do not need to rule it out. From the point of view of treating structures as n-tuples, it would have to involve an ordinal-indexed tuple instead. Perhaps there would be concrete problems defining a structure preserving mapping between the two?

Fredrik, you've toyed with the model theoretic way of defining structure, but it seems you've shied away from it or don't think it applies in certain cases. Hurkyl's raised some issues, but I'm not sure what the problems are. For instance:

... I think the natural way to define metric spaces as structures would be to just allow more than one set in the definition of structure/model. Instead of associating a n-place predicate symbol with a function from Xⁿ into X, we can associate it with a function from Xⁿ into Y.

I'm not sure what you thought the problem with treating metric spaces as models was so I'm not sure I've got the suggestion: structures/models began as n-tuples, so there was already more than one set in the definition; is the thought that you have more than one domain? I.e. (X, Y, R, O...)? And, in particular, this being a metric space, is the thought that Y be the real numbers? THe n-place symbol you're thinking of being the distance function of the metric space?

There are languages that have different sorts of variables, x1, x2, x3.. and y1, y2, y3..., and in the model theory for such languages introduces two sets for the domains of these two languages. There's not much fuss made of them because a two sorted language can be replaced by a one sorted language + two new predicate symbols F and G, and quantification over a sort treated as a standard restricted quantification over an F or G. In the model theory, there will be just one set for the domain, but two new places in the n-tuple. Either presentation is regarded as ok.

However, if my guess about what you have in mind is right, (if not, ignore) then Y can't just be a mere domain - it's got to be something that has the same structure as the real numbers, and which has certain operations and properties defined on it. I don't think that's a fatal drawback to this approach, though - one just has to remember that, after a bit, parts of maths rely on other parts of maths; it's just that these other parts have to be included in the structure.

 

[Fredrik]

I'm not sure what you thought the problem with treating metric spaces as models was so I'm not sure I've got the suggestion: structures/models began as n-tuples, so there was already more than one set in the definition; is the thought that you have more than one domain? I.e. (X, Y, R, O...)? And, in particular, this being a metric space, is the thought that Y be the real numbers? THe n-place symbol you're thinking of being the distance function of the metric space?

Yes, that's the idea. I was thinking that if we take the "structure" to have two domains, X and \mathbb R, we can associate a 2-place predicate symbol with the distance function d:X\times X\rightarrow\mathbb R.

However, if my guess about what you have in mind is right, (if not, ignore) then Y can't just be a mere domain - it's got to be something that has the same structure as the real numbers, and which has certain operations and properties defined on it.

I agree. The axioms that d is supposed to satisfy won't make sense otherwise. This makes things pretty complicated. We seem to need some recursive definition of "structure" to allow some of the "domains" to be previously defined structures.

 

[yossell]

This makes things pretty complicated. We seem to need some recursive definition of "structure" to allow some of the "domains" to be previously defined structures.

I don't know if it's so bad. When a distance function is explained as a function from n-tuples to reals, we might say that the theory of real numbers is implicitly understood or appealed to. Though the axioms for the real numbers don't appear explicitly in a presentation of metric spaces, perhaps they're there in the background. So the models you'll need for to be the structures in the metric spaces will have to be models for the full theory - including the background stuff that introduces the real numbers and axiomatizes them.

I'm not sure I see a problem for your approach in this case.

But I thought one thing you might not like is that models are very sensitive to the linguistic formulation of the theory. Whether you formulate arithmetic in a language without any constants, and refer to numbers using descriptions, such as the successor of the successor of the number that is not the successor of any other, or whether you include all the constants 0, 1, 2, 3, 4...; we feel is an irrelevant difference. But it shows up in the models for the two theories.

 

[Hurkyl]

Anyways, back to the original goal...



Recall the example of fields -- you didn't need to invent a "field structure" to talk about field homomorphisms. You just recognize that every field has an associated ring structure and is completely determined by it, and a homomorphism of fields is the same thing as a homomorphism of the ring structures. The category of fields is a full subcategory of the category of rings.

Manifolds have the same relationship to topological spaces.



Some notions related to that of topological spaces:

• A simplicial set is an algebraic structure that can be viewed as an encoding of how to build a topological space out of simplices. The drawback is that many simplicial sets describe the same topological space. (There are spaces that can't be described in this way, but I don't think you'd ever want to look at them. )
• A locale is a category-theoretic reformulation of the notion of topological space. The notion is slightly different, in a good way or in a bad way depending on your POV. While it is easy to describe a locale as an algebraic object, the homomorphisms go "backwards".
• A frame is a locale, but homomorphisms of frames go in the opposite direction than homomorphisms of locales, so they fit better into the way you want to describe things.

My earlier example of a "Euc-set" is related to manifolds. You can put a Grothendieck topology on the category of Euclidean spaces, which makes it a site. You can then consider the topos of all sheaves on that site. The manifolds ought to be a full category of this topos, although there will be other objects in it too (e.g. orbifolds). (This sort of construction should be described in your book on topoi)

A sheaf on Euc is the same thing as a "continuous Euc-set". Either way, the notion is mainly algebraic -- but the bit of being "continuous" may put a wrinkle in your plans.

(There may be technical details I'm overlooking due to the fact that Euc is not Cartesian)

 

[Fredrik]

I don't know if it's so bad. When a distance function is explained as a function from n-tuples to reals, we might say that the theory of real numbers is implicitly understood or appealed to. Though the axioms for the real numbers don't appear explicitly in a presentation of metric spaces, perhaps they're there in the background. So the models you'll need for to be the structures in the metric spaces will have to be models for the full theory - including the background stuff that introduces the real numbers and axiomatizes them.

Very good point. I don't know why I didn't think of it myself.

Recall the example of fields -- you didn't need to invent a "field structure" to talk about field homomorphisms. You just recognize that every field has an associated ring structure and is completely determined by it, and a homomorphism of fields is the same thing as a homomorphism of the ring structures. The category of fields is a full subcategory of the category of rings.

It seems to me that we can go even further. Consider the class of all structures associated with the language/lexicon/signature {·,i,e}, where · is a binary operation symbol (a 2-place predicate symbol), i is a unary operation symbol and e is a constant symbol. We can turn this class into a category C by choosing the arrows to be structure-preserving maps. Then Grp is a subcategory of C.

Suppose we also define the category D of all structures associated with the signature {·}, with structure-preserving maps as arrows. This is the category of magmas. Now the group axioms imply that every magma homomorphism between groups is a group homomorphism. So just as the field homomorphisms are determined by the ring structure of the fields, group homomorphisms are determined by the magma structure of the groups.

(I chose to talk about groups/magmas here instead of fields/rings, because the fact that the multiplicative inverse operation isn't defined on the whole domain makes things awkward. Seems like the formal definition of "structure" should also mention such possibilities).

My earlier example of a "Euc-set" is related to manifolds. You can put a Grothendieck topology on the category of Euclidean spaces, which makes it a site. You can then consider the topos of all sheaves on that site. The manifolds ought to be a full category of this topos, although there will be other objects in it too (e.g. orbifolds). (This sort of construction should be described in your book on topoi)

I'll have a look in the book. Right now I understand almost nothing of what you just said.

 

[Fredrik]

I'm going to take another crack at a definition of "structure" that's general enough to include metric spaces and vector spaces. First, a few comments about the syntax of first-order logic (mainly to explain my terminology).

A first-order language is defined by an alphabet (a list of allowed symbols) and a set of rules that tells us how to construct formulas (finite sequences of symbols that we can think of as representing logical propositions). The alphabet consists of a bunch of symbols that all first-order languages have in common \{\lnot,\rightarrow,\forall\}\cup\{v_0,v_1,\dots\} (the v_n are called variable symbols), and a set of additional symbols. This set is what defines the language we're dealing with. The equality sign = may be included in this set, but it doesn't have to be. The set of all other members of this set is called the signature of the language. A signature L is always a union of a set C and sets R₀, O₀, R₁, O₁,...

L=C\cup\bigcup_{n=0}^\infty (R_n\cup O_n)

The members or C are called constant symbols. For each natural number n, the members of R_n are called relation symbols of arity n, and the members of O_n are called operation symbols of arity n.

I deliberately omitted parentheses, because they're not needed if we use Polish notation, e.g. we write =+235 instead of 2+3=5. It's useful to introduce abbreviations that use parentheses and many other symbols, such as \exists and \land, but I'm not going to saying anything more about that.

It's time to define "structure". I'll start with the simpler kind, the one that isn't general enough to even include metric spaces. Recall that a relation on X of arity n is a subset of Xⁿ, and that an operation on X of arity n is a function from Xⁿ into X, i.e. a subset f of Xⁿ×X that satisfies these two conditions:

F1. If (x,y) is in f and (x,y') is in f, y'=y.
F2. If x is in Xⁿ, there's a y in X such that (x,y) is in f.

I will call a subset f of Xⁿ×X that satisfies F1, but not necessarily F2, a partial operation on X of arity n. (Note that this makes all operations partial operations).

A structure for the language defined by the equality symbol = and the signature L, is a triple (S,L,I), where I is a function that assigns a member of S to each constant symbol, and for each natural number n assigns a relation on S of arity n to each relation symbol of arity n and a partial operation on S of arity n to each operation symbol of arity n. The set S is called the domain of the structure.

The reason why the definition speaks of partial operations instead of operations is that I want fields to be structures even when we explicitly include a symbol for the multiplicative inverse operation.

Suppose that (S,L,I) and (S',L,I') are structures for the same language. A function f from S into S' is said to be an L-homomorphism if

H1. f\circ I=I'
H2. For each natural number n, f\circ Im=I'm for all m in O_n.
H3. For each natural number n, each x₁,...,x_n and each r in R_n, Ir(x_1,\dots,x_n)\in S if and only if I'r(f(x_1),\dots,f(x_n))\in S'.

A category of L-structures can be defined with L-structures as objects and L-homomorphisms as arrows. (I called this the "standard" category of L-structures first, but I realized that it isn't. For some choices of L, the standard category of L-structures has L-homomorphisms as arrows, but for other choices it doesn't. Topological spaces is a good example of a category where the arrows are not L-homomorphisms, because the arrows are continuous maps, not open maps).

We can define a subclass of the class of all L-structures by imposing additional axioms, and we can turn it into a category by taking the arrows to be those arrows in the class of all L-structures that don't contradict the axioms. For example, the category of monoids and the category of groups are both subcategories of the standard category of {·}-structures.

Now let's consider structures with multiple domains. I'll put that in a separate post. (I have something else that I'm going to do first, so I'm not going to do it right away).

 

[Fredrik]

I think I see why the books never define structures with multiple domains. The language gets really awkward when we try to define partial relations and operations over several sets. It seems pretty obvious that it can be done, but it's a real pain.

 

[Hurkyl]

How about the following? It is a definition of something called a sketch:

A sketch consists of:

1. A set of types
2. A set of formal function symbols with domain and codomain among the types
3. A set of assertions that one string of formal functions symbols is equal to another
4. A set of assertions that a formal function symbol is the identity
5. A set of assertions that one type is the "product" of some others, and a particular set of formal functions is the list of projections
6. A set of assertions that one type is the equalizer of a pair of formal functions, and a particular formal function is the inclusion
7. A set of assertions that one type is the "disjoint union"of some others, and a particular set of formal functions is the list of injections
8. A set of assertions that one type is the coequalizer of a pair of formal functions, and a particular formal function is the projection

(Plus the obvious axioms on how the domain and codomain of function symbols relate to everything)

A model of a sketch consists of:

1. A set for each type
2. A function for each formal function symbol, with the appropriate domain and codomain
3. For each identity assertion, the corresponding function should be the identity.
4. For each equation of strings of formal function symbols, the corresponding composites of functions should be equal
5. For each product assertion, the type should be bijective to the Cartesian product of the others, and the formal functions should be projections
6. blah
7. blah
8. blah

And a homomorphism of models consists of one function for each formal type, whose domain and codomain are the corresponding sets in the two models. These homomorphisms should commute with all formal functions; i.e.

\varphi_T \circ f_1 = f_2 \circ \varphi_S​

where \varphi is the homomorphism, \varphi_S,\varphi_T are the components corresponding to the formal types S and T, f_1, f_2 are the functions corresponding to the formal function f : S \to T.


The assertions are powerful enough to specify that certain functions must be injective or surjective. Together with products, this let's you talk about relations -- e.g. a binary relation on S and T is just a subtype of SxT; that is, injective map R --> SxT. It's also enough to talk about the union and intersection of subtypes, so you get "and" and "or" as well.

Equational axioms ala universal algebra fit into this too. e.g. the identity axiom of groups ex=x is the same as saying that the composite

G \xrightarrow{(e, 1)} G \times G \xrightarrow{\mu}​

is equal to the identity, where e is the nullary function that picks out the identity element of G, 1 is the identity function on G, and \mu is multiplication. The assertion implies the function

x \mapsto \mu(e,1)x = \mu(e, x) = ex​

is the identity function; so x = ex.



I suppose you wouldn't be surprised to hear this is category theory. A sketch is:

1. A small category
2. A set of assertions that a particular cone must be a limit in any model
3. A set of assertions that a particular cocone must be colimit in any model

Talks of cones and limits is a compact way to describe what I was saying about products and equalizers. #1 could be weakened to a presentation of a category via a graph of generators and relations, much like I did in the above.

Models of a sketch are functors satisfying the assertions, and homomorphisms of models are natural transformations of functors.

 

[Hurkyl]

This time I'm not trying to be gratuitously category-theoretic. It's just that, this time, a sketch really is the algebraic idea that's trying to be captured here.


The point behind having a category is to be the algebraic structure that not only contains all of our function symbols, but also knows when two different composites of function symbols should be equal. This category can be conveniently presented by a graph of generators modulo relations -- this is rather similar to how one writes a presentation of, say, a group.



The point behind having limits (e.g. products, equalizers, pullbacks) is several-fold:

With products, we can include n-ary function symbols in a way no different than ordinary functions. We can even let n be an infinite cardinal!

We can define types by equations.

We can define monomorphisms and talk about subtypes -- including subtypes of products. Such subtypes can be viewed as relations.

We can take the intersection of subtypes. Among other things, when viewed as relations, this gives us the logical connective "and".



The point behind additionally having colimits (e.g. disjoint unions, quotients) is several-fold:

We get disjoint unions.

It let's us present define types via generators and relations. The coequalizer of two function symbols f,g:X --> Y is the type whose elements are named by elements of Y, but also satisfy the relations f(x)~g(x).

We can talk about surjective function symbols.

Together with limits, we can talk about the union of subtypes. Among other things, this gives us the logical connective "or".

Together with limits, we can talk about the image of a function symbol.

 

[quasar987]

Homotopy types: The homotopy category is not concrete -- roughly speaking its objects cannot be represented as "sets with structure", no matter clever a notion of structure you might come up with.

That's interesting.. i wonder how one goes about proving such a bizarre statement.

(I imagine that the homotopy category has as its objects the topological spaces and as its morphisms the homotopy classes of continuous maps)

By the way, I have studied some mathematical logic since the other discussion, so I'm now familiar with how structures/algebras are defined in model theory/universal algebra. [...]

What reference would you recommend ?

 

[Landau]

(I imagine that the homotopy category has as its objects the topological spaces and as its morphisms the homotopy classes of continuous maps)

Yes.

That's interesting.. i wonder how one goes about proving such a bizarre statement.

The precise statement is that \textbf{Toph} is not concretizable, meaning there does not exist a faithful functor F:\textbf{Toph}\to\textbf{Set}. A proof of this statement can be found here.

 

[Fredrik]

What reference would you recommend ?

Sorry, I didn't see the question until now. I first read about first-order formal languages, "structures" and what it means for a set of sentences to "logically imply" another sentence, in Enderton, and in Rautenberg. I don't think either of them is really easy to follow, so it was really helpful to have access to both. Then I bought Kunen's book "Foundations of mathematics". That's a very good book, so I can recommend it without reservations. But I got the feeling that a lot of the stuff that I found easy to understand would have been quite hard to understand if I hadn't read the about the stuff I mentioned above in Enderton/Rautenberg first.