9
$\begingroup$

What is known about the decidability of (first-order formulas in) the structure $(\mathcal{L}(H),\leq)$, where $\mathcal{L}(H)$ is the collection of all closed linear subspaces of a (separable) Hilbert space $H$, and $X\leq Y$ means $X\subseteq Y$? (Clearly meets and joins always exist and are first-order definable, so you can throw those in too.)

I can find some reference to the fact that this problem is open for infinite dimensional $H$, but known to be answered in the affirmative for finite dimensional $H$ (see: http://arxiv.org/pdf/math/0412144.pdf). I'm unfamiliar with the quantum logic literature, so references dealing with this question would be appreciated!

Improve this question
$\endgroup$
2
  • $\begingroup$ Isn't the logic just the equational theory of the lattice? (It would so appear from the linked paper. They do appeal to its first order theory for the decidability proof, but that's generally an overkill by a couple of orders of magnitude, so to speak.) $\endgroup$
    – anemone
    Commented Mar 18, 2015 at 18:19
  • $\begingroup$ I think, as in that paper, "quantum logic" is usually used to refer to the equational/quantifier-free theory. It just happens that I am interested in the question about the first-order theory (from which the corresponding fact about the equational theory would follow, of course). A negative result about the first-order theory would be interesting to me, for independent reasons (undecidability of lattices makes me think of the Turing degrees). $\endgroup$
    – Iian Smythe
    Commented Mar 18, 2015 at 18:52

1 Answer 1

Reset to default
7
$\begingroup$

A year after you posted the question, Fritz showed the common theory of all such lattices is undecidable: https://arxiv.org/abs/1607.05870

In reponse to @MattF's query I'll post an example of how infinite dimension differs from finite. Namely, the lattice of closed subspaces is modular only in the finite-dimensional case. This is due to Birkhoff and von Neumann 1936 although they gave fewer details.

Let $e_1,e_2,\dots$ be a countable orthonormal basis for a separable subspace of your Hilbert space. Let $A$, $B$ be respectively the closed subspace spanned by the vectors $$a_n=e_{2n}+10^{-n}e_1+10^{-2n}e_{2n+1},\qquad b_n=e_{2n},$$ and let $C$ be spanned by $A\cup\{e_1\}$. Then $B$ is incomparable with both $A$ and $C$ (under inclusion), and $A$ is a proper subspace of $C$.

Let's prove that $A$ is a proper subspace of $C$. If not, $e_1$ should be expressible as a combination of vectors from $A$, i.e., $$e_1=\sum k_na_n=\sum k_n e_{2n}+\sum k_n10^{-n}e_1+\sum k_n10^{-2n}e_{2n+1}=0$$ since first and third terms must be 0, so that all the coefficients $k_n=0$. This gives the contradiction $e_1=0$.

The modular law requires that $$A\subset C\implies A\vee (B\cap C)=(A\vee B)\cap C$$ but in this case we have $$A=A\vee (B\cap C)\quad\text{and}\quad (A\vee B)\cap C=C,$$ so we have a counterexample. On the other hand, in finite-dimensional Hilbert spaces the modular law does hold.

Improve this answer
$\endgroup$
1
  • $\begingroup$ The obvious algorithm would be taking sentences $E_1 \ldots E_k$ about subspaces $P_1 \ldots P_n$, and seeing whether they have a non-trivial solution in a Hilbert space of dimension at most $2^n$. This paper says that algorithm must fail -- do you understand the paper well enough to provide an example of such sentences whose only non-trivial solutions are in dimension higher than $2^n$? $\endgroup$
    – user44143
    Commented Mar 26, 2018 at 2:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .