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?

  • $\begingroup$ I'm not sure what's meant here by the notation $M\vdash \phi$. Usually $\vdash$ expresses provability, which is a relation between a collection of formulas and a formula. $\endgroup$ – mmw Sep 30 '15 at 19:30

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.$$


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

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.