Predicate calculus: Proof problem (please check for me)


by Waylander
Tags: calculus, check, predicate, proof
Waylander
Waylander is offline
#1
Aug3-05, 07:27 PM
P: 5
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.
Phys.Org News Partner Science news on Phys.org
Lemurs match scent of a friend to sound of her voice
Repeated self-healing now possible in composite materials
'Heartbleed' fix may slow Web performance
EnumaElish
EnumaElish is offline
#2
Aug3-05, 09:39 PM
Sci Advisor
HW Helper
EnumaElish's Avatar
P: 2,483
This looks okay to me -- but I don't have a logic degree. Can you take a shortcut and write: "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. Since d was arbitraryly chosen, it must be true for all d." That is, can you "merely" rename d as x?
Waylander
Waylander is offline
#3
Aug4-05, 01:16 AM
P: 5
Quote Quote by EnumaElish
This looks okay to me -- but I don't have a logic degree. Can you take a shortcut and write: "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. Since d was arbitraryly chosen, it must be true for all d." That is, can you "merely" rename d as x?
hmm... yeah I guess you could. Thanks. ^_^

honestrosewater
honestrosewater is offline
#4
Aug4-05, 01:44 AM
PF Gold
honestrosewater's Avatar
P: 2,330

Predicate calculus: Proof problem (please check for me)


I wish I would have kept going with predicate logic, but what about
[tex]\forall x \in \mathbb{N} \ \exists y \in \mathbb{N} \ ((x < y) \rightarrow (y < x))[/tex]
?? Even if you mean
[tex](\forall x \in \mathbb{N} \ \exists y \in \mathbb{N} \ (x < y)) \rightarrow (\forall x \in \mathbb{N} \ \exists y \in \mathbb{N} \ (y < x))[/tex]
isn't this still a semi-counterexample?

Do you have some inference rules? Normally, to prove that a propostion is a tautology, you derive it from the empty set (of premises). You would use universal and existential generalization, which I'm shaky on, and I'm not sure how to work with predicates either, but it would go something like this:
Start by assuming Pwa, where w is some arbitrary individual; derive Paw; infer, by conditional proof, (Pwa -> Paw); generalize from (Pwa -> Paw) to AxEy(Pxy -> Pyx).
I could be wrong but thought I would mention it just in case.
Waylander
Waylander is offline
#5
Aug4-05, 03:05 AM
P: 5
Quote Quote by honestrosewater
I wish I would have kept going with predicate logic, but what about
[tex]\forall x \in \mathbb{N} \ \exists y \in \mathbb{N} \ ((x < y) \rightarrow (y < x))[/tex]
?? Even if you mean
[tex](\forall x \in \mathbb{N} \ \exists y \in \mathbb{N} \ (x < y)) \rightarrow (\forall x \in \mathbb{N} \ \exists y \in \mathbb{N} \ (y < x))[/tex]
isn't this still a semi-counterexample?

Do you have some inference rules? Normally, to prove that a propostion is a tautology, you derive it from the empty set (of premises). You would use universal and existential generalization, which I'm shaky on, and I'm not sure how to work with predicates either, but it would go something like this:
Start by assuming Pwa, where w is some arbitrary individual; derive Paw; infer, by conditional proof, (Pwa -> Paw); generalize from (Pwa -> Paw) to AxEy(Pxy -> Pyx).
I could be wrong but thought I would mention it just in case.
Um for the example I think the statement is still true... I think it is saying
For all x: (x < some Natural Number y -> there exists some y < x)
And since this is true for all x then that statement is true for that example, and is not a counter example... I think.

Though those domains and that predicate would be a counter example for:
(∃y)(∀x)(p(x, y) -> p(y, x))
honestrosewater
honestrosewater is offline
#6
Aug4-05, 04:46 AM
PF Gold
honestrosewater's Avatar
P: 2,330
Quote Quote by Waylander
Um for the example I think the statement is still true... I think it is saying
For all x: (x < some Natural Number y -> there exists some y < x)
And since this is true for all x then that statement is true for that example, and is not a counter example... I think.
I don't know what that means. Either x and y refer to the same individual, respectively, in both Pxy and Pyx (as in my first statement), or they refer to possibly different individuals (as in my second statement). Of course, this depends on the scope of the quantifiers.

[tex]\forall x \in \mathbb{N} \ \exists y \in \mathbb{N} \ ((x < y) \rightarrow (y < x))[/tex]

