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?

  • $\begingroup$ what is $\varphi$? it is easy to find a model for the first two axioms : any antireflexive symetrical graph will do. $\endgroup$ May 12 at 17:10
  • $\begingroup$ @OlivierRoche I think its also E and can you please explain because I believe our course didn't cover this topic in our university. $\endgroup$
    – Nomi
    May 13 at 15:17

2 Answers 2


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


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


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.