# Prove that removing elements from a sorted list of numbers does not make the list unsorted

In other words, you have an ordered finite list of numbers which is sorted ascendingly (without loss of generality), for example [1,2,5,7,10,12]. Remove elements from the list, the list is still sorted. Prove this mathematically.

I know this is intuitive but how to prove it mathematically.

I tried induction but I struggled with mathematical representation of a sorted list (how to denote a sorted list mathematically).

• My first stab would be using induction on the number of elements removed from the list. Your base case ($n=0$) is obviously true, and the inductive step would involve removing a single element from a sorted list.
– MPW
Commented Sep 18, 2015 at 2:10
• Thanks. This is an elegant proof which does not require any mathematical representation.
– user215750
Commented Sep 18, 2015 at 2:13

Suppose

$$a_1, a_2, \ldots, a_n$$

is sorted. This means

$$i \geq j \implies a_i \geq a_j \tag{1}$$

Now we remove $a_k$.

$$a_1, \ldots, a_{k-1}, a_{k+1}, \ldots, a_n$$

Now show that this new list satisfies the property of a sorted array. If $i \geq j$ and $i,j \neq k$, then it is still true that $a_i \geq a_j$ from $(1)$. Thus the array is still sorted.