- #1
Waylander
- 5
- 0
Hey guys,
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.
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.
Last edited: