Although sentential logic studied in Sections 1.1 and 1.2 is probably sufficient to get you through your daily activities, it is not sufficient for higher mathematics. This was realized in the late 1800s by the German logician Gottlob Frege, who observed that mathematics requires a more extensive language than simple logical sentences connected by ∧, ∨, ∼, ⇒, ⇔. Frege introduced what is called predicate logic1(or first‐order logic), which are sentences which in addition to the logical connectives of sentential logic, includes quantifiers, variables, and functions called predicates (or propositions). Predicate logic allows one to express concepts we often hear in mathematics, like
for any real number x, there exists a real number y such that x < y
which is impossible to express in sentential logic.
Two phrases one hears again and again in mathematics are for all, and there exists. These expressions are called quantifiers and are necessary to describe mathematical concepts. The meaning of an expression like x < y in itself is not clear until we describe the extent of x and y. This leads to the two basic quantifiers of predicate logic, the universal quantifier, meaning “for all” and denoted by ∀ (upside down A), and the existential quantifier, meaning “there exists,” and denoted by ∃ (backwards E). Inherent in the use of quantifiers is the concept of a universe set, which is the collection or set of objects under discussion, often being the real numbers, integers, natural numbers, and so on.
Some common number universes in mathematics are the following.
Propositions (or predicates) in predicate logic often contain more than one variable, which means the proposition must contain more than one quantifier to put limits on the variables. The following Table 1.29 illustrates propositions with two variables and what it means for the propositions to be true or false. To simplify notation, we assume the universe is known, so we do not include it.
Table 1.29 Propositions with two variables.
Proposition | Proposition is true when | Proposition is false when |
(∀x)(∀y)P(x, y) | For all x and y, P(x, y) is true | There exists some x, y. such that P(x, y) is false |
(∃x)(∀y)P(x, y) | There is an x such that for all y, P(x, y) is true | For all x, P(x, y) is false for some y |
(∀x)(∃y)P(x, y) | For all x, P(x, y) is true for some y | There exists an x such that for all y P(x, y) is false |
(∃x)(∃y)P(x, y) | There exists x, y. such that P(x, y)is true | For all x, y. P(x, y) is false |
Table 1.30 Sentences in predicate logic.
Proposition | English meaning | Truth value |
(∀x ∈ ℝ) (x2 ≥ 0) | For any real number, its square is nonnegative. | True |
(∃n ∈ ℕ) (n is a prime number) | There exists a prime number. | True |
(∃n ∈ ℕ) (2 /| n) | There exists at least one odd natural number. | True |
(∃n ∈ ℕ) (2 | n) | There exists at least one even natural number. | True |
(∀x ∈ ℕ) (∃y ∈ ℕ) (x = y + 1) | For any natural number x, there is a natural number y satisfying x = y + 1. | False |
(∀x ∈ ℝ) (∃y ∈ ℝ) (x < y) | For any real number x, there is a real numbery greater than x. | True |
(∃x ∈ ℝ) (∀y ∈ ℝ) (x < y) | There exists a real number x such that all real numbers y are greater than x. | False |
(∀x ∈ ℝ)(∃y ∈ ℝ) (y = 2x) | For any positive real number x, there is a real number y that satisfies y = 2x. | True |
Here's a question to ponder. Do the two propositions (∃x)(∀y)P(x, y) and (∀y)(∃x)P(x, y) mean the same thing or does one imply the other or are they completely unrelated? For example do the following to two propositions:
mean the same thing? The answer is they do not since the first proposition is false, while the second proposition is true. Do you understand that?
To show how the order of the universal and existential quantifiers makes a difference in the meaning of a proposition, here's a simple example of a third‐grade class consisting of three boys and three girls, members of the sets
and the two‐variable predicate (or proposition)
where Figure 1.7 illustrates the relationships between the quantifiers ∀ ∀, ∃ ∀, ∀ ∃, ∃ ∃. The dot at the intersection of a boy and girl indicates the boy likes the girl. For example, Figure 1.7a means every boy likes every girl, while Figure 1.7c means Bob likes Ann and Betty, and Carl likes Carol.
Figure 1.7 gives visual support for the implications
which is stated explicitly in Figure 1.8.
In the next few sections, we will introduce strategies for proving theorems, and it will be necessary to know how quantified propositions are negated. The propositions in Table 1.31 show their negations in the language of predicated logic. The universe U, where the variables x and y are members might be any one of the common number systems ℕ, ℤ, ℚ, ℝ, ℂ or a subset of one line the intervals [0, 1], [0, ∞), and so on.
Table 1.31 Negation in predicate logic.
Proposition | Negation of proposition |
(∀x ∈ U) P(x) | (∃x ∈ U) [∼P(x)] |
(∃x ∈ U) P(x) | (∀x ∈ U) [∼P(x)] |
(∀x ∈ U) (∃y ∈ U) P(x, y) | (∃x ∈ U) (∀y ∈ U) [∼P(x, y)] |
(∃x ∈ U) (∀y ∈ U) P(x, y) | (∀x ∈ U) (∃y ∈ U) [∼P(x, y)] |
(∀x ∈ U)(∀y ∈ U)P(x, y) | (∃x ∈ U)(∃y ∈ U)[∼P(x, y)] |
(∃x ∈ U)(∃y ∈ U)P(x, y) | (∀x ∈ U)(∀y ∈ U)[∼P(x, y)] |
As an aid to understanding and involving conjunctions and disjunctions, Professor Snarf has conducted a survey among his students about their liking for peanuts and qumquats.3 If we let
we can write the following propositions about students likings of peanuts and qumquats.
There are several important relations between these propositions, including
which means that if every student likes peanuts or every student likes qumquats, then it follows that every student likes peanuts or qumquats. But the converse does not follow since just because every student in the class likes either peanuts or qumquats that does not mean the class belongs to one of two distinct groups, peanut lovers or qumquat lovers.
Several important relationships between the previous propositions are as follows:
…Arnold Haultain
…Norman Bates
…William Shakespeare
Write the following sentences in the symbolic language of predicate logic. The universe of each variable is given in parentheses. For these problems, we use the notation
Which of the following propositions are true in the given universe? The universe is given in parentheses.
Very quickly, true or false.
In which of the universes ℕ, ℤ, ℚ, ℝ, ℂ are the following sentences true for x and y.
Tell if the sentence
is true or false in the following universe U.
Which statements are true in the universe U = {1, 2, 3}.
Given the statements
which of the following sentences are true in the universe of real numbers.
State the following famous theorems in the language of predicate logic.
Let f be a continuous function on the closed interval [a, b]. If f changes sign from negative to positive on [a, b], then there exists a number c between a and b, such that f(c) = 0.
If n is a natural number greater than 2, then there are no natural numbers a, b, and c that satisfy an + bn = cn.
If P is any regular polyhedron and if v, e, f are the number of vertices, edges, and faces, respectively, then v − e + f = 2.
If a, b are real numbers and n is a positive integer, then
Negate the following sentences in words.
Negate the following sentences in symbolic form.
A sequence of real numbers converges to a limit L if and only if
(∀ε > 0)(∃N ∈ ℕ)(∀n > N)(|xn − L| < ε)
If P(x, y) : y ≤ x2 + 1, where (x, y) are points in the plane, determine which of the following is true. Hint: A picture (i.e. graph) is worth a thousand words.
Which of the following statements are true and which are false for real numbers x, y?
State the denial of words of wisdom attributed to Abraham Lincoln: “You can fool some of the people all the time and all the people some of the time, but you can't fool all the people all of the time.”
Restate the following sentences in plain English.
Tell if the following sentences are true or false in each universe ℕ, ℤ, ℚ, ℝ.
A satisfiable sentence is a sentence that is true in at least some universe. For example, the sentence (∃x ∈ U)(x > 0) is satisfiable since it is true in the universe of real numbers. Tell if the following sentences are satisfiable, and if so, give a universe.
Letting
translate the following sentence to predicate logic.
There is a wealth of information related to topics introduced in this section just waiting for curious minds. Try aiming your favorite search engine toward predicate logic, negation of logical statements, first‐order‐logic, and universal quantifier.
3.91.8.23