Homomorphisms as structure-preserving maps

[Fredrik]

Homomorphisms as "structure-preserving" maps

A function f between groups is said to be a homomorphism if it "preserves" the product in the sense that f(xy)=f(x)f(y). A function f between fields is said to be a homomorphism if it "preserves" both addition and multiplication in the sense that f(xy)=f(x)f(y), f(x+y)=f(x)+f(y). Homomorphisms are often described as "structure-preserving maps". We should be able to define homomorphisms as structure-preserving maps, if we define "structure" first, and also what it means for the structure to be "preserved". I suggest the following definition:

We define a structure as a 4-tuple (S,R,O,C), where S is a set, R is a set of relations on S, O is a set of operations on S, and C is a subset of S. The members of C are called constants. If (S,R,O,C) and (S',R',O',C') are structures, a map f:S→S' is said to be structure preserving if the following holds for all x,y,x₁,...,x_n in S:

a) If r is a relation in R such that (x,y) is in r, then there's a r' in R' such that (f(x),f(y)) is in r'.
b) For each n=1,2,..., if m is an operation of arity n in O, then f(m(x₁,...,x_n))=m(f(x₁),...,f(_n))
c) If x is in C, then f(x) is in C'.

(A relation of arity n is a subset of Sⁿ. An operation of arity n is a function from Sⁿ into S).

Unless I missed something essential (and I might have), this should take care of the definition of "homomorphism" for groups, rings, fields, topological spaces and a lot more, but not for metric spaces, vector spaces, manifolds and a lot more. A metric space involves a function that isn't an operation. A vector space also involves a function (scalar multiplication) that isn't an operation, and it also involves a previously defined structure (a field). And manifolds...uh...I don't even want to think about it.

What I'd like to know if there is a more general definition that covers these other things as well. I know the term homomorphism is used for vector spaces, but I don't think I've heard it used for metric spaces. I've heard people say that diffeomorphisms are isomorphisms between manifolds, but perhaps they just meant isomorphisms as they are defined in category theory (where they don't have to be structure preserving).

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. I understand the reason why texts on those subjects talk about relation symbols instead of relations and so on, and I feel that we don't need to do that here, as long as we're just looking for a single definition of homomorphism.

 

[Office_Shredder]

You should look into category theory

 

[Fredrik]

I'm familiar with the basic definitions of category theory, so I know that it doesn't answer my question. It can't tell us which functions are the homomorphisms of a given class of structures (e.g. groups). Instead, the choice of what functions to call homomorphims (or just morphisms) is part of what defines a category. For example, category theory allows us to define a category that consists of the class of vector spaces and all functions between vector spaces that satisfy f(x+y)=f(x)+f(y) for all x,y. This defines a category of vector spaces, just not the standard one, and its isomorphisms are group isomorphisms, not what we'd normally consider vector space isomorphisms (i.e. linear bijections).

 

[Hurkyl]

If you have any prior notion of "object with structure" and "structure-preserving map", you can collect all instances into a category. Then your prior notion of "object with structure" is now the same as the new notion of "object in that category", and similarly for maps.

You can accelerate thing by skipping the first step of trying to come up with a prior notion of structure.

The members of C are called constants.

A constant is a nullary operation -- i.e. an operation of arity 0. You don't need to treat them separately.

b) For each n=1,2,..., if m is an operation of arity n in O, then f(m(x1,...,xn))=m(f(x1),...,f(n))

m is not an element of O'; it is not an operation on S'.

c) If x is in C, then f(x) is in C'.

Merely mapping constants to constants is inadequate. e.g. in a variety of universal algebras with two constant symbols 0 and 1, the function associated to a morphism must actually satisfy f(0)=0 and f(1)=1.



Fields: Their characterization is essentially non-algebraic. I suppose you luck out because you don't care about characterizing them, and the notions of ring homomorphism between fields and field homomorphism between fields are equivalent.

Topological spaces: You have types of stuff: points and open sets. Morphisms are awkward because the induced functions work in both directions: points are mapped forwards, but open sets are mapped backwards. You could switch to the notion of Locale so that you have only one type of stuff, but the function associated to a morphism still works backwards.

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.


