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**

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

Know someone interested in this topic? Share a link to this question via email,
Google+,
Twitter, or
Facebook

Have something to add?

- Similar discussions for: Predicate calculus: Proof problem (please check for me)

Loading...

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