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

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.

• Finite trees maybe, let a sequence of integers consist of some sort of branch, and at non-integers you have a branching node. The branching node splits based on some coding, but the idea would be to have the tree above the branching node coded by the rest of the sequence occurring after the fraction. In this way based on whatever coding you pick for how to split the branching nodes, the uniform transformation extends the tree above the root, by leaving non-branching nodes (ie integers) alone, and possibly adding more splits at a branching node (non-integers) – Not Mike Mar 15 '12 at 10:01
• MO needs some sort of collaborative drawing board, then the above would make much more sense. – Not Mike Mar 15 '12 at 10:04
• @Michael, If you can draw it and scan it, then email it to me, I can post it somewhere online (or you can yourself). – David Roberts Mar 15 '12 at 10:43
• I'm not sure about the definitions. The definition of uniform transformation implies that $x \sim Tx.$ But for $T=\mathbb{Z}^+\!\!\uparrow$ and $x= 3/2 ,1$ we have $y=Tx=3/2,2$ so order equivalence fails: $x_1 \gt x_2$ but $y_1 \lt y_2.$ My understanding is that Harvey Friedman goes to great effort to make his examples as natural seeming as possible. – Aaron Meyerowitz Mar 15 '12 at 17:26
• Thanks, Aaron. I really have no idea what $(x,Tx)$ means, that it is concatenation was only a guess. I will inquire further. – David Roberts Mar 15 '12 at 23:48

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.

• I heartily agree that this is a very impressive achievement. I would love to see such a combinatorial statement, say about trees, as Michael Blackmon suggested, that gives rise to such an $F$. Thanks for clearing up my (now patently obvious!) mistake. – David Roberts Mar 17 '12 at 3:32