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

  • $\begingroup$ Without knowing what T represents, this is impossible to answer. $\endgroup$
    – Lee Mosher
    May 15 at 19:08
  • $\begingroup$ 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. $\endgroup$ May 15 at 19:19
  • $\begingroup$ i have edited it. @AtticusStonestrom $\endgroup$
    – Nomi
    May 15 at 19:26
  • $\begingroup$ @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 $\endgroup$ May 15 at 19:37
  • 1
    $\begingroup$ 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 :) $\endgroup$ May 15 at 19:44

1 Answer 1


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

  • $\begingroup$ +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. $\endgroup$ May 15 at 19:39
  • 1
    $\begingroup$ Good point. If $T$ is inconsistent, then any statement is both proved and refuted by $T$. $\endgroup$
    – GEdgar
    May 15 at 19:42
  • $\begingroup$ BUT NOTE: The full statement shows that $\phi$ is not the same as $E$. math.stackexchange.com/questions/4451207 $\endgroup$
    – GEdgar
    May 15 at 21:28

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.