Undecidability in Weihrauch Degrees

摘要

We prove that the 1-quasiorder and the 2-quasiorder of finite fc-labeled forests and trees have hereditarily undecidable first-order theories for k > 3. Together with an earlier result of P. Hertling, this implies some undecidability results for Weihrauch degrees.