Skip to Content

Return to the home page

Archive for the 225 book tag

Logic: Or

Standard post by ancoop on July 6, 2018
Comments are off for this post

Let’s get another little word.

Definition. Given two propositions P and Q, the proposition P\vee Q (read P or Q) has truth value as given below:

P Q P\vee Q
T T T 1
T F T 2
F T T 3
F F F 4

 

Exercise. Prove the following propositions. First make sure you know what they mean.

Proposition. \vee is commutative.

Proposition. \vee is associative.

Lines 2-4 probably aren’t surprising, but line 1 bothers pretty much everybody, so we should explore it a bit. Consider a statement like Barack Obama was born in Hawaii or Angela Merkel has a Ph.D. in chemistry. The two statements that make up this statement are both true (Obama was indeed born in Hawaii, and Merkel was a chemist before entering politics), so this is the type of statement that’s relevant to line 1. But we normally wouldn’t use the word or here; we’d use the word and instead. So seeing it written with the word or kind of makes us uncomfortable. Unfortunately (actually, very fortunately) there isn’t the option to assign a truth value of U — we have to give either a T or an F. And (there’s a long story, which you’ll work out for homework) it turns out to be much better to give a T than to give an F.

When we want to be extra clear, we refer to this flavor of or — the one with a T in the first row — we call it inclusive or. Generally speaking mathematicians use inclusive or, so get used to it!

Let’s take a look at how \vee interacts with \wedge. Try your hand at proving the following, using truth tables:

Theorem. \vee and \wedge distribute over one another; that is:

  1. (P\wedge Q)\vee R is equivalent to (P\vee R)\wedge (Q\vee R) (this is \vee distributing over \wedge.)
  2. (P\vee Q)\wedge R is equivalent to P\wedge R)\vee(Q\wedge R) (this is \wedge distributing over \vee.)

We also have the following very useful and very interesting result, which lets us translate between ands and ors:

De Morgan’s Law:

  1. \sim (P\wedge Q) is equivalent to (\sim P)\vee (\sim Q)
  2. \sim (P\vee Q) is equivalent to (\sim P)\wedge (\sim Q)

We are now ready to give our first logical computation, and formulate a useful denial of (P\wedge Q)\vee R. We’ll use the symbol \equiv to mean is equivalent to.

\sim\left[(P\wedge Q)\vee R\right]
\equiv \left(\sim(P\wedge Q)\right)\wedge (\sim R) by De Morgan’s Law 2
\equiv \left((\sim P)\vee (\sim Q)\right)\wedge (\sim R) by De Morgan’s Law 1

Notice that just as in arithmetic, we work from the outside in, and write each step out. Also just as with arithmetic (and this can’t be emphasized enough) brackets are both useful and necessary!

The formula we ended with looks very little like the formula we started with–for example, it’s much longer. Why might a formula like

\left((\sim P)\vee (\sim Q)\right)\wedge (\sim R)

be more useful than

\sim\left[(P\wedge Q)\vee R\right]?

Let’s assign the variables as follows:

P= Roses are red.
Q= Violets are blue.
R= The king of France is bald.

 

Then (P\wedge Q)\vee R says

Either roses are red and violets are blue, or the king of France is bald.

Its denial \sim((P\wedge Q)\vee R) says

It is not the case that either roses are red and violets are blue, or the king of France is bald.

But what does that mean? Our logical computation says that it means just the same thing as

The king of France is not bald, and either roses aren’t red or violets aren’t blue.

Try convincing yourself, and explaining to someone else, why these two denials mean the same thing.

As with arithmetic, this is not the only way to come up with a denial of (P\wedge Q)\vee R. Above we applied de Morgan’s Law first; but since we know that \wedge and \vee distribute over one another, we could equally well have derived

\sim\left[(P\wedge Q)\vee R\right]
\equiv \sim\left[R\vee(P\wedge Q)\right]
\equiv \sim\left[(R\vee P)\wedge (R\vee Q)\right]
\equiv \left[\sim(R\vee P)\right]\vee\left[\sim(R\vee Q)\right] by de Morgan’s Law 1
\equiv \left[(\sim R)\wedge (\sim P)\right]\vee\left[(\sim R)\wedge(\sim Q)\right] by de Morgan’s Law 2

