Existence of 'uniform transformations' of sequences of rationals (apres Friedman)

Question

Let $\mathbb{Q}^*$ be the set of finite sequences of rationals, and let $x \sim y$ if and only if

1. they have the same length, and for all $1 \le i,j \le length(x)$, $x_i \lt x_j$ iff $y_i \lt y_j$ ('order equivalence')

2. if $x_i \in \mathbb{Z}^+$ then $y_i \in \mathbb{Z}^+$

3. if $x_i \not\in \mathbb{Z}^+$ then $x_i = y_i$.

Definition: We say that the function $T:\mathbb{Q}^* \to \mathbb{Q}^*$ is a uniform transformation (with respect to $\sim$) if and only if for all $x \in \mathbb{Q}^*$ we have $(x,Tx) \sim (Tx,TTx)$.

We also have analogous definitions when restricting attention to $\mathbb{Q}^k$ (note that a uniform transformation necessarily restricts to a function $\mathbb{Q}^k \to \mathbb{Q}^k$ for all $k$).

This definition is due to Harvey Friedman (http://www.cs.nyu.edu/pipermail/fom/2012-March/016316.html), and I can only guess that the latter condition involving $(x,Tx)$ involves concatenation of strings [EDIT: it cannot be concatenation, see Aaron's comment below. If anyone can reverse engineer a definition, that would be great. I'll see if I can get Friedman to clarify]. Friedman arrived at this definition by abstracting the required properties of a function he calls $\mathbb{Z}^+\!\!\uparrow$ - it takes a finite string, finds the first entry which is not a positive integer, and then adds 1 to all entries after that. For example.

$$\mathbb{Z}^+\!\!\uparrow(1,3/2,3,5) = (1,3/2,4,6).$$

[EDIT 2: my definition of $\mathbb{Z}^+\!\!\uparrow$ is wrong, see Aaron's answer. The correct definition is to add 1 to all (necessarily integer) entries larger than the supremum of the non-integer entries.]

Now I was wondering if there are any other examples of uniform transformations. I hope there are, because $\mathbb{Z}^+\!\!\uparrow$ looks to me fairly contrived (of course, it is contrived), and others Friedman has asked personally have said the same. On the other hand, perhaps this function (or one like it) arises naturally from some combinatorial problem. My questions

A. What are other examples of uniform transformations?

B. Can we arrive at the function $\mathbb{Z}^+\!\!\uparrow$ 'naturally'?

Any other thoughts are appreciated.

Answer 1

I think that concatenation is correct but your definition of $\mathbb{Z}^+ \uparrow$ is not. The examples from the slides are short and non-decreasing so not general enough for illustration. $$\mathbb{Z}^+ \uparrow (6, \frac32 , 1 , 4 , \frac12 ,2)=(7, \frac32, 1, 5, \frac12 , 3)$$ Write $x\equiv y$ for order equivalence and $x \sim y$ for the stronger relation with conditions on integers and non-integers.

If $x$ is a finite sequence of rationals $x$ and $f:\mathbb{Q} \to \mathbb{Q}$ is a non-decreasing function (possibly defined in terms of $x$) then $x \equiv Fx \equiv FFx$ where $F$ is termwise application of $f.$ Also $(x,Fx) \equiv (Fx,FFx)$

If, in addition, there is a threshold $t$ such that $f(r)=r$ when $r \le t$, then not only is $x \equiv Fx$ but $x_i=Fx_i$ whenever $x_i \le t.$

In this example of $F=\mathbb{Z}^+ \uparrow$ we take $t$ to be the largest (in value) non-integer in $x$ and define $$f(r)=\begin{cases} r &\mbox{if } r \le t \\ r+1 & \mbox{if } r \gt t. \end{cases} $$

Then indeed we have $x \sim Fx$ and also $(x,Fx) \sim (Fx,FFx)$ even if we strengthen the third condition to

3) If $x_i \not\in \mathbb{Z}^+$ then $x_j=y_j$ for all $x_j$ with $x_j \le x_i$

Again, this example arises from Harvey Friedman using his full powers (for many years) to come up with natural seeming finite combinatorial constructions which will persuade the average (non-foundations) mathematician that YOU care about mathematics, not logic. And yet YOU should care not only about ZFC but also about stronger axioms. What he has accomplished is very impressive. Many mathematicians might still feel rather unconvinced.