My Glimpse Inside The Ivory Tower Of Mathematics

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

If you have any comments on this book, please visit https://groups.google.com/forum/#!forum/glimpse-of-mathematics.

The source code for the book is at https://github.com/tlocke/maths.

This book is available in the following formats:

In the realm of Propositional Logic, I found that they deal with things that are either true or false. In the English language, sentences that are either true or false are known as statements. Here are some sentences together with explanations of whether they are statements or not:

This is a question, so not a statement.

Yay, an actual statement! It’s a sentence that is either true or false.

This isn’t true or false, it sounds like someone admonishing somebody. Not a statement.

Yes, a statement.

This sounds like a statement, but according to those logicians in the ivory tower it doesn’t count because it relies on knowing who ‘he’ is.

This is a proverb, not a statement.

I’ve got this nagging doubt in my mind. Most statements I can think of aren’t totally ambiguous. Take the ‘Elephants have four legs’ example. Maybe there’s a three legged elephant in existence, perhaps one in a zoo got gangrene or something and had to have a leg amputated…​ Nevertheless, let’s suspend our disbelief and imagine all those perfect statements.

At that point, Alfred Tarski spoke up, ‘What about this then?’.

Well, I’m not sure what to do. It seems like a statement, but if it’s true then it’s false, and if it’s false then it’s true! Okay, let’s get round it by saying that this isn’t really a statement. What do you think Taski? But Tarski’s mind was on other things…​

It seems that the next thing the logicians do is string together simple statements to make compound statements. So two simple statements might be:

And a compound statement formed from these two simple statements is:

We’ve joined the two simple statements together with the logical conective ‘and’. This compound statement is true if both the simple statements are true, otherwise it is false. Another compound statement we can make from our two simple statements is:

Here’s we’ve joined the two simple statements together with the logical connective ‘or’. This compound statment is false if both simple statements are false, otherwise it’s true.

Rather than always writing statements out in full, those work-shy logicians write them in a shorthand. First they label each simple statement with a capital letter of the alphabet. They call the label an atomic formula. Then they use funny symbols to denote logical connectives. Here’s a table of the symbols used for logical connectives:

So for the compound statement:

the two simple statements can have the atomic formulas P and Q:

and the compound statement can be written as the compound formula:

Now that we’ve said what P and Q stand for we can take this compound statement:

and write it using the atomic formulas to give the compound formula:

You’ll notice that the formulas have brackets round them. This is useful for later on when formulas get more complicated.

Let’s say that Abelard does like coffee, but doesn’t like cake. Then:

Then using our common sense reasoning we know that it isn’t true that Abelard likes coffee and likes cake, so this is written formally as:

and also we know that it is true that either Abelard likes coffee or Abelard likes cake and this is written formally as:

This process of taking a formula and substituting in the true or false values and working out if the formula as a whole is true or false, they call evaluating the formula for particular values.

Here’s an ambiguous compound statement:

Assigning labels to the simple statements:

the compound statement can be transated into two formulas with different meanings:

‘Hold on, you blithely said that these two formulas have different meanings, but how do you know that?’. Good point, erm, what would Bertrand Russell do? Bear with me. Okay, using our geography knowledge we know that P is true, Q is false and R is false and so evaluating the first formula gives:

and the second formula evaluates to:

So when substituting in the same values, the first formula evaluates to false and the second evaluates to true, and so the two formulas are different.

I think what the Ivory Tower is teaching me here is that even though I started out translating from English (what they call a natural language) to formulas (what they call a formal language), it turns out that as well as being shorter, formulas are unambiguous. It seems to me that the English statements are just a jumping off point, and formulas are much better at describing this mathematical realm. W00t, I said, ‘mathematical realm’!!!

Say you’ve got a formula:

To logicians, an interpretation (also called a truth assignment) is the assignment of true or false to P and Q. So one interpretation is:

and another is:

so for a compound formula with two atomic formulas, there are four possible interpretations:

and to make it easier to write they use T for true and F for false:

A truth table. A medieval device for extracting a confession? No, a mathematical device for showing if a formula is true or false for every possible interpretation. The truth table for (P ∧ Q) is:

so what we’ve done is written a row for each interpretation of P and Q, and then in the final column we’ve put the result of evaluating (P ∧ Q). The truth table for (P ∨ Q) is:

You can use a truth table to show that (P ∧ Q) means the same as (Q ∧ P):

For each interpretation, the last two columns are the same, and so (P ∧ Q) means the same as (Q ∧ P).

There’s another logical connective called not, which has the symbol ¬ and the truth table:

Usually the brackets are omitted for ¬, so when you see:

it’s taken to mean:

Anyway, let us cast it loose amongst the other functions and employ the truth table to see what results. Picking a formula at random, let’s try:

which gives the truth table:

Let us now extract a full confession from:

which gives the truth table:

One other thing, the first two logical connectives we encountered (∧ and ∨) both acted on two formulas, and so they’re known as binary connectives. The ¬ connective acts on one formula and so is called a unary connective.

‘Sir, I demand satisfaction!’. Yeah, we’re not in Poldark, they don’t watch that in their Ivory Tower. Why waste time on TV dramas when you could be doing maths?

An interpretation satisfies a formula if it is true under that interpretation. An example you say? An example? Okay, okay, you started off humble and now you’re making demands. I just feel you need to take a moment to think about your attitude to this whole thing.

Under the interpretation:

the formula:

evaluates to:

since it’s true, we can say that this interpretation satisfies this formula. ‘Could you show me another example please?’, ‘Certainly dear reader’. Under the interpretation:

the formula:

evaluates to:

and so this interpretation satisfies this formula.

This is the opposite of satisfaction. An interpretation falsifies a formula if it is false under that interpretation. Under the interpretation:

the formula:

evaluates to:

since it’s false, we can say that this interpretation falsifies this formula. Under the interpretation:

the formula:

evaluates to:

and so this interpretation satisfies this formula.

The formula:

has the truth table:

which shows that every possible interpretation satisfies the formula. In the Tower such a formula is called a valid formula.

The formula:

has the truth table:

which shows that every possible interpretation falsifies the formula. In the Tower such a formula is called an unsatisfiable formula.

A formula that is neither valid nor unsatisfiable is said to be contingent. For example the formula:

has the truth table:

which shows that the formula is neither valid not unsatisfiable and so it is contingent. Another way of putting it is to say that a formula is contingent if it is both satisfiable and falsifiable.

There’s another binary connective called implies that has the truth table:

Take the two simple statements:

Joining the two with an implication could give the compound statement:

If Abelard really is at the cafe and the cafe really is open, then this compound statement is true. If Abelard isn’t at the cafe, then whether or not the cafe is open, the compound statement is still true (another way of putting it is to say that if Abelard is not at the cafe, then this is still consistent with with the statement that ‘Abelard is at the cafe only when the cafe is open’). The only time the compound statement is false is if Abelard is at the cafe but the cafe is not open.

There are a few different ways that ‘implies’ occurs in English. The statement:

could be written in these alternative ways:

Here’s an example of → in action. The formula:

Has the truth table:

Another example; the truth table for (Q → (P ∧ ¬Q)) is:

The biconditional connective is a binary connective with the truth table:

Translating from English to a formula, the sentence:

is written:

which of course is true. An example that is false is:

which is written:

If two formulas are an identity (also called logically equivalent), then they mean the same under all interpretations. In other words if two formulas are an identity, then the formula formed by joining them with the ↔ connective will be valid. For example, if the pair of formulas:

are an identity, then:

will be valid. Its truth table is:

and so indeed we can say that this pair of formulas is an identity. The symbol for identity is ≡, and so we can write the identity as:

(A → B) ≡ (¬A ∨ B)

The two formulas in an identity can be substituted for each other in other formulas, without changing the meaning of those other formulas. The commonly used identities have their own names. The identity that we’ve just found:

is called the material implication identity.

A special type of identity that some binary connectives have is commutativity. The connective ∧ is commutative which means that:

This identity is called conjunction commutativity. Not all binary connectives are commutative though. For example the pair of formulas:

is not an identity because:

is not a valid formula, and so → is not commutative. Here’s a table showing the binary functions, and whether they’re commutative or not, and if they are, giving the name of the associated identity.

Another type of identity that some binary connectives have is associativity. The ∧ connective is associative, which means:

because the formula:

is valid. So if you’ve got three formulas joined by ∧, it doesn’t make any difference if the first two are evaluated first, or the last two. This identity is called conjunction associativity. Here’s a table showing all the binary connectives, and whether they’re associative or not, and if they are, giving the name of the identity:

Another ‘itivity’. Here are the distributivity identities:

Here’s the pattern as I see it. If there are two binary connectives y and z, then if y distributes over z then:

‘Hey, Tony’, Benjamin Peirce said as he tapped me on the knee and leaned over confidentially, ‘there’s another type of identity that I call idempotence’. The ∧ connective is idempotent because:

