- #1
S.Daedalus
- 221
- 7
In asking this question, I have two problems: 1. I am not entirely certain this is the right forum to ask it; if it isn't, I hope someone will kindly send me somewhere else. 
2. I am also not sure I understand enough of the topic to even ask a sensible question... But I guess there's only one way to find out.
Anyway, here goes. In his 1967 paper, Diagonal Arguments and Cartesian Closed Categories, Lawvere provided a unified way to look at the various famous results by Cantor, Russell, Gödel, Turing, Tarski etc. through the lens of category theory. The argument itself is simple enough to present a quick example, a proof of Cantor's theorem that there can be no onto function from \mathbb{N} to its powerset.
First, we need a proposed enumeration of all the subsets of a set (\mathbb{N} for convenience), S_m. Then define f: \mathbb{N} \times \mathbb{N} \to \{0,1\} as:
<br /> f(n,m) =<br /> \begin{cases}<br /> 1 & \text{if } n \in S_m \\<br /> 0 & \text{if } n \notin S_m \\<br /> \end{cases}<br />
So f(-,m) is the characteristic function for each S_m. Let \alpha: \{0,1\} \to \{0,1\} be the negation function \alpha(0) = 1, \alpha(1) = 0. Finally, we need a map \Delta: \mathbb{N} \to \mathbb{N} \times \mathbb{N}, the diagonal map, that sends every n \in \mathbb{N} to (n,n) \in \mathbb{N} \times \mathbb{N} -- it 'copies' its input. Using those, we can construct a map g: \mathbb{N} \to \{0,1\} as follows:
g(m) = \alpha(f(\Delta(m)))
This is the characteristic function of a set G = \{m \in \mathbb{N}| m \notin S_m\}. The crux now is that this set can't be part of the S_m: for if that were the case, then g(-) = f(-,m_0) for some m_0, which we could evaluate at m_0: g(m_0) = f(m_0,m_0), which by definition of g implies g(m_0) = \alpha(f(m_0,m_0)) = f(m_0,m_0), which is clearly false (\alpha being the negation operator). So we have a set G that is a subset of \mathbb{N}, yet which is clearly not part of our proposed, arbitrary enumeration of subsets of \mathbb{N}.
If someone wants to have a look at a better presentation of the argument, http://de.arxiv.org/abs/math/0305282" a good expository paper showing the basic structure and generalization to other diagonalization proofs.
That is all well and good (and elegant)! However, the proof relies on the existence of a Cartesian product -- otherwise, one could not define the diagonal map. In categories lacking such structure, it seems to me that the proof therefore doesn't work. My question is, basically -- what does that mean? It seems to me that, for instance, Gödel incompleteness or the undecidability of the halting problem should be more general than that -- as a concrete example, the category of Hilbert spaces endowed with the usual tensor product is not Cartesian. This is the arena of quantum mechanics, and thus of quantum computation -- yet, for a quantum computer, the halting problem is as undecidable as it is for a classical one.
So what am I missing? If diagonalization arguments are a feature of Cartesian categories, does the undecidability of the halting problem in Hilb come about by some other means? Or is it just not applicable? What about incompleteness? It would surprise me if that should be limited to CCs...
Does this question even make sense, or am I thinking about things completely the wrong way round?
2. I am also not sure I understand enough of the topic to even ask a sensible question... But I guess there's only one way to find out.Anyway, here goes. In his 1967 paper, Diagonal Arguments and Cartesian Closed Categories, Lawvere provided a unified way to look at the various famous results by Cantor, Russell, Gödel, Turing, Tarski etc. through the lens of category theory. The argument itself is simple enough to present a quick example, a proof of Cantor's theorem that there can be no onto function from \mathbb{N} to its powerset.
First, we need a proposed enumeration of all the subsets of a set (\mathbb{N} for convenience), S_m. Then define f: \mathbb{N} \times \mathbb{N} \to \{0,1\} as:
<br /> f(n,m) =<br /> \begin{cases}<br /> 1 & \text{if } n \in S_m \\<br /> 0 & \text{if } n \notin S_m \\<br /> \end{cases}<br />
So f(-,m) is the characteristic function for each S_m. Let \alpha: \{0,1\} \to \{0,1\} be the negation function \alpha(0) = 1, \alpha(1) = 0. Finally, we need a map \Delta: \mathbb{N} \to \mathbb{N} \times \mathbb{N}, the diagonal map, that sends every n \in \mathbb{N} to (n,n) \in \mathbb{N} \times \mathbb{N} -- it 'copies' its input. Using those, we can construct a map g: \mathbb{N} \to \{0,1\} as follows:
g(m) = \alpha(f(\Delta(m)))
This is the characteristic function of a set G = \{m \in \mathbb{N}| m \notin S_m\}. The crux now is that this set can't be part of the S_m: for if that were the case, then g(-) = f(-,m_0) for some m_0, which we could evaluate at m_0: g(m_0) = f(m_0,m_0), which by definition of g implies g(m_0) = \alpha(f(m_0,m_0)) = f(m_0,m_0), which is clearly false (\alpha being the negation operator). So we have a set G that is a subset of \mathbb{N}, yet which is clearly not part of our proposed, arbitrary enumeration of subsets of \mathbb{N}.
If someone wants to have a look at a better presentation of the argument, http://de.arxiv.org/abs/math/0305282" a good expository paper showing the basic structure and generalization to other diagonalization proofs.
That is all well and good (and elegant)! However, the proof relies on the existence of a Cartesian product -- otherwise, one could not define the diagonal map. In categories lacking such structure, it seems to me that the proof therefore doesn't work. My question is, basically -- what does that mean? It seems to me that, for instance, Gödel incompleteness or the undecidability of the halting problem should be more general than that -- as a concrete example, the category of Hilbert spaces endowed with the usual tensor product is not Cartesian. This is the arena of quantum mechanics, and thus of quantum computation -- yet, for a quantum computer, the halting problem is as undecidable as it is for a classical one.
So what am I missing? If diagonalization arguments are a feature of Cartesian categories, does the undecidability of the halting problem in Hilb come about by some other means? Or is it just not applicable? What about incompleteness? It would surprise me if that should be limited to CCs...
Does this question even make sense, or am I thinking about things completely the wrong way round?
Last edited by a moderator:
