In David Deutsch's classic paper Quantum theory, the Church-Turing principle and the universal quantum computer (1985), Deutsch writes on p. 99:

C(ℱ) itself, also known as the set of recursive functions, is denumerable and therefore infinitely smaller than the set of all functions from ℤ to ℤ.

(I thought that this might be in typo in the original publication, but it is also present in the version that was retypeset in 1999 which is easily findable on the Internet.)

Since ℤ=ℤ, what is "the set of all functions from ℤ to ℤ?"

  • 2
    $\begingroup$ $\mathbb{Z}$ can be both the domain and the range of a function. So why is $\mathbb{Z} = \mathbb{Z}$ a problem? $\endgroup$ – keisuke.akira Jul 19 '20 at 2:41

Recall that a function between two sets (say $A,B$) is simply a binary relation that associates to every element of the first set $A$ exactly one element of the second set $B$. Therefore, a function can be represented as a set $G$ of ordered pairs $(x,y), x \in A, y \in B$, satisfying the following: each element of $A$ appears exactly once in this set (to make sure there are no repetitions and that a single element cannot be mapped to two different outputs, i.e., this map is a function).

Now, to count the total number of functions between two sets we need to count the number of unique sets (of the form $G$ above) that can be constructed. One can show that the number of functions from a set $A$ to a set $B$ is $|B|^{|A|}$ (see, for example, this intuitive answer).

Do the same for $A = \mathbb{Z} = B$ but beware of their cardinalities (and realize that this set is uncountable, see for example, here).

Update (from the comments): The notation ``set of all functions from $\mathbb{Z}$ to $\mathbb{Z}$'' is shorthand for $\{f | f: \mathbb{Z} \rightarrow \mathbb{Z}\}$, i.e., all functions whose domain and range is $\mathbb{Z}$ (or subsets of $\mathbb{Z}$).

  • $\begingroup$ but ℤ and ℤ are the same number, are they not? Or is "ℤ to ℤ" shorthand for saying "all integers" ? If that is true, whey not just say "in ℤ?" Or is it saying "from any integer to any other integer?" $\endgroup$ – vy32 Jul 19 '20 at 11:27
  • $\begingroup$ @vy32 It is a shorthand for the set of all integers. This notation is ubiquitous (pretty much every math textbook ever written) so I wouldn't blame the author. Basically, this means that the set of "inputs" to the function is $\mathbb{Z}$ and so is the set of "outputs". But since $\mathbb{Z}$ also means any subset of it, it could be any collection of integers (including a single integer mapped to a single integer). Does that answer your question? $\endgroup$ – keisuke.akira Jul 19 '20 at 12:38
  • $\begingroup$ — yes, that answers my question! If you could add it as an answer, I will accept it. I do not blame the author. I blame myself for not having taken enough math classes. $\endgroup$ – vy32 Jul 19 '20 at 13:16
  • $\begingroup$ @vy32 Updated. I don't think anyone needs to be blamed here :) That, I guess, is the purpose of this forum. $\endgroup$ – keisuke.akira Jul 19 '20 at 19:54

Just consider the set of all functions from $\mathbb{Z}$ to a two point set $\{0,1\}$. The cardinality of the set of all functions between these two sets is $2^{|\mathbb{Z}|}$.

Now ask yourself is the power set of $ \mathbb{Z}$ countable. If the answer is NO then the answer to your question is also a NO.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.