Interpretable structure

From Wikipedia, the free encyclopedia

It has been suggested that this article or section be merged with Interpretation (model theory). (Discuss)

In model theory, a structure N is called interpretable in M if all the components (universe, functions, relations etc.) of N can be defined in terms of the components of M. In particular, the universe of N is represented as a definable subset of some power of the universe of M; sometimes a definable quotient of the universe of M is employed instead of the universe itself. Interpretability entails that every formula in the language of N can be translated into corresponding formula in the language of M that essentially expresses the same content.

One of the goals of set theory in early 20th century was to build a set-theoretic universe in which all mathematical structures could be interpreted^{[citation needed]}.

[edit] Definition

Suppose that $L 1, L 2$ are two first order languages. Let $M$ be an $L 1$ -structure and $N$ be an $L 2$ -structure.

Let $n$ be a natural number. Suppose we have chosen the following

A $L 1$ -formula $ψ D$ which has $n$ free variables.
A $L 1$ -formula $ψ E$ which has $2 n$ free variables.
For each constant symbol $c$ of $L 2$ a $L 1$ -formula $ψ c$ with $n$ free variables.
For each $m$ -ary function symbol $f$ of $L 2$ a $L 1$ -formula $ψ f$ with $(m + 1) n$ free variables.
For each $m$ -ary relation symbol symbol $R$ of $L 2$ a $L 1$ -formula $ψ R$ with $m n$ free variables.

Suppose that $ψ E$ defines an equivalence relation $E$ on the set defined by $ψ D$ . Suppose that $σ$ is a bijection from the equivalence classes of $E$ to the domain of $N$ .

The intuition behind the following definition is that the interpretation of each symbol in $L 2$ is controlled by the sets defined by the corresponding formula we chose above.

Then we say that $(\psi_D,\psi_E,\{\psi_c:c \in L_2\},\{\psi_f:f \in L_2\},\{\psi_R:R \in L_2\},\sigma)$ is an interpretation of $N$ in $M$ iff the following all hold:

For each constant symbol $c \in L_2$ and every $a \in M^n$ , we have that $\sigma(a/E)=c^N \Leftrightarrow M \models \psi_c(a)$ .
For each $m$ -ary function symbol $f \in L_2$ and every $a_1,\ldots,a_m,b \in M^{n}$ , we have that $f^N(\sigma(a_1/E),\ldots,\sigma(a_m/E))=\sigma(b/E) \Leftrightarrow M \models \psi_f(a_1,\ldots,a_m,b)$ .
For each $m$ -ary relation symbol $R \in L_2$ and every $a_1,\ldots,a_m \in M^{n}$ , we have that $R^N(\sigma(a_1/E),\ldots,\sigma(a_m/E)) \Leftrightarrow M \models \psi_R(a_1,\ldots,a_m)$ .

[edit] Example: Valued Fields

Let $L R I N G$ be a language with two binary function symbols $+,\times$ , a unary function symbol $-$ , two constant symbols $0,1$ . We call this the language of rings. Let $L$ be an extension of $L R I N G$ by the unary predicate symbol $V$ .

Suppose that $F$ is a field, and $D$ is a Valuation ring of $F$ .

Suppose we make $F$ into an $L$ -structure by interpreting $+,\times,-,0,1$ via the field on $F$ , and so that for each $a \in F$ , $F \models V(a)$ iff $a \in D$ .

Now, the maximal ideal $M$ of $D$ is definable (without parameters) via the formula $V(x) \land \forall y (yx=1 \rightarrow \lnot v(y)$ .

In this way one can show that the residue field $D / M$ as a structure in the language of rings is interpretable in $F$ .

Similarly, the units $F *$ of $F$ and the units $D *$ of $D$ are definable, and one can interpret the quotient as an ordered group.

Note that in general there are many more structures interpretable in a valued field.

Logic Portal

v • d • e

Logic

History and core topics

History	General · Chinese · Greek · Indian · Islamic

Core topics	Reason · Philosophical logic · Philosophy of logic · Mathematical logic · Metalogic · Logic in computer science

Key concepts and logics

Reasoning	Deduction · Induction · Abduction

Informal	Proposition · Inference · Argument · Validity · Cogency · Term logic · Critical thinking · Fallacies · Syllogism · Argumentation theory

Philosophy of logic	Platonic realism · Logical atomism · Logicism · Formalism · Nominalism · Fictionalism · Realism · Intuitionism · Constructivism · Finitism

Mathematical	Formal language · Formal grammar · Formal system · Deductive system · Formal proof · Formal interpretation · Formal semantics · Formula · Wff · Set · Element · Class · Axiom · Rule of inference · Relation · Theorem · Logical consequence · Consistency · Soundness · Completeness · Decidability · Satisfiability · Independence · Set theory · Axiomatic system · Proof theory · Model theory · Recursion theory · Type theory · Syntax

Propositional	Boolean functions · Monadic predicate calculus · Propositional calculus · Logical connectives · Truth tables

Predicate	First-order · Quantifiers · Second-order

Modal	Deontic · Epistemic · Temporal · Doxastic

Other non classical	Computability · Fuzzy · Linear · Relevance · Non-monotonic

Controversies

Paraconsistent logic · Dialetheism · Intuitionistic logic · Paradoxes · Antinomies · Is logic empirical?

Key figures

Alfarabi · Algazel · Alkindus · Al-Razi · Aristotle · Averroes · Avicenna · Boole · Cantor · Carnap · Church · Dharmakirti · Dignāga · Frege · Gentzen · Kanada · Gödel · Gotama · Hilbert · Ibn al-Nafis · Ibn Hazm · Ibn Taymiyyah · Kripke · Mozi · Nagarjuna · Pāṇini · Peano · Peirce · Putnam · Quine · Russell · Skolem · Suhrawardi · Tarski · Turing · Whitehead · Zadeh

Lists

Topics	General · Basic · Mathematical logic · Boolean algebra · Set theory

Other	Logicians · Rules of inference · Paradoxes · Fallacies · Logic symbols