Skip to main content
added 36 characters in body; deleted 1 character in body
Source Link
user44143
user44143

Another example is the theory $\text{Th}(\mathcal{P}(\mathbb{R}),\subset,<)$ of subsets of the reals, where $S$ is less than $S'$ iff every element of $S$ is less than every element of $S'$.

The theory is consistent and complete by definition. Shelah proved that it is not decidable, which means it also has no decidable extension, and Gurevich and Shelah jointly proved that it does not interpret arithmetic.

To be more precise, Gurevich and Shelah work with a variant of the theory where $<$ applies only to singletons, and they prove that it does not interpret even the weak set theory of null set, singleton and union: \begin{align} \forall x \exists y \forall z &[z \in y\leftrightarrow z=x]\\ \forall w \forall x \exists y \forall z &[z \in y\leftrightarrow z \in w \text{ or } z \in x]\\ \exists y \forall z &[z \notin y]\\ \end{align}\begin{align} \exists y \forall z &[z \notin y]\\ \forall x \exists y \forall z &[z \in y\leftrightarrow z=x]\\ \forall w \forall x \exists y \forall z &[z \in y\leftrightarrow z \in w \text{ or } z \in x]\\ \end{align} The two results on decidabilityundecidability and non-interpretability are both difficult, but these questions of mine have more details.

Another example is the theory $\text{Th}(\mathcal{P}(\mathbb{R}),\subset,<)$ of subsets of the reals, where $S$ is less than $S'$ iff every element of $S$ is less than every element of $S'$.

The theory is consistent and complete by definition. Shelah proved that it is not decidable, which means it also has no decidable extension, and Gurevich and Shelah jointly proved that it does not interpret arithmetic.

To be more precise, Gurevich and Shelah work with a variant of the theory where $<$ applies only to singletons, and they prove that it does not interpret even the weak set theory \begin{align} \forall x \exists y \forall z &[z \in y\leftrightarrow z=x]\\ \forall w \forall x \exists y \forall z &[z \in y\leftrightarrow z \in w \text{ or } z \in x]\\ \exists y \forall z &[z \notin y]\\ \end{align} The two results on decidability and non-interpretability are both difficult, but these questions of mine have more details.

Another example is the theory $\text{Th}(\mathcal{P}(\mathbb{R}),\subset,<)$ of subsets of the reals, where $S$ is less than $S'$ iff every element of $S$ is less than every element of $S'$.

The theory is consistent and complete by definition. Shelah proved that it is not decidable, which means it also has no decidable extension, and Gurevich and Shelah jointly proved that it does not interpret arithmetic.

To be more precise, Gurevich and Shelah work with a variant of the theory where $<$ applies only to singletons, and they prove that it does not interpret even the weak set theory of null set, singleton and union: \begin{align} \exists y \forall z &[z \notin y]\\ \forall x \exists y \forall z &[z \in y\leftrightarrow z=x]\\ \forall w \forall x \exists y \forall z &[z \in y\leftrightarrow z \in w \text{ or } z \in x]\\ \end{align} The two results on undecidability and non-interpretability are both difficult, but these questions of mine have more details.

Source Link
user44143
user44143

Another example is the theory $\text{Th}(\mathcal{P}(\mathbb{R}),\subset,<)$ of subsets of the reals, where $S$ is less than $S'$ iff every element of $S$ is less than every element of $S'$.

The theory is consistent and complete by definition. Shelah proved that it is not decidable, which means it also has no decidable extension, and Gurevich and Shelah jointly proved that it does not interpret arithmetic.

To be more precise, Gurevich and Shelah work with a variant of the theory where $<$ applies only to singletons, and they prove that it does not interpret even the weak set theory \begin{align} \forall x \exists y \forall z &[z \in y\leftrightarrow z=x]\\ \forall w \forall x \exists y \forall z &[z \in y\leftrightarrow z \in w \text{ or } z \in x]\\ \exists y \forall z &[z \notin y]\\ \end{align} The two results on decidability and non-interpretability are both difficult, but these questions of mine have more details.