tomtom2357 wrote: Another interesting idea is that if square roots come in pairs, then maybe compositional square roots come in pairs too. Let f(x) be our original function, and let g(x) and h(x) be a pair of compositional square roots of f(x), and let i(x)=g(h(x)), what would i(x) look like? Knowing one of the square roots of a function, how do you calculate its pair?

There's generally many more than "a pair". Consider f(x) = 0. Define g

_{a}(x):=a for x !=a and g

_{a}(a):= 0 - then g

_{a}(g

_{a})=0 for any a!=0.

The same example shows us we know little about the composition of two different compositional square roots. In the above example, b!=a, then g

_{a}(g

_{b})(x) is a for all x.

mfb wrote:>> It appears that the argument works the same for uncountable totally ordered sets?

As long as there is a bijection from this set M to R which preserves the ordering: Of course. Map your function f': M->M to a function f:R->R, find g, map it back to g':M->M.

Right, for sets order-isomorphic to R, that obviously works. I was thinking about the general case. For instance, the density argument works for any uncountable Hausdorff-space, and since totally ordered sets are Hausdorff with order topology, that argument works for any totally ordered set. However, the step "countable complement" => dense is at least worth a proof... and the question not immediately clear to me is whether "monotoneuous bijective => continuous" works for any totally ordered set. I think this is not necessarily true. However, if we add the requirement for f to be continuous, then the same argument should hold.

mfb wrote:Oh, and I can add another category: f:R->R bijective with f(x)>x for all x or f(x)<x for all x. Injective should be sufficient, and I think it is required for the general statement.

I don't think injective is sufficient; without surjectivity, you potentially get chains of the type {x, f(x), ...} as well, and it's at least not clear how it follows that there's infinitely many of each type in this setup.

Deedlit wrote:We do have to worry about uncountable branchings of preimages - I'm not sure if an uncountable branching is always equivalent to a countably infinite branching, since there are uncountably many possibly tree structures.

I think we do need to at least think about cardinalities here in general.

Consider f:R->R defined as following: x in unique decimal representation. If x is integer !=0, map it to 1. If x is not integer, cut off anything before the decimal point, then replace all occurances of the highest occuring digit with the next lower digit. If this would map an irrational x to a rational one, map it to an arbitrary irrational with the "available digits" instead (we can chose a fixed one for each type of "max digit" - we do this just so the rationals and irrationals don't "connect"). Lastly, map any rational only containing digits 1 and 0 behind the decimal point to 1.

This function, unless I missed some case, should have two equivalence classes, one ending at 0, one ending at 1, and the one ending at 0 will have uncountable preimages on each level. We cannot pair these two (even if we leave other "fixable" issues aside) in the "typical" way of jumping from same preimage depth to the same for the other set and then back - if we could, we'd need g to map a countable set surjectively into an uncountable set, and that's obviously not possible.

But that says nothing about what "skipping" we can do within the tree with uncountable width, of course, and much less about what's possible there in the general case. I think we could find a decomposition for the uncountable set: since every point has infinite preimages (or none), we can start pairing those from top down such that preimage(x) -> preimage(y) -> x -> y -> 0 etc. We don't get into issues at the top level since we can let g map to zero, and we always have infinite selection of further preimages for every point. So on the level below, with a in preimage(x) and b in preimage(y), we can map preimage(a)->preimage(b)->a->b->x->y->0, and so on. In fact, this should also work for any tree where all preimages have equal even or infinite cardinality, but that's something I need to think through more as well.

But: If we modify f so that instead of ending at a fixed point 0, we end in a loop (e.g. by mapping 0->1->0 and moving the end point for the rational part to 2), then that method doesn't work, and I think by standard argument, we already know we can't map that tree to itself. So that should then be an example where the cardinalities matter. I think.