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

About 7 years old · traced to

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.

References

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.