Discrete Math Question on Universal and Existential Quantifiers

nicnicman

Hi everyone,

I've got a test tomorrow and while working through a practice test I got stuck. Here is the problem:

In the question below suppose P(x,y) is a predicate and the universe for the variables x and y is {1,2,3}. Suppose P(1,3), P(2,1), P(2,2), P(2,3), P(2,3), P(3,1), P(3,2) are true, and P(x,y) is false otherwise. Determine whether the following statements are true.

∀y∃x(P(x,y) → P(y,x)).

I understand that to find the truth value of a statement I should loop through each combination of values and if any result in False the statement is False. However, I'm not sure how I would loop through this one as x and y don't seem to be doing anything.

Any help would be appreciated.

Stephen Tashi

Why do you say that?

The way I see it, you loop through each value of y.
Inside the loop on y , you loop through each value of x.
If the loop through x has one case where P(x,y)->P(y,x) then the [itex] \exists x [/itex] condition is satisfied. The inner loop doesn't have to produce a true statement for all values x, it only has to work for one value of x.

Roughly like this:

for y = 1 to y = 3
{
for x = 1 to x = 3

if ( P(x,y) -> P(y,x) ) then there is no need to test more x values, leave this loop on x and proceed to the next y value.

end loop on x
}

If you get to this point, none of the x values worked, so the statement is false since the [itex] \forall y [/itex] failed for this particular value of y. You can leave the loop on y.

end loop on y

nicnicman

Thanks for the reply, but I still having trouble.

I'm trying to put what is happening in English:

For every y there is an x such that . . .

I guess I'm getting stuck on what is happening inside the parentheses:

If P(x,y), then P(y,x). This doesn't make sense to me.

Or, P(x,y) implies P(y,x).

Stephen Tashi

Haven't you studied the truth table for the statement "if A then B".

For example, consider the case x = 2, y = 3.
the statement becomes" if (P(2,3) then P(3,2)
P(2,3) is given to be True in the problem.
P(3,2) is given to be True in the problem.

Hence the if...then... statement is true in this case because A is True and B is True.
(The only case where 'if A then B" is False is when A is True and B is False.)

You could pretend the statement-function P(x,y) is a verbal statement like "Person x has property belonging to person y". However, I think it's easier just to proceed in a mechanical fashion.

nicnicman

Yeah, we have studied the truth tables for IF, I just wasn't making the connection. However, how would the statement ever be false. For what it's worth, the answer I was given on the practice exam is TRUE.

Would the statement be false if x = 1 and y = 2?

Thanks again.

Stephen Tashi

By "the statement", do you mean "if (P(x,y) then P(y,x)"? (which is not the entire statement)
if P(1,2) then P(2,1) is True because P(1,2) is False. The if...part is False. The only time "If A then B" is false is when A is True and B is False.

nicnicman

Shoot, I got that backwards. What I meant was if x = 2 and y =1.

Then you would have P(2, 1) implies P(1, 2). Since P(2,1) is TRUE and P(1,2) is FALSE, then the statement is FALSE. Correct?

Stephen Tashi

Correct, The statement "if P(2,1) then P(1,2)" is False in that case.

To determine the truth of "There exists an x such that if (P(x,1) then P(1,x)" you'd have to see if some other value of x makes "if P(x,1) then P(1,x)" evaluate to True.

nicnicman

There is no other combination that makes If P(x,y), then P(y,x) false. However, since ∀y∃x is saying, "For all y's there is an x..." and we have shown that there is case that doesn't prove true for a given y, then the statement is False. Maybe I'm seeing this wrong, but isn't the statement False?

Stephen Tashi

You're seeing it wrong. The [itex] \exists x [/itex] doesn't mean that if (P(x,1) then P(1,x) must be true for all values of x. It only claims it is true for at least one value of x. The fact you showed one value of x made "if P(x,1) then P(1,x)" evaluate to False, doesn't rule out that there might exist another value of x that makes it True. Let x = 1, then P(1,1) is False, so x = 1 works to make "if P(1,1) then P(1,1)" evaluate to True.

nicnicman

Thanks for the help. I just took my exam and your explanations helped a lot.