Why does the ordering function invert itself?

Question

I notice in my R console that x=sample(1:n); all(order(order(x)) == x) always evaluates TRUE, for any n. Just to assure you I'm not on the wrong SE site here, I know exactly what the code means, but this still makes my brain hurt. Can anyone draw a picture or give an explanatory proof to show what's going on?

Programming background

In R, sample scrambles a sequence, sampling without replacement, and order gives indices such that x[order(x)] is ascending. == does element-wise comparison, returning a vector of logical values. all returns TRUE for a list that's all TRUE and FALSE if the list contains any FALSE elements.

Answer 1

In general, when $x$ is a list of $n$ elements, $\text{order}(x)$ is a permutation of $\{1,2,\ldots,n\}$ such that $x_{\text{order}(x)_i} \le x_{\text{order}(x)_j}$ whenever $i<j$. (The elements of $x$, taken in the order given by $\text{order}(x)$, are non-decreasing.) When $x$ is itself a permutation of $\{1,2,\ldots,n\}$, this constraint uniquely defines the order function, and indeed we can say that $x_{\text{order}(x)_i}=i$. (The elements of a permutation of $\{1,2,\ldots,n\}$, taken in non-decreasing order, are just $1,2,\ldots,n$.)

So, in the group of permutations under the composition operator, $\text{order}(x)=x^{-1}.$ But this immediately gives the desired result: $$ \text{order}(\text{order}(x))=\text{order}(x)^{-1}=\left(x^{-1}\right)^{-1}=x. $$

Answer 2

any is a quantifying operator. If test whether one sequence is identic independent of order to the other. So x=sample(1:n); any(order(order(x)) == x) has always to be true. order() is idempotent. That is, if applied once there is no more change in the next application of order() to the sequence it is applied to.

From order You get the information the order() has the argument decreasing. Per default that is set to FALSE. To invert the order the command has to be

x=sample(1:n); order(order(x),decreasing=TRUE) == x)

Then the any() is obsolete. any implements "Are Some Values True?". So in x=sample(1:n); any(order(order(x)) == x) the identity check == is applied elementwise on the cross of the two lists x and order(order(x)) and then the complete misses are discarded in favor of the few matches.

So

x=sample(1:n); order(order(x)) == order(x) is TRUE always verifying the idempotence of order().