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:
(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 ℤ?"
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
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP