Want to take part in these discussions? Sign in if you have an account, or apply for one below
Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.
1 to 40 of 40
I want to attempt to apply my theory of funcoids to study of integral curves of different smoothness classes. For a start I consider curves in $\mathbb{R}^n$ for finite $n$.
Below I will ask a question about staroids. But after this I describe this in terminology of common knowledge (without using funcoids or staroids), for these who has not read my book.
For this I probably need to well understand $n$-staroids for finite $n$ ($2$-staroid is essentially the same as funcoid).
Denote $\mathsf{Strd}(-,-)$ (where the poset $\mathsf{Strd}(S_0, \dots, S_{n-1})$ that is a staroid between posets $S_0, \dots, S_{n-1}$ looks like to be an unbiased tensor product).
I want to prove that $\mathsf{Strd}(-,-)$ is a tensor product in the category $\mathbf{Pos}$.
Something equivalent to this is claimed (for the special case of join-semilattices) in this this MathOverflow answer.
However I have some trouble to write down a proof.
I ask for help to prove that $\mathsf{Strd}(-,-)$ is a tensor product. It should be a consequence of the (to be proved) fact that $\mathsf{Strd}(A,B,C) = \mathsf{Strd}(\mathsf{Strd}(A,B), C)$.
The first (easy) step (for the special case of join-semilattices) is to note that a staroid between join-semilattices $S_0, \dots, S_{n-1}$ of finite arity $n$ is a multi-join-homomorphism (a join-semilattice homomorphism in each argument separately) $\prod_{i\in n} S_i \rightarrow 2$ for join-semilattices $S_i$.
(The last paragraph describes it in a language without funcoids and staroids. So you can answer my question even if you have not read my writings.)
Then the MathOverflow answer states that this is equivalent to order homomorphism $\bigotimes_{i\in n} S_i \rightarrow 2$ (where $\bigotimes$ is a tensor product). I don’t understand why.
Moreover when I tried to prove $\mathsf{Strd}(A,B,C) = \mathsf{Strd}(\mathsf{Strd}(A,B), C)$, I had a trouble leading me to think that it isn’t an equality (and then $\mathsf{Strd}(-,-)$ would be not a tensor product), but I remembered that this is stated in that MO question. I think the error is on my part, not the MO answer, and thus it is indeed a tensor product (and this would be a beautiful result), but I don’t understand what exactly is wrong with my reasoning. I probably need help.
I want an explicit proof (not something about ring or distributive lattices) for the following reasons:
Then the MathOverflow answer states that this is equivalent to order homomorphism $\bigotimes_{i\in n} S_i \rightarrow 2$ (where $\bigotimes$ is a tensor product). I don’t understand why.
It didn’t quite say that. It said it is equivalent to join-preserving homomorphisms $\bigotimes_{1 \leq i \leq n} S_i \to 2$. Does that make it more understandable?
So the point as I see it is that on the category of join-semilattices, there is a tensor product $\otimes$ with the universal property that join-preserving maps $S \otimes T \to U$ are in natural bijection with poset maps $\phi: S \times T \to U$ such that $\phi(s, -): T \to U$ is join-preserving for every $s \in S$ and $\phi(-, t): S \to U$ is join-preserving for every $t \in T$. This is constructed by a standard procedure: $S \otimes T$ is the quotient of the free join-semilattice $F(S \times T)$ on $S \times T$ (let $i: S \times T \to F(S \times T)$ be the universal embedding), by the smallest equivalence relation $\sim$ such that $i(s \vee s', t) \sim i(s, t) \vee i(s', t)$, $i(s, t \vee t') \sim i(s, t) \vee i(s, t')$, $0 \sim i(0, t) \sim i(s, 0)$, and such that $x \sim y$ and $x' \sim y'$ implies $x \vee x' \sim y \vee y'$. (Hopefully those are all the relations that need be considered.) That $S \otimes T$ as so constructed satisfies the universal property is a routine verification.
It might help at this point to introduce some terminology. If $S_1, \ldots, S_n$ and $T$ are join-semilattices, then let’s say a map $\phi: S_1 \times \ldots \times S_n \to T$ preserves joins in $n$ separate arguments if, for each $i$ between $1$ and $n$, and $s_j \in S_j$ for $j \neq i$, the function $\phi(s_1, \ldots, s_{i-1}, -, s_{i+1}, \ldots, s_n): S_i \to T$ preserves joins.
Then, for example, join-homomorphisms $(S \otimes T) \otimes U \to V$ are in natural bijection with functions $(S \otimes T) \times U \to V$ that preserve joins in two separate arguments, which are in natural bijection with functions $S \times T \times U \to V$ that preserve joins in three separate arguments. A parallel argument shows that join-homomorphisms $S \otimes (T \otimes U) \to V$ are also in natural bijection with functions $S \times T \times U \to V$ that preserve joins in three separate arguments.
This shows there is a natural bijection between join-homomorphisms $(S \otimes T) \otimes U \to V$ and join-homomorphisms $S \otimes (T \otimes U) \to V$, for every join-semilattice $V$. By the Yoneda lemma, this is enough to conclude that there is an isomorphism $(S \otimes T) \otimes U \cong S \otimes (T \otimes U)$, natural in all three arguments $S, T, U$.
Or, if you like, you can construct $Strd(A, B, C)$ directly as a quotient of the free join-semilattice $F(A \times B \times C)$, modulo an equivalence relation which is analogous to the equivalence relation described for the case $S \otimes T = Strd(S, T)$ – and then show $Strd(Strd(A, B), C) \cong Strd(A, B, C)$ directly. (Technically that’s an isomorphism, not an equality. But canonical isomorphisms are practically as good as equalities, just as you can enact the same game of chess on two different chessboards.)
Hi Todd,
I’ve started to think about details of your proof.
I spent maybe half of hour (maybe even more) and yet have a trouble to understand why multi-join-homomorphisms are the same as $F(S_1\times\dots\times S_n) / \sim$.
Todd, you can consider yourself now as a teacher and choose whether you explain it to me in details now or give me more time for myself to try to figure it out without external help.
Hi again Todd,
I’ve looked into this nLab page about free semilattices. It seems unrelated with the formulas you’ve given.
I am lost and ask for help.
Okay then, try thinking it over a little longer. But as a hint: join-preserving homomorphisms $F(S_1 \times \ldots \times S_n) \to T$ correspond exactly to plain-old functions $\phi: S_1 \times \ldots \times S_n \to T$. Such a homomorphism induces a well-defined homomorphism $F(S_1 \times \ldots \times S_n)/~ \to T$ on the set (the join-semilattice) of $\sim$-equivalence classes, if and only if $\phi$ preserves joins in separate arguments. That’s because the definition of $\sim$ is tailor-made for that to be true.
I still encourage you to learn about tensor products in Algebra. Tensor products of abelian groups would be enough (and the construction is highly analogous). In my opinion they require less sophistication to appreciate than much of what you have developed in your mathematics (and I mean that in a nice way).
Dear Todd,
Ugh,
The first step (join-preserving homomorphisms $F(S_1 \times \ldots \times S_n) \to T$ correspond exactly to plain-old functions $\phi: S_1 \times \ldots \times S_n \to T$) is quite obvious.
The next step (Such a homomorphism induces a well-defined homomorphism $F(S_1 \times \ldots \times S_n)/~ \to T$ on the set (the join-semilattice) of $\sim$-equivalence classes, if and only if $\phi$ preserves joins in separate arguments.) looks like obvious, but I have a trouble to write down the proof.
Excuse me, I want your help. I keep thinking. I think give enough time I can solve it, but the time may be somehow too long.
In the first place: it’s fine to ask. Also, depending on how one approaches it, the proof can wind up looking unpleasantly complicated, so it may be well to discuss it here. I’ll divide the argument into three parts.
Part 1: the condition on $\sim$ that $x \sim y$ and $x' \sim y'$ implies $x \vee x' \sim y \vee y'$ means that the join $\vee$ is well-defined on $\sim$-equivalence classes, and that the map
$F(S_1 \times \ldots \times S_n) \stackrel{q}{\to} F(S_1 \times \ldots \times S_n)/\sim,$where the quotient map $q$ takes an element $x$ to its equivalence class $[x]$, preserves joins. The join on $F(S_1 \times \ldots \times S_n)/\sim$ is associative, commutative, and idempotent since it is so on $F(S_1 \times \ldots \times S_n)$. Thus if we define $[x] \leq [y]$ to mean $[x] = [x] \vee [y] = [x \vee y]$, we do indeed get a join-semilattice structure on the quotient.
Part 2: suppose we have a join-preserving map $\psi: F(S_1 \times \ldots \times S_n)/\sim \to T$. Let $i: S_1 \times \ldots \times S_n \to F(S_1 \times \ldots \times S_n)$ be the canonical inclusion. I claim that $\psi \circ q \circ i$ preserves binary joins in separate arguments. This is easily checked: if $1 \leq j \leq n$ and $s_k \in S_k$ for $k \neq j$ are given, then for $t, t' \in S_j$ we have
$i(s_1, \ldots, s_{j-1}, t \vee t', s_{j+1}, \ldots, s_n) \sim i(s_1, \ldots, s_{j-1}, t, s_{j+1}, \ldots, s_n) \vee i(s_1, \ldots, s_{j-1}, t', s_{j+1}, \ldots, s_n)$according to the definition of $\sim$, so that $q i(s_1, \ldots, s_{j-1}, t \vee t', s_{j+1}, \ldots, s_n) = q i(s_1, \ldots, s_{j-1}, t, s_{j+1}, \ldots, s_n) \vee q i(s_1, \ldots, s_{j-1}, t', s_{j+1}, \ldots, s_n)$ in the quotient (i.e., the two sides are in the same equivalence class). Since they are equal in the quotient, we get upon applying $\psi$ the equality
$\psi q i(s_1, \ldots, s_{j-1}, t \vee t', s_{j+1}, \ldots, s_n) = \psi q i(s_1, \ldots, s_{j-1}, t, s_{j+1}, \ldots, s_n) \vee \psi q i(s_1, \ldots, s_{j-1}, t', s_{j+1}, \ldots, s_n)$(since $\psi$ preserves joins). Arguing similarly, $\psi q i$ preserves the empty join $0$ in separate arguments, and so we conclude $\psi q i$ preserves finite joins in separate arguments.
Part 3: now we argue in the converse direction. This part can trip up the unwary with ugly complications, especially if one gets hung up too much on inductive arguments about the structure of $\sim$.
Suppose we start with a map $\phi: S_1 \times \ldots \times S_n \to T$ that preserves finite joins in separate arguments. There is a unique join-preserving map $\tilde{\phi}: F(S_1 \times \ldots \times S_n) \to T$ such that $\tilde{\phi} \circ i = \phi$. We must show that this induces a well-defined join-preserving map
$\psi: F(S_1 \times \ldots \times S_n)/\sim \to T$such that $\psi (q(x)) = \tilde{\phi}(x)$ for all $x \in F(S_1 \times \ldots \times S_n)$ (clearly at most one function $\psi$ can satisfy this equation since $q$ is surjective).
The general strategy is this. Suppose one has an equivalence relation $E$ on a set $X$ and one wants to show that some function $h: X \to Y$ induces a well-defined map $\psi: X/E \to Y$ on equivalence classes. For this it is sufficient to prove that $E \subseteq F$, where $F$ is the “$h$-equivalence relation” defined by $(x, y) \in F$ iff $h(x) = h(y)$.
In our case $E = \sim$ is by definition the smallest equivalence relation (i.e., the intersection of all equivalence relations) on $F(S_1 \times \ldots \times S_n)$ such that
$E$ contains pairs of the form $(i(s_1, \ldots, s_{j-1}, t \vee t', s_{j+1}, \ldots, s_n), i(s_1, \ldots, s_{j-1}, t, s_{j+1}, \ldots, s_n) \vee i(s_1, \ldots, s_{j-1}, t', s_{j+1}, \ldots, s_n))$,
$E$ contains pairs of the form $(i(s_1, \ldots, s_{j-1}, 0, s_{j+1}, \ldots, s_n), 0)$,
If $E$ contains $(x, y)$ and $(x', y')$, then $E$ contains $(x \vee x', y \vee y')$.
So it is sufficient to show that the $\tilde{\phi}$-equivalence relation contains these pairs, or that
$\tilde{\phi}(i(s_1, \ldots, s_{j-1}, t \vee t', s_{j+1}, \ldots, s_n)) = \tilde{\phi}(i(s_1, \ldots, s_{j-1}, t, s_{j+1}, \ldots, s_n) \vee i(s_1, \ldots, s_{j-1}, t', s_{j+1}, \ldots, s_n))$, which is clear because $\tilde{\phi} \circ i = \phi$ and $\tilde{\phi}$ preserves binary joins, which reduces the equation to
$\phi(s_1, \ldots, s_{j-1}, t \vee t', s_{j+1}, \ldots, s_n)) = \phi(s_1, \ldots, s_{j-1}, t, s_{j+1}, \ldots, s_n) \vee \phi(s_1, \ldots, s_{j-1}, t', s_{j+1}, \ldots, s_n))$which holds since $\phi$ preserves binary joins in separate arguments;
similarly, $\tilde{\phi}(i(s_1, \ldots, s_{j-1}, 0, s_{j+1}, \ldots, s_n) = \tilde{\phi}(0)$ is clear because $\tilde{\phi} \circ i = \phi$ and $\tilde{\phi}$ preserves the empty join $0$, which reduces the equation to
$\phi(s_1, \ldots, s_{j-1}, 0, s_{j+1}, \ldots, s_n) = 0$which again holds since $\phi$ preserves $0$ in separate arguments;
finally, if $\tilde{\phi}(x) = \tilde{\phi}(y)$ and $\tilde{\phi}(x') = \tilde{\phi}(y')$, then $\tilde{\phi}(x \vee x') = \tilde{\phi}(y \vee y')$, which is clear since $\tilde{\phi}$ preserves joins.
This completes the proof.
(never mind)
Regarding #4: I didn’t give any formulas for the construction of free join-semilattices; I just took its existence for granted.
But actually I think the construction at SemiLat is nice. If $X$ is a set then $P_{fin}(X)$, the set of all finite subsets of $X$ partially ordered by inclusion, is the free join-semilattice on $X$. For if $Y$ is a join-semilattice and $f: X \to Y$ is a function, then the map $\tilde{f}: P_{fin}(X) \to Y$ taking $\{x_1, \ldots, x_n\}$ to $\bigvee_{i=1}^n f(x_n)$ in $Y$ is clearly the unique join-preserving map such that $\tilde{f} \circ i = f$ (in the notation of the previous post).
Dear Todd,
Thank you very much for your support.
“join-homomorphisms $(S \otimes T) \otimes U \to V$ are in natural bijection with functions $(S \otimes T) \times U \to V$ that preserve joins in two separate arguments,”
^^ this is (almost) clear (1. I don’t see why this is a natural bijection; 2. I am not sure if that is is natural is used below in the proof.)
I don’t understand the last thing to finish the proof:
“which ($(S \otimes T) \times U \to V$) are in natural bijection with functions $S \times T \times U \to V$ that preserve joins in three separate arguments”.
I don’t understand your last claim, because $(S \otimes T) \times U \to V$ is not in the form $\square\otimes\square\rightarrow V$ and thus it seems that we can’t apply the proved above.
Also: How do we apply Yoneda lemma? AFAIK, $2$ is not an object of $\mathbf{Set}$ and thus $\square\rightarrow 2$ is not a presheaf.
Maybe I’ll work my way backwards, i.e., starting with your last question:
Also: How do we apply Yoneda lemma? AFAIK, $2$ is not an object of $\mathbf{Set}$ and thus $\square\rightarrow 2$ is not a presheaf.
My response will wind up being a kind of prepared lecture.
I should warn you that when category theorists say “Yoneda lemma”, they often are referring to a circle of results which has the Yoneda lemma at its core as the central unifying statement, and that it is often some offshoot of Yoneda that one really has in mind if one is being literal. In the case of interest for us here, and in many other cases, the offshoot takes the general form “if $X$ and $Y$ satisfy the same universal property, then $X$ and $Y$ are isomorphic”.
To be more precise: experience has shown that whenever we say that some object $X$ (of a category $C$) “satisfies a universal property”, it can always be formalized as saying that there is a functor $F: C \to Set$ and a specific natural isomorphism $\hom_C(X, -) \to F$. For example, in the case of join-semilattices, we say the construct $S_1 \otimes S_2$, a certain join-semilattice, satisfies a certain universal property. What is it? Well, it’s that there is a map $i: S_1 \times S_2 \to S_1 \otimes S_2$ that preserves joins in separate arguments, and which is universal in the sense that given any join-semilattice $T$ and a map $\phi: S_1 \times S_2 \to T$ that preserves joins in separate arguments, there is a unique join-preserving map $\psi: S_1 \otimes S_2 \to T$ such that $\psi \circ i = \phi$.
Now let us reinterpret this statement to make it fit the formalized context. Our category $C$ in this case is the category of join-semilattices. The object $X$ is $S_1 \otimes S_2$. The functor $F: C \to Set$ is the functor which assigns to each join-semilattice $T$ the set of functions $\phi: S_1 \times S_2 \to T$ preserving joins in separate arguments. Perhaps it will be suggestive to you if I denote this set as $Strd(S_1 \times S_2, T)$. However we choose to denote it, let’s pause to note that if $f: T \to T'$ is a join-preserving map, then we get an induced function $Strd(S_1 \times S_2, T) \to Strd(S_1 \times S_2, T')$, taking $\phi: S_1 \times S_2 \to T$ to $f \circ \phi: S_1 \times S_2 \to T'$. Furthermore, if we denote this induced function by $Strd(S_1 \times S_2, f)$, then it is easily checked that if we have another join-preserving map $g: T' \to T''$, then we have
$Strd(S_1 \times S_2, g \circ f) = Strd(S_1 \times S_2, g) \circ Strd(S_1 \times S_2, f):$this merely says $(g \circ f) \circ \phi = g \circ (f \circ \phi)$ for all $\phi: S_1 \times S_2 \to T$ preserving joins in separate arguments. In other words, we officially have a functor $Strd(S_1 \times S_2, -): C \to Set$, the one whose object assignment was described a few sentences ago. That functor will be our $F: C \to Set$.
Now what we are saying is that this functor $F = Strd(S_1 \times S_2, -)$ is representable; more particularly that it is represented by $X = S_1 \otimes S_2$: by definition this means there is a natural isomorphism
$\eta: \hom_{SemiLat}(S_1 \otimes S_2, -) \stackrel{\sim}{\to} Strd(S_1 \times S_2, -).$It is perhaps well at this point to comment on the significance of the naturality and how the Yoneda lemma ties in at this point. For one thing the isomorphism means that for each object $T$, there is a bijection
$\eta_T: \hom_{SemiLat}(S_1 \otimes S_2, T) \stackrel{\sim}{\to} Strd(S_1 \times S_2, T)$so that for each separate-join-preserving $\phi: S_1 \times S_2 \to T$ there exists a unique $\psi: S_1 \otimes S_2 \to T$ that maps to $\phi$ under the bijection $\eta_T$. But the naturality imposes an important constraint: that the bijections $\eta_T$ are not arbitrary, but follow a uniform rule over $T$. The Yoneda lemma specifies more precisely what that rule is: any such natural transformation $\eta: \hom_{SemiLat}(S_1 \otimes S_2, -) \to Strd(S_1 \times S_2, -)$ is uniquely determined by the element $\eta_{S_1 \otimes S_2}(1_{S_1 \otimes S_2}) \in Strd(S_1 \times S_2, S_1 \otimes S_2)$. In fact, for the desired natural isomorphism, that element is precisely the universal separate-join-preserving map $i: S_1 \times S_2 \to S_1 \otimes S_2$. The natural isomorphism $\eta_T$ is determined by the universal map $i$ via the commutative naturality diagram
$\array{ \hom_{SemiLat}(S_1 \otimes S_2, S_1 \otimes S_2) & \stackrel{\eta_{S_1 \otimes S_2}}{\to} & Strd(S_1 \times S_2, S_1 \otimes S_2) & & & & & & 1_{S_1 \otimes S_2} & \to & i: S_1 \times S_2 \to S_1 \otimes S_2 \\ \mathllap{\hom_{SemiLat}(S_1 \otimes S_2, \psi)} \downarrow & & \downarrow \mathrlap{Strd(S_1 \times S_2, \psi)} & & & & & & \downarrow & & \downarrow \\ \hom_{SemiLat}(S_1 \otimes S_2, T) & \underset{\eta_T}{\to} & Strd(S_1 \times S_2, T) & & & & & & \psi & \to & \psi \circ i }$where reading off the bottom row, we derive the rule $\eta_T(\psi) = \psi \circ i$. Recapping then the natural bijection $\eta_T$: for each $\phi \in Strd(S_1 \times S_2, T)$, there exists a unique $\psi \in \hom_{SemiLat(}S_1 \otimes S_2, T)$ such that $\psi \circ i = \phi$.
So now we have worked out a particular case of what the Yoneda lemma is saying. You can think of this aspect of the Yoneda lemma as taking the general and vague-sounding phrase “universal property”, and re-expressing it in the precise terms of representability of functors $F$ by objects $X$ via isomorphisms $\eta: \hom_C(X, -) \stackrel{\sim}{\to} F$, and saying that all such forms of representability work the same way: that there is a universal element $i = \eta_X(1_X) \in F(X)$ which governs the uniform rule for $\eta$, that for any object $T$ we have $\eta_T(\psi) = F(\psi)(i)$.
To be continued.
Another aspect or consequence of the Yoneda lemma is that any two objects $X, X'$ of a category $C$ that satisfy the same universal property must be (canonically) isomorphic. The word “canonically” here means that the universal property itself uniquely specifies the isomorphism.
I will apply this consequence in a while to our specific situation with join-semilattices, but first I will beg your indulgence and say in general but precise terms what the preceding paragraph means. We know by now that when we say that $X$ “satisfies a universal property”, we mean that there is some functor $F: C \to Set$ and a specified natural isomorphism $\eta: \hom_C(X, -) \to F$. We also know that such an isomorphism is uniquely determined by the universal element $i = \eta_X(1_X) \in F(X)$.
Thus, if we have two objects $X, X'$ satisfying the same universal property, we have two specified natural isomorphisms $\eta: \hom_C(X, -) \stackrel{\sim}{\to} F$ and $\eta': \hom_C(X', -) \stackrel{\sim}{\to} F$. We may thus form a composite of transformation
$\hom_C(X', -) \stackrel{\eta'}{\to} F \stackrel{\eta^{-1}}{\to} \hom(X, -)$which will be a (specified) natural isomorphism $\hom_C(X', -) \to \hom_C(X, -)$. If you like, you could see this as saying that the functor $\hom_C(X, -)$ is represented by $X'$.
Now the general Yoneda lemma says that for any functor $G: C \to Set$, the class of natural transformations $\hom_C(X', -) \to G$ is in (natural!) bijection with the set $G(X')$: that there is a natural isomorphism
$G(X') \to Nat(\hom_C(X', -), G)$which sends any $i \in G(X')$ to the natural transformation $\eta$ defined on components by “$\eta_T: \hom_C(X', T) \to G(T)$ equals the function $\psi \mapsto G(\psi)(i)$”. In particular, for the case $G = \hom_C(X, -)$, we have an isomorphism
$\hom_C(X, X') \to Nat(\hom_C(X', -), \hom_C(X, -)).$At this point it is well to introduce the famous “Yoneda embedding”, which can be expressed in various ways. Here we are referring to a functor $y: C^{op} \to Set^C$, where $Set^C$ is the category of functors $C \to Set$ and natural transformations between them, defined on objects by assigning to an object $X$ of $C^{op}$ (which is the same as an object of $C$) the functor $\hom_C(X, -): C \to Set$. For a morphism $f: X' \to X$ of $C^{op}$, which is to say a morphism $f: X \to X'$ of $C$, we define $y(f): y(X') \to y(X)$ to be the natural transformation $y(f): \hom(X', -) \to \hom(X, -)$ whose component at $T$ is the function $y(f)_T: \hom_C(X', T) \to \hom(X, T)$ that maps $g: X' \to T$ to $g \circ f: X \to T$. (In other words, the only reasonable thing.)
According to the way the Yoneda lemma works (i.e., how the proof of the Yoneda lemma works), the isomorphism in the last displayed line is therefore the functorial map given by $y$:
$\hom_C(X, X') \stackrel{\sim}{\to} Nat(\hom_C(X', -), \hom_C(X, -)): f \mapsto y(f)$or in other words that $y: C^{op} \to Set^C$ is a full and faithful embedding. Sometimes when category theorists refer to the Yoneda lemma, they are really referring to this consequence of the Yoneda lemma, that the Yoneda embedding is full and faithful.
Exploring the meaning of this further: suppose we have a natural isomorphism $\phi: \hom_C(X', -) \to \hom_C(X, -)$, with inverse $\phi^{-1}: \hom_C(X, -) \to \hom(X', -)$. For example, $\phi$ could be the composite $\eta^{-1} \circ \eta'$ mentioned a little while ago. Because the map $f \mapsto y(f)$ is an isomorphism, there is a unique $g: X \to X'$ such that $y(g) = \phi$, and a unique $h: X' \to X$ such that $y(h) = \phi^{-1}$. By functoriality of $y: C^{op} \to Set^C$, we have
$1_{\hom_C(X, -)} = \phi \circ \phi^{-1} = y(g) \circ y(h) = y(g h)$where the composition $g h$ is performed in $C^{op}$; it is the same as the composition $h g: X \to X$ in $C$. At the same time, we have, again by functoriality of $y$, the equation $1_{\hom_C(X, -)} = y(1_X)$. Thus $y(g h) = y(1_X)$; since as we said the assignment $f \mapsto y(f)$ is a bijection, we conclude $g h = 1_X$ in $C^{op}$, or $h g = 1_X$ in $C$. By a completely symmetrical argument, we also conclude $g h = 1_{X'}$ in $C$. Thus $g$ and $h$ are inverse to each other, and $X, X'$ are isomorphic.
Putting this all together, the general conclusion emerges: no matter how they are constructed, if both $X$ and $X'$ satisfy the same universal property (i.e., if they both represent the same functor $F$), then $X$ and $X'$ are canonically isomorphic.
What we will do next is apply this to our specific situation, showing that for join-semilattices $S_1, S_2, S_3$, the two constructions $(S_1 \otimes S_2) \otimes S_3$ and $S_1 \otimes (S_2 \otimes S_3)$ satisfy the same universal property: they both represent the functor $Strd(S_1 \times S_2 \times S_3, -): SemiLat \to Set$. Then we will know there is a canonical isomorphism
$(S_1 \otimes S_2) \otimes S_3 \to S_1 \otimes (S_2 \otimes S_3)$and this will be our associativity isomorphism $\alpha_{S_1, S_2, S_3}$ for the monoidal structure. This will also give us an opportunity to discuss the abstract arguments above in a more concrete situation.
Dear Todd,
Thanks. But I will read it later, not now. I need to work as a Perl programmer to pay for food and for Internet. Right now I have a programming task.
Thanks Todd,
I’ve followed the course of your proof.
The next step is to write in details it for arbitrary $n$-ary staroids for finite $n$ and add it to my draft of the second volume of my book.
But also the following idea arises: Is $\mathsf{Strd}(\square;\square)$ a tensor product in general case of arbitrary posets (not just join semilattices)?
I am going to publish this as a question at MathOverflow, and if nobody is answers, put it at Open Problem Garden.
Sorry for the delay in wrapping this up – you’ll see from how comment 13 ends I haven’t finished the explanation yet.
I think maybe it would be prudent to wait until I finish the explanation before asking more questions. Where I’m going with this is that the category $SemiLat$ of join-semilattices is symmetric monoidal closed, with the tensor product I defined.
The category of posets is also symmetric monoidal closed, but here the product is simply cartesian product. If you have some other product in mind, then I don’t know what it is. I don’t even understand your notation (for example, what are those boxes). Anyway, I hope you’ll be willing to wait just a bit longer for me to finish the explanation before going off to MO. I’ll try to do that soon.
Dear Todd,
I have almost written my version of the proof down.
I do not understand the last thing:
the two constructions $(S_1 \otimes S_2) \otimes S_3$ and $S_1 \otimes (S_2 \otimes S_3)$ satisfy the same universal property: they both represent the functor $Strd(S_1 \times S_2 \times S_3, -): SemiLat \to Set$.
This looks like obvious but where is a proof that they represent this functor?
Nevermind, I’ve realized why they represent the same functor.
I don’t see the last thing:
How $(S_1 \otimes S_2) \otimes S_3 \cong S_1 \otimes (S_2 \otimes S_3)$ implies $\mathsf{Strd}(\mathsf{Strd}(S_1,S_2),S_3) \cong \mathsf{Strd}(S_1,\mathsf{Strd}(S_2,S_3))$?
Didn’t you read comment #16? I said I wasn’t done!
Continuing the discussion: first let me correct a potential misunderstanding about notation. Towards the end of comment 2. I used the notation $Strd(A, B)$ by following what was said in comment 1.; apparently this notation in 1. was meant to indicate a binary tensor product for join-semilattices, and similarly $Strd(A, B, C)$ was meant for a triple tensor product, etc. Later, in comment 12., I reappropriated the notation $Strd$ so that $Strd(S \times T, U)$ means the set of functions $\phi: S \times T \to U$ which preserve joins in separate arguments. I am going to stick now with that latter meaning, but apologize if this caused confusion earlier.
I will now return to the argument from the fourth and fifth paragraphs of comment 2., which was meant to indicate why there is a canonical isomorphism $(S_1 \otimes S_2) \otimes S_3 \to S_1 \otimes (S_2 \otimes S_3)$. As is apparent by the end of comment 13., this follows “from the Yoneda lemma” by observing that both $(S_1 \otimes S_2) \otimes S_3$ and $S_1 \otimes (S_2 \otimes S_3)$ are representing objects for the functor $Strd(S_1 \times S_2 \times S_3, -): SemiLat \to Set$.
At this point – and maybe I should have said so earlier – it may be well to discuss the real point behind this tensor product: that it is the adjoint to the appropriate hom for join-semilattices, in other words the category $SemiLat$ is a symmetric monoidal closed category.
What is the appropriate hom? Let $S, T$ be join-semilattices, and define $Hom(S, T)$ to be the set of join-preserving maps $f: S \to T$, realized as a join-semilattice by putting $(f \vee g)(s) \coloneqq f(s) \vee g(s)$ in $T$ for all $s \in S$. Here it should be verified that the function $f \vee g$ thus defined is indeed a join-preserving map if $f, g$ are, but this is easy by associativity and commutativity of $\vee$: in brief, we have
$(f \vee g)(s \vee s') = f(s \vee s') \vee g(s \vee s') = f(s) \vee f(s') \vee g(s) \vee g(s') = f(s) \vee g(s) \vee f(s') \vee g(s') = (f \vee g)(s) \vee (f \vee g)(s')$and arguing similarly for preservation of the empty join $0$.
Proposition: Let $S_1, \ldots, S_{n-1}, S_n$ and $T$ be join-semilattices. Then maps $S_1 \times \ldots \times S_{n-1} \to Hom(S_n, T)$ that preserve joins in ($n-1$) separate arguments are in natural bijection with maps $S_1 \times \ldots \times S_{n-1} \times S_n \to T$ that preserve joins in ($n$) separate arguments.
This can really be left to the reader. A function $\phi: S_1 \times \ldots \times S_{n-1} \times S_n \to T$ induces a map $\hat{\phi}: S_1 \times \ldots \times S_{n-1} \to Func(S_n, T)$ where $\hat{\phi}(s_1, \ldots, s_{n-1})$ is the function $\phi(s_1, \ldots, s_{n-1}, -): S_n \to T$, and $\hat{\phi}(s_1, \ldots, s_{n-1})$ lies in $Hom(S_n, T)$ if and only if $\phi$ preserves joins in the last argument. Moreover, $\hat{\phi}: S_1 \times \ldots \times S_{n-1} \to Hom(S_n, T)$ preserves joins in each of its arguments if $\phi$ preserves joins in each of the first $n-1$ arguments: for the $i^{th}$ argument, we have
$\hat{\phi}(s_1, \ldots, s_{i-1}, s \vee s', s_{i+1}, \ldots, s_{n-1}) = \hat{\phi}(s_1, \ldots, s_{i-1}, s, s_{i+1}, \ldots, s_{n-1}) \vee \hat{\phi}(s_1, \ldots, s_{i-1}, s', s_{i+1}, \ldots, s_{n-1})$iff for all $s_n \in S_n$ we have
$\hat{\phi}(s_1, \ldots, s_{i-1}, s \vee s', s_{i+1}, \ldots, s_{n-1})(s_n) = \hat{\phi}(s_1, \ldots, s_{i-1}, s, s_{i+1}, \ldots, s_{n-1})(s_n) \vee \hat{\phi}(s_1, \ldots, s_{i-1}, s', s_{i+1}, \ldots, s_{n-1})(s_n)$but by definition of $\hat{\phi}$ this is the same as saying
$\phi(s_1, \ldots, s_{i-1}, s \vee s', s_{i+1}, \ldots, s_{n-1}, s_n) = \phi(s_1, \ldots, s_{i-1}, s, s_{i+1}, \ldots, s_{n-1}, s_n) \vee \phi(s_1, \ldots, s_{i-1}, s', s_{i+1}, \ldots, s_{n-1}, s_n)$which is the same as saying $\phi$ preserves joins in the $i^{th}$ argument. The naturality statement is a routine verification. $\Box$
Thus, for example, we have isomorphisms (natural in all of its arguments)
$Hom(S_1 \otimes S_2, T) \cong Strd(S_1 \times S_2, T) \cong Hom(S_1, Hom(S_2, T)$which says that $- \otimes S_2: SemiLat \to SemiLat$ is left adjoint to the functor $Hom(S_2, -): SemiLat \to SemiLat$: a crucial part of the statement that $SemiLat$ is thereby a symmetric monoidal closed category.
Continuing this theme, we also have isomorphisms (natural in all arguments)
$Hom((S_1 \otimes S_2) \otimes S_3, T) \cong Hom(S_1 \otimes S_2, Hom(S_3, T)) \cong Hom(S_1, Hom(S_2, Hom(S_3, T)))$ $Hom(S_1 \otimes (S_2 \otimes S_3), T) \cong Hom(S_1, Hom(S_2 \otimes S_3, T)) \cong Hom(S_1, Hom(S_2, Hom(S_3, T)))$so that in particular we have a natural isomorphism $Hom((S_1 \otimes S_2) \otimes S_3, -) \cong Hom(S_1 \otimes (S_2 \otimes S_3), -)$. By the Yoneda lemma, we derive an isomorphism
$\alpha_{S_1, S_2, S_3}: (S_1 \otimes S_2) \otimes S_3 \to S_1 \otimes (S_2 \otimes S_3).$also natural in all of its arguments. This gives the associativity constraint $\alpha$ for the monoidal structure.
Inductively, we have by the proposition above that $Strd(S_1 \times \ldots \times S_n, T) \cong Hom(S_1, -) \circ Hom(S_2, -) \circ \ldots \circ Hom(S_n, -)(T)$ and so, for example, each of $(S_1 \otimes S_2) \otimes S_3$, $S_1 \otimes (S_2 \otimes S_3)$, and the “unbiased” triple tensor product $F(S_1 \times S_2 \times S_3)/\sim$ introduced in comment 7, are all representing objects of $Hom(S_1, -) \circ Hom(S_2, -) \circ Hom(S_3, -)$ and hence are canonically isomorphic to each other.
What is $Func(S_n, T)$? I don’t understand what is $Func$.
The set of functions from $S_n$ to $T$.
Dear Todd,
Why have you did a lengthy proof that $(S_1 \otimes S_2) \otimes S_3 \to S_1 \otimes (S_2 \otimes S_3)$ is a canonical isomorphism? Isn’t it a consequence of the fact that $\otimes$ is a tensor product? Or is the issue that this is not just an isomorphism, but as you name it a “canonical isomorphism”?
To prove that you have a “tensor product”, i.e., a monoidal product, you have to exhibit the associativity isomorphism. That’s what I was doing.
There is no guarantee that any old thing you call a “tensor product” will have the properties required of a monoidal product; you have to prove it. So in this case, where else is it proven?
When I bang on about “canonical” isomorphism: that’s actually very important. For example, it leads quickly to a proof that the pentagon equation will hold for our associativity (which I hadn’t gotten to yet, but I can if you’re interested). The key is that there is a unique isomorphism between representing objects (that respects universal elements).
There is no guarantee that any old thing you call a “tensor product” will have the properties required of a monoidal product; you have to prove it. So in this case, where else is it proven?
I thought you got existence of tensor product $S_1\otimes S_2$ for semilattices as granted.
Now I understand you did not. Then what you denote writing $S_1\otimes S_2$?
Victor, there seems to be some confusion here. Yes, I initially constructed a tensor product, whose value at a pair $(S_1, S_2)$ is denoted $S_1 \otimes S_2$.
But then, to show that this tensor product is part of a monoidal category structure, one must go further and construct explicit associativity isomorphisms. That part is not immediate just from the construction of the tensor product. One way or another, it’s another thing that has to be constructed.
(The sentence of mine you quoted was not expressed as well as it should have been. The point is that to give a monoidal category structure, there’s still more structure to be exhibited, even after the tensor product has been constructed.)
The title of this thread “… proof that a category is monoidal”, is similarly suboptimally expressed. “Monoidal” is not a property of a category: it involves extra structure on a category, namely a tensor product, an associativity, etc., satisfying some further properties. (Just like we don’t say “proof that a set is a topological space” – that doesn’t make sense, because a topological space is not a set satisfying some property, it’s a set equipped with a structure called a topology.)
Ignoring issues that in ZFC a certain set may very well just be a topological space…
Dear Todd,
You misunderstood my question.
I ask where is the definition of $\otimes$. It seems that you use it without a definition.
$S \otimes T \coloneqq F(S \times T)/\sim$, as in comment 7. That comment also gives an “unbiased” definition of $n$-fold tensor products.
Actually, I say it explicitly already in my second paragraph of comment 2., if you look carefully.
I don’t understand what is “monoidal closed category”.
Did you try looking it up? monoidal closed category
Actually, what we have here for $SemiLat$ is a symmetric monoidal closed category, meaning a symmetric monoidal category for which each functor $- \otimes T$ has a right adjoint, which in my comments here I have denoted by $Hom(T, -)$. The notation in the linked article would have instead $[T, -]$.
By the way, I should mention that my comments above work out a very specialized example, and that category theorists would tend to place the fact that $SemiLat$ forms a symmetric monoidal closed category within a much more general context of commutative monad or commutative algebraic theory. But I don’t want to try to say too much at you all at once. I bring it up now because what you think of as looking “complicated” is easily generalized to much broader contexts, known to category theorists since the early 70’s (work of Anders Kock on commutative monads).
Excuse me, I misunderstand something:
You have proved that $Strd(S_1\times\dots\times S_n, T)$ is an unbiased tensor product (in category of join-semilattices) for any $T$ (and particularly for $T=2$, the case which I call “$n$-ary staroids is an unbiased tensor product”).
But take $T=\emptyset$ for a counter-example.
Please help me to understand what is my error.
Counterexample to what, exactly? I don’t know what the problem would be even if we weren’t including empty joins, but as far as I’m concerned, finite joins include empty joins, so that $T$ has at least a bottom element. Did you see earlier (as in comment 2.) where I say ’$0$’? That $0$ is a bottom element.
Possibly you are not heeding the warning I tried to give at the beginning of comment 21., which explained that I would be appropriating the notation $Strd(S_1 \times \ldots \times S_n, T)$ to mean the set (or even join-semilattice) of maps $S_1 \times \ldots \times S_n \to T$ which preserve joins in separate arguments. Such maps are in natural bijection with maps $S_1 \otimes \ldots \otimes S_n \to T$. It’s the domain $S_1 \otimes \ldots \otimes S_n$ (constructed as $F(S_1 \times \ldots \times S_n)/\sim$) which I would call an “unbiased” tensor product – but perhaps this mention of unbiased is a distraction at this point. I do not call the join-semilattice $Strd(S_1 \times \ldots \times S_n, T)$ a tensor product.
Right now it’s hard for me to tell how carefully you are reading what I’ve written. But I hope you are putting some thought into it before you ask questions. I was kind of hoping you take at least some initiative in looking stuff up like monoidal closed category, before saying you don’t understand it.
I am confused.
You have formed tensor product $\otimes$ for the category of join-semilattices and proved that it is associative (up to isomorphism).
But I’ve asked for a different thing.
I asked to prove that $Strd(-,-)$ is a tensor product in the category of join-semilattices.
$Strd(A,B)$ is by definition a map $A\times B\rightarrow 2$ preserving finite joins in separate arguments.
So are both $\otimes$ and $Strd(-,-)$ tensor products? If such, they must be isomorphic, must not them? And where is the proof that they are isomorphic?
Victor:
This “discussion” is somewhat exasperating to me because, although I have tried repeatedly to explain how I am using notation, there are continued misunderstandings.
I believe now it would be best if I abandon my usage of the “Strd” notation, because we seem to be talking at cross-purposes. Maybe I’ll start using the notation $Multijoin(S_1 \times \ldots \times S_n, T)$ instead, to denote what I had intended (as in 21.). I suppose it is my fault, that I should have anticipated that this would be confusing to you, despite warnings.
$Strd(A,B)$ is by definition a map $A\times B\rightarrow 2$ preserving joins in separate arguments.
No, I’m pretty sure you can’t mean exactly what you say here.
You do say in comment 1. that a “staroid” (between $A$ and $B$, presumably) is a map $f: A \times B \to 2$ that preserves joins in separate arguments. That much is completely fine. I have no problem with that.
It would also make sense to me if you meant to say $Strd(A, B)$ denotes the set (or the join-semilattice) of such staroids between $A$ and $B$. That would be defining $Strd(A, B)$ as a definite thing that depends on $A$ and $B$.
(It would also make grammatical sense to define $Strd(-, -)$ as a relation, to mean “there exists a staroid from $A$ to $B$. I’m quite sure you don’t mean that, but it would at least make grammatical sense.)
But, simply at a grammatical level, it seems incoherent to me to say “$Strd(A, B)$ is a map $A \times B \to 2$ preserving joins in separate arguments”. If there are two distinct such maps $f$ and $g$, it would seem to be saying that $Strd(A, B) = f$ and $Strd(A, B) = g$ are both valid assertions according to this “definition”, making $Strd(A, B)$ (as $f$) unequal to itself (as $g$).
Besides: a staroid (as a map) couldn’t be a tensor product of two things (as object), since “map” and “object” are of different types.
Let me assume that you meant to say $Strd(A, B)$ is the set or join-semilattice of maps $A \times B \to 2$ that preserve joins in separate arguments. Then it is at least grammatical to ask whether $Strd(A, B)$ and $A \otimes B$ are isomorphic, and if so where I “prove” it.
But this is not at all what I meant by $A \otimes B$. Nor do I understand how $Strd(A, B)$ is reasonably construed as any type of tensor product, because tensor products are covariant in each argument, whereas $Strd(A, B)$ would be contravariant in its arguments. You will never see a proof from me that $A \otimes B$ and $Strd(A, B)$ are isomorphic.
I will say that the join-semilattice $Strd(A, B)$ is isomorphic to $Hom(A \otimes B, 2)$, and thus is a kind of dual of the tensor product $A \otimes B$. If you are satisfied with that, we can continue with the discussion.
Dear Todd,
Thanks you very much.
Now we know that $Strd$ is not a tensor product.
Thus, the discussion about this is of no interest for my research anymore.
However, reading what you have written was a good exercise for me. But this is only an exercise, no particular results of your proofs are of any specific interest to me.
I will probably re-read this thread, now with understanding that you was not proving “tensoriality” of $Strd$ as I implied previously.
$Strd(A, B)$ would be contravariant in its arguments
What do you mean? $Strd(A, B)$ is a set. What does its contravariance mean?
From 1.:
Then the MathOverflow answer states that this is equivalent to order homomorphism $\bigotimes_{i\in n} S_i \rightarrow 2$ (where $\bigotimes$ is a tensor product). I don’t understand why.
My carefully written posts explained that point for you in detail.
I want to prove that $\mathsf{Strd}(-,-)$ is a tensor product in the category $\mathbf{Pos}$.
Something equivalent to this is claimed (for the special case of join-semilattices) in this this MathOverflow answer.
No, you obviously misunderstood what was claimed in Mamuka’s answer.
Moreover when I tried to prove $\mathsf{Strd}(A,B,C) = \mathsf{Strd}(\mathsf{Strd}(A,B), C)$, I had a trouble leading me to think that it isn’t an equality (and then $\mathsf{Strd}(-,-)$ would be not a tensor product), but I remembered that this is stated in that MO question.
You mean Mamuka’s MO answer? As I just said, you misunderstood.
What do you mean? $Strd(A, B)$ is a set. What does its contravariance mean?
In view of the declared lack of interest that all my posts have for you, this will be my last response to you. The functor which takes $(A, B)$ to $Strd(A, B)$ is a contravariant functor.
Thus, the discussion about this is of no interest for my research anymore.
Goodbye then, and good luck in your research.
In view of the declared lack of interest that all my posts have for you, this will be my last response to you.
Well, one thing was useful: your proof that finitary staroids are isomorphic to certain semilattice morphisms to the object $2$ (and thus are isomorphic to ideals). It is a very important result.
I will attempt to generalize it for infinitary staroids (staroids where $n$ is infinite).
1 to 40 of 40