which reads Either the king of France is not bald and roses are not red, or the king of France is not bald and violets are not blue.

As with arithmetic, the commutative, associative, and distributive rules for \wedge and \vee will become so second nature to you that will begin applying them without thinking about it. But here we’ve spelled everything out.

Cardinality

Standard post by ancoop on July 6, 2018
Comments are off for this post

Consider the following question:

Are there more Horsemen of the Apocalypse, or teams in the American Football Conference – East Division?

The standard way to answer this question would be to count each collection. First let’s do the Horsemen of the Apocalypse.

With the help of artist Viktor Vasnetsov, we form a bijection like

We can make a bijection to count the teams of the AFC – East, for example

So the two sets both have four elements, hence are the same size. This is one utility of cardinality: we can check whether two sets are the same size by counting each set, then comparing the resulting numbers.

But what if we didn’t know how to count? You may not remember what it was like not to be able to count (don’t worry, you’ll soon be experiencing that same feeling again), but there was a time when nobody could count.

Overview of Cardinality

 

One, Two, Three, Four, Five, Six, Seven, Eight, Nine, Ten, … One Hundred

Here are the ways to say some numbers in a few languages of the Indo-European language family:

French Latin Irish Serbian German English
1 un unus haon jedan ein one
2 deux duo do dva zwei two
3 trois tres tri tri drei three
4 quatre quattuor ceahtair četri vier four
5 cinq quinque cuig pet funf five
6 six sex se šest sechs six
7 sept septem seacht sedam sieben seven
8 huit octo hocht ossam acht eight
9 neuf novem naoi devet neun nine
10 dix decem deich deset zehn ten
20 vingt viginti fiche dvadeset zwanzig twenty
27 vingt sept viginti septem fiche seacht dvadeset sedam siebenundzwanzig twenty-seven
81 quatre-vingts un octoginta unus ochto a haon ossamdeset jedan einundachtzig eighty-one
100 cent centum cead sto hundert one hundred
1000 mille mille mile hiljada tausend one thousand

 

There are some interesting patterns here: the word for three is almost identical across all these languages, as are the words for four (sometimes the initial sound is k, sometimes ch, sometimes f, but it always ends in r) and seven. In fact, the numbers 1-10 are what linguists call cognate: they appear to all descend from the same word in the original Proto-Indo-European language, which was spoken somewhere in what’s now Iran or Afghanistan.

Another word that is common across all the languages is the word for one hundred. This one is a little less obvious, but the linguists tell us the Proto-Indo-European word was kmtom. (In some languages that k became a c or s; in others it became an h). So you might be tempted to think that the languages just all have basically the same ways to count.

. . . until you look at the words for 20. In English and German, the word for 20 is derived from the word for 2, but with some decoration. In Serbian, it’s just two tens. The Latin word viginta is derived from the word ginta, which means a group of 10 (which is different from the number 10, sort of like the difference between dozen and twelve), and vi, which is an old word for two (that sounds like the Serbian dva). French vingt is the same as in Latin. In Irish, the word for 20 is just its own thing unrelated to any other numbers.

When we get to 81, each language has its own completely different way to express the number:

French quatre-vingt un four-twenty one
Latin octoginta unus eight-groups-of-ten one
Irish ochto a haon eight+decoration and one
Serbian ossamdeset jedan eight-ten one
German einundachtzig one and eight+decoration
English eighty-one eight+decoration one

 

So what’s going on here? The linguists tell us that the Proto-Indo-Europeans knew how to count to ten, and had a word for one hundred, but didn’t have words for anything in between. The theory is that kmtom didn’t actually mean 100 anyway, just a big number, which the English word hundred sort of still does sometimes — I’ve told you a hundred times rarely means precisely 100. There are also other uses of the word hundred that don’t mean 100 of anything, just some kind of vaguely large number:

  • In England and Wales, counties were divided into hundreds: administrative subdivisions which ranged from 50 to 200 households.
  • Several units of measurement from medieval English law: a hundredweight is either 108 or 112 pounds, depending; a hundred of herring is 120 fish; a hundred of spices is 108 pounds; a hundred of garlic is 225 bulbs.

