Non-Trivial Language Property

languages

Definition

Non-Trivial Language Property

A language property that is not trivial.

Non-Trivial Language Property

Fix an alphabet $\Sigma$ and let $\mathcal{U}\subseteq \mathcal{P}({\Sigma }^{\ast })$ be a chosen universe of languages (typically $\mathcal{U}={\mathrm{RE}}_{\Sigma }$, the recursively enumerable languages for Rice’s theorem).

A language property $P$ is non-trivial iff

$$\exists L_{+},L_{-}\in \mathcal{U}:P(L_{+})=\mathrm{true}\wedge P(L_{-})=\mathrm{false}$$