Another thing which has bothered me in the past was that a set of 2-tuple integers could be mapped by a set of 1-tuple integers, seemingly without any information loss.
The "seemingly" suggests that you remain unconvinced. If you define for example some kind of distance between an arbitrary (x,y) and (0,0), for any (x,y) you can easily count how many points are closer to the origin. There may be ties but it's easy to define a rule to break them. This means you can order all the pairs of integers: (0,0), (1,0), (0,1), (-1,0), (0, -1), (1,1), (1,-1), (-1,-1), (-1,1), (2,0),....
I am not sure if you have heard of them, but space-filling curves are a way to demonstrate this. This is a great video on the Hilbert curve https://www.youtube.com/watch?v=3s7h2MHQtxc
This picture is for natural numbers but it shows you one way to do the mapping: