Basic logic — quantifiers

When I started writing about basic logic, I thought I was going to do the whole lot in one post. I’m quite taken aback by how long it has taken me just to deal with AND, OR, NOT and IMPLIES, because I thought that connectives were the easy part.

Anyway, I’ve finally got on to quantifiers, which are ubiquitous in advanced mathematics and which often cause difficulty to those beginning a university course. A linguist would say that there are many quantifiers, but in mathematics we normally make do with just two, namely “for all” and “there exists”, which are often written using the symbols and (If it offends you that the A of “all” is reflected in a horizontal axis and the E of “exists” is reflected in a vertical axis, then help is at hand: they are both obtained by means of a half turn.)

Let me begin this discussion with a list of mathematical definitions that involve quantifiers. Some will be familiar to you, and others less so.

Basic logic — connectives — IMPLIES

I have discussed how the mathematical meanings of the words “and”, “or” and “not” are not quite identical to their ordinary meanings. This is also true of the word “implies”, but rather more so. In fact, unravelling precisely what mathematicians mean by this word is a sufficiently complicated task that I have just decided to jettison an entire post on the subject and start all over again. (Roughly speaking what happened was that I wrote something, wasn’t happy with it for a number of reasons, made several fairly substantial changes, and ended up with something that simply wasn’t what I now feel like writing after having thought quite a bit more about what I want to say. The straw that broke the camel’s back was a comment by Daniel Hill in which he pointed out that “implies” wasn’t, strictly speaking, a connective at all.

I’ll mention a number of fairly subtle distinctions in this post, and you may find that you can’t hold them all in your head. If so, don’t worry about it too much, because you can afford to blur most of the distinctions. There’s just one that is particularly important, which I’ll draw attention to when we get to it.

Basic logic — connectives — NOT

I realized after writing the title of this post that it might look as though I was saying, “I’m going to discuss connectives … not!” Well, that’s not what I meant, since “not” is a connective and I’m about to discuss it.

NOT.

If you don’t know how to negate a mathematical statement, then you won’t be able to do serious mathematics. It’s as simple as that. So how does the mathematical meaning of the word “not” differ from the ordinary meaning? To get an idea, let’s consider the following sentences.

“We are not amused.”

“He is not a happy man.”

“That was not a very clever thing to do.”

“ is not a perfect square.”

“ is an element of the set , but it is not the largest element of ”

“ is not a subset of .”

Basic logic — connectives — AND and OR

In my introductory post I talked about fake difficulties. It will take some time and several more posts before I can say what I really mean by that notion, but this post will get me a bit closer. So far I have mentioned that if you can’t solve a problem because you haven’t been bothered to look up what the words mean, then your difficulties are not genuine. A more interesting category of fake difficulties is a failure to grasp a few basic logical principles. I call this a fake difficulty even though for some people it is genuinely difficult; the reason I do so is that when mathematicians consider a problem to be hard, it is not for basic logical reasons. To put that another way, with a little bit of practice one can make basic logical deductions completely mechanically, and it is absolutely essential to learn how to do so. It is a simple skill (which is not to say that no work is needed), and it underlies all mathematical reasoning. Trying to understand university-level mathematics without a secure grasp of basic logic is like trying to learn long multiplication without knowing your tables — only a lot harder.

What am I talking about when I use the phrase “basic logic”? I am talking about having a good understanding of the following.

Logical connectives. The main ones are “and”, “or”, “not” and “implies”.

Quantifiers. The phrases “for all” and “there exists” come up a lot in mathematics and you have to be capable of dealing with sentences like this: for every there exists such that for every

Relationships between statements. Given a statement, you should have no trouble forming its negation, its converse and its contrapositive. Of course, for that you need to know what those three things are.

Welcome to the Cambridge Mathematical Tripos

Introduction.

This is the first of what I hope will be a long series of posts aimed at providing back-up to first-year Cambridge mathematicians. This may seem a strange thing to do, since the Cambridge system of supervisions (classes taught on a one-to-two basis, usually discussing questions set by lecturers) already provides an excellent back-up to lectures. Do Cambridge undergraduates, who already have closer attention than in any other university I know about, really need even more help?

Well, perhaps they are lucky enough to need it less than mathematicians anywhere else, but there are several facts that convince me that even more can be done than is done already. Let me list a few of them.