Predicate calculus - propositions

Printable View

August 2nd 2009, 07:34 PM
yoonsi

Predicate calculus - propositions

Let $p(x,y)$ denote the predicate $"x\leq y"$ and let $q(x,y)$ denote $"x<y"$ both with domain of definition N x N.

$\forall x \forall y \forall z ((p(x,y) \wedge p(y,z)) \rightarrow (p(x,z))$

$\forall x \forall y (\exists z(q(x,z) \wedge q(z,y)) \rightarrow (q(x,y))$

$\forall x \forall y (\exists z(q(x,z) \wedge q(z,y)) \leftrightarrow (q(x,y))$

$\exists x \forall y p(x,y)$

$\exists y \forall x p(x,y)$

This is a question I've been given. The question asks for me to translate them all into good English phrases. This I believe I have done correctly. It also asks me to say whether the proposition is true for each.
I have found that each is true, but I find this a bit suspicious, assuming at least one should be false, or maybe they're trying to throw me off (Itwasntme)
So I was wondering, does anyone disagree with my finding that all are true?
August 2nd 2009, 07:41 PM
Danneedshelp

$\exists x \forall y p(x,y)$

$\exists y \forall x p(x,y)$

For these, try fixing x and y and seeing if they hold.

Suppose, for the second one, we choose some really large number; such as, y=10^10 . By doing so, I am saying I found a y such that every number x is less than or equal to this number. But, what do we know about the natural numbers? Can this be true?
August 2nd 2009, 07:54 PM
yoonsi

$ \exists x \forall y p(x,y) $

This one is saying...that there is a natural number x, such that all natural numbers y are greater than or equal to x?
if I fix 1 as x, then this is true. (assuming 1 is the lowest natural number)

and

$ \exists y \forall x p(x,y) $

That one is saying, that there is a natural number y, such that all natural numbers x, are less than y?
no matter what value you fix for y, this cannot be true..

Soo, first is true and second is false? (Evilgrin)
Also... in the instance given (Domain of definition N x N) or even in general, is 0 a natural number?

Thanks so much Dan =]
August 2nd 2009, 08:50 PM
Danneedshelp

Quote:

Originally Posted by yoonsi

$ \exists x \forall y p(x,y) $

This one is saying...that there is a natural number x, such that all natural numbers y are greater than or equal to x?
if I fix 1 as x, then this is true. (assuming 1 is the lowest natural number)

and

$ \exists y \forall x p(x,y) $

That one is saying, that there is a natural number y, such that all natural numbers x, are less than y?
no matter what value you fix for y, this cannot be true..

Soo, first is true and second is false? (Evilgrin)
Also... in the instance given (Domain of definition N x N) or even in general, is 0 a natural number?

Thanks so much Dan =]

Yes, you got it. As for the natural numbers, the definition does not include zero (1,2,3…).