80-110: The Nature of Mathematical Reasoning

Spring 1998

Class 16: 3/10/98

 

1. Sentential Semantics

The argument we considered last week involves only atomis sentences:

Argument 1

Premise 1: tet(a)

Premise 2: a = b

Conclusion: tet(b)

We could evaluate the validity of this argument in Tarski’s World by visiting each possible world and checking the truth of these sentences in each world. Suppose, however, our argument was a little more complicated:

Argument 2

Premise 1: tet(a) V cube(a)

Premise 2: Øcube(a)

Conclusion: tet(a)

Whereas argument 1 involved only atomic sentences, argument 2 involves "molecular sentences."

The "Ø" in premise 2 is the symbol for negation, so the sentence translates as: it is not the case that a is a cube. The "V" in premise 1 is the symbol for disjunction, so it is to be read as: a is a tetrahedron or a is a cube. These are called "sentential connectives" because they connect smaller sentences into bigger ones. The argument is again clearly valid. And again we might establish its validity by looking through all the possible worlds in TW. How would this go? In argument 1 all the sentences are atomic sentences, and it should be clear how the computer evaluates the truth of an atomic sentence in a TW world. But how would the machine evaluate the premises, which are not atomic? The answer is called "sentential semantics," and involves how to decide on the truth of a compound sentence once you know the truth of its parts. For example, the semantics of the negation is given by the following table, which is called a "truth table."

We read it as follows. In the first column, we are considering all the possible truth values of the sentence A, whatever A is. In the second, we consider the truth of the sentence "ØA." So the first row is to be read: the sentence ØA is false whenever the atomic sentence A is true. The second row reads: the sentence ØA is true whenever the atomic sentence A is false. So negation, which is considered a unary connective because it only operates on 1 argument, is completely simple. The binary connectives disjunction, which I write with the symbol "v," and conjunction, which I write with the symbol "&," are a little more complicated, but their semantics are given by the following truth table:

In the first row, the atomic sentence A is true and the atomic sentence B is true, as are the sentences "A v B" and "A & B". In the second, A is true and B false, etc. These tables give a machine all the info they need to evaluate the truth of the sentences in argument 2, provided the truth of the atoms can be determined. The machine in essence constructs the following table whenever it would evaluate argument 2:

For whatever world of TW it found itself in, it would first decide on the truth of tet(a) and cube(a), which would place it in the appropriate row. Then it could judge the truth of the premises and the conclusion accordingly. Having done so for all the worlds it can represent, we could ask it if there were any in which the premises were true and the conclusion false.

A minutes thought about this table, however, and you will notice that we need not even go into TW to judge this argument valid. The table alone shows us that only in row 2, or when a is tetrahedron and not a cube, are all the premises true. And in this row, the conclusion is also true. It is impossible for the premises to be true and the conclusion false simultaneously. You might also notice that because nothing can be both a tetrahedron and cube at the same time, the first row is not possible. That is, it is a spurious row.

Several concepts are used about mathematical claims perhaps more comprehensible with possible worlds: satisfiable, logically equivalent, tautologous, logically true, etc. These are defined roughly in the follow way:

A set of sentences are satisfiable just in case there is some possible world in which they are all true. A sentence is logically true just in case there are no possbile worlds in which it is false. Two sentences are logically equivalent just in case they are true in exactly the same possible worlds. Tautology can be defined via truth tables.

For some problems, some rows of the truth table may be spurious, the truth table for the sentence tet(a) v cube(a) looks like:

tet(a) cube(a) tet(a) V cube(a)

T T T

T F T

F T T

F F F

In fact nothing can be both a cube and a tetrahedron at the same time, so row 1 is said to be spurious. That is, there is no possible world in which a is a cube and a tetrahedron. But this is not the truth table's fault, this is our fault for suppressing a relationship between the two predicates, namely that they cannot both be true of any object, in particular a: Ø(tet(a) & cube(a)). Likewise, the truth table for the sentence a=a is:

a=a a=a

T T

F F

The second row is spurious, i.e., it doesn't represent any real possibilities. But again, that is not the truth table's fault, it is our fault for not expressing an assumption about the predicate "=", that there is nothing that doesn't equal itself.

So we can now define tautology and see its relation to the definition of logical truth. A sentence is tautologous just in case it is true in every row of its truth table. Of the sentences we have studied so far, a sentence will be tautologous exactly when it is logically true as long as no rows in its truth table are spurious.

2. Sentential Semantics and Possible Worlds

In the last class we discussed the idea of semantic checks for validity: visit all possible worlds, and in each assess the truth of the premises and conclusion. If there is a world (or worlds) in which the prems are true and the conclusion false, the argument is invalid. In Tarski’s World we can do this, because the worlds are finite. In standard mathematics, of course, there is a serious problem with this approach, because there are an infinity of possible worlds. How could we ever visit them all? The good news is that sometimes we don’t have to visit them all to see if an argument is valid. We just have to know about what happens in certain regions of the possible worlds. Consider an argument identical in structure to argument 2:

Argument 3

P1: P v Q

P2: ~P

C: Q

To assess whether this argument is valid it would seem that we would have to check every possible world to see whether the premises P1 and P2 are true and the conclusion C is false. Consider the two atomic sentences in this argument: P, Q. We can use these atoms to partition the entire infinite set of possible worlds into four subsets that are exlusive and exhaustive.

 

Each region might contain an infinity of possible worlds, but within a region, the truth or falsity of the propositions P and Q are constant. Thus, if the argument involves claims that only involve P and Q, then there are only four relevant possibilities we need to consider, and they are exactly the regions in the picture. This is what a truth table does. It extracts the atomic sentences that occur anywhere in the argument, and allows us to break up the infinity of possible worlds into a finite partition of 2N cells, where N is the number of atomic sentences involved.


Back to Lecture Notes Index