2
$\begingroup$

This question relates to products of structures all with the same symbol set $S$. After I give a little background the question follows.

Direct Products

This definition of the direct product is taken from Ebbinghaus, et.al.

Let $I$ be a nonempty set. For every $i\in I$, let $\mathcal{A}_{i}$ be an $S-$structure. The domain of the direct product is $ \left\{ g:g\in\left[I\rightarrow\bigcup_{i\in I}A_{i}\right]\wedge\forall i\in I\left(g\left(i\right)\in A_{i}\right)\right\} . $

Here, $\left[I\rightarrow\bigcup_{i\in I}A_{i}\right]$ denotes the set of all functions whose domain is $I$ and range contained in $\bigcup_{i\in I}A_{i}$. For $g\in\prod_{i\in I}A_{i}$, we also write $\left\langle g\left(i\right):i\in I\right\rangle $.

For a constant symbol $c$, $ c^{\mathcal{A}}:=\left\langle c^{\mathcal{A}_{i}}:i\in I\right\rangle . $

For an $n-$ary relation symbol $R$ and for $g_{1},...,g_{n}\in\prod_{i\in I}A_{i}$, say that $R^{\mathcal{A}}g_{1}...g_{n}$ iff for all $i\in I$, $R^{\mathcal{A_{\mathit{i}}}}g_{1}\left(i\right)...g_{n}\left(i\right)$.

For an $n-$ary function symbol $f$ and for $g_{1},...,g_{n}\in\prod_{i\in I}A_{i}$, say that $ f^{\mathcal{A}}\left(g_{1},...,g_{n}\right):=\left\langle f^{\mathcal{A_{\mathit{i}}}}\left(g_{1}\left(i\right),...,g_{n}\left(i\right)\right):i\in I\right\rangle . $

Partial Isomorphisms (One-to-one Homomorphisms)

Ebbinghaus defines a partial isomorphism to be an injective homomorphism on page 180.

Suppose $\mathcal{A}$ and $\mathcal{B}$ are $S-$structures and $p$ is a map whose domain is a subset of $A$ and range is a subset of $B$. Then $p$ is called a partial isomorphism if

$p$ is injective $p$ is a homomorphism in the following sense

for any constant symbol $c$ and any $a\in\mathsf{dom}\left(p\right)$, $c^{\mathcal{A}}=a$ iff $c^{\mathcal{B}}=p\left(a\right)$

for any $n-$ary relation symbol $R$ and $a_{1},...,a_{n}\in\mathsf{dom}\left(p\right)$, $R^{\mathcal{A}}a_{1}...a_{n}$ iff $R^{\mathcal{B}}p\left(a_{1}\right)...p\left(a_{n}\right)$

for any $n-$ary function symbol $f$ and $a_{1},...,a_{n}\in\mathsf{dom}\left(p\right)$, $f^{\mathcal{A}}\left(a_{1},...,a_{n}\right)=a$ iff $f^{\mathcal{B}}\left(p\left(a_{1}\right),...,p\left(a_{n}\right)\right)=p\left(a\right)$

The Question

Do there exist maps $p_{i}:A_{i}\rightarrow A$ that are partial isomorphisms?

If not, then is there any way to take a family of structures and "create" a new structure that each structure in the family can be homomorphically injected into the new structure?

1 Answers 1

2

If $c,d$ are constant symbols, $f$ a unary function symbol, $I=\{0,1\}$ and we have $A_0 \vDash f(c) = d$ and $A_1 \not\vDash f(c) = d$, then there is no structure $A$ for which there exists partial homomorphisms $p_i : A_i \to A$. My category theory is rusty, but it seems like what you're looking for is the existence of coproducts in the category of $S$-structures, and generally these do not exist. In certain very simple cases, you can get the kind of structure you want by taking the disjoint union of the $A_i$ (in fact many coproducts in various categories are formed this way). But that will only work in very simple cases. In a more general class of cases, you can form a coproduct by "amalgamating" structures, where you "sort of" take a disjoint union, but there's some part of each structure which will be common to all structures (namely the smallest substructure of each structure, i.e. what you get after closing off the set of interpretations of constant symbols under the functions). This only works if all the structures' smallest substructures are isomorphic.

