(Non-)Cartesian Categories and Diagonal Arguments

  • Thread starter S.Daedalus
  • Start date
  • #1
221
7

Main Question or Discussion Point

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. :smile: 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 [tex]\mathbb{N}[/tex] to its powerset.

First, we need a proposed enumeration of all the subsets of a set ([tex]\mathbb{N}[/tex] for convenience), [tex]S_m[/tex]. Then define [tex]f: \mathbb{N} \times \mathbb{N} \to \{0,1\}[/tex] as:
[tex]
f(n,m) =
\begin{cases}
1 & \text{if } n \in S_m \\
0 & \text{if } n \notin S_m \\
\end{cases}
[/tex]
So [tex]f(-,m)[/tex] is the characteristic function for each [tex]S_m[/tex]. Let [tex]\alpha: \{0,1\} \to \{0,1\}[/tex] be the negation function [tex]\alpha(0) = 1, \alpha(1) = 0[/tex]. Finally, we need a map [tex]\Delta: \mathbb{N} \to \mathbb{N} \times \mathbb{N}[/tex], the diagonal map, that sends every [tex]n \in \mathbb{N}[/tex] to [tex](n,n) \in \mathbb{N} \times \mathbb{N}[/tex] -- it 'copies' its input. Using those, we can construct a map [tex]g: \mathbb{N} \to \{0,1\}[/tex] as follows:
[tex]g(m) = \alpha(f(\Delta(m)))[/tex]
This is the characteristic function of a set [tex]G = \{m \in \mathbb{N}| m \notin S_m\}[/tex]. The crux now is that this set can't be part of the [tex]S_m[/tex]: for if that were the case, then [tex]g(-) = f(-,m_0)[/tex] for some [tex]m_0[/tex], which we could evaluate at [tex]m_0[/tex]: [tex]g(m_0) = f(m_0,m_0)[/tex], which by definition of [tex]g[/tex] implies [tex]g(m_0) = \alpha(f(m_0,m_0)) = f(m_0,m_0)[/tex], which is clearly false ([tex]\alpha[/tex] being the negation operator). So we have a set [tex]G[/tex] that is a subset of [tex]\mathbb{N}[/tex], yet which is clearly not part of our proposed, arbitrary enumeration of subsets of [tex]\mathbb{N}[/tex].

If someone wants to have a look at a better presentation of the argument, http://de.arxiv.org/abs/math/0305282" [Broken] 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:

Answers and Replies

  • #2
236
0
I think (I only skimmed the argument) that the product can be taken on the underlying set, not necessarily the full object (i.e. after applying the forgetful functor) and therefore holds at least in concrete categories.
 
  • #3
221
7
Hmm, not sure if I understand you correctly -- it seems to me just talking about the Cartesian product of the underlying sets would miss some objects, those that don't lie in the image of the Segre embedding. The thing is, I think that states in the tensor product of Hilbert spaces don't map one to one to states in the Cartesian product of the 'sets of states' associated with each Hilbert space, only the separable ones do (is that correct?). However, for separable states, I can see the argument working, but I don't think that's enough...
 

Related Threads for: (Non-)Cartesian Categories and Diagonal Arguments

Replies
2
Views
2K
  • Last Post
Replies
1
Views
1K
Replies
3
Views
2K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
1
Views
1K
Replies
4
Views
4K
  • Last Post
Replies
4
Views
2K
Replies
11
Views
2K
Top