Math 190 - <More on Predicates and Quantifiers>Fall 2003 B Page 1

Last time we learned about predicates, that is, statements with variables whose truth value depends on the values of the variables.

Examples:

$x < 7

$z is a prime number

$t is a square

$S is a Hausdorff space

$G is a group

When we use predicates we need to be clear about what kinds of things we can use to replace the variable. So there is usually some specified or understood replacement set from which we can draw to replace the variable. We sometimes call the set of all things from the replacement set that satisfy a predicate (make it true) the truth setof the predicate.

We also learned how quantifiers can be used to express the idea that all members of a set satisfy a predicate, or how a particular but unspecified member of a set can satisfy a predicate:

$For all x, x < 7(Symbolically: x (x < 7) )

$There exists a z such that z is a prime number

( Symbolically x (x is a prime number) )

We sometimes call  a universal quantifierand  an existential quantifier.

Math 190 - <More on Predicates and Quantifiers>Fall 2003 B Page 1

Note that x P(x) makes the assertion that all elements of the replacement set of P(x) are in the truth set.

Also, note that x P(x) makes the assertion that there is at least one element of the replacement set if P(x) n the truth set.

Examples:

$Suppose P(x) is Ax is an even number greater than 15." In order to make sense, the replacement set must be something like the integers or whole numbers. We would have to know or decide, depending on the kind of mathematic we were doing (we=ll let it be the integers right now). The truth set is all even integers greater than 15. The proposition x P(x) asserts that there is an even number greater than 15. The proposition x P(x) asserts that all integers are even and greater than 15.

Given the Real numbers as a replacement set in the examples below,

$What is the truth set of the predicate Q(x): x2 < 0? What is asserted by x Q(x) and by x Q(x)?

$What is the truth set of R(x): x3 > 0? What is asserted by x R(x) and by x R(x)?

Math 190 - <More on Predicates and Quantifiers>Fall 2003 B Page 1

Building Bigger and Better Predicates:

There are at least two ways to get bigger and better predicates than the simple one-variable predicates that we have been using so far.

First: use more than one variable.

$x < y

$x + y > 7

$x is a multiple of y

$y = ln x

$x2 + y2 = r2

Each of these then have replacement sets for each variable. The truth sets become order pairs (or triples or whatever) that you plug in to make the statement true. For example, the replacement sets for x2 + y2 = r2 could all be real numbers, and one of the elements of the truth set becomes (3, 4, 5) where it is understood that x = 3, y = 4, and r = 5.

When we do this we can then of course use quantifiers to make propositions:

xy (x < y)

xy (x < y)

xy (x < y)

xy (x < y)

xy (x + y > 7)

xy (x + y > 7)

xy (x + y > 7)

xy (x + y > 7)

Math 190 - <More on Predicates and Quantifiers>Fall 2003 B Page 1

xy (x + y = y)

xy (x + y = y)

xy (x + y = y)

xy (x + y = y)

xy (x is a multiple of y)

xy (x is a multiple of y)

xy (x is a multiple of y)

xy (x is a multiple of y)

xy (xy = 1)

xy (xy = 1)

xy (xy = 1)

xy (xy = 1)

Math 190 - <More on Predicates and Quantifiers>Fall 2003 B Page 1

The Second way of making bigger and better predicates is to use a single quantifier with a multi-variable predicate:

  • x (x + y = y) Truth set: All Reals
  • x (y + x = x + y)Truth set: All Reals
  • x (xy = y)Truth set: All Reals
  • x (xy = x)Truth set: {1}
  • x (x + y = x)Truth set: {0}
  • x (xy = 1)Truth set: All Reals except 0
  • x (x2 = y)Truth set: All Non-neg. Reals

Math 190 - <More on Predicates and Quantifiers>Fall 2003 B Page 1

We can now use all these predicates and quantifiers to express a wide variety of ideas:

If the replacement set is Whole Numbers:

xy (x < y)

xy (xy = yx)

xy (x + y = y)

If the replacement set is Integers:

xy (x + y = 0)

xyqr (x = yq + r and 0  r < y)

z (y = xz)

If the replacement set is Real Numbers:

xy (xy = y)

xyz ( x(yz) = (xy)z )

x y (if x  0, then xy = 1)

not (x y (x < y))

Math 190 - <More on Predicates and Quantifiers>Fall 2003 B Page 1

Negations:

The negation of the statement x P(x) is x (not P(x))

The negation of the statement x P(x) is x (not P(x))

These rules can be combined to find the negation of complicated statements:

The negation of the statement xyzrst P(x, y, z, r, s, t)

is the statement

xyzrst (not P(x,y, z, r, s, t))