My apologies if this answers is vague, I'm in a rush (Super Bowl in 30 minutes). Please ask if you'd like me to clarify or expand on anything.


Definition: Given a family of sets, groups, rings, or more generally, $S$-structures $\{A_i\}_{i\in I}$, their Cartesian product is defined exactly as you defined it, and it's given the structure you describe.

Definition: Given a family of objects $\{A_i\}$ in some category, we'll say that an object $A$ is a weak categorical product of the family if there are morphisms $\pi_i : A \to A_i$ for each $i$.

Note: This definition is not a standard definition. Also, it doesn't say precisely what $A$ is, it just tells us what properties an object $A$ would have to have to be deemed a weak categorical product. Furthermore, it doesn't even tell us whether such an $A$ exists, or whether it's unique. Finally, note that the definition involves the existence of morphisms from $A$ to the $A_i$.

Definition: A weak categorical coproduct of a family $\{A_i\}$ is an object $A$ together with maps $p_i : A_i \to A$.

Note: The difference between products and coproducts is whether the maps are $A_i \to A$ or $A \to A_i$

Your first question can be rephrased, then, as: Are Cartesian products weak coproducts in the category of $S$-structures? In general, the answer is No, and in the original part of my post I started with a counterexample. Still, one might want to ask, in what situations does the Cartesian product give a weak coproduct? What is a nice set of conditions for which we can say: Cartesian products form weak coproducts iff said conditions hold.

I'm tempted to say that there is no such "nice" set of conditions. Perhaps a series of counterexamples would demonstrate for you that Cartesian products tend not to form coproducts, but rather than do that, let me tell you what Cartesian products often do form:

