1

Let $L = \{ R,c \}$; where $R$ is a binary predicate symbol and $c$ is a constant symbol, and let $\mathcal M$ be an $L$-structure such that

$|\mathcal M| = \{ 1, 2, 3, 4 \}$;

$R^{\mathcal M} = \{ <1,2>, <2,3>, <3,4>, <4,1> \}$;

$c^{\mathcal M} = 2$.

Given that the sets {2}, {3}, {1,3}, and binary relations {<1,3>}, {<3,4>} are definable in $\mathcal M$, I've been asked to give the formulae that define them.

Could anyone give any explanation as to how I go about doing this? I can't find any useful examples.

Mauro ALLEGRANZA
  • 94,169
Emma L
  • 11

1 Answers1

1

Defining a subset, or a relation, $A$ over $M$ means to find a formula in the language $L$ which the right number of free variable (one for subset, two for a binary relation, and so on), such that: $A=\{x: M\models\varphi[x]\}$ (and similarly for the ordered pairs and whatnot).

I'll help with the simplest one, $$\{2\}=\{x: M\models x=c\}$$

Asaf Karagila
  • 393,674
  • Okay, I understand that I need to find such a formula, but what terms can I use to build up the formula? For {2} it is clear as you have just used the constant symbol, but for {3} would it suffice to say {3}={x:M⊨x=c+1}? This still has one free variable. .. – Emma L Mar 11 '14 at 22:08
  • But you have to write a formula in the language $L$. Is $+$ in your language? – Asaf Karagila Mar 11 '14 at 22:09
  • No, just R and c are in my language. Can R be interpreted as any binary relation such as =,< or > then? But {3}={x:M⊨x>c} wouldn't be specific enough. – Emma L Mar 11 '14 at 22:22
  • No, the interpretation is given. You can't reinterpret it. You need to find a way to pick up $3$ using $R$ and $c$. Can you come up with an idea? – Asaf Karagila Mar 11 '14 at 22:23
  • I'm sorry, I have no idea. Where does it tell me the interpretation of R? Is it just =? Or am I meant to be using the fact that 3 comes after 2 in our definition of |M|? (Apologies for being so slow - I haven't got the grasp of any part of the Logic course yet!) – Emma L Mar 11 '14 at 22:38
  • You have a dictionary, and an interpretation. Work with that. Note, for example, that $3$ is the only element of $|M|$ such that $R^M(2,3)$ is true, but $2=c^M$. So what can we say about $3$ using the language of $R$ and $c$ and is true in $M$ (and it is only true for $3$)? – Asaf Karagila Mar 11 '14 at 22:51
  • 1
    @EmmaL - please, reflect on Asaf's hint; what is the "reading" of ${ 2 } = { x : \mathcal M \vDash x = c }$ ? It is : "the set wuth $2$ as only element is the set of all objcets $x$ in the domain $|\mathcal M|$ of the $L$-structure $\mathcal M$ that satisfy the formula (with one free variable $x$) $\varphi(x)$, where $\varphi(x)$ is $x = c$. It's all right up to now ? Now, you must build a formula $\psi(x)$ such that : ${ 3 } = { x : \mathcal M \vDash \psi(x) }$; the only difficulty (but this is the goal of the exercise) is to find the right $\psi(x)$. 1/2 – Mauro ALLEGRANZA Mar 12 '14 at 07:57
  • 1
    @EmmaL - again, we have Asaf's hint: use the fact that $R^{\mathcal M} (2,3)$ is true, and that $2 = c^{\mathcal M}$. We may try as $\psi(x)$ with : $\exists y (R(y,x) \land y = c)$. How we read it ? It is of the "form" $\psi(x)$ ? Yes : $y$ is bound but $x$ is free. Which elements of the domain $|\mathcal M|$ satisfy it ? i.e. for which element $a \in |\mathcal M|$ $R^{\mathcal M} (c^{\mathcal M}, a)$ is true ? for $a = 3$ ... – Mauro ALLEGRANZA Mar 12 '14 at 08:04
  • I think I understand. So we would end up with {4}= {x:M⊨∃y(R(y,z)∧y=c)∧R(z,x)} ? – Emma L Mar 12 '14 at 11:24