Hey guys,(adsbygoogle = window.adsbygoogle || []).push({});

I've been given a problem and I attempted it but I have no idea if it is right, I was hoping you guys could help me.

Show that (∀x)(∃y)(p(x, y) -> p(y, x)) is a tautology.

Since, I am new to logic and Predicate Calculus I was wondering if someone could check my working, (I was amazed how hard it is to get logic 0.0):

Okay, i was told to assume that we will only deal with non-empty sets.

Let D any non-empty set and let p(x,y) be a predicate with a domain of definition D x D. Then since D is non-empty we can find some d ∈ D.

since "p(d,d) -> p(d,d)" is true

We can say there is some y ∈ D such that "p(d, y) -> p(y, d)" is true (namely y=d).

so

(∃y)(p(d, y) -> p(y, d)) is true

and we can also say

¬(∃y)(p(d, y) -> p(y, d)) is false

(Note: the following is the section I am unsure if I am right or not)

therfore for since

¬(∃y)(p(d, y) -> p(y, d)) is false

So for any d it must be false.

so

(∃x)¬(∃y)(p(x, y) -> p(y, x)) must also be false.

(∃x)¬(∃y)(p(x, y) -> p(y, x)) <=> ¬(Ax)(∃y)(p(x, y) -> p(y, x))

so ¬(∀x)(∃y)(p(x, y) -> p(y, x)) is false too

and we can say

¬¬(∀x)(∃y)(p(x, y) -> p(y, x)) must be true

therefore (∀x)(∃y)(p(x, y) -> p(y, x)) must be true for any non-empty domain and any predicate p. tehre for (Ax)(∃y)(p(x, y) -> p(y, x)) is a tautology.

**Physics Forums - The Fusion of Science and Community**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Predicate calculus: Proof problem (please check for me)

Loading...

Similar Threads for Predicate calculus Proof | Date |
---|---|

Proof in predicate calculus | Jun 22, 2012 |

Proof in predicate calculus 2 | Nov 2, 2011 |

Proof in predicate calculus | Oct 31, 2011 |

Proof in predicate calculus | Oct 22, 2008 |

Proof in predicate calculus | Sep 24, 2008 |

**Physics Forums - The Fusion of Science and Community**