# Is the formula (∃x)(∀y)ϕ(x, y) provable or refutable from T?

Is the formula (∃x)(∀y)ϕ(x, y) provable or refutable from T?

T = {(∀x)¬E(x, x), (∀x)(∀y)(E(x, y) → E(y, x)), (∀x)(∃y)ϕ(x, y)}


E(x,y) means that x and y are neighbors. I think is provable because (∀x)(∀y)(E(x, y) → E(y, x) in this statement they are implying.

I believe ϕ(x, y) is same as E(x,y)

This is from first part of question

(That is, E(x, y) means in a graph that “the vertices x and y are adjacent”.) Write a formula ϕ(x, y) in the first-order logic over the language (The phrases “x and y are adjacent” and “x and y are neighbors” have the same meaning.)

• Without knowing what T represents, this is impossible to answer. May 15 at 19:08
• hi Nomi. just to second @LeeMosher's comment, I think they meant to write that we need to know what $\phi$ represents to answer the question. May 15 at 19:19
• i have edited it. @AtticusStonestrom
– Nomi
May 15 at 19:26
• @Nomi as a side note – it is extremely peculiar that the problem would use $E(x,y)$ and $\phi(x,y)$ to mean the same thing! are you sure you're understanding correctly? to remove confusion I would recommend further replacing every instance of $\phi(x,y)$ with $E(x,y)$ in the question, as the instances of $\phi$ are completely redundant May 15 at 19:37
• since GEdgar has already answered your question as you wrote it, I would recommend asking a different question that addresses the problem as your textbook wrote it :) May 15 at 19:44

Suppose $$\phi$$ is the same as $$E$$.
Note $$(\exists x)(\forall y) E(x,y)$$ implies $$(\exists x)E(x,x)$$; but this contradicts $$(\forall x)\neg E(x,x)$$. So $$T$$ refutes $$(\exists x)(\forall y) E(x,y)$$.
• +1, this answer is of course much better than mine! but there's one detail which (imo) should be pointed out to the OP: for this proof to work you need to first check that $T$ is consistent. May 15 at 19:39
• Good point. If $T$ is inconsistent, then any statement is both proved and refuted by $T$. May 15 at 19:42
• BUT NOTE: The full statement shows that $\phi$ is not the same as $E$. math.stackexchange.com/questions/4451207 May 15 at 21:28