From archaeological evidence, we also know that this people-group were pastoralists: they herded sheep and/or goats.  (Archaeologists can’t tell the difference between sheep bones and goat bones.) It takes a lot more than 10 sheep-goats to sustain a family. So how did the Proto-Indo-Europeans manage to keep track of their flocks without being able to count them?

They used bijections, in a way that’s still used to this day by shepherds all around the world. The equipment used is simple: a container and a pile of pebbles. In the morning, as the sheep-goats are leaving their pen, drop a pebble into the container every time a sheep-goat passes you. This is a bijection between the flock and the pebbles in the container. At the end of the day, as the sheep-goats come back into their pen, remove one pebble for each sheep-goat that passes you on its way in. If the container is empty, you know you haven’t lost any animals; if there’s still pebbles left in the container, you know you have lost one.

One needn’t use pebbles; one could instead make marks on a stick with a knife, for example (this method of recordkeeping persisted in Europe through the 1800s, though it ultimately resulted in the destruction of the Houses of Parliament). This is one theory of the origin of the Ishango Bone, one of the world’s oldest surviving mathematical artifacts (dating from before 18,000 BCE):

All of this is to say: if what we’re interested in is comparing the sizes of two sets, we don’t actually need to compute the size of each set and compare them; instead, we can look for bijections between the two sets.

Logic: Not & And

Standard post by ancoop on July 6, 2018
Comments are off for this post

Statements by themselves aren’t that interesting; let’s see how to combine them.

“not”

A writing teacher once told me the best way to clean up your writing is to eliminate as many adverbs and adjectives as possible. But one very important adverb–which changes the meaning of anything it touches–is the word not. Let’s formalize this.

Definition. Given a statement S, the statement \sim S (read It is not the case that S or the abbreviated version not S is true exactly when S is false.

Note that if S is a statement, it’s either true or false; in either case, we know what truth value \sim S has. So \sim S is by definition a statement. Also note the word exactly, which modifies when.

Proposition 1. \sim \sim S is true exactly when S is true.

Proof. There are only two kinds of statements S, namely true and false.

If S is false, then \sim S is true (this is the definition of \sim S). But the only (that’s the exactly in the definition of \sim) way for \sim \sim S to be true would be if \sim S were false; since \sim S is true, we know \sim\sim S is false. So in this situation, S and \sim\sim S are both false.

If S is true, then \sim S is false (remember, \sim S is only true when S is false). So \sim \sim S is true. So here again, S and \sim \sim S agree with one another.

In both cases, we’ve seen that S and \sim \sim S agree. Thus when S is true, \sim \sim S is true; and this is the only way for \sim \sim S to be true. \Box.

Notice that \sim \sim S is a different formula from S. For example, if S is I wear a plaid shirt every day, then

\sim S is It is not the case that I wear a plaid shirt every day and
\sim \sim S is It is not the case that it is not the case that I wear a plaid shirt every day.

But of course \sim \sim S and S are the same insofar as truth goes. One might say they mean the same thing.

To make better formal sense of the distinction between being the same statement and merely being statements that mean the same thing, we need the following definition:

Definition. A propositional formula or propositional form is a string of logical connectives and variables, so that when each of the variables is substituted with a statement, the result is a statement.

For example, \sim Q is a propositional formula because if we supply a statement in place of Q, we obtain a statement.

Definition. Two propositional forms are equivalent if, whenever we substitute the same statements in for their variables, we obtain statements with the same truth values.

Armed with this definition, we can rewrite Proposition 1 in a different way:

Restatement of Proposition 1. Q and \sim\sim Q are equivalent.

denials, useful and otherwise

Definition. A formula equivalent to \sim P is called a denial of P. If we plug a statement in to the variable P, we obtain a denial of that statement.

E.g. \sim\sim\sim Q and \sim\sim\sim\sim\sim Q are denials of Q. \sim\sim T is a denial of \sim T.

E.g. A denial of Andrew Cooper is from Texas is It is not the case that Andrew Cooper is from  Texas.
Another denial is Andrew Cooper is not from Texas.
Another denial is Andrew Cooper is either from someplace other than Texas, or he is not from anyplace in particular, a drifter if you will, rootless, without a home.

These examples show that there are many different denials of any given formula or statement.

One question I want you to ask, and to keep asking is: is a given formulation of a statement useful to me? Utility is in the eye of the beholder, so I won’t give you a formal definition of what I mean when I say useful denial. But I’ll say this: merely attaching It is not the case that… to the beginning of a statement probably will not yield any insight.

You might be asking yourself: why should I expect that formulating a denial would yield any insight, anyway? Here’s why, and it’s a very important less in thinking that I hope you take away from this course into the rest of your life beyond mathematics. Statements are, by definition, either true or false (and not both). So, when we are faced with a statement we don’t understand (or wish to understand better, or wish to prove), we usually ask questions like

  • What does this statement mean?
  • If this statement were true, what else would be true?
  • When have I encountered similar (or just similar-looking) statements in the past?

These are great questions, but they don’t always get us where we need to go. Sometimes they can even lead us astray. Since we know that the statement in question is either true or false, we could as well ask about it:

  • What would it mean for this statement to be false?

That is, we could formulate a denial of the statement. If we articulate all the ways the statement could be false, then we have also articulated what it means for the statement to be true: that’s just everything not on our list.

I call this method what-if-not thinking, and we’re going to use it a lot. But it depends, critically, on being able to formulate denials precisely and accurately. (Don’t worry, we’ll develop lots of practice.)

 

truth tables

Definitions like that of \sim are kind of hard to read, so let’s record them symbolically. We can think of \sim P as being like a function: you tell it the truth value of P, and it tells you the truth value of \sim P. So, just like you first did in some long-ago algebra class, we can record the values in a table. We call such a table a truth table. The truth table for \sim looks like this:

P \sim P
T F
F T

We can make a truth table for any formula; here’s the truth table for \sim\sim P:

P \sim\sim P
T T
F F

Observe that we always list the input values (the first column) in the same order.

It’s pretty clear that Two formulae are equivalent if the output columns of their truth tables are the same.

 

“and”

not was nice, but it only acts on one statement or formula. (We call such operations unary, from the Latin unus “one”.) Let’s get some binary operations: operations which combine two statements or formulae. We’ll start with the word and.

Before reading any further, make sure you’ve done the pre-meeting exercise: read the dictionary.com entry on the word and and see if it would help you understand what the word meant, if you didn’t already know. Try this definition also.

Instead of giving a wordy definition, I’ll just give the truth table for “and”. The symbol we use is \wedge. Since there are two inputs, each of which has two possible truth values, there are four possible inputs:

P Q P\wedge Q
T T T 1
T F F 2
F T F 3
F F F 4

Because we’re going to use this table rather than just look at it, I’ve given numbers to the rows.

Let’s play around a bit with this. What’s Q\wedge P? We’ll make a truth table. In order to compare it with the truth table for P\wedge Q, we need to list the inputs in the same order.

P Q Q\wedge P
T T T 1
T F F 3
F T F 2
F F F 4

 

Look carefully at the row labels. In order to populate row 2 of the Q\wedge P  table, we have to look at row 3 of the P\wedge Q table — this row is the “FALSE and TRUE” row.

We can conclude from this truth table that

Proposition. P\wedge Q and Q\wedge P are equivalent formulae.

Or, somewhat more pithily, we say

Restatement of Proposition. \wedge is commutative.

While this proposition may not surprise you, it does indicate a slight difference from the  ordinary-English word and.

Let’s try something else out, too: what about (P\wedge Q)\wedge R? This time we’re have three inputs, each of which has two possible truth values, for a total of 2\times 2\times 2=8 possible input truth values:

P Q R P\wedge Q (P\wedge Q)\wedge R
T T T T T 1
F F 2
F T F F 3
F F 4
F T T F F 3
F F 4
F T F F 3
F F 4

Here I’ve done two tricks: first, instead of writing so many Ts and Fs, I combined some rows in the P and Q columns to make the table easier to read. Second, I wrote down the intermediate step of computing P\wedge Q as a separate column. The last column records which row of the truth table for \wedge I used to go combine the values in the third and fourth columns to get the truth value in the last column.

Exercise. Make a truth table for P\wedge(Q\wedge R).

Proposition. (P\wedge Q)\wedge R is equivalent to P\wedge(Q\wedge R).

The pithy way to say this is

Restatement of Proposition. \wedge is associative.

Finally, let’s do two truth table computations with \sim and \wedge:

Exercise. Make truth tables for P\wedge (\sim P) and \sim\left( (\sim P)\wedge P\right). Before beginning this, think hard about how many rows and how many columns your truth table will require. Then see if you notice anything interesting.

Tautologies and Contradictions

The result of the previous exercise will leave us with the need for the following definition:

Definition. A formula which always has a truth value of T, no matter what inputs it takes, is called a tautology. A formula which always has a truth value of F, no matter what inputs it takes, is called a contradiction.

If we’re thinking of propositional formulae as functions, then tautologies and contradictions are the constants. (There are only two constant functions, because statements can only be true or false (and not both).)

The philosopher’s version of this definition goes something like A tautology is a sentence that is true in virtue of its form. and A contradiction is a sentence that is false in virtue of its form., the point being that neither a tautology nor a contradiction can contain much in the way of meaningful content, because its form gets in the way. But that’s all a bit above our heads.

Shades of Meaning

Here’s a shocking claim:

and and but mean the same thing.

What do I mean by this? Consider the two statements:

  1. I have a dog and he weighs twelve pounds.
  2. I have a dog but he weighs twelve pounds.

In terms of the facts on the ground, what do we know in situation 1? That I have a dog. That the dog weighs twelve pounds. What do we know if situation 2? Exactly the same information!

So what’s different? Presumably, if I’m saying statement 2, it’s because I’m vaguely embarrassed to have such a small dog (sorry, Mugzy). That is, the difference between and and but lies in how the speaker feels about the circumstances. And because that’s not something that can be true or false, our logical framework just doesn’t care about it.

You might think this is a bug, but I see it as a feature. (Perhaps better to say: you might see this as a bug, and I see it as a feature.) It will allow us to subtly influence our reader’s perception — and our own perception — in ways that may make our written proofs clearer and easier to understand.

A neat thinking trick you can deploy to help make sure you aren’t being unduly influenced (say, when you’re watching talking heads): every time someone says but, just repeat what they said with an and instead. And make sure you don’t use but when you mean and.

Logic: Overview

Standard post by ancoop on June 4, 2018
Comments are off for this post

Quando orientur controversiae, non magis disputatione opus erit inter duos philosophos, quam inter duos Computistas. Sufficiet enim calamos in manus sumere sedereque ad abacos, et sibi mutuo dicere:

Calculemus!

When controversies arise, there will be no more need for debates between two philosophers than there is between two computers. It will be enough for them to take their pencils into their hands, sit at their abaci, and say to each other:

Let’s compute!

Gottfried Leibniz

 

Logic is the business of writing down our reasoning in such a way that anyone who comes along can think what we thought, in a way that unambiguously compels assent. It is a useful tool across mathematics (why we learn it as part of this course) and a field of mathematical study in its own right, with applications to computer science and engineering, linguistics, and philosophy.

In some sense, logic is just a way of encoding ordinary argumentation. Though some facts about logic seem counterintuitive, we will see that, once we decide that we care about whether sentences are true or false, and that a few basic operations behave the same way they do in ordinary rhetoric, there is really no other option. We must accept the counterintuitive results along with the intuitive ones, and reject some of our intuitions. This theme of being able to formalize some, but not all, of our intuitions is a common one across mathematics.

What we’ll learn in this class is only a piece of “propositional logic” and “predicate logic”, which in turn is only a piece of the branch of mathematics that is logic.

Besides the statement-based theory we’ll learn, logicians also study other, nonstandard systems of reasoning, which are just as beautiful and interesting as what we’ll deal with. But in some way those other systems all differ from the basic way that people construct and interpret arguments.

Don’t worry, the logicians will forgive us if we use the word “logic” just for a slice of their very deep and beautiful field.

Perhaps the important thing about the logic we’ll learn (so-called predicate logic) is its computational flavor. That is, if we write out an argument in terms of logical symbols, and if we are good enough at logical computations, we can decide whether the argument is right or wrong. We can be sure (as sure as we are that the only solution of x^2-6x+9=0 is x=3) that the argument is correct.

Overview of Logic

  • Statements (this page). The basic unit of logic is the statement or proposition.
  • Not & And. Statements can be made more interesting by combining them. We can write propositional formulae to discover useful facts about how statements relate to each other in general.
  • Or. Another little word.
  • Conditionals. If-then statements are the bread and butter of mathematical proofs.
  • Order of Logical Operations. Just like arithmetic operations, the order of logical operations matters.
  • Logic in Proofs. Simple chains of statements can be used to make deductions and structure proofs.
  • Quantifiers. All about “for all” and “there is”.
  • Uniqueness. We all like to feel special. But “unique” is something else!
  • A Case Study: Divisibility. An illustration of how logic comes into a familiar idea.
  • Watch Out! Some common pitfalls to avoid.

Statements

Logic deals with statements.

Definition. A statement is a sentence which is either true or false, and not both.

This isn’t a philosophy course, so we won’t concern ourselves with what it means for something to be true. I’ll refer to that idea as capital-T Truth. We’re interested in the more mundane concept of little-t truth, which we don’t need to know much about, other than it comes in two flavors (true and false), and we’re going to be dealing with sentences which have to be one and can’t be both.

Being a statement imposes two kinds of constraints:

  • a form or grammatical constraint: the statement must be a sentence. In fact it should be a declarative sentence with a subject and a verb.
  • a meaning or semantic constraint: the statement must be either true or false, and not both.

Practice Question. Which of the following are statements? For each non-statement, explain why it’s a nonstatement. For each statement, explain how you know it’s a statement.

  1. The only solution of x^2-6x+9=0 is x=3
  2. \frac{9}{3}
  3. The improper Riemann integral of a function might exist without the function being integrable.
  4. 2^3 + 3^2 = 17
  5. What can we say about the sequence \langle f_n\rangle?
  6. 2^x + x^2 = 17
  7. Foreign cars are better than domestic cars.
  8. Euclid was left-handed.
  9. The function x\mapsto\Phi(x) is harmonic for x\neq 0.
  10. This sentence is false.

a: This is a statement (it’s true)
b: This is not a statement (it’s not a sentence)
c: This is a statement.
d: This is a statement (it’s true)
e: This is not a statement (it’s a sentence, but not a declarative sentence)
f: This is not a statement.
g: This is not a statement.
h: This is a statement.
i: This is not a statement.

We’re ready for our first proof!

Theorem. The sentence This sentence is false is not a statement.

Proof. Let’s denote the sentence This sentence is false by the letter S.

If S were a statement, then S would be either true or false.

If S were true, then by the meaning of S we could conclude that S would have to be false. So S would be both true and false. (This, however, is not allowed for statements.) So S can’t be true.

If S were false, then by the meaning of S we could conclude that S would have to be true. So S would be both false and true. (This, however, is not allowed for statements.) So S can’t be false.

We’ve just established that S cannot be a true statement, and that S cannot be a false statement. But those are the only two types of statements. So S must not be a statement at all. \Box

Let’s dwell on the proof we just saw.

  • First, notice that the claim being proved is set apart from the text clearly, so that everyone knows what we are doing: we are proving that This sentence is false is not a statement.
  • Next, we have indicated where the proof itself starts (with the boldface word Proof). This may seem a bit over-the-top, but it’s clear anyway.
  • We’ve also given a clear indication of when the proof ends: we say so explicitly (“So S must not be a statement at all.”) and give a special symbol: \Box.
  • One good trick to make this proof more readable was the first line of the proof: we replaced This sentence is false with the letter S. We didn’t have to do this, but it saved us some headaches from reading things like
    “If This sentence is false were false, then by the meaning of This sentence is false, we could conclude that This sentence is false would have to be true.”
  • The clarity of all of the above was helped by formatting: the use of symbols, italics, boldface, and indentation.

Finally, I want to point out that this, our first proof, was also our first reductio ad absurdum or proof by contradiction. We’ll talk more about that later, but notice that we started by supposing the opposite of what we wanted to establish: we wanted to show S was not a statement, but we assumed S was a statement to begin with. Then we painted ourselves into a logical corner. That’s the essence of a reductio ad absurdum.

 

What the sentence This sentence is false shows is that being a statement has to do with both grammar (form) and semantics (meaning): the very similar sentence This sentence appears in black type is definitely a statement, even though its form is the same.

Skip to toolbar