Prove that $∀x∀y(P(x, y) → ¬P(y, x)),∀x∃yP(x, y)$ can be deduced to $¬∃v∀zP(z, v)$

486 Views Asked by At

Using natural deduction rules prove the statement:

$∀x∀y(P(x, y) → ¬P(y, x)),∀x∃yP(x, y)$ can be deduced to $¬∃v∀zP(z, v)$

I don't want to be given an answer, but a hint on how to start because I am stuck for a long time on this problem not knowing how to start efficiently.

1

There are 1 best solutions below

2
On

Obviously here you can use proof by negation together with formal inference rules regarding quantifiers allowed in your system, and then a useful hint would be the predicate $P$ here can be interpreted as a strict partial order and thus $∃v∀zP(z,v)$ must be false when $z=v$, which is certainly an unavoidable special case for $∃v∀zP(z,v)$, while the given premise $∀x∃yP(x,y)$ can avoid such special case...