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

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?

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

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