give a first-order formula with no free variables that is true iff a relation is a partial order

Question

Full question:

"Give a first-order formula with no free variables that takes a binary relation, E, as an interpretation and is true if, and only if, the relation is a partial order"

My answer is:

$\forall x \left( \neg \exists y \left( \left( \left(x,y\right) \in E \land \left(y,x\right) \in E \right) \Rightarrow x = y \right) \land \left(x,x\right) \in E \land \forall y\forall z \left(\left(x,y\right) \in E \land \left(y,z\right) \in E \Rightarrow \left(x,z\right) \in E \right) \right)$

Am I going about this the right way?

Thanks for any help.

Answer 1

A Partial Order Relation is

• Reflexive $\forall x~(x,x)\in E$
• Antisymmetrix $\forall x~\forall y~[((x,y)\in E\wedge (y,x)\in E)~\to~x=y]\\\forall x~\neg\exists y~[(x,y)\in E\wedge (y,x)\in E\wedge x\neq y]$
  • NB: You have conflated these statements. Use one or the other.
• Transitive $\forall x~\forall y~\forall z~[((x,y)\in E\wedge (y,z)\in E)~\to~(x,z)\in E]$

Putting it together $${\forall x~\forall y~\forall z}~\Big[{(x,x){\in}E}\wedge{\big[((x,y){\in}E\wedge (y,x){\in}E)\to{x=y}\big]}\wedge{\big[((x,y){\in}E\wedge (y,z){\in}E)\to(x,z){\in}E\big]}\Big]$$

Answer 2

try with the following (only missing the $x \neq y$ portion in yours)

$$\forall x ((x,x)\in E \land(\lnot \exists y (y\neq x \land (x,y)\in E \land (y,x)\in E))\land \forall y \forall z ((x,y)\in E \land (y,z)\in E \Rightarrow (x,z)\in E)$$

Answer 3

Should you be using $E$ as a 2-place predicate maybe?

In that case:

$$\forall x \ E(x,x) \land \forall x \forall y ((E(x,y) \land E(y,x)) \rightarrow x = y) \land \forall x \forall y \forall z ((E(x,y) \land E(y,z)) \rightarrow E(x,z))$$