Let $K_i$ be a class of structures, show that Th$(\bigcup_{i\in I} K_i)=\bigcap_{i\in I}$Th$(K_i)$

80 Views Asked by At

I am following Hodges's Shorter Model Theory and tried my hand at the following exercise (ex 2.2 Q2), could anyone check my working please?

Let $L$ be a first order language and for each $i\in I$ let $K_i$ be a class of structures, show that Th$(\bigcup_{i\in I} K_i)=\bigcap_{i\in I}$Th$(K_i)$.

So we need to prove $\forall x (x \in Th(\bigcup_{i\in I} K_i) \iff x\in \bigcap_{i\in I}$Th$(K_i))$, ie. $\forall x(x\in \{\varphi|\forall A\in \bigcup_{i\in I} K_i.A\vDash \varphi\} \iff \forall i\in I(x\in \{\varphi|\forall A\in K_i.A\vDash \varphi\})$

$\to$: On the RHS (what we need to prove), since $x$ is in a set quantified over all $\varphi$, I took $x$ as $\varphi$. Therefore really what we need to prove is $\forall i\in I \forall A(A \in K_i \to A\vDash \varphi)$. So let $i$ and $A$ be arbitrary index and structure respectively, and assume $A \in K_i$.

On the LHS, again by the same reasonsing as above, I took $x$ as $\varphi$. So we now have $\forall A(A\in \bigcup_{i\in I} K_i\to A\vDash \varphi)$. Let $A$ be an arbitrary structure, and we get $\exists i\in I (A\in K_i) \to A\vDash \varphi$.

But we assumed an arbitrary $A \in K_i$, so using this as a witness (ie doing an existential generalisation) we get $\exists i\in I (A\in K_i)$, so from that we get $A\vDash \varphi$.

$\leftarrow$: Using the same analysis of definitions as above, we see that we can assume $\forall i \in I \forall A (A\in K_i \to A\vDash \varphi)$ on the RHS, and on the LHS (or what we need) we have $\forall A(\exists i\in I (A\in K_i)\to A\vDash \varphi)$, so let $A$ be an arbitrary structure, and assume $\exists i\in I (A\in K_i)$.

This means we have an instance $j$ of $A\in K_j$ (ie. existential instantiated the assumption). But we can also universal instantiate our assumption from RHS and get $A\in K_j \to A\vDash \varphi$. So by Modus Ponens we get $A\vDash \varphi$.


Def of Th(K) according to Hodges:

Let $L$ be a language and $K$ a class of $L$-structures. We define the $L$-theory of $K$, Th(K), to be the set (or class) of all sentences $\psi$ of $L$ such that $A\vDash\psi$ for every structure $A$ in $K$.

1

There are 1 best solutions below

0
On BEST ANSWER

You are severely overcomplicating things.

$ \varphi\in Th(\bigcup_iK_i)$ if and only if $\varphi$ is satisfied by every structure in $\bigcup_iK_i,$ if and only if for all $i$, $\varphi$ is satisfied by every structure in $K_i$.

$\varphi\in\bigcap_iTh(K_i)$ if and only if for all $i,$ $\varphi\in Th(K_i),$ if and only if for all $i,$ $\varphi$ is satisfied by every structure in $K_i.$