A formal language problem

Question

Translated as best I could the problem is stated as follows:

Over the set $A=\{\alpha,\beta,\gamma,\delta,\epsilon,\eta\}$ a model $\mathbb{A}$ of language $\mathcal{L}=\{q\}$ ($ar(q)=2$) is defined with the following graph ($q^A$ is represented with the arrows)

Find the formula $F_a$ for each $a\in A$ such that $F_a(x)$ defines $a$.

---

I have only a rough understanding of formal languages, and would appreciate a detailed solution to this problem.

Answer 1

Following Rob Arthan's hint I got to this,

Alpha is the only element that is in relation with an element not in relation with any other element, with which there is an element in relation, that is not in relation with itself.

\begin{align} F_\alpha(x) =& \exists y\in A, \quad \nexists z\in A, \quad (y,z)\in q \quad \land \quad (x,y)\in q \quad \\&\land \exists m\in A, \quad (m,m)\notin q \quad \land (m,x)\in q \end{align}

Beta is simply the only element in relation with itself

$$ F_\beta(x) = (x,x) \in q $$

Gamma is the only element with which no other element is in relation

$$ F_\gamma(x) = \nexists y \in A, \quad (y,x) \in q $$

Delta is the only element not in relation with any other element, with which there is no element in relation that is also in relation to itself.

$$ F_\delta(x) = \nexists y\in A \quad (x,y) \in q \qquad \land \qquad \nexists z\in A, \quad (z,z)\in q \quad \land \quad (z,x) \in q $$

Epsilon is the only element not in relation with itself, that is in relation with some other element, and with which there is an element in relation, that is also in relation with itself

$$ F_\epsilon(x) = (x,x) \notin q \qquad \land \qquad \exists y\in A, \quad (x,y) \in q \qquad \land \qquad \exists z\in A, \quad (z,x) \in q, \quad (z,z) \in q $$

Eta is the only element not in relation with any other element, with which there is an element in relation, that is also in relation with itself

$$ F_\eta(x) = \nexists y\in A, \quad (x,y) \in q \qquad \land \qquad \exists z\in A, \quad (z,x)\in q \quad \land \quad (z,z) \in q $$

---

I believe this is correct, and I went over it a few times, though I felt a bit of an idiot doing this "by eye", so to speak. It simply took me too long, and I assume there is a way to quickly and systematically deduce this information from a table,

\begin{matrix} &\alpha & \beta & \gamma & \delta & \epsilon & \eta\\ \alpha & 0 & 0 & 0 & 1 & 0 & 0\\ \beta & 0 & 1 & 0 & 0 & 1 & 1 \\ \gamma & 0 & 0 & 0 & 0 & 0 & 1 \\ \delta & 0 & 0 & 0 & 0 & 0 & 0\\ \epsilon & 1 & 0 & 0 & 0 & 0 & 1 \\ \eta & 0 & 0 & 0 &0 & 0 & 0\\ \end{matrix}

like one would for a truth table of a boolean function?

---

Secondly, I'm still not sure from the text of the problem how I should have known to solve the problem thusly. Could someone elaborate or link to a helpful resource?

Answer 2

As this sounds like a textbook or homework exercise, a detailed solution would be out of place, but here is a hint:

Write $x \mathrel{q} y$ to mean $q$ relates $x$ to $y$ in the model $\Bbb{A}$ in your diagram (so, for example, $\varepsilon \mathrel{q} \alpha$ holds but $\alpha \mathrel{q} \varepsilon$ does not). Now use quantifiers to express a defining characteristic of each node in the diagram: e.g., $\gamma$ is the only node $x$ such that $y \mathrel{q} x$ never holds, $\beta$ is the only node $x$ such that $x \mathrel{q} x$, etc.