A little paradox

This post is intended as a footnote to one that I wrote a couple of years ago about the meaning of “implies” in mathematics, which was part of a series of posts designed as an introduction to certain aspects of university mathematics.

If you are reasonably comfortable with the kind of basic logic needed in an undergraduate course, then you may enjoy trying to find the flaw in the following argument, which must have a flaw, since I’m going to prove a general statement and then give a counterexample to it. If you find the exercise extremely easy, then you may prefer to hold back so that others who find it harder will have a chance to think about it. Or perhaps I should just say that if you don’t find it easy, then I think it would be a good exercise to think about it for a while before looking at other people’s suggested solutions.

Basic logic — summary

Here is the promised post that I hope will be easier to refer back to than the much longer posts I’ve written on individual aspects of basic logic. What I imagine people doing is reading the longer posts and using this one to jog their memories later. If you can think of any important points that I made in earlier posts and have forgotten to mention here, I’d be grateful to know of them.

Once again, the main topics dealt with were these.

Logical connectives. AND, OR, NOT, IMPLIES (or in symbols, ).

Quantifiers. “for every” and “there exists” (or in symbols, and ).

Relationships between statements. Negation, converse, contrapositive.

Basic logic — tips for handling variables

Roughly speaking, a variable is any letter you use to stand for an unknown object of a certain type. For example, if you write then and are variables. If you write, “Let be a subset of ” then is a variable (it is an unknown set of a certain kind) whereas isn’t (it’s the name we give to the set of all positive integers). I suppose the definition I’ve just given isn’t quite perfect, since if I asked you to solve the simultaneous equations and then one would normally call and variables even though their values are completely determined by the equations. Though even then one could say that they started out as “unknown”.

Just in case I’ve gone and confused the issue, let me try to clear it up instantly. It would be quite normal to say something like this: “Let and be two real numbers. Suppose that they satisfy the equations and Determine the values of and ” It is then reasonable to call them variables, because when I started discussing them I gave no information about them whatever. I then went on to specify some relationships between and and it so happened that from those relationships it was possible to deduce the exact values of and

Basic logic — relationships between statements — converses and contrapositives

Converses.

What is the relationship between the following two statements?

1. If is 1 or a prime number, then is divisible by .

2. If is divisible by then is 1 or a prime number.

At first sight, this doesn’t look a very difficult question: the first statement is of the form and the second is of the form We say that the second statement is the converse of the first. (Note that the first statement is also the converse of the second.)

Basic logic — relationships between statements — negation

I want to talk in the next couple of posts about transformations that can be applied to a statement. The three transformations I plan to discuss are forming the negation, the converse, and the contrapositive. For those who like an abstract definition to keep them going, let me quickly give the three relevant ones here. If is a statement, then “not “, sometimes written in symbolic form as is its negation. If has the form then the converse of is the statement And finally, again if has the form the contrapositive is the statement

If that was too abstract for you, then maybe you’ll be happier to pick the idea up by looking at some examples. (I myself find that easier. I like to see enough examples for the abstract concept to become obvious. But others seem to prefer the abstract concept in order to understand the point of the examples. In this post I am indulging those kinds of people.)

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.