Theorem: In the category of $S$-structures (where morphisms are maps $\phi : A \to B$ that respect constant and function symbols in the usual way, and respect relation symbols in the following way: $R^A\vec{a} \Rightarrow R^B\phi\vec{a}$ -- note we don't require $R^A\vec{a} \Leftrightarrow R^B\phi(\vec{a})$), Cartesian products form weak categorical products.

Proof: The projection maps $\pi_i : A \to A_i$ given by:

$$\pi_i\left(\langle a_j\rangle_{j\in I}\right) = a_i$$

can be easily seen to give the desired morphisms.

Given that Cartesian products typically form categorical products, then perhaps it's not so surprising that they don't tend to form coproducts. The things which do tend to form coproducts are some variations on disjoint unions. Indeed:

Proposition: If $S$ is a purely relational signature, and $\{A_i\}$ a family of $S$-structures, then their disjoint union $A = \bigsqcup A_i$ forms a coproduct, where the structure is given by: $R^A\vec{a}$ iff $\vec{a}$ all belong to the same $A_i$, and $R^{A_i}\vec{a}$. The desired maps $p_i : A_i \to A$ are the obvious inclusion maps.

More generally, a pure disjoint union won't work, what we need to do is "amalgamate."

Fact: Every $S$-structure $A$ has a smallest substructure $B$, which can be regarded as the intersection of all the substructures of $A$, or, equally, as the set obtained by starting with all the $A$-interpretations of the constant symbols, and closing off under applications of $A$-interpreted function symbols. Given a structure $A$, let $A'$ denote its smallest substructure.

Let's say a family $\{A_i\}$ of $S$-structures is agreeable if they all have the same smallest substructure $A'_i$ (up to isomorphism). That is, there is an $S$-structure $B$ such that for all $i$, $B \cong A'_i$. If the $A_i$ are agreeable, let's define $A = \coprod A_i = B \sqcup \bigsqcup (A_i \setminus A'_i)$.

Exercise (which I believe is true): $S$-structures $\{A_i\}$ have a weak categorical coproduct iff they are agreeable, and in this case a coproduct can be made by putting an appropriate $S$-structure on $\coprod A_i$.

Note: The previous proposition about purely relational structures is a corollary of the above exercise. Indeed, if $A$ is purely relational, then $A' = \emptyset$.

Let me end by saying that this does not contradict Magidin's answer to your other question. Sometimes, Cartesian products can be used to form the type of things you're looking for, namely what I've called a weak categorical coproduct. Sometimes. And, not to take away from Magidin's answer, but I'm tempted to say that what I've written above is closer to how you want to think about these objects in general.

  • 0
    I very much appreciate your answer. This is related to another *answer* for a similar question The url for the answer is here http://math.stackexchange.com/questions/86501/gluing-together-mathematical-structures-how The part that's relevant is where he says "More generally." What I don't get is how that family *induces a homomoprhism into the product*. What is meant by the word induce? How do we know the script F's which are induced homomorphisms exist? And finally, do the two answers contradict one another? Again, thank you for your time.2012-02-06
  • 0
    Thank you. I will try to consult literature on category theory and weak products and coproducts. I need to understand how your answer appears to contradict Magidin's. The $\mathcal{F}_{i_{0}}$ that Magidin mentions is exactly what I want, right? I would like to know how it is known that they exist? Many thanks!2012-02-06
  • 0
    As I mentioned, "weak products" and "weak coproducts" are not standard definitions. What you will find are definitions for products and coproducts. A product is what I've called a weak product, which additionally satisfies some universal properties. I didn't bother to mention this in my answer because the universal properties are irrelevant in this context. In my answer I only state that the Cartesian product does not always give an object like the one you're looking for. In some cases it does, and Magidin's answer gives you a case in which it does. In this sense, they don't contradict.2012-02-06
  • 0
    Thanks for that. I believed that what I saw as a contradiction was just a failure on my part. Would you mind saying a bit about what the two cases are again for me? Two types of product perhaps? What is the type of product which will give me the object I'm looking for?2012-02-06
  • 0
    Since you want to have maps *from* the $A_i$ *into* the desired object $A$, you want a *coproduct*, which is "often" formed by taking a disjoint union of the $A_i$, or some variation of that. If you wanted to have maps *from* $A$ *into* the $A_i$, you would be looking for a *product* which is "often" formed by the Cartesian product of the $A_i$. In general, products and coproducts need not exist, and when they do exist, there may be different ways to construct them. Sometimes a Cartesian product might form a (weak) coproduct, but this tends to be just coincidental, more or less.2012-02-06
  • 0
    I've been skimming some literature and it seems that if S is a set of structures (with same symbol set), then the product, if it exists, admits retracts which is what I think Magidin is talking about. The retracts slyly prove that 1-1 homomorphisms exist from each structure into the product. Incidentally, when I see the word "morphism" in a cat theory sense, I can interpret that as "homomorphism" in a math logic sense, right? So all I have yet to do is prove that the product exists and satisfies the definition of product in the categorical sense; then retracts come from a theorem?2012-02-08
  • 0
    Magidin's answer actually makes no reference to a Cartesian product. Let me state his theorem in my terminology: If you have a collection of objects $\{A_i\}$ such that (a) there is a morphism between any two, and (b) a weak categorical product $A$ of these objects exist, then (assuming AC) one can combine the morphisms from (a) to get morphisms $A_i \to A$, making $A$ a weak categorical coproduct as well. You can't generally interpret categorical "morphisms" to be FOL "homomorphisms". In general, morphisms need not even be functions. Nonetheless, in standard, down-to-earth categories...2012-02-09
  • 0
    ... like Rings, Groups, Graphs, etc. the morphisms are implicitly taken to be homomorphisms in the algebraic sense of the word (just as when we think of $\mathbb{R}$ as a vector space, we implicitly take the zero vector to be 0, and implicitly take the vector addition to be normal addition), which are homomorphisms in the FOL sense of the word.2012-02-09