Show that $A,B$ definable $\implies A\cup B$ is definable

193 Views Asked by At

So I'm working with this definition from Shawn Hedmans "A First Course in Logic"

Definition 2.24 Let $\phi(x_1,\ldots,x_n)$ be a $\cal{V}$-formula. Let $M$ be a $\cal{V}$-structure having underlying set $U_M$. The set of all $n$-tuples $(b_1,\ldots,b_n) \in (U_M)^n$ for which $M\models \phi(b_1,\ldots,b_n)$ is denoted by $\phi(M)$. The set $\phi(M)$ is called a $\cal{V}$-definable subset of $M$.

Here is the problem:

Let $A$ and $B$ be definable subsets of structure $M$ . Suppose that $A$ and $B$ are both sets of $n$-tuples of elements from the underlying set of $M$ . Show that $A\cup B$ is definable.

I'm not really sure how to show this. Assume that $A,B$ are both are definable as above then. $A = (a_1, \ldots, a_n)$ and $B = (b_1, \ldots, b_n)$. Here is my problem, I find the definition somewhat weirdly formulated. Given that I have some some "abstract" definable set and the above definition am I allowed to draw the conclusion that there then exists a formula $\phi$ such that $M\models \phi(A)$?

I'm thinking along the lines of $M\models \phi \text{ and } M \models \psi$ then $M\vdash \phi$ and $M\vdash \psi \implies M \vdash \phi \wedge \psi \implies M \models \phi \wedge \psi $ Then if $A$ makes $\phi$ true and $B$ makes $\psi$ true then (?) $A\cup B$ is the subset of $(U_M)^n$ which makes $M \models \phi \wedge \psi $ with $\phi(A)\wedge\psi(B)$. Is my reasoning nonsense?

1

There are 1 best solutions below

0
On BEST ANSWER

As you almost exactly say, the hypothesis that subset $A$ of domain of $M$ is definable means, by definition, that there's a formula $\phi$ such that $$A=\{a:M\models \phi(a)\}.$$

So suppose in particular that $A$ and $B$ are definable. Then there are formulas $\phi$ and $\psi$, say in the one free variable $x$, such that

$$A=\{a:M\models \phi(a)\}$$ $$B=\{a:M\models \psi(a)\}.$$

Now, let $\theta=\phi\lor \psi$. Then

$$ M\models \theta(a)\text{ iff } M\models \phi(a)\text{ or }M\models \psi(a)$$ $$\text{ iff }a\in A\text{ or }a\in B$$ $$\text{ iff }a\in A\cup B.$$

Hence

$$\{a:M\models \theta(a)\}=A\cup B,$$

which is to say that $\theta$ defines $A\cup B$.