TransWikia.com

What is the set of all functions from ℤ to ℤ?

Quantum Computing Asked on August 20, 2021

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 Answers

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}$).

Correct answer by keisuke.akira on August 20, 2021

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.

Answered by Upstart on August 20, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP