Computability Theory has many examples of this. For example, the halting set $K$ is order-isomorphic to $\mathbb{N}$, but there is no computable order-preserving bijection between them.
François G. Dorais
- 44.4k
- 6
- 150
- 233