Search Results

This question is very close to this old MSE question of mine, which is still unanswered. Is there an (ideally reasonably-natural!) expansion of the structure $(\mathbb{N};+)$ in a finite language whos …

This is a followup to this question. Consider $\mathbb{C}$ as a structure - in the sense of first-order logic - with the graphs of addition and multiplication. Let $\mathcal{X}$ be the substructure wi …

I don't know a reference, but here's a (slightly overkill) proof: It's known that $(\mathbb{Z};+,\times)$ interprets an algebraically closed field $K$ of infinite transcendence degree and characterist …

Originally asked at MSE: Let $\Sigma=\{+,<,0,1\}$ be the usual language of Presburger arithmetic. Given a "reasonable" logic $\mathcal{L}$, let $\mathbb{Pres}(\mathcal{L})$ be the $\mathcal{L}$-theory …

I am looking for examples of proofs of Godel's (First) Incompleteness Theorem which are essentially different from (Rosser's improvement of) Godel's original proof. This is partly inspired by question …

Below, all structures are finite, in a finite language, with underlying set an initial segment of the natural numbers. This has been edited to fix errors pointed out by Emil Jerabek in his answer belo …

For a computable$^*$ ordinal $\alpha$ (viewed as an $\{<\}$-structure), say that a first-order sentence $\sigma$ in a relational language $\Sigma\supseteq \{<\}$ decidably clarifies $\alpha$ iff $\alp …

The following question arose while trying to read Shelah's papers Models with second-order properties I-V. For simplicity, I'm assuming a much stronger theory here than Shelah: throughout, we work in …

Throughout, "computable structure" means "first-order structure in a computable language with domain $\omega$ whose atomic diagram is computable." Say that a computable structure $A$ is compact for co …

Given a clone $\mathcal{C}$ over $\{\top,\perp\}$, let $\mathsf{FOL}^\mathcal{C}$ be the version of first-order logic with connectives from $\mathcal{C}$ in place of the usual Booleans. Given a clone …

By "logic" I mean regular logic in the sense of abstract model theory (see e.g. the last section of Ebbinghaus/Flum/Thomas' book). My question is simple: Is there a logic $\mathcal{L}$ which is fully …

(See e.g. here for background on the Eudoxus reals, which motivates this question.) Let $\mathcal{Z}=(\mathbb{Z};+,<)$. Say that a Eudoxus function is an $f:\mathbb{Z}\rightarrow\mathbb{Z}$ such that …

The answer is yes. I believe the following is best attributed to Feferman 1960; more generally, look up "arithmetized completeness theorem" (which is annoyingly different from the arithmetic completen …

Throughout, all structures are finite. Say that a class of finite structures $\mathbb{K}$ is $\mathsf{FOL}_\varepsilon^\text{inv}$-elementary iff it is the class of finite models of a sentence in the …

Suppose $\mathscr{V}$ is a pseudovariety in a countable language $\Sigma$. Say that a minimal description of $\mathscr{V}$ (in the sense of Eilenberg/Schutzenberger rather than Reiterman) is a pair $( …