and the ∨ connective is idempotent because:

but → is not idempotent. So I think what Peirce was telling me is that a connective is idempotent if, when it joins a formula with itself, you end up with the formula again. Like those tricks where you end up with the number you first thought of. Ben showed me that ∨ is idempotent by doing the following:

is valid, as shown by truth table:

and → is not idempotent because:

is not valid, as shown by the truth table:

Here’s a table showing whether each function is idempotent or not.

The unary connective ¬ is idempotent because:

is valid.

I found in the Tower that Mathematicians are often good at music too. De Morgan was a flautist. I’ve got no musical ability. De Morgan’s Laws are a couple of identities:

and:

Some say they’re obvious. Do you find them obvious? I don’t.

‘What does that entail, lol!’, yeah thanks for that. In English you might have some premises leading to a conclusion such as:

To convert the premises and conclusion from English into logical formulas, we first of all define the atomic formulas:

So the premises and conclusion becomes:

Now, do the premises entail the conclusion? In other words, for every interpretation where the premises are true, is the conclusion true? If the premises entail the conclusion, the following formula must be valid:

In effect we’ve joined the premises together with ∧ and then added on the conclusion with an → to get the formula. Bring on the table of truth!

The last column is always true, so the formula is valid, so the premises do entail the conclusion. Logicians denote an entailment with the ⊨ symbol. So the entailment we’ve just found can be written:

Here’s another example of some premises and a conclusion in English:

In logic symbols the argument is:

It’s an entailment if:

is valid. Doing a giant truth table:

Shows that the formula is valid and so we can write that:

Writing down formulas involves writing a lot of parentheses. There are a couple of conventions for reducing the number of parentheses you have to write, while still keeping a formula unambiguous. I’ve already discovered that logicians write:

to mean:

They also assume that if brackets aren’t explicitly written, then they they implicity exist from left to right. For example the following formula has no explicit parentheses:

But the implied formula is:

A set is a collection of distinct elements, where there’s no order, and duplicates aren’t allowed. Some example are:

Written out in set notation, these look like:

When the set includes an elipsis (…​) at one end or both, it denotes an infinite series. An ellipsis in the middle of a set of elements is used to save writing out all the items of an obvious set.

The terms finite set and infinite set mean what you think they mean, a set with a finite number of elements and a set with an infinite number of elements.

Some sets of numbers are common enough to have their own names and symbols:

If two sets have exactly the same elements in them, then they are equal. In set notation, if sets A and B are equal, set theorists write:

if A and B aren’t equal they write:

Let’s say we’ve got two sets S and T:

S and T are equal because all that matters for identity is that the two sets have the same elements in them. So we can write:

Let’s make up two sets A and B:

Sets don’t have any duplicates so the two sets A and B are equal and we can write:

‘Hey, you said that sets can’t have duplicates, but then you wrote {1, 2, 2}. What gives?’. When you write {1, 2, 2}, you’re describing a set with two elements, 1 and 2. So {1, 2, 2} = {1, 2}. So these are two ways of describing the same set. ‘Well, okay I suppose. I have to say I’m not entirely convinced, but carry on for now’.

And another thing, it’s the convention for sets to be represented by capital letters, and elements to represented by lower case letters.

I learnt from Common Sets Of Numbers that Z stands for the set of integers. So the number 1 is an element of Z. Or equivalently the number 1 is a member of Z, or simply 1 is in Z. Set theorists write this as:

The number 1.5 is not in Z. They write this as:

Up to this point I’d seen sets specified in three ways:

Then I came across a method of defining a set by specifying a rule in a mathematical notation called set builder notation. For example:

which specifies the set:

This rule is read as, ‘the set consists of all values of x such that x is an integer and x is greater than 7.’ The condition on the right hand side of the bar re-uses the connectives from Propositional Logic. Another example of set builder notation is:

which specifies the set:

This rule is read as, ‘the set consists of all values of x such that x is a real number and x equals x squared.’

Let’s say we’re talking about a set of books:

U = {Emma by Jane Austen, Anna Karenina by Leo Tolstoy, Crime and Punishment by Fyodor Dostoevsky, Use of Weapons by Ian Banks, Wuthering Heights by Charlotte Bronte, The New Men by C. P. Snow}

Since we’re only considering this set for the time being, it’s called the universal set. In different situations we can specify a different universal set. For example if we’re only talking about natural numbers, then that would be our universal set. A Venn diagram of our universal set:

