Press the right key for the next slide (or swipe left)

also ...

Press the left key to go backwards (or swipe right)

Press n to toggle whether notes are shown (no equivalent if you don't have a keyboard)

Press m or double tap to see a menu of slides

\title {Logic I \\ Logic (PH133)}

\maketitle

\def \ititle {Logic (PH133)}

\def \isubtitle {Lecture 7}

\begin{center}

{\Large

\textbf{\ititle}: \isubtitle

}

\iemail %

\end{center}

Readings refer to sections of the course textbook, \emph{Language, Proof and Logic}.

\section{Watch Out, Here Come Multiple Quantifiers}

\emph{Reading:} §11.1

\section{Watch Out, Here Come Multiple Quantifiers}

Let me give you a brief history of our engagement with quantification.
We started with the simplest case.

This sort of thing is great if you're a poet, but not much use otherwise.

Even Aristotle knew way, way back before the internet that it was necessary, in order to do useful logic,

to have more sophisticated forms of expression in our formal language.

And this was great, I mean people were really happy with this for like, 2000 years or more,

I think that, logically speaking, they were easily entertained---quite unlike you and me, of course.

They were content to say some squares are blue or whatever,

and you know they spent quite a long time sorting out the logic of sentences like these.

But the thing about these sentences is that they involve just one quantifier whereas, if you think about it, ...

... many ordinary senetnces are not like this.

Every time I go to the dentist someone dies.

Many ordinary sentences, like this line from Phoebe in friends, involve not just one quantifier ...

... but two. One of the big advances in modern logic is that it provides us with tools powerful enough to deal with sentences involving arbitrary combinations of quantifiers.

This is one main topic for the next lectures (another is proofs involving quantifiers).

\section{Something Is Above Something}

So how can we start thinking about sentences with multiple quantifiers in our formal language, awFOL?

\begin{minipage}{\columnwidth}

Something is above something:

\hspace{3mm} ∃x ∃y Above(x,y)

\end{minipage}

Here's a very simple possible situation in which b is above a.

Now suppose that we lost the name a.

Actually, we didn't really lose it. There were some terrorists, the logical equivalent of Hezbollah,
(here they are pictured in Southern Lebanon looking all military and disciplined)
and they were taking a break from doing their good work for Bashar Assad in his war on Syria
and Bashar had given them some cool weapons
and they were like, let's destroy the name a.

And so they did.

So we can't say b is above a anymore. We can only say that b is above something.

Luckily we know how to do this. We just drop the a, replace it with a variable (in this case, y), and add an existential quantifier.

Why existential? Because we're talking about something, not everything.

But look what happened next.

This time is wasn't Hezbollah.

It was my terrible twins, just back from training with the taliban.
(You may laugh but it's just very hard to get quality childcare without religion these days.)

Yes, and they destroyed the name b.

So now we can't name that object either, we can only say that something is above something.

But, look, we already know how to do this. We just remove the name b from the sentence we last had, replace it with a variable (in this case, x) and add an existential quantifer out the front.

Now we've got a sentence with multiple quanifiers without doing anything new, just replacing names with quantifiers.

Let's consider translation the other way, from awFOL back to English.

Do we understand this sentence of awFOL?

Well, is it true in this possible situation?

And is it true in this possible situation? How do we know?

Take this possible situation first.

There is a procedure for determining the truth or falsity of an existentially quantified sentence.

We first give every object a name.

In this possible situation there are two objects so there we assign two names.

(Look, here are a and b again. I guess they weren't destroyed forever. Maybe we had a little war on terror and got them back.)

Then we make new sentences by removing an existential quantifier and replacing the variable with each name in turn.

Look here: two objects so two names so two sentences.

Now if either of these are true, ...

... then so is the sentence we started with, ∃x ∃y Above(x,y).

But what does it take for one of these to be true?

Consider the second.

To work out whether it's true we have to apply the same procedure again.

The first step is to give everything a name, but since everything already has a name there's nothing we need to do.

Then we make new sentences by removing an existential quantifier and replacing the variable with each name in turn.

This gives us these new sentences, Above(b,a) and Above(b,b)

Now if either of these are true, then so is the sentence we started with, ∃y Above(b,y).

But the first of these is true!

This tells us that ∃y Above(b,y) is true.

And that tells us that ∃x ∃y Above(x,y) is true as well.

This is how we can understand sentences of awFOL involving multiple quantifiers.

To work out whether they are true, we apply the procedure for determining the truth of an existentially quantified statement removing just one quantifer.

And we keep applying these procedures until not quantifiers are left.

This is much like doing complex truth-tables.

Magic, no?

If you've been following along you should be able to do the same in any other possible situation like this one.

The procedure has three steps. First ... well, you know what the procedure is.

You do things ...

... and you can see whether the sentence is true or false.

11.2, 11.4

\section{Multiple Quantifiers: Something Makes Someone Want to Die Inside}

\section{There Is Exactly One}

\section{There Is Exactly One}

There is one creator (at least one, maybe more).

\hspace{3mm} ∃x Creator(x)

Ahura Mazda is the one and only creator.

\hspace{3mm} Creator(a) ∧ ∀x( Creator(x) → x=a )

All squares are broken.

\hspace{3mm} ∀x( Sqr(x) → Brkn(x) )

There is one and only one creator.

\hspace{3mm} ∃y( Creator(y) ∧ ∀x( Creator(x) → x=y ) )

\hspace{3mm} or:

\hspace{3mm} ∃y ∀x( Creator(x) ↔ x=y )

There is one creator (at least one, maybe more).

∃x Creator(x)

Ahura Mazda is the one and only creator.

∃y( Creator(a) ∧ ∀x( Creator(x) → x=a )

All squares are broken.

∀x( Sqr(x) → Brkn(x) )

There is one and only one creator.

∃y( Creator(y) ∧ ∀x( Creator(x) → x=y ) )

Look, two quantifiers. But not just two quantifiers, one is existential and the other is universal. Mixed quantifiers!

Here's another, shorter way of expressing the same proposition (these are logically equivalent)

or:

∃y( ∀x( Creator(x) ↔ x=y ) )

Ex: There is one and only one female creator.

Ex: There is one and only one creator and she is female.

14.10--14.12, *14.13

11.10, 11.13

14.2

\section{∃Intro}

\emph{Reading:} §13.2

\section{∃Intro}

Although this is about the rule ∃Intro, I want to start by revising universal elimination.

Consider this argument. Actually it's not true that puffins have yellow beaks.

Well, there might be a bit of yellow,

but that's not what I'd call a yellow beak.

Anyway, back to the argument. How can we formalise it?

One approach would be to use sentence letters. Nothing wrong with this

except that it doesn't capture the structure in virtue of which the argument is valid. There's a counterexample to this form.

Here it is. So how can we do better?

Start with the conclusion.

We need a name and a predicate.

These allow us to write the conclusion as 'YelBk(a)'. Easy, no? (It's supposed to be easy, we're just revising stuff.)

What about the second premise?

For this we need another predicate.

And then we can write this in awFOL as 'Puf(a)', Ayesha is a Puffin

Finally, we have to formalise the first premise. How?

Well you know that, for universal sentences, we're always going to work from this example about all Fs are Gs.

So, well you know how it goes by now I hope.

Now we have the argument translated into awFOL in such a way that the translation is logically valid too. Can we prove it?

Yes, we can.

To this end, we need the rule we looked at at the end of last lecture, universal elim.

This allows us to infer that what is true of all things is true of Ayehsa in particular.

In English, If she's a puffin then she has a yellow beak.

Of course we have to cite the rule we're using and the line we're applying it to.

So you remember how universal-elim goes. We start with a universally quantified sentence ...

... universal something ...

... and we add the something to our proof, replacing the variable with whatever name we like.

Meraviglioso

Now we have just what we need to get to the conclusion. But what's the rule and what lines should we cite?

It's arrow-elim and the lines we should cite are 2 and 3.

So far so good, ...

now for existential elim

Here's some English

It's clear, I suppose, how we translate the premise. But what about the conclusion?

Well we're talking about something so we're going to need the existential quantifier.

But how can we prove this argument?

Well, that's just what the rule existential-intro is made for.

You have a statement about some named person, in this case about Ayesha.

You remove the name and replace it with a variable (here I've used x as the variable,
but you can use y or z or any variable you like),
and add an existential quantifier to the front.

Of course we have to cite the rule and the line referenced, as always.

And that's it.

Now the premise of this argument is the conclusion of the argument we proved just a moment ago.

So we can join the two arguments together to make one big one.

Look, these premises allow us to prove this conclusion.

I know this maybe isn't the most exciting thing ever.
I'm just showing you so you can see how to get from universal to existential.
In case you ever need to.

\section{∃Elim}

\emph{Reading:} §12.2, §13.2

\section{∃Elim}

\begin{minipage}{\columnwidth}

Note this restriction on the use of ∃Elim:

\end{minipage}

\section{Translation with Quantifiers}

\emph{Reading:} §9.5, §9.6

\section{Translation with Quantifiers}

\begin{minipage}{\columnwidth}

All discordians weep:

∀x( Dscrdn(x) → Wps(x) )

\end{minipage}

\begin{minipage}{\columnwidth}

All \textbf{quadrumanous} discordians weep:

∀x( ( \textbf{Quadr(x) ∧} Dscrdn(x) ) → Wps(x) )

\end{minipage}

\begin{minipage}{\columnwidth}

All quadrumanous discordians weep \textbf{and wail}:

∀x( ( Quadr(x) ∧ Dscrdn(x) ) → ( Wps(x) \textbf{ ∧ Wls(x)} ) )

\end{minipage}

\begin{minipage}{\columnwidth}

All quadrumanous discordians weep and wail \textbf{except Gillian Deleude}:

∀x( ( Quadr(x) ∧ Dscrdn(x) \textbf{∧ ¬(x=a)} ) → ( Wps(x) ∧ Wls(x) ) )

\end{minipage}

Some persuasive and useful arguments are not valid.

∃x(Persuasive(x) ∧ Useful(x) ∧ Argument(x) ∧ ¬Valid(x))

All discordians weep.

∀x( Dscrdn(x) → Wps(x) )

All quadrumanous discordians weep.

∀x( (Quadr(x)∧ Dscrdn(x) ) → Wps(x) )

All quadrumanous discordians weep and wail.

∀x( ( Quadr(x) ∧ Dscrdn(x) ) → ( Wps(x) ∧ Wls(x) ) )

All quadrumanous discordians weep and wail except Gillian Deleude.

∀x( ( Quadr(x) ∧ Dscrdn(x) ∧ ¬(x=a) ) → ( Wps(x) ∧ Wls(x) ) )

9.4–-9.5

9.8–-9.9

9.12-–9.13

\section{Scope and Quantifiers}

\emph{Reading:} §9.5, §9.6

\section{Scope and Quantifiers}

\begin{minipage}{\columnwidth}

Underlining shows the scope of the quantifiers:

\end{minipage}

\section{∀Intro}

\emph{Reading:} §12.1, §12.3, §13.1

\section{∀Intro}

\begin{minipage}{\columnwidth}

Why is this proof incorrect?

\end{minipage}

12.4--12.5

*12.6--12.7

12.9--12.10

\section{Summary of Quantifier Rules}

\emph{Reading:} §13.1, §13.2

\section{Summary of Quantifier Rules}

10.20

*10.24--10.7

10.28--10.29

13.2--13.3, 13.8--13.9

13.11, 13.13, 13.15

\section{Two Things Are Broken}

\emph{Reading:} §14.1

\section{Two Things Are Broken}

To translate sentences involving number into awFOL, use identity. For example,

`Two things are broken' might be translated as:

∃x ∃y ( Broken(x) ∧ Broken(y) ∧ ¬(x=y) )