I am learning a programming learning and there while learning semantics I came across this question.
Let $\mathbb N^\infty$ be the set of all infinite sequences of natural numbers (e.g., $[0,0,2,2,4,4,\dotsc]\in\mathbb N^\infty$) and let $\leq_p\subseteq\mathbb N^\infty\times\mathbb N^\infty$ be the relation that compares infinite sequences of natural numbers by their prefix sums. The $n$th prefix sum $p_n(s)$ for some $n\in\mathbb N$ of a sequence $s\in\mathbb N^\infty$ is the sum of the first $n$ elements of $s$. We have $s\leq_p s'$ if and only if $s = s'$ or there is an $n\in\mathbb N$ such that $p_n(s)<p_n(s')$ and $p_m(s) = p_m(s')$ for all $m\in \{0,\dotsc, n-1\}$.
- Prove that $\leq_p$ is transitive.
- Give an example for an infinite chain in $(\mathbb N^\infty, \leq_p)$.
It will be great, if someone explain me how to prove this. Thank you.
Hint. This is equivalent to plain old lexicographical ordering.