A diffeomorphism is indeed an isomorphism in the category of smooth manifolds. (Or, more verbosely, the category of smooth manifolds and smooth maps) The reason we have many words like "diffeomorphism", "isometry", "homeomorphism" and so forth is that we are frequently interested in several categories at once. e.g. when studying Riemann manifolds, we might be interested both in smooth metric-preserving maps as well as plain ordinary smooth maps, and from time to time even merely twice-differentiable maps!

 

[Fredrik]

A constant is a nullary operation -- i.e. an operation of arity 0. You don't need to treat them separately.

I know. Also, every operation of arity n is a relation of arity n+1, so we don't even have to treat operations separately. I chose to treat them separately to make the definition look more like the definitions in the mathematical logic books I'm reading and the definition in this book on universal algebra that I downloaded. (Except that they don't include any relations).

m is not an element of O'; it is not an operation on S'.

Merely mapping constants to constants is inadequate. e.g. in a variety of universal algebras with two constant symbols 0 and 1, the function associated to a morphism must actually satisfy f(0)=0 and f(1)=1.

D'oh. That first one was a major brain fart by me, and the second was was pretty silly too. I'm glad you caught them, because now I finally see why these books talk about relation symbols instead of relations and so on. It's not just because it has to be that way when we're dealing with first-order formal languages. It's also needed for the definition of homomorphisms that I'm trying to make. New attempt:

I define a structure to be a triple (S,R,I) where S is a set, R is a set of relation symbols such that the arity of the symbol is explicitly included in the notation (e.g. r⁽ⁿ⁾ is a relation symbol with arity n), and I is a function that assigns a relation on S of the appropriate arity to each relation symbol.

Suppose that (S,R,I) and (S',R,I') are two structures with the same relation symbols. A function f:S→S' is said to be a homomorphism if

(f(x_1),...,f(x_n))\in I'r^{(n)} \Leftrightarrow (x_1,...,x_n)\in Ir^{(n)}

for each relation symbol r⁽ⁿ⁾ of arity n and for each n=1,2,... (I think this would be a bit clearer if we treat operations and constants separately).

Fields: Their characterization is essentially non-algebraic. I suppose you luck out because you don't care about characterizing them, and the notions of ring homomorphism between fields and field homomorphism between fields are equivalent.

That's another good catch. You're quite useful. Now I'm going to have to think about whether my (new) definition allows e.g. a non-abelian division ring to be isomorpic to a field (i.e. abelian division ring).

Topological spaces: You have types of stuff: points and open sets. Morphisms are awkward because the induced functions work in both directions: points are mapped forwards, but open sets are mapped backwards. You could switch to the notion of Locale so that you have only one type of stuff, but the function associated to a morphism still works backwards.

I was thinking that S is the set and that each subset of S is a unary relation on S. You're right about the homomorphisms. My improved definition doesn't work. This makes me wonder why homeomorphic topological spaces are considered equivalent, instead of topological spaces that would be isomorphic according to my definition.

I guess what we really want is a notion of equivalence that ensures that every theorem that we derive using the properties of a specific "structure" (a concept that I still haven't defined satisfactorily) will be guaranteed to hold for any structure that's "equivalent" to the one we used.

If "structure" doesn't apply to all these things that are defined by "a set and then some", like groups, fields, topological spaces, Hilbert spaces and manifolds, then I wonder, isn't there some other term that can be used? Aren't they all special cases of a single more general concept?

 

[Fredrik]

It's OK for other people to contribute here too. (Not that I don't appreciate Hurkyl's contributions. I always do). Let's focus on one specific detail to make things easier. Why is the category of topological spaces that has continuous maps as morphisms more interesting than the category of topological spaces that has open maps as morphisms? (f:X→Y is said to be open if f(E) is open for every open E).

I've been thinking that we want the morphisms to have the property that the corresponding isomorphisms tell us when two structures are equivalent in the sense that any theorem that holds for a specific structure also holds for all isomorphic structures. Does that hold for topological spaces when the isomorphisms are continuous bijections but not when they're bijective open maps?

 

[Hurkyl]

Does that hold for topological spaces when the isomorphisms are continuous bijections

I assume you meant "homeomorphism" and not "continuous bijection"?


Incidentally, all isomorphisms in the category of topological spaces and continuous maps are also open.
Additionally, all isomorphisms in the category of topological spaces and open maps are also continuous.

 

[Fredrik]

I assume you meant "homeomorphism" and not "continuous bijection"?

Yes. I assumed those two were the same, but I guess I should have thought it through.

Incidentally, all isomorphisms in the category of topological spaces and continuous maps are also open.
Additionally, all isomorphisms in the category of topological spaces and open maps are also continuous.

So...the isomorphisms of the first category are the same as the isomorphisms of the second category. I guess that solves that problem.

I'll try to prove the things you wrote here as an exercise. Thank you again for your comments.

Edit: I'm too lazy to try hard to find an example of a continuous bijection with an inverse that isn't continuous, but unless I made a mistake, I have verified the other details.

 

[dx]

I think the only way we can have a useful general theory of 'structure preserving maps' is if that theory talks only about properties that all structure preserving maps possess, and this is the case with category theory as far as I can tell.

To me, this seems to imply that this general theory cannot define a structure preserving map as a specific type of map between sets, but only characterize them by their structure-independent features (and therefore the theorems of category theory apply to all 'structures'). For example, we require that composition of structure preserving maps φ : A → B and χ : B → C must be a structure preserving map ψ : A → C and that there exists an 'identity structure preserving map' and so on.

The reason this is powerful is kinda the same as the reason the notion of 'topological space' is powerful. It isolates and characterizes the idea of 'continuity' in a terminology which ensures that no irrelevant features of specific examples enter the description. To study continuous functions on Euclidean space, we don't need much of the information contained in the euclidean metric. So the old definition of continuity (For every epsilon, there exits a delta such that...) is 'redundant'. The modern definition of continuity (If Δ is open, so is φ^-1[Δ]) uses a terminology which does not refer to the metric at all, and applies to any topological space.

 

[Fredrik]

I think the only way we can have a useful general theory of 'structure preserving maps' is if that theory talks only about properties that all structure preserving maps possess, and this is the case with category theory as far as I can tell.

But category theory doesn't have a concept of "structure preserving" as far as I know. For example, we can define a category of groups with morphisms that don't "preserve" group multiplication.

To me, this seems to imply that this general theory cannot define a structure preserving map as a specific type of map between sets, but only characterize them by their structure-independent features (and therefore the theorems of category theory apply to all 'structures'). For example, we require that composition of structure preserving maps φ : A → B and χ : B → C must be a structure preserving map ψ : A → C and that there exists an 'identity structure preserving map' and so on.

I would like these things to follow logically from a general definition of "structure preserving". And I think my second attempt in this thread works (although it would have been clearer if I had mentioned operation symbols and constant symbols explicitly). It seems to work at least for groups, rings (and therefore also fields), modules (and therefore also vector spaces), and topological spaces. I wonder if we can also make it work for metric spaces, manifolds, fiber bundles... I have to get some sleep, but I'll think about that tomorrow.

 

[Fredrik]

Now I'm going to have to think about whether my (new) definition allows e.g. a non-abelian division ring to be isomorpic to a field (i.e. abelian division ring).

It doesn't. So that's one less thing to worry about.

 

[dx]

But category theory doesn't have a concept of "structure preserving" as far as I know. For example, we can define a category of groups with morphisms that don't "preserve" group multiplication.

In category theory, the 'structure' of the objects in a category is completely encoded in the morphisms and their compositions. So you can't say that the morphisms 'don't preserve the structure', since they define what the 'structure' is in that particular category. For example, consider a topological group. If this is viewed as an object in the category of topological spaces, there is no need for the morphisms to preserve the group structure.

I would like these things to follow logically from a general definition of "structure preserving"

Consider the definition of a topoligical space. The axioms that characterize open sets do not follow from a general definition of 'open set'. This reminds me of something that Niels Bohr said: 'A mutually exclusive relationship always exists between the practical use of any word and attempts at its strict definition'.

 

[Hurkyl]

But category theory doesn't have a concept of "structure preserving" as far as I know. For example, we can define a category of groups with morphisms that don't "preserve" group multiplication.

Then the structure that is being preserved by the morphisms isn't the group structure.


One nice concrete¹ example of a category is the category of natural numbers and matrices. The objects of this category are natural numbers, and they are only really there to serve as a reminder of when we're allowed to multiply two matrices.

But if you really want to, you can think of the arrows as structure-preserving maps. What structure? The one implicitly defined by matrix arithmetic, of course! And we can use matrices to describe "elements" and even talk about subobjects (via the rowspace of a matrix).

Of course, this category is a concrete category; it's equivalent to the category of finite-dimensional vector spaces and linear transformations. The forgetful functor sends a natural number n to the set Rⁿ, and it sends matrices to the appropriate set functions.


1: Meant in the natural language sense.

 

[Fredrik]

In category theory, the 'structure' of the objects in a category is completely encoded in the morphisms and their compositions. So you can't say that the morphisms 'don't preserve the structure', since they define what the 'structure' is in that particular category. For example, consider a topological group. If this is viewed as an object in the category of topological spaces, there is no need for the morphisms to preserve the group structure.

Then the structure that is being preserved by the morphisms isn't the group structure.

OK, that makes sense. But it makes me wonder if this is a useful point of view. The reason why the explicitly defined "structure-preserving maps" are significant is that they give us a concept of "isomorphism" that ensures that theorems derived using the properties of a specific structure (e.g. SO(3)) holds for all structures that are isomorphic to it (e.g. SU(2)/Z₂). That can be proved as a metatheorem. Is there a corresponding metatheorem about the isomorphisms we end up with when we define the structure implicitly by a choice of arrows, and what exactly does it say?

Consider the definition of a topoligical space. The axioms that characterize open sets do not follow from a general definition of 'open set'.

I don't really understand this comment. I haven't suggested that they should. What I have suggested is that the appropriate concept of "isomorphism" should come from taking the morphisms to be (explicitly) structure-preserving, i.e. in this case they should be open maps, not continuous maps. However, it also turns out that both choices give us the same isomorphisms.

 

[Landau]

I'm too lazy to try hard to find an example of a continuous bijection with an inverse that isn't continuous, but unless I made a mistake, I have verified the other details.

The standard example is
[0,2\pi )\to S^1
t\mapsto e^{it}.

 

[dx]

I don't really understand this comment. I haven't suggested that they should. What I have suggested is that the appropriate concept of "isomorphism" should come from taking the morphisms to be (explicitly) structure-preserving, i.e. in this case they should be open maps, not continuous maps. However, it also turns out that both choices give us the same isomorphisms.

A topological space is defined as a set X together with a collection of subsets of X called its 'topology', such that

i.) If A and B are in the topology, then so is their intersection.

ii.) If A_λ (λ in Λ) are in the topology, so is their union.

iii.) X and {} are in the topology.

These properties of open sets are not derived from a definition of 'open set', but merely postulated. We have an intuitive idea of what an open set is: "a set which contains all points sufficiently close to to each of its points", and such intuitve ideas are always at the back of ones mind when the language of topological spaces is being used. Otherwise it would just be a formal play with symbols.

Similarly, we have an intuitive idea of what a 'structure preserving map' is, and from that idea we abstract the essential features so that they can be discussed independently of specific examples. An isomoprhism is a morphism A → B such that there exists a morphism B → A which composes with the original map to give the identity (both ways). This is a 'categorical definition' of an isomorphism, and does not require any concrete definition of what a 'morphism' is. It is taken to be a primitive notion, and enters only as an element of the Hom(_,_) sets.

Such categorical definitions are useful because they apply to all categories. For example, if you are able to find a categorical definition of the 'direct product' or 'direct sum' of two objects, that definition can be applied to any category, and therefore the language of category theory helps us find appropriate definitions. If you want to consider objects of the form of triples (S, R, I), then category theory will help you find a natural definition of a 'product' of such objects, etc.

 

[Hurkyl]

Is there a corresponding metatheorem about the isomorphisms we end up with when we define the structure implicitly by a choice of arrows, and what exactly does it say?

In the end, I bet it simply boils down to two things (which I'm not sure are actually different):

• Theorem: If F is a functor from C to D, and f is an isomorphism in C, then F(f) is an isomorphism in D
• For any diagram drawn in a category, we can create an 'isomorphic' diagram by replacing its objects with isomorphic ones (choosing a specific isomorphism), and composing the arrows with the isomorphisms and their inverses as appropriate.

(A functor is a "structure-preserving map" between categories, if you will. It only preserves structure up to natural isomorphism, though)

Example 1: "Cartesian product" is a functor from Set x Set to Set. It immediately follows that if X and X' are bijective sets, and Y and Y' are bijective sets, then X x Y and X' x Y' are bijective sets.

Example 2:: The "singular homology" construction defines functors on the category Top of topological spaces and continuous maps. It immediately follows that homeomorphic topological spaces have isomorphic singular homology groups.


Following up on that latter example: there is a relation on continuous maps called "homotopy". This relation is an equivalence relation. It is even a "congruence" on Top: f~g implies fh~gh and kf~kg. It turns out that that homotopic maps turn into equal maps after taking singular homology. There are a variety of other purposes for which the difference between homotopy and equality is insignificant.

Therefore, it is desirable to construct a new category hTop -- the homotopy category -- by modding out by this equivalence relation. Its objects are again topological spaces, but the arrows are now equivalence classes of continuous maps. Isomorphims in this category are homotopy equivalences. An isomorphism class of objects is a homotopy type.

So to reorganize the above data, homology is a property of homotopy types; the structure of "topological space" contains a lot of irrelevant information. Homology defines a functor on hTop, and the various other purposes I mentioned can be carried out in hTop rather than in Top.

So, in these cases, the topic of interest really is this category hTop (or other related constructions). Whatever 'structure' a homotopy type consists of, that's the structure we want to study.

The problem... hTop is not concrete. This is the example I gave earlier of a category that cannot be viewed as "sets with structure". There is a theorem that any functor U:hTop->Set must not be faithful. That means there are homotopy types X and Y, and a pair of distinct arrows f,g from X to Y with the property that U(f) = U(g).

 

[Hurkyl]

I should also add you can build a formal language out of diagrams rather than logical connectives as is usually done. I imagine that in such a language, preservation of logic by isomorphism is self-evident.

I didn't pay too much attention to it, but the one construction I saw was used to prove a cute little theorem: a property (described in this language) of categories is preserved and reflected by equivalence of categories if and only if the property can be described on a blackboard. (i.e. which amounts to never asserting as a conclusion that two objects must be equal. Isomorphic is still okay)

("preserved" means that if X has the property, then so does F(X). "reflected" means that if F(X) has the property, then so does X)

 

[Hurkyl]

I've attached a diagram that expresses the proposition "A pair of objects has a product".

A model in a category C of this diagram is a functor from the 2-point category into C (i.e. a pair of objects) with the following property:

There exists a functor from the category drawn in the second diagram that is compatable with the first one (i.e. every pair of arrows X <-- Z --> Y such that X and Y were the objects selected by the first functor) with the property that:

For every functor from the third diagram compatible with the second functor:

There exists a unique functor from the fourth diagram compatible with the third. (the triangles commute)



In this language, it's immediate that the property is invariant under isomorphisms; if I replace the two objects with isomorphic ones (and choose a specific isomorphisms), I can produce compatible natural isomorphisms on all of the relevant functors by swapping those two objects for their isomorphic copy, and composing the arrows appropriately.

It's also immediately evident that if XxY is a product of X and Y, then XxY is also a product of X' and Y'. (If X' and Y' are isomorphic to X and Y)

 

[Fredrik]

• Theorem: If F is a functor from C to D, and f is an isomorphism in C, then F(f) is an isomorphism in D

I understood this part at least, but I had difficulties after that. I'll try again tomorrow.

 

[Hurkyl]

Oh, I've worked out something I wanted to mention earlier.


There is a particular kind of structure that can be defined for any small category: that of a category action, which is analogous to a group acting on a set.

A right action of the category C on a set X consists of:

• An function "domain" that maps each element of X to an object of C.
• For each arrow f : A --> B of C, there is a partial operation defined on the
  elements with domain B. (turning them into elements with domain A)
• All of the axioms needed to play nicely with composition within C

Any object A of C can be used to create a set with a right action of C as follows:

• The elements of this set are all arrows with codomain A.
• The "domain" function is the domain operation on C
• The action of an arrow is given by composition in C

(drawing pictures helps, I think)

Any arrow A --> B of C yields a "structure-preserving" homomorphism of right C-sets, turning the C-set defined by A into the C-set defined by B. (This homomorphism is again just composition)

Using this transformation, we can now view every object of the category as a set with structure. and the arrows as structure-preserving maps.


Frequently, we can get away by not taking all arrows with a given codomain, but instead those whose domain lies in some smaller set. (This trick allows us to do all of the above with many large categories)

(It's always fair to use a smaller set, but if it's too small, this representation doesn't work well; it can "forget" the difference between distinct objects and maps)

------------------------------------------------------------------------------

Interesting example: Consider again the category Mat (not a standard name) of natural numbers and matrices. In this example, it is good enough to use 1 as the domain of all of our elements.

Given any natural number n, I create a right Mat-set, which I will suggestively name Rⁿ. It's elements are all arrows whose domain is 1 and whose codomain is n -- in other words, its elements are precisely the set nx1 column vectors.

Since 1 is the only object I'm using for domains, the only operations are those coming from functions 1 --> 1, which are 1x1 matrices; i.e. scalars. The action of a scalar? Right multiply the nx1 column vector by the 1x1 matrix.

Mat is a category with extra structure -- in this case, an addition operation between parallel arrows that distributes over composition. So this addition operation applies to our elements of Rⁿ as well.

After putting together all of the category action axioms and additive category axioms, you'll find that this abstract construction has reproduced the explicit "vector space over R" structure on all of the standard finite-dimensional vector spaces Rⁿ that we're familiar with.


It turns out we've actually reproduced the entire notion of "vector space over R" if we proceed further, but I didn't want to delve into too many details at once.

 

[Hurkyl]

Ooh, let's try this recipe on another category.

Let Man be the category of manifolds.
Let Euc be the full subcategory of Euclidean spaces. (its objects are the Rⁿ, its arrows are all continuous maps between them)

Euc generates Man, so we can use it for our elements. Explicitly, a right Euc-action is a set X whose elements I will call "shapes", together with

• A function X --> N. I will call this "dimension"
• If f:R^m->Rⁿ is continuous, and x is a shape of dimension n, then xf is a shape of dimension m.
• The product is "associative": x(fg) = (xf)g, when defined.

A homomorphism of right Euc-sets is a function T with the property that

• If x is a shape of dimension n, then so is T(x).
• T(xf) = T(x)f whenever xf is defined

For any manifold M, there is a right Euc-set M whose shapes of dimension n are the continuous functions Rⁿ --> M.


Unfortunately, I'm not sure if "homomorphism" and "continuous" coincide for manifolds. There might be too many homomorphisms, but then again manifolds are nice, and topology can surprise me.

However, I am pretty sure "homomorphism" and "continuous" coincide when we consider just the Euclidean spaces. But I don't know a direct proof -- I am invoking abstract nonsense to make that conclusion. (specifically, the Yoneda lemma)

If they don't coincide, there are notions of topology for categories (e.g. Grothendieck topology), and I am nearly certain an appropriate notion of "continuous right Euc-set" would ensure that homomorphism and continuous coincide.

 

[Fredrik]

I haven't abandoned the discussion. I just feel that I need to understand categories a bit better before I continue, so I started reading a book about it.

By the way, a functor is supposed to be a pair of functions that take objects to objects and arrows to arrows, but the class of objects can be a proper class. So what do we mean by "function" here?

 

[dx]

By the way, a functor is supposed to be a pair of functions that take objects to objects and arrows to arrows, but the class of objects can be a proper class. So what do we mean by "function" here?

I'm not sure what the distinction between set and class is with regard to functions. Do we need a different notion of 'function' for classes? To me the phrase "F associates an object F(A) to the object A" seems unambiguous.

 

[Fredrik]

I'm not sure what the distinction between set and class is with regard to functions. Do we need a different notion of 'function' for classes? To me the phrase "F associates an object F(A) to the object A" seems unambiguous.

That's not a definition. It's just a comment that tells you how to think about a concept that's left undefined.

The definition goes like this: Suppose X and Y are sets and that G\subset X\times Y. The triple f=(X,Y,G) is said to be a function from X into Y if

(i) for each x\in X, there's a y\in Y such that (x,y)\in G.
(ii) \Big((x,y)\in G and (x,y&#039;)\in G\Big)\Rightarrow y=y&#039;

Alternatively, you can say that a subset G\subset X\times Y is a function from X into Y if...the same two conditions are satisfied. This defines a function to be what someone who prefers the first definition would call the graph of the function.

I've been reading in Goldblatt's book today. I think he said that we can leave functions undefined instead of set membership. I understand how that makes sense if we want to use categories as the foundation of mathematics instead of set theory, but what if we just want to use category theory to organize and generalize mathematical concepts?

 

[Hurkyl]

The notion for function is the same for classes and sets; it's just that the graph of a function whose domain is a proper class is itself a proper class.

You use functions and relations between proper classes all the time -- e.g. in ZFC, \in is a binary relation on Set, and { } is a function from Set to Set (it's the function that sends the set S to the set {S}).

Note that to even reason about proper classes, you have already implicitly chosen a formalism that permits us to talk about such things.

 

[Fredrik]

OK, I've been reading some category theory and mathematical logic, and I still don't see an answer to what I'm mostly concerned about. I thought that there would be a definition of "structure" and "structure-preserving" that covers all of the "sets with something defined on them" that we work with in mathematics.

When you study the definitions of "group", "ring" etc. you can't help noticing how similar the definitions are. It seems obvious that they're special cases of something more general. This something is called an "algebraic structure" or an "algebra". But it doesn't seem to be possible to extend this to include all of the "sets with something else defined on them" in mathematics. (I don't see how to do it for metric spaces. I can do it for modules, if I treat the scalar multiplication function as a unary operation for each scalar, but I don't know if "structures" with uncountably many operation symbols make sense).

I understand that "category" is another generalization of these concepts. While "structure" generalizes "group", "category" generalizes...uh not sure what I should call them...let's go with "L-structures and L-homomorphisms". (For example "groups and group homomorphisms". "L" is the set of symbols that distinguish one first-order language from another. I've seen it called a "language", a "lexicon" or a "signature").

It bugs me that "category" doesn't generalize "homomorphism" in a way that explains why the definitions of the standard choice of arrows in so many categories look so similar. For example, I was able to guess the appropriate way to define the arrows in the category of fiber bundles, and it certainly wasn't the definition of "category" that helped me do that. It was my intuition about what "structure-preserving" means. I just feel that there must be a way to turn that intuition into a definition, and it surprises me a lot that there doesn't seem to be a textbook answer to this.

 

[Landau]

It bugs me that "category" doesn't generalize "homomorphism" in a way that explains why the definitions of the standard choice of arrows in so many categories look so similar. For example, I was able to guess the appropriate way to define the arrows in the category of fiber bundles, and it certainly wasn't the definition of "category" that helped me do that. It was my intuition about what "structure-preserving" means. I just feel that there must be a way to turn that intuition into a definition, and it surprises me a lot that there doesn't seem to be a textbook answer to this.

I don't think this can be done. A lot of time there are several possible choices of arrows between objects. For example, while SET - the category whose objects are sets, and whose arrows are functions - is the standard category with sets as obhects, we can just as well consider the category whose objects are sets and whose arrows are injective functions. Or Banach Spaces with bounded linear maps, or Banach Spaces with linear contractions (Lipschitz continuous with constat K<=1). Or...
Categoy Theory won't tell you what the "homomorphisms" (arrows) should be, you have to choose them yourself. After all, in any category, the arrows are the most important, not the objects.

 

[Fredrik]

I don't think this can be done. A lot of time there are several possible choices of arrows between objects. For example, while SET - the category whose objects are sets, and whose arrows are functions - is the standard category with sets as obhects, we can just as well consider the category whose objects are sets and whose arrows are injective functions.

That's why I'd like to generalize the "structure" concept instead of talking about "categories". Functions don't have to be injective (or have any special properties) to preserve the "structure" of a set, because there are no operations to preserve. Group homomorphisms on the other hand have to satisfy f(gh)=f(g)f(h), because that's precisely what's required to preserve the "multiplication" operation.

Categoy Theory won't tell you what the "homomorphisms" (arrows) should be...

I know, but model theory does. At least when the class of objects is the the class of structures for a given first-order language. The only problem is that the definition of "structure" isn't general enough to include all those things that I think of as "structures", lacking a better term (metric spaces, manifolds, fiber bundles,...).

 

[Landau]

I was just arguing that Category Theory won't do what you want (i.e. I was agreeing with your last post).

 

[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&#039;: Y \to X such that f&#039; \circ f =f \circ f&#039; = 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&#039;
H2. For each natural number n, f\circ Im=I&#039;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&#039;r(f(x_1),\dots,f(x_n))\in S&#039;.

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.