Homomorphisms as "structurepreserving" mapsby Fredrik Tags: homomorphisms, maps, structurepreserving 

#37
Jul1910, 10:47 PM

Emeritus
Sci Advisor
PF Gold
P: 16,101

"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 nonalgebraic axiom that says the ring is actually a field. But this is still an ordinary firstorder theory with two types. Pseudometric 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. Firstorder logic lets you add an axiom to insist on nondegeneracy. Infinitary or secondorder logic would let you add axioms insisting the ring of distances really is the real numbers, if you insisted on such a thing. For the record, in any case I can imagine, any bijection of sets gives a structurepreserving 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:
I'm not sure if this is useful for your purpose? 



#38
Jul1910, 11:09 PM

Emeritus
Sci Advisor
PF Gold
P: 16,101

It might not be a useful shift in perspective, but I claim that the categorytheoretic 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. 



#39
Jul2010, 08:25 AM

Emeritus
Sci Advisor
PF Gold
P: 9,017

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 firstorder logic. 



#40
Jul2010, 02:02 PM

P: 5

Well, this is an interesting thread. Mind if I stick in my twopennyworth? 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 [tex]\mathcal{C}[/tex] is a category with [tex]X,\,\,Y,\,\,Z \in \mathcal{C}[/tex]. Further suppose that [tex]f:X \to Y, \,\, g: Y \to Z \in \mathcal{C}[/tex]. Then, essentially by definition [tex]g \circ f: X \to Z[/tex]. By definition, for all [tex]X,\,\,Y \in \mathcal{C}[/tex] there exist arrows [tex]id_X: X \to X \in \mathcal{C}[/tex] such that [tex] id_X \circ f= f[/tex] and [tex]id_Y:Y \to Y[/tex] such that [tex]g \circ id_Y = g[/tex]. 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 [tex]f: X \to Y \in \mathcal{C}[/tex] there exists [tex]f': Y \to X[/tex] such that [tex] f' \circ f =f \circ f' = id_X[/tex], then I define the category of arrows [tex] f : X \to Y[/tex] (generically) as a monoid; id est this category Arr has the structure of a monoid. Now define the functor [tex]F: \mathcal{C} \to \mathcal{D}[/tex] such that [tex]F(f \circ g) = F(f) \circ F(g)[/tex] and [tex]F(id_X) = F_{id_X}[/tex] which is no more (or less) than to say that the the functors that take Arr onto Arr is a generalized monoid homomorphism. 



#41
Jul2010, 08:51 PM

Emeritus
Sci Advisor
PF Gold
P: 16,101

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 grouptheoretic 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. 



#42
Jul2110, 01:23 AM

P: 341

V. interesting discussion, though I'm not following all of it.
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: 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 ntuple. 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. 



#43
Jul2110, 11:44 AM

Emeritus
Sci Advisor
PF Gold
P: 9,017





#44
Jul2110, 03:13 PM

P: 341

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. 



#45
Jul2110, 03:29 PM

Emeritus
Sci Advisor
PF Gold
P: 16,101

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:
My earlier example of a "Eucset" 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 Eucset". 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) 



#46
Jul2110, 07:37 PM

Emeritus
Sci Advisor
PF Gold
P: 9,017

Suppose we also define the category D of all structures associated with the signature {·}, with structurepreserving 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). 



#47
Jul2210, 05:26 PM

Emeritus
Sci Advisor
PF Gold
P: 9,017

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 firstorder logic (mainly to explain my terminology).
A firstorder 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 firstorder languages have in common [itex]\{\lnot,\rightarrow,\forall\}\cup\{v_0,v_1,\dots\}[/itex] (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_{0}, O_{0}, R_{1}, O_{1},... [tex]L=C\cup\bigcup_{n=0}^\infty (R_n\cup O_n)[/tex] 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 [itex]\exists[/itex] and [itex]\land[/itex], 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^{n}, and that an operation on X of arity n is a function from X^{n} into X, i.e. a subset f of X^{n}×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^{n}, there's a y in X such that (x,y) is in f. I will call a subset f of X^{n}×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 Lhomomorphism if H1. [itex]f\circ I=I'[/itex] H2. For each natural number n, [itex]f\circ Im=I'm[/itex] for all m in O_{n}. H3. For each natural number n, each x_{1},...,x_{n} and each r in R_{n}, [itex]Ir(x_1,\dots,x_n)\in S[/itex] if and only if [itex]I'r(f(x_1),\dots,f(x_n))\in S'[/itex]. A category of Lstructures can be defined with Lstructures as objects and Lhomomorphisms as arrows. (I called this the "standard" category of Lstructures first, but I realized that it isn't. For some choices of L, the standard category of Lstructures has Lhomomorphisms as arrows, but for other choices it doesn't. Topological spaces is a good example of a category where the arrows are not Lhomomorphisms, because the arrows are continuous maps, not open maps). We can define a subclass of the class of all Lstructures 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 Lstructures 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). 



#48
Jul2310, 01:12 PM

Emeritus
Sci Advisor
PF Gold
P: 9,017

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.




#49
Jul2410, 06:59 AM

Emeritus
Sci Advisor
PF Gold
P: 16,101

How about the following? It is a definition of something called a sketch:
A sketch consists of:
A model of a sketch consists of:
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. [tex]\varphi_T \circ f_1 = f_2 \circ \varphi_S[/tex]where [itex]\varphi[/itex] is the homomorphism, [itex]\varphi_S,\varphi_T[/itex] are the components corresponding to the formal types S and T, [itex]f_1, f_2[/itex] are the functions corresponding to the formal function [itex]f : S \to T[/itex]. The assertions are powerful enough to specify that certain functions must be injective or surjective. Together with products, this lets 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 [tex]G \xrightarrow{(e, 1)} G \times G \xrightarrow{\mu}[/tex]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 [itex]\mu[/itex] is multiplication. The assertion implies the function [tex]x \mapsto \mu(e,1)x = \mu(e, x) = ex[/tex]is the identity function; so x = ex. I suppose you wouldn't be surprised to hear this is category theory. A sketch is:
Models of a sketch are functors satisfying the assertions, and homomorphisms of models are natural transformations of functors. 



#50
Jul2410, 09:29 AM

Emeritus
Sci Advisor
PF Gold
P: 16,101

This time I'm not trying to be gratuitously categorytheoretic. 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 severalfold: With products, we can include nary 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 severalfold: We get disjoint unions. It lets 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. 



#51
Jul2610, 05:52 AM

Sci Advisor
HW Helper
PF Gold
P: 4,768

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



#52
Jul2610, 07:27 AM

Sci Advisor
P: 905





#53
Aug210, 05:58 AM

Emeritus
Sci Advisor
PF Gold
P: 9,017




Register to reply 
Related Discussions  
The modern "LargeScale Structure of Spacetime" book  Science & Math Textbook Listings  15  
"Shape preserving" fitting algorithms  General Math  1  
Google Maps... "Street View"  General Discussion  4  
Explaining the structure of Galaxy "Filaments"  Cosmology  11  
structure of the lunar crust and the "thumper experiment"  Earth  1 