Prove that $\leq_p\subseteq\mathbb N^\infty\times\mathbb N^\infty$ is transitive

47 Views Asked by At

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\}$.

  1. Prove that $\leq_p$ is transitive.
  2. Give an example for an infinite chain in $(\mathbb N^\infty, \leq_p)$.

Image.

It will be great, if someone explain me how to prove this. Thank you.

1

There are 1 best solutions below

2
On

Hint. This is equivalent to plain old lexicographical ordering.