For two sets A and B, A is a subset of B if and only if every element of A is a member of B. The set theorist will write:

Going back to our universal set of books, let’s define two sets:

then:

written as a Venn diagram:

In other words we’re saying that for the books in our univeral set, those written by female authors are a subset of those written before the 20th century.

A theorem is a mathematical statement that has been proven to be true. It’s a theorem that for any set S you can say that:

A proof is an argument made up of small, incontrovertible steps that lead to the theorem. A proof that S ⊆ S is:

Another theorem that I came across says that for any set S:

A proof of ∅ ⊆ S is:

For two sets A and B, A is a proper subset of B if and only if A ⊆ B and A ≠ B. Set theorists write:

With the universal set of books and the two sets:

then:

drawn as a Venn diagram:

The set that you get from adding two sets together is the union of the the two sets. As I’ve come to expect, there’s a special symbol for this operation, ∪. Going back to our example with the universal set of books we could define two sets

then:

For two sets A and B, the intersection of A and B is the set of elements that and in both A and B. The symbol for this operation is ∩. Going back to the example with the universal set of books we could define two sets:

then:

Cardinality is the size of a set. For a finite set this is the number of elements of the set. So for:

the cardinality of D is 7. Set theorists write this as:

The power set of a set S is the set of all the subsets of S. The power set of S is written:

Take for example the set of primary colours:

The subsets of C are:

so the power set is:

Set theorists have shown that if a set S has cardinality |S| = n, then:

Looking at the cardinalities of the power sets of sets with cardinality 0, 1, 2, 3 we get:

I find that writing this out in a table makes it easier to spot what’s going on:

So I saw that the next S is the previous S with the new element added. Also, the next 𝓟(S) is all the sets in the previous 𝓟(S) and also all the sets in the previous 𝓟(S) with the new element added to each one.

So the theorem |𝓟(S)| = 2ⁿ is working for all the cardinalities of S we’ve tried. From wandering round in the Ivory Tower, I found that in maths you have to have things nailed down inescapably, it’s no good to just say that it looks like it works after a few tries. That’s the purpose of a proof, to give a water-tight argument for why a mathematical statement is true.

Here’s a proof of |𝓟(S)| = 2ⁿ:

I’m told that the proof we just did of |𝓟(S)| = 2ⁿ was an example of proof by induction. I tried to find out the underlying form of proof by induction and it turns out to have three parts:

Say we’ve got a mathematical statment P that depends on n ∈ N. It’s the purpose of the proof to show that P is true for all values of n.

Here’s another example of proof by induction. Say we’ve got a set:

Our proposition P is:

Query: Is this similar to recursion in say Haskell?

Sometimes a mathematician will come up with statement that she thinks is true, a conjecture in other words, then another mathematician could disprove the conjecture with a counterexample. A conjecture might be:

Another mathematician can say, ‘that can’t be true, what about the set {1}, that has cardinality one?’. Thus the conjecture has been disproved by counterexample.

Set difference

Set Intersection ∩.

On your first day as an assistant librarian, you’re asked to compile a book that is a catalogue of all of the books in the library that don’t mention themselves. Eventually you present the chief librarian with your completed catalogue. The chief librarian asks, ‘Does the catalogue mention the catalogue?’. Well no, you answer…​but then if the catalogue doesn’t mention itself, then it should be in the catalogue, in which case it shouldn’t…​

You’ve become a victim of Russell’s Paradox, and you’re fired. Lol!

In terms of sets, Russell’s Paradox is asking, what’s the set of all sets that don’t have themselves as an element? That set doesn’t exist.

So, that’s solved it in maths language, but how should you have answered the chief librarian? Well, you could say that the book (set) he’s asked for can’t exist. But you can write a book (set), which has the same contents as has been requested, except that it doesn’t contain itself.

Curry’s Paradox is:

Do you owe me a million pounds then? Anyway, they told me that there’s an equivalent paradox for sets.

They also told me that there’s a paradox with the set of all sets, so that doesn’t exist either. As it seems to me, a paradox is something that is clearly incorrect, but you can’t see the flaw in the argument. Of course, all paradoxes can be resolved, and the resolution deepens one’s understanding. ‘Ooh, hark at him pontificating on the philosophy of it all!!’ Okay, okay.

I’m not quite sure why yet, but in maths land they talk about sets of formulas, calling them theories and often giving them Greek capital letters! So they say:

Also, if ψ is a formula then:

stands for: