A finite list of reals, and its strictly increasing and strictly decreasing sublists

Let $N\in \mathbb{N}$ (The natural numbers $\mathbb{N}$ (von Neumann)). A finite list of reals of length $N$ is a function $a:N\to \mathbb{R}$, written $a_i$ for $a(i)$; here $N=\{i:i<N\}$ is the von Neumann natural itself (On $\mathbb{N}$ the order is membership: $m<n⟺m\in n$, Order on the natural numbers), so the indices are $0,1,\dots ,N-1$ and the list of length $0$ is the empty function. The list is pairwise distinct when $a$ is injective, that is when $a_i\mathrm{\ne }{a}_j$ whenever $i\mathrm{\ne }j$ (Injection, surjection, bijection).

A sublist of $a$ of length $L$, for $L\in \mathbb{N}$, is a function $s:L\to N$ that is strictly increasing on indices, meaning $s(p)<s(q)$ whenever $p<q<L$; its terms are $a_{s(0)},\dots ,a_{s(L-1)}$. Such an $s$ is injective, since natural-order trichotomy gives $p<q$ or $q<p$ when $p\mathrm{\ne }q$, and hence $s(p)\mathrm{\ne }s(q)$ (Trichotomy of the order on $\mathbb{N}$).

The sublist $s$ is

• strictly increasing when $a_{s(p)}<a_{s(q)}$ for all $p<q<L$;
• strictly decreasing when $a_{s(p)}>a_{s(q)}$ for all $p<q<L$,

the order being that of the ordered field $\mathbb{R}$ (Ordered field).

Boundary readings, which are part of the definition and not exceptions. A sublist of length $0$ or $1$ has no pair $p<q<L$ at all, so it is both strictly increasing and strictly decreasing, vacuously. A list of length $N$ has a sublist of length $1$ exactly when $N\ge 1$, namely $s(0):=i$ for any $i<N$; and it has no sublist of length $L$ with $L>N$, since $s$ would be an injection of $L$ into $N$, contrary to the finite pigeonhole principle (The pigeonhole principle on $\mathbb{N}$, clause 2).

Every count here is a natural number. The length of a list and the length of a sublist are naturals, and no cardinality of an infinite set is used; a list is a function on a natural number, so it is finite in the sense of The cardinality $\mid A\mid$ of a finite set.

• A sublist is a choice of positions, not a choice of values. Two positions carrying equal values are different sublists of length $1$. This is why the monotonicity conditions are stated on $a_{s(p)}$ and $a_{s(q)}$ rather than on a set of values, and why the pairwise-distinctness hypothesis has to be imposed separately when a result needs it.

• Strictness on both sides. The indices increase strictly, so a sublist reads the list left to right without repeating a position; the values increase or decrease strictly, so no two terms of a monotone sublist are equal. Neither strictness is redundant: a list may repeat a value, and then a nondecreasing sublist could be longer than any strictly increasing one.

• The empty list. At $N=0$ the only sublists are the empty one, of length $0$. Any statement asserting the existence of a sublist of length $1$ is therefore false at $N=0$, and any statement about lists of length $mn+1$ has content at $m=0$ or $n=0$ precisely because $mn+1\ge 1$.