How to amalgamate a family of structures?

[phoenixthoth]

How to "amalgamate" a family of structures?

Given a collection of structures all using the same language, is there a way to come up with a structure C such that each given structure is, in any sense, a "subobject" of C?

Right now I'm looking at coproducts to see if that will help. Please see the attached pdf.

 

[Stephen Tashi]

I notice this page http://www.j-paine.org/make_category_theory_intuitive.html has links that purportedly do more practical stuff with category that I thought possible. If you find something that works, please explain it to me!

 

[chiro]

Hey phoenixthoth.

For this kind of mathematics, do you have a set theory equivalent of an intersection to extrapolate a subset or "sub-object" of a complete object?

 

[phoenixthoth]

I notice this page http://www.j-paine.org/make_category_theory_intuitive.html has links that purportedly do more practical stuff with category that I thought possible. If you find something that works, please explain it to me!

The Rosetta Stone article looks interesting.. Something that unifies certain aspects of Physics, topology, and logic & computation. Should be a fascinating read.

Hey phoenixthoth.

For this kind of mathematics, do you have a set theory equivalent of an intersection to extrapolate a subset or "sub-object" of a complete object?

Yes. (btw, when I say 'structure' I mean this.)

If you have two structures of the same signature, just intersecting their domains and leaving the signature alone would give rise to the type of object you're referring to. If the signatures are different, the situation is more complicated.

If coproducts of structures exist, then the coproduct object is exactly what I need. Every time I find a reference that mentions coproducts, the reference says that they don't always exist. So the main question is whether or not coproducts of structures exist in general or perhaps with additional assumptions.

 

[Hurkyl]

Consider a theory with a constant symbol C and a unary function f.

Define one structure S to have a single element C_S. f(C_S) = C_S.

Define another structure T to have two elements C_T and *, and f(C_T) = f(*) = *.

Suppose S and T are both substructures of some bigger structure U.

If i is the embedding S --> U, then $f(C_U) = f(i(C_S)) = i(f(C_s)) = i(C_S) = C_U$

If j is the embedding T --> U, then $f(C_U) = f(j(C_T)) = j(f(C_T)) = j(*) \neq j(C_T) = C_U$

and thus we have a contradiction.
I think constant symbols make the difference. If you don't have any, then I believe you can just take the disjoint union of all of your structures, then arbitrarily extend all of the functions to have values on all inputs, but having constant symbols forces relations between the different structures if you try to amalgamate them.

 

[phoenixthoth]

I just have a couple of questions.

Consider a theory with a constant symbol C and a unary function f.

Define one structure S to have a single element C_S. f(C_S) = C_S.

Define another structure T to have two elements C_T and *, and f(C_T) = f(*) = *.

Suppose S and T are both substructures of some bigger structure U.

If i is the embedding S --> U, then $f(C_U) = f(i(C_S)) = i(f(C_s)) = i(C_S) = C_U$

If j is the embedding T --> U, then $f(C_U) = f(j(C_T)) = j(f(C_T)) = j(*) \neq j(C_T) = C_U$

and thus we have a contradiction.

How do we know that $f(i(C_S)) = i(f(C_s))$ and $f(j(C_T)) = j(f(C_T))$?

What if the word "embedding" were replaced with "injective homomorphism (of structures)?"

I think constant symbols make the difference. If you don't have any, then I believe you can just take the disjoint union of all of your structures, then arbitrarily extend all of the functions to have values on all inputs, but having constant symbols forces relations between the different structures if you try to amalgamate them.

Interestingly enough, the disjoint union is the coproduct of families of sets.

If the results in my pdf are accurate, then I'm not saying S and T are embedded in U; I'm saying that there is an injective homomorphism from S to U and likewise for T. Is there the same contradiction in that case?

 

[Hurkyl]

I just have a couple of questions.
How do we know that $f(i(C_S)) = i(f(C_s))$ and $f(j(C_T)) = j(f(C_T))$?

What if the word "embedding" were replaced with "injective homomorphism (of structures)?"

"Injective homomorphism" is usually what one means by embedding; I'd add the caveat that "injective" should actually be "monic", but I believe they mean the same thing here.

Is there the same contradiction in that case?

Yes: my proof relied crucially on both i and j being homomorphisms, and j being injective.

Interestingly enough, the disjoint union is the coproduct of families of sets.

Yep; that's why I took the idea of disjoint union as the starting point of trying to figure something out. It's often a good starting point: take the disjoint union, identify what needs to be identified, then add what you need to make it work for whatever you're doing.

 

[phoenixthoth]

Hey Hurkyl

How do we know

$j(*) \neq j(C_T)$

?

 

[Hurkyl]

Because j is assumed injective, $j(*) = j(c_T)$ would imply $* = C_T$.

 

[phoenixthoth]

Gotchya. Thanks for this counterexample.

Now I'm wondering if there's any way to salvage any sort of concept of amalgamation.

Suppose I have a structure in a language with constant symbols, and an interpretation of those constant symbols as elements in the domain of that structure. For example, <N, z, S> the structure whose domain is the set of natural numbers, z is a constant symbol interpreted as 0, and S is the function symbol interpreted as successor.

What is the relation between that structure, <N, z, S> for instance, and a structure obtained by not assigning an interpretation to constant symbol(s), in this case <N, S>.

What is the relationship between <N, z, S> and <N,S>?

 

[phoenixthoth]

The aggregate of all structures over a fixed language is a proper class.

So let's look at your U, the amalgam of S and T.

You proved that U cannot be a structure in which S and T are embedded.

But is there another type of object, like a "semi-structure", something that is almost a structure but requirements are weakened and S and T are isomorphic to two sub-objects of U, called S' and T'?

Something like a category of some kind?

 

[Hurkyl]

Ignoring size issues, if you have a category C of structures and homomorphisms, you can take it's "cocompletion": the category you get by formally adding all colimits to it. In particular, coproducts are colimits.

If I haven't made a mistake, in the cocompletion, the map from A to the coproduct of A and B is always monic, so this category would have the property you want.

(the cocompletion is given by taking the category of presheaves on C. C can be viewed as a good subcategory of the category of presheaves by the "yoneda embedding", which by the yoneda lemma is a full and faithful functor)

 

[phoenixthoth]

This site contains relevant info, yes?

http://ncatlab.org/nlab/show/free+cocompletionI'm having a little trouble since I never studied category theory much.

the map from A to the coproduct of A and B is always monic, so this category would have the property you want.

How would that statement be formalized in terms of C being the category of structures and homomorphisms, is the category that has the property I want PSh(C)?edit: in the definition of the free cocompletion of C, which is PSh(C), why do we need the assumption that C is a small category? http://ncatlab.org/nlab/show/category+of+presheaves