Logical Theory of the Monoid of Languages over a Non Tally Alphabet

Abstract

We consider the first-order theory of the monoid P(A*) of languages over a finite or infinite alphabet A (with at least two letters) endowed solely with concatenation lifted to sets: no set theoretical predicate or function, no constant. Coding a word u by the submonoid u* it generates, we prove that the operation (u*, v*) → (uv)* and the predicate {(u*,X) | ε ∈ X, u ∈ X} are definable in 〈P(A*); ·,=〉. This allows to interpret the second-order theory of 〈A*; ·,=〉 in the first-order theory of 〈P(A*); ·,=〉 and prove the undecidability of the Π₈ fragment of this last theory. These results involve technical difficulties witnessed by the logical complexity of the obtained definitions: the above mentioned predicates are respectively Δ₅ and Δ₇.