Find a model and a non-model of a theory $T=\{\mathtt{(∀x)¬E(x, x),(∀x)(∀y)(E(x, y)→E(y, x)),(∀x)(∃y)ϕ(x, y)}\}$ over language $L$ where $L=(E)$

Question

Find a model and a non-model of a theory $$\mathtt{T} = \{\mathtt{(∀x)¬E(x, x), (∀x)(∀y)(E(x, y) → E(y, x)), (∀x)(∃y)ϕ(x, y)}\}$$ over the language $\mathtt{L}$ where $\mathtt{L}=\mathtt{(E)}$.
$(\mathtt{E(x, y)}$ means in a graph that “the vertices $\mathtt{x}$ and $\mathtt{y}$ are adjacent” or “the vertices $\mathtt{x}$ and $\mathtt{y}$ are neighbors”$)$

By a non-model of $\mathtt{T}$, we mean a structure of the same language that is not a model of $\mathtt{T}$.

Can anyone help me understanding the question, and hint a approach to solve it?

Answer 1

A model of $T$ is a set $X$ together with some specified set $E^X \subseteq X\times X$ such that all of the statements written in $T$ are true under that interpretation.

The first statement in $T$ is $(\forall x)\neg E(x, x)$. Thus to have a model of $T$ you will need, in particular, it to be true that for every $x \in X$ the pair $(x, x)$ is not in $E^X$ (i.e., the relation $E^X$ must be antireflexive). On it's own that's not enough: You need to find a set $X$ and a relation $E^X$ where all three of your statements in $T$ are true (I assume that in the third statement the $\varphi$ should be an $E$, otherwise I don't know what it means).

To find a non-model of $T$ you need a set $Y$ and a set $E^Y \subseteq Y \times Y$ such that at least one statement in $T$ is not true about $(Y, E^Y)$.

Answer 2

I take it that $T=\{\mathtt{(∀x)¬E(x, x),(∀x)(∀y)(E(x, y)→E(y, x)),(∀x)(∃y)E(x, y)}\}$.

All you have to do is to exhibit a graph, $(V,E)$ say, that satisfies:

1. $(∀x)¬E(x, x)$ i.e. there is no edge from a vertex to itself.
2. $(∀x)(∀y)(E(x, y)→E(y, x))$ i.e. the relation $E$ is symmetrical.
3. $(∀x)(∃y)E(x, y)$ i.e. any vertex is connected to some vertex by an edge.

I leave it to you to show that the graph $(V,E)$ where $V = \{v_1, \ v_2\}$ and $E=\{(v_1, v_2), \ (v_2, v_1)\}$ is a model of $T$.