So I can assign x = 1 and y = 2 : (1 < 2) -> (2 < 1). False.

[tex](\forall x \in \mathbb{N} \ \exists y \in \mathbb{N} \ (x < y)) \rightarrow (\forall x \in \mathbb{N} \ \exists y \in \mathbb{N} \ (y < x))[/tex]

So I can assign the first x = 3, first y = 4 : 3 < 4. True. And I can assign the second x = 1, but there exists no y in N less than 1, so this and the conditional are false.

You're saying:
1)) Pdd [conditional proof (d is an arbitrary individual)]
2)) Pdd [1, reiteration]
3) Pdd -> Pdd [1, 2 cond. proof]
4) Pdc -> Pcd [3, by what rule? (c is non-arbitrary)]
I don't see how step (4) is valid. How can you substitute c for only some instances of d?
When Pdd is true, Pdc and Pcd will also be true, of course, for at least d = c. However, when Pdd is false, Pdc or Pcd may be true or false, unless you specify that c = d.
Bah, maybe I'm just confusing things, but this really doesn't seem right to me.

Edit: In fact, what's to stop you from doing this:
1) Pdd -> Pdd [premise]
2) Pdc -> Pcd [1, your rule]
3) Pcd -> Pdc [1, your rule?]
4) Pdc <-> Pcd [2, 3, equivalence]
Hurkyl
Hurkyl is offline
#7
Aug4-05, 05:47 AM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,101
Don't forget the rule:

P(a)
----
(∃x):P(x)



Incidentally, in:

[tex]\forall x \in \mathbb{N} \ \exists y \in \mathbb{N} \ ((x < y) \rightarrow (y < x))[/tex]

If you choose x = 1, I could choose y = 1, and then (x < y) &rarr; (y < x) would be true!

You don't always have to pick y = x, incidentally: for example, P(x, y) could be an equivalence relation, and then you just pick y to be anything at all. But you do need to pick y = x for the general proof, where P is arbitrary.
honestrosewater
honestrosewater is offline
#8
Aug4-05, 06:15 AM
PF Gold
honestrosewater's Avatar
P: 2,330
Quote Quote by Hurkyl
Incidentally, in:

[tex]\forall x \in \mathbb{N} \ \exists y \in \mathbb{N} \ ((x < y) \rightarrow (y < x))[/tex]

If you choose x = 1, I could choose y = 1, and then (x < y) → (y < x) would be true!
Oh, right. Sheesh.

I still want to figure out if and how that one rule is valid.
EnumaElish
EnumaElish is offline
#9
Aug4-05, 09:59 AM
Sci Advisor
HW Helper
EnumaElish's Avatar
P: 2,483
Quote Quote by Hurkyl
If you choose x = 1, I could choose y = 1, and then (x < y) → (y < x) would be true!
Don't you need a weak inequality for this to be true?
honestrosewater
honestrosewater is offline
#10
Aug4-05, 11:17 AM
PF Gold
honestrosewater's Avatar
P: 2,330
Quote Quote by EnumaElish
Don't you need a weak inequality for this to be true?
What's a weak inequality - <? I thought Hurkyl was pointing out that (False -> False/True) is true. And since [itex]\forall x (\neg(x < x))[/itex], there exists some y that makes the implication true by making the antecedent false: (y = x).

[tex]\forall x \in \mathbb{N} \ \exists y \in \mathbb{N} \ ((x < y) \rightarrow (y < x))[/tex]
AKG
AKG is offline
#11
Aug4-05, 12:38 PM
Sci Advisor
HW Helper
P: 2,589
  | (no assumptions)
  |----------------
  | 
1 | | p(a,a)                       Assumption
  | |---------
2 | | p(a,a)                       1, Repitition
  |
3 |  p(a,a) --> p(a,a)             1-2, Conditional Introduction
4 | (Ey)(p(a,y) --> p(y,a))        3, Existential Introduction
5 | (Ax)(Ey)(p(x,y) --> p(y,x))    4, Universal Introduction


Register to reply

Related Discussions
Predicate Logic Problem Set Theory, Logic, Probability, Statistics 3
Consistency-related proof in predicate logic Calculus & Beyond Homework 3
Predicate logic proof Calculus & Beyond Homework 10
Calculus: answer check please Introductory Physics Homework 6
Grade 12 Calculus, can someone pls, check for me? Introductory Physics Homework 2