What's the correct definition of the $\Upsilon$ category of schedules?

Question

I'm reading this article about game semantics and I'm a bit puzzled with the definition given for $\Upsilon$ in section $3.3$. There are some points that are either unintelligible or that don't make sense at all.

The definition provided is based on the concept of schedule:

A schedule $e:\{1, \ldots, n\} \rightarrow {0, 1}$ is a sequence of $0$ and $1$s. We also define $|e| = n$, $|e|_0$ is the number of $0$s in $e$ and $|e|_1$ is the number of $1$s. The notation $e \upharpoonright m$ denotes the restriction of $e$ to its first $m$ terms.

(Where $e$ is actually a function, but we can view $e$ as the sequence $e(1)\cdot e(2)\cdots e(n)$.)

Now the definition of the category $\Upsilon$ is:

• The objects are the natural numbers. We think of $p \in \Upsilon_0$ as the totally ordered set $(p) = \{1, \ldots, p\}$. We write $(p)^+$ for the set of even elements and $(p)^-$ for the set of odd elements of $(p)$.

• The morphism in $\Upsilon(p, q)$ are schedules $e$ such that $|e|_0 = p$ and $|e|_1 = q$.

  A schedule $e: p \rightarrow q$ corresponds to obvious order preserving (collectively surjective) embeddings $l:(p) \rightarrow (p+q)$ and $r : (q) \rightarrow (p+q)$ and thus to order relations $l(x) < r(y)$ from $(p)^+$ to $(q)^+$ and $r(y) < l(x)$ from $(q)^-$ to $(p)^-$

• The identity in $\Upsilon(p, p)$ is the copy-cat function $c$ of length $2p$, such that $c(2k+1) \neq c(2k+2)$. The induced orders are $\leq$ on $(p)^+$ and on $(p)^-$

• Let $e:p \rightarrow q$ and $f: q \rightarrow r$ be morphisms in $\Upsilon$, then their composition $e;f:p \rightarrow r$ is defined by taking the corresponding order relations , composing them as relations and reconstructing the function

Where I emphasized in bold the parts I don't understand. In particular:

• What's the meaning of embedding when he defined morphisms? I know what an embedding functor is, but this definition doesn't apply here.

• What does "$l(x) < r(y)$ from $(p)^+$ to $(q)^+$" mean? Where do $x$ and $y$ come from? My guess is: $x \in (p)^+$ and $y \in (q)^+$. What are $l$ and $r$? My guess would be that $l$, given the index $x$ of a $0$ returns its index in $e$ and $r$ does the same for $1$s but then the $l(x) < r(y)$ part doesn't make any sense to me.

• What's an induced order?

• What does reconstructing a function mean?

---

I hope my question is on-topic here. I didn't ask it on tcs because it doesn't look like a research level question to me.

---

Edit

Reading carefully the rest of the paper, later mentions that $l$ and $r$ are injections, so maybe for embedding he simply meant injection(?).

Assuming this, this is what I thought: the point about morphism means that $e$ could be seen to represent two injective functions $l:\{1, \ldots, p\} \rightarrow \{1, \ldots, p+q\}$ and $r:\{1, \ldots, q\} \rightarrow \{1, \ldots, p+q\}$ such that the union of their images is $\{1, \ldots, p+q\}$. These functions have the property that, for $x \in (p)^+, y \in (q)^+$, $l(x) < r(y)$ and for $x \in (p)^-, y \in (q)^-, r(y) < l(x)$ (although in the text this seems like a consequence of an "obvious order preserving ...". no idea what order he's talking about and how it's obvious.)

We can obtain these functions assigning the lowest values to even arguments for $l$, the next lower values for even arguments to $r$, then the next lower values to odd arguments for $r$ and finally the remaining values for $l$. (i.e. $r(2) = 1, r(4) = 2, \ldots, r(2k) = k$ then $l(1) = k+1, \ldots l(2t+1) = k+t+1$ etc.)

However such $l$ and $r$ are not unique, which is a problem in the rest of the paper since he later uses $l$ and $r$ in some definitions, which cannot be done if $l$ and $r$ aren't unique.

Edit2

Maybe the embedding means order-embedding. However even in this case I don't see how $e$ can be related with one obvious couple of order embeddings. I mean: the most obvious choice is to put $l(x)$ to be the index of the $x$th $0$ in $e$ and similarly for $r(y)$ and $1$s, but then the last statement in the description is wrong(take $e = 010$ we have that $r(1) = 2 > l(1) = 1$ but we should have $r(y) < l(x)$ for odd $x$ and $y$.

Is there any obvious way to define two embeddings $l$ and $r$ in a unique way?

Answer 1

I remember finding this bit very elliptic too. To me, this is clearly research-level, but anyway...

One point that you seem to have missed is that a schedule is defined as a map $e \colon \{1,\ldots,n\} \to \{0,1\}$ satisfying $e(1) = 1$ and $e(2k+1) = e(2k)$.

The intuition behind this is that we're considering views, in the game semantical sense. That is, we have an arrow arena, say $A \to B$, and two opponents, one on the left, say $L$, one on the right, say $R$, and the arrow arena lets us play against both of them at the same time. Only, $A$ and $B$ are `polarised' games, i.e., players should take turns and the starting player is specified, and $R$ is to start in $B$, whereas we are to start in $A$. Finally, we are only allowed to change side when its our turn on both sides (this is called the switching condition) and the first move of all is to be played by $R$.

Schedules model `shapes of plays' in such a setting. E.g., $0$'s and $1$'s stand for moves in $L$ and $R$, respectively. Hence, $e(1) = 1$ says that $R$ is to play first. Furthermore, $e(2k+1) = e(2k)$ says that all oour moves are immediately answered by the corresponding opponent.

Any schedule $p \to q$ is equivalently specified by the first point in $q$ after which we have played in $p$, then the first point after that in which we switched again to $q$, etc. The first relates an odd index in $q$ to an odd index in $p$, the second relates an even index in $p$ to an even one in $q$, etc, hence defining relations $R \colon (p)^+ \not\to (q)^+$ and $L \colon (q)^- \not\to (p)^-$.

Any such pair of relations comes from a schedule iff the union of $R$, $L$, and the underlying orders of $p$ and $q$ generates a total ordering on $p+q$. I haven't done the exercise of proving that such pairs $(R,L)$ are stable under composition...

Anyway, a graphical intuition is that instead of drawing schedules as (vertical) lists of $0$'s and $1$'s, you may draw any of them as two vertical lists of dots side by side ($0$'s to the left, $1$'s to the right!), plus arrows indicating when to switch from right to left and back.

The meaning of `induced orders' are the obtained relations $R$ and $L$. So for copycat, they are relations $p^+ \not\to p^+$ and $p^- \not\to p^-$.

A doubt remains, to me at least, about their definition of copycat. I'd have said copycat induces the discrete order on both $(p)^+$ and $(p)^-$. Am I missing anything?