Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

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.

share|improve this answer
    
I very much appreciate your answer. This is related to another answer for a similar question The url for the answer is here math.stackexchange.com/questions/86501/… 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. –  atat Feb 6 '12 at 1:46
    
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! –  atat Feb 6 '12 at 15:30
    
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. –  Amit Kumar Gupta Feb 6 '12 at 21:24
    
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? –  atat Feb 6 '12 at 23:10
    
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. –  Amit Kumar Gupta Feb 6 '12 at 23:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.