I want to mention first that these are homework questions. I have done 3 out of 4.
"Do you remember how we used the pairing function and the Gödel numbering to associate each program in the language L with a unique natural number? To be precise, we demanded that every program in L is associated with unique number, and we also required that every natural number is associated with a valid program in L . Now it is your task to develop such one-to-one mappings for other things. If you think that a mapping cannot be defined, please give a reason."
- Define such a mapping for quintuples of natural numbers.
This one was pretty easy.
(a, b, c, d, e) ↔ < <a, b>, <c, <d, e> > > (one possible solution)
- Define such a mapping for odd natural numbers.
I am not sure about this one. I was able to figure out the even number one using the example of where f(x) = (x/2)
(x1, x2, ..., xn, xn+1, xn+2, ..., xn+m) ↔ [m, f(x1), f(x2), ..., f(xn)] – 1 with f(x) = ⎣x/2⎦
Define such a mapping for pairs (x, y), where x and y are letters from the English alphabet.
I determined this is not possible because there are only a finite number of such pairs.
Define such a mapping for the set of natural numbers {0, 1,…, 1000}.
I determined this is not possible because there are only a finite number of such pairs as well.
I just wanted to confirm if my thinking was correct in these questions. 2 gave me trouble.
This question is a little unclear; I'm confused whether they're asking for (e.g.)
An injection from $\mathbb{N}$ to $\mathbb{N}^5$,
An injection from $\mathbb{N}^5$ to $\mathbb{N}$, or
A bijection from $\mathbb{N}$ to $\mathbb{N}^5$.
The choice of interpretation here determines whether 3 and 4 are doable, as you observe.
Meanwhile, I don't understand your approach to 2: what is the thing you've written down? What two sets is it a map between? The way I read the question, they're asking for a bijection between the naturals and the odd naturals, which looks nothing like what you've written.