4

Let $P$ be a $2$-ary predicate. Is it true that

$$\forall x, y P(x, y)$$

is equivalent to

$$\forall x, y P(x, y) \wedge P(y, x)$$

This seems obviously true, but how do you formally prove it?

user83740
  • 41
  • I believe you would have to demonstrate that $P(x,y)\leftrightarrow{P(y,x)}$. Someone correct me if I'm wrong. – rurouniwallace Jun 24 '13 at 20:36
  • @ZettaSuro What you are saying (i.e. $P$ is symmetric) would be necessary if we wanted to show, for any $a,b$ that $P(a,b)$ is equivalent to $P(a,b)\wedge P(b,a)$. But the quantifiers allow the argument to through. This got me too for a second: if P(x,y) is "$x<y$, then we can't say for any $a,b$ that $a<b$ is equivalent to $a<b\wedge b<a$. But with the quantifiers, the two sentences are false. – Francis Adams Jun 24 '13 at 22:52

3 Answers3

1

Hint: Suppose it is true that:

$$ \forall x,y,~~P(x,y) \iff \boxed{\forall a,b,~~P(a,b)} $$

Then by letting $a:=x$ and $b:=y$, we know that: $$ \boxed{\forall x,y,~~P(x,y)} $$ Likewise, by letting $a:=y$ and $b:=x$, we know that: $$ \forall y,x,~~P(y,x) \iff \boxed{\forall x,y,~~P(y,x)} $$ Hence, it follows that:

$$ \forall x,y,~~[P(x,y) \land P(y,x)] $$

Adriano
  • 41,576
  • This only seems to take the argument one way ... – Mark Bennet Jun 24 '13 at 21:13
  • @MarkBennet Conversely, suppose that $\forall x,y,[P(x,y) \land P(y,x)]$. Then by conjunction elimination, we have $∀x,y,P(x,y)$, as desired. This was only a hint, so I figured it would be okay to omit this part. – Adriano Jun 24 '13 at 21:48
0

From $$\tag0\forall x\forall y P(x,y)$$ by specialization (with $u$ being a "new/unused" variable) $$\forall y P(u,y)$$ and by specialization again $$P(u,x)$$ hence by generalization $$\forall u P(u,x)$$ and by another specialization $$\tag1P(y,x).$$ Also, by specialization from $(0)$ $$\forall yP(x,y)$$ and by another specialization $$\tag2 P(x,y).$$ Now from $(1)$ and $(2)$ by conjunction $$P(x,y)\land P(y,x)$$ and by generalization $$\forall y (P(x,y)\land P(y,x))$$ and finally $$\forall x\forall y( P(x,y)\land P(y,x)).$$ So far we have $$\forall x\forall y P(x,y)\vdash \forall x\forall y (P(x,y)\land P(y,x))$$ hence by the deduction theorem $$(3)\forall x\forall y P(x,y)\rightarrow \forall x\forall y (P(x,y)\land P(y,x)).$$

For the other direction, from $$\forall x\forall y( P(x,y)\land P(y,x))$$ by specialization $$\forall y( P(x,y)\land P(y,x))$$ and then $$ P(x,y)\land P(y,x)$$ and by conjunction elimination $$ P(x,y)$$ and by generalization again $$\forall y P(x,y)$$ and finally $$\forall x\forall y P(x,y).$$ Thus $$ \forall x\forall y (P(x,y)\land P(y,x))\vdash \forall x\forall y P(x,y)$$ and by the deduction theorem $$\tag4 \forall x\forall y (P(x,y)\land P(y,x))\rightarrow \forall x\forall y P(x,y).$$

From $(3)$ and $(4)$ we have by biconditional introduction $$ \forall x\forall y P(x,y)\leftrightarrow \forall x\forall y (P(x,y)\land P(y,x))$$ as desired.

Hagen von Eitzen
  • 374,180
0

Hint: I always like to explicitly specify a domain of quantification. IMHO, this makes for a more intuitive and "math-like" proof. So, with $U$ as the domain of quantification, the problem becomes to prove:

$\forall x,y (x,y\in U \to P(x,y))\leftrightarrow \forall x,y (x,y\in U \to P(x,y)\wedge P(y,x))$

(Some philosophy instructors may take exception to introducing set theoretic notation like this. Too "math-like".)

For '$\to$':

Assume $\forall x,y (x,y\in U \to P(x,y))$. Assume $a,b\in U$. Then obtain both $P(a,b)$ and $P(b,a)$, and generalize as required.

For '$\leftarrow$':

Assume $\forall x,y (x,y\in U \to P(x,y)\wedge P(y,x))$. Assume $a,b\in U$. Then obtain $P(a,b)$, and generalize as required.

Dan Christensen
  • 14,529