All men are mortal.There is really no good way to express this argument using propositional calculus.
Socrates is a man.
Therefore, Socrates is mortal.
p: All men are mortal.
q: Socrates is a man.
r: Socrates is mortal.
and is therefore not a valid argument in the propositional calculus.
p q r
Something is a man → It is mortal Something is Socrates → It is a man Something is Socrates → It is mortal
We need to go beyond the propositional calculus to the predicate calculus, which allows us to manipulate statements about all or some things, suggested by the above attempt at formulating the argument about Socrates.
We begin by rewording the statment "All men are mortal" a little more slickly than we did above:
"For all x, if x is a man then x is mortal."The sentence "x is a man" is not a statement in propositional calculus, since it involves an unknown thing x and we can't assign a truth value without knowing what x we're talking about. This sentence can be broken down into its subject, x, and a predicate, "is a man." We say that the sentence is a statement form, since it becomes a statement once we fill in x. Here is how we shall write it symbolically: The subject is already represented by the symbol x, called a term here, and we use the symbol P for the predicate "is a man." We then write Px for the statement form. (It is traditional to write the predicate before the term; this is related to the convention of writing function names before variables in other parts of mathematics.) Similarly, if we use Q to represent the predicate "is mortal" then Qx stands for "x is mortal." We can then write the statement "If x is a man then x is mortal" as Px→Qx. To write our whole statement, "For all x, if x is a man then x is mortal" symbolically, we need symbols for "For all x." We use the symbol ∀ "∀" to stand for the words "for all" or "for every." Thus, we can write our complete statement as
∀x[Px→Qx].The symbol "∀" is called a quantifier because it describes the number of things we are talking about: all of them. ^{} Specifically, it is the universal quantifier because it makes a claim that something happens universally.
Armed with some of the language of predicate calculus, we are now ready for our first valid argument in predicate calculus:
Express the argument about Socrates,
All men are mortal.in symbolic form.
Socrates is a man.
Therefore, Socrates is mortal.
∀x[Px → Qx] | |
Ps | |
Qs |
Mathematics is expressed in the language of the predicate calculus. ^{} Here's an example of a mathematical statement expressed symbolically.
Write the following statement symbolically: "If a number is greater than 1 then it is greater than 0."
"For all x, if x is a number and x is greater than 1, then x is greater than 0."Let us write N for the predicate "is a number" and use the standard notation ">" for "is greater than." Our statement is then:
∀x[(Nx(x>1)) → (x>0)].Notice that we put the phrases "x>1" and "x>0" in parentheses to make the meaning clearer.
∀x[(x>1) → (x>0)].In fact, we're being a little sloppy even in our original solution. We can run into logical paradoxes if we allow ourselves to let x range over "everything" possible. We should, instead, agree beforehand what universe of things the quantifier "∀x" really refers to. In this example, we might agree that the universe is the set of all real numbers. There is no need to allow x to also refer to, say, an elephant.
Now write the following statement symbolically: "Given any two numbers, the square of their sum is never negative."
"For all x and all y, if x and y are numbers then the square of their sum is not negative."Since "the square of their sum" is (x+y)^{2}, our statement can be written like this:
∀x[∀y[(NxNy)→~{(x+y)^{2}<0}]].Rather than write "x["y[ . . . ]] we often write
∀x,y[(NxNy)→~{(x+y)^{2}<0}].If we prefer not to have the negation, we could write
∀x,y[(NxNy)→{(x+y)^{2}≥0}].Once more, we could be lazy and write
∀x,y[(x+y)^{2}≥0].
∃x[PxHx].
Now we can write our statement symbolically, using lots of brackets to make the meaning clear:
∀x[Px→(∃y[PyB(x,y)])].
Many mathematical definitions are made in terms of quantifiers. An interesting example is the notion of "divisible by." To say that a number x is divisible by 2, for example, is to say that x is 2 times some integer, or that there exists some integer n such that x = 2n. Generalizing a bit and writing symbolically, we can make the following definition.
Divisible By
If x and y are integers, we say that x is divisible by y if ∃n[In(x=yn)]. Here, I is the predicate "is an integer." Note
∃n[x = yn]. |
First notice that our statement is a universal one about integers: "For every integer n, if n is divisible by 6 then it is divisible by 3 and by 2." Now, when we want to write "n is divisible by 6" we have to watch out for the fact that we've already used the variable n and can't reuse it as in the definition of "divisible by" above. What we do is pick another letter, say m, and write
∃m[n = 6m]for "n is divisible by 6." In general, the variable being quantified (the one immediately to the right of the quantifier) is a dummy variable; its name does not matter, as long as the same name is used consistently throughout the statement.
Doing the same with divisibility by 3 and 2, we can write our statement as follows:
∀n[(∃m[n = 6m])→(∃m[n = 3m])(∃m[n = 2m])].
∀n[(∃m[n = 6m])→(∃i[n = 3i])(∃j[n = 2j])].This leads to an interesting question: For a given n, how are i and j related to m? Pondering this question leads to the mathematical proof of the statement.
In this last example we've started to see how mathematics can be translated into symbolic form. It was the hope of mathematicians at the end of the nineteenth century that all of mathematics could be made purely formal and symbolic in this way. The most serious attempt to do this was in Whitehead and Russell's Principia Mathematica (1910), which translated a large part of mathematics into symbolic language. The hope then was that there could be developed a purely formal procedure for checking the truth of mathematical statements and producing proofs. This project was cut short by Gödel's incompleteness theorem (1931), which effectively showed the impossibility of any such procedure. Nonetheless, mathematicians still feel that anything that they do should be expressible in symbolic logic, and the language that they actually use in writing down their work is a somewhat less formal version of the predicate calculus.