The undecidability conjecture for the Sigma-1 theory of Young's lattice with all constants

Let P\mathcal P be the set of partitions, and consider Young's lattice with a constant symbol for every partition, P,,π:πP\left\langle \mathcal P,\leq,\pi:\pi\in\mathcal P\right\rangle. The all-constants Sigma-1 undecidability conjecture. The Σ1\Sigma_1-theory of P,,π:πP\left\langle \mathcal P,\leq,\pi:\pi\in\mathcal P\right\rangle is undecidable. This would establish undecidability at the earliest quantifier-complexity level for the language with all partition constants; the source notes that the analogous result is known for subword order, while the corresponding interpretation approach may not work directly for Young's lattice.

Sources & referencesView supporting material

Primary source

Alexander Wires, “Complexity in Young's Lattice”, arXiv:1907.13360 (2019).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.