0

I've recently learned that the cardinality of the integers and that of the rationals is the same, as you can map the rationals to the integer grid, draw a spiral that eventually touches every point and label from the centre outwards. If I understand it correctly, this is equivalent to saying that there's a bijective map between $\mathbb{N}^2$ and $\mathbb{N}$.

My question is, is there an extension to this idea that has a bijective map between tuples of integers of any size and single integers? For the 3rd dimension I can envision some kind of system with concentric cubic shells, but I can't visualise anything higher than that.

Please note that I'm not formally trained in math. I enjoy learning math on YouTube recreationally but I'll struggle to read denser notation.

ApexPolenta
  • 101
  • 7
    yes, you can go by induction. For example, $\Bbb{N}^3=\Bbb{N}\times \Bbb{N}^2$. Use your bijection $f:\Bbb{N}^2\to\Bbb{N}$ to map $\Bbb{N}\times\Bbb{N}^2\to \Bbb{N}\times \Bbb{N}=\Bbb{N}^2\to \Bbb{N}$, $(a,(b,c))\mapsto (a,f(b,c))\mapsto f(a,f(b,c))$. This is a composition of bijections, hence a bijection. – peek-a-boo Feb 08 '23 at 03:29
  • You can also use the same spiral idea but in higher dimensions. – Qiaochu Yuan Feb 08 '23 at 03:57
  • @peek-a-boo Any chance you have a resource I can use to interpret your answer? I'm not sure what it means – ApexPolenta Feb 08 '23 at 04:04
  • I'm sorry, unfortunately I don't have any good/elementary resources; I picked this stuff up along the way while reading baby Rudin (Walter Rudin, Principles of Mathematical Analysis). But the idea is pretty simple: you have to establish the following fact: if $A_1,A_2$ have the same cardinality, and $B_1,B_2$ have the same cardinality (i.e there exist bijections between them), then so do $A_1\times A_2$ and $B_1\times B_2$ (you just make an 'obvious' bijection). Do this with $A_1=A_2=\Bbb{N}$, and $B_1=\Bbb{N}^2,B_2=\Bbb{N}$. That's essentially what my comment above is saying. – peek-a-boo Feb 08 '23 at 04:12
  • 1
    Want a kind of tricky way? Consider the map $f : \mathbb{N}^n \to \mathbb{N}$ given by $f(a_1, \ldots, a_n) = p_1^{a_1} \cdots p_n^{a_n}$ where $p_1, \ldots, p_n$ are the first $n$ primes. Observe that this map is one-to-one by the unique factorization theorem for primes and in fact embeds $\mathbb{N}^n$ as a strict subset of $\mathbb{N}$. – Charles Hudgins Feb 08 '23 at 04:21
  • @peek-a-boo Never mind, I read it again and I think I can kind of make sense of it. So I start with a triplet of integers $(a, b, c)$ and a mapping from $\mathbb{N}^2$ to $\mathbb{N}$. Then all I need to do is map $b$ and $c$ to a single integer (call this $d$), then map $a$ and $d$ to an integer. Is that basically correct? Seems reversible since the result uniquely maps to $(a,d)$ and $d$ uniquely to $(b, c)$ – ApexPolenta Feb 08 '23 at 04:42
  • 1
    yes that's exactly it. Writing it with the bijection $f$ is just the more formal way of saying things. – peek-a-boo Feb 08 '23 at 05:08

0 Answers0