00:00

all right everyone welcome back i’m dave

this video types of quantifiers and how to use them so in this episode we’re

going to learn about different types of quantifiers and how to use them

and before we get started though i wanted to talk about how this episode is

part of the series logic and mathematical proofs in-depth tutorials

for beginners the link for the full series playlist is below in the description

so let’s go ahead and get started um in today’s video uh we’re going to talk

about quantifiers logic rules and propositional functions and then

we’re going to talk about the universal quantifier the existential quantifier

and the uniqueness quantifier and then we’re going to practice negating

quantifiers in the next video we’ll talk about combining multiple

combining quantifiers so today’s video is all about giving a good solid

00:01

introduction and will include the working negation as

part of this video so let’s go ahead and get started and see how it goes [Music]

all right so the first question is of course what are quantifiers so let’s put

this together and let’s go ahead and get started so i’m going to go up here and

try to answer this question right here what are quantifiers so first off we

need to talk about uh what variables are

so variables and mathematical statements so we talked about in the first episode

what mathematical statements are so these are sentences that have the

declarative sentences that have a truth value either true or false

um and so we need to talk about variables in order to talk about

quantifiers we need variables and we’re going to have two main types of

quantifiers in this video we’re going to have the universal quantifier and the

symbol for universal quantifier is going to be this upside down a right here

00:02

and it’s going to be used to express that a variable may take on any given

value in a collection so this upside down a is the way we

write it mathematically symbol symbolically and you know it’s going to represent

these phrases in english right here so this is your intuition here so for any x

for every x for all x so all these mean the same thing

mathematically and this is the symbol that we use for it and a fourth one if x

is any so here’s four ways of representing in english this um

mathematical symbol right here there are more but there’s probably the most four

popular ways so the other quantifier that we’re going to talk about here is

the existential quantifier which looks like a backwards e

and it’s going to be used to express that a variable can take on at least one

value in a given collection all right and so some common ways to to

say that in english for this symbol right here their existing x

00:03

is another one is for some x there exists an x there is an x or there are x

so these are four popular ways of saying um this right here which is what we say

symbolically okay so one common thing in mathematics though

um or in everyday english and is that we often have hidden quantifiers so what

are hidden quantifiers so here’s an example of a sentence um

you know it’s a declarative sentence and it has a truth value true or false

but it has a lot of hint of quantifiers in it and often to determine whether

it’s true or false you need to know explicitly what the quantifiers are so

sometimes we’ll use language that will help us hide the quantifiers

it just sounds shorter and snazzier like this but in reality

you know you can expand it out and show all the quantifiers so we’d say

something like there existed a sequence of 56 games right so we have an

existence statement right here such that for all games so here we’re using the

00:04

universal quantifier right here for all games in this sequence there was at

least one at bat so in other words there exists again so really there’s some

hidden quantifiers in this statement right here now

if you want to say the negation of this statement right here

and you wanted to say something more more valuable than say he did not have a

56 game hitting streak what is that what does that mean so we’ll need to know

often what um you know what are precise negations and so we’re

going to talk about that to a great deal and we’re going to call that those

working negations in other words in other words

one way to negate this is just to say it

did not happen right but what would that mean

explicitly written out with all the hidden quantifiers so we’ll look at that

this coming video in this video and the upcoming video

all right so what are the logic rules for a quantified statement

so we’re going to need two logic rules here and i’m going to explain them here

00:05

right now and we’re going to talk about them throughout this video here so

mathematical statements are sometimes written with hidden quantifiers so you

may want to rephrase a given statement before writing in symbolic form

before you apply the logic rule because you need to know what all the

quantifiers are before you start applying these logic rules so there’s

two logic rules one for uh universal and so how do you negate a universal um

quantified statement like this and so the way we’re going to negate it is by

changing the for all to their exist and by changing the p of x to

the negative the negation of p of x so um in other words what we’re saying

here is that this right here is logically equivalent to

um the negation of for all x p of x so that’s what this logic rule says is that

these are logically equivalent to each other in other words the negation of the

00:06

universal quantifier right here is logically equivalent to existential

quantifier but then we’re going to negate the propositional function here

and then we have logic rule number two the negation of this statement right here

so the negation of it in existence means for all x

it’s not true that p of x holds so similarly this right here would be

logically equivalent to the negation of their existing x such that p of x

so that’s what this logic rule 2 is saying is that the negation of an

existence is a universal so we’re going to talk about these

and motivate these two logic rules as we move forward here okay so um

you know whenever we see something like this

before we discuss quantifiers in detail we’re going to need to know what

00:07

propositional functions mean so this is the goal is to understand these two

logic rules and you know so to do that we first need to know what propositional

functions are and then we can better understand these uh logic rules here and

these universal quantifier here and the existential quantifiers here so we have

all of this um steps that we need to take you know

what are propositional functions what are the quantifiers and then how do

we work with negating how do we come up with a working negation working negation

is more powerful than just saying something does not happen

so we’ll come up with that towards the end and we’ll see all these three steps

here in progress so let’s get started so what are propositional functions

so we’re going to begin with this part right here which says that

the this statement x is less than 5 and it has two parts to it so it has the x

00:08

part which is the variable and it has the is less than five which is called the

predicate so we know when we put these two together

we have something called a propositional function so p of x is the

propositional function x is less than 5.

now the reason why we call it a function

is because we’re going to plug in x’s so we’re going to substitute in x values

into the sentence here and we’re going to get out a true or false we’re going

to get either true or false and so and we’re only going to get one you know

you know truth value out and so this is going to be a function so p denotes the

predicate and x is called the variable so as a quick example once a value has

been assigned to the value of x p of x becomes a proposition it has a truth

value so for example for this p right here x

is less than five what is p one so p one is the statement one is less than

00:09

five one is less than five and now that we’ve using a one instead

of an x now this has a truth value so p of one will be equal to yeah so p of one

is equal to you know is this true or false so one is less than five so that’s

true just assuming the natural uh real numbers with the natural

ordering on it right and so p of two would be

2 is less than 5 and is that true or false that’s also true right so p of 1

is true p of 2 is true so you can see how these are functions here

this is a sentence right here or this is a mathematical statement

x is less than five is a sentence it doesn’t necessarily have a truth value

this is a mathematical statement it is either true or false and not both and

this is the actual output values from the propositional function all right so

what are propositional functions a little bit more detail

00:10

so a propositional function in the variable x is a sentence

about x that becomes a statement whenever x is given a particular value

so again the difference between these two right here statement has a

definitive true or false value now and generally speaking we want to

have more than one variable um so we’ll have a way to say we have a finite

number of uh variables and we can just enumerate them x1 x2 x xn

and we can plug in all of these into the propositional function and then we get

an output and that output um you know has an actual value a true

or false value so again we still have a propositional function it’s just that

it’s multivariable and then we and p is still called the predicate

and so here’s a here’s an example right so now we have three variables here so

it’s going to denote the sentence x minus y equals z

00:11

and then we can plug in two three and one for x y and z respectively and so if

you know if we plug in 2 3 1 then we’re going to get 2 minus 3 equals -1

and then this is a declarative statement so it has a

true or false value right and we can see that that’s true

now what about p of 5 0 7 so again we plug in x and y and z and we

can tell that this sentence right here or this statement this mathematical

statement is false all right so there we go so now let’s start talking about uh

universal quantifiers here so universal quantifiers so the first thing is

the sentence here is symbolized by the formula so this is a for all right here

and you know we talked about this in a couple of

a couple of minutes ago but this is a symbol right here we use for a for all

and so what can we say about this this is a universal quantifier

00:12

so let’s look at an example express a sentence every student in this

class has studied calculus and so that’s a

mathematical statement and we’re going to express it as a universal quantify

universal quantification so we’re going to let p of x denote the sentence x is

studied calculus so i was a little bit careful here with my wording here

because when you don’t have a particular value you don’t have a statement yet so

this is just a sentence but when you substitute in an x then it

becomes a mathematical statement so the sentence can be written as for

all x p of x where x is the universe of discourse

is the students in this class so that’s understood

now if you wanted to actually write it out you could say something like c is

the set of of um students in this class right so c is the set of students

00:13

in this class and then we can write this out

like this we could say for all x and c and then we would say p of x and so

you know right here is a free variable it if you don’t specify the universe of

discourse but if you specify it if you actually

name the set and you use symbolic notation like this then we say the

variables bound to that right there now this right here can be determined as

true or false because we’re bounding x to the set

right here and we could go through this set and we could check if every one

is true or not all right so the next example um

let p of x be the sentence x is greater than three what is the truth value of

this quantification for all x p of x where the universe of discourse is a set

00:14

of real numbers so if if we say x can be any real number

and so in other words we’re asking the question

for all real numbers are they greater than three

and so let’s move over here and so you know p of x is not true for all real

numbers all real numbers are not greater than three in particular three is not

greater than three so we can find one value in the universe of discourse so

you just need one value whether it be three is not greater than three or or

two is you know p of two is false so consequently this statement right here

is false because it’s not true that all of them are greater than three all right

so uh universal quantifier and now let’s look at it from a

slightly different perspective let’s say our universe of discourse is

actually finite we have a finite number of them

so then this statement right here this universal

quantification right here has the same truth value as this conjunction right

00:15

here p of x1 p of x2 and so this is the logical and symbol right here

now what i’d like to do is to motivate why this is true right here

so these are all true if and only if the conjunction is true

so i’d like to motivate this a little bit here by looking at maybe some code

right here real quick because we did python in our last video

so let’s let’s bring in some python here and see what we can do here

so i’m going to go here and look at this

setup right here let’s move me over here sorry let’s move me over here

and so now what i’m going to do is look at some python right here

so first off we’re going to get a setup going here we’re going to load the logic

uh file that we looked at last time and then now we’re going to declare some

variables uh so if you’re not clear what i’m doing

right here is we’re just looking at some examples um

00:16

and i wanted to um you know declare some variables so i’m going to declare some

variables p q r s and t these are just propositional variables i also want to

name some of these right here p one through p5 all right so i declared those um

and again it’s in the previous episode of this series here how we set this up

all right so i want to look at some examples two types of examples first

examples with a logical and connective so let’s do that real quick so the first

thing i want to refresh your memory on is the fact that if you

look at p and q and if you look at q and p

that we get the same truth um you know the same truth values in other words

p and q and q and p are logically equivalent to

each other so we could say that uh something like this right here

we could say p and q is logically equivalent to q and p

so these are logically equivalent to each other and so it doesn’t matter

00:17

which way you say the q and the p now when we print out these truth tables

like this we can see that all the true and false values line up and they’re all

they’re all the same right here so we can see the logical equivalence now what

if we look at three variables though let’s just look at three variables real

quick so q and p and r so the parentheses are around the q and p here

um and now the parentheses are around the p and r so

if we execute this cell right here and print out these true tables right here so

we’ll see that these are also logically equivalent to each other the q and p and

r so if i write that say over here so the q and q and

t is logically equivalent to p and q and t and because

the parentheses this parenthesis right there

because the parentheses don’t matter these are logically equivalent to each

00:18

other we can just say that this is just going to be q p and q and t

so you know we we write it without parentheses because it doesn’t matter

which way you insert the parentheses so i just want to refresh your memory on

that real quick in fact i’ll just do another one right

here with lots of variables right here so we have p and q and then we have q and

p3 and p4 and then we have np and if we execute that and get that

truth table there it’s just going to be um you know all of these right here and

what what we’re going to notice here is that the only way all of these n’s are

true right here the only way that’s true all of them are false here

is if they’re all actually true every single one of them has to be a true in

order to get a true out from the uh full and statement right here and so i’ll

just go down here and do one more um and so you know i just wanted to

00:19

um point that out to you that you know if you look at

this and statement right here um the only way that this and statement is true

is if every single one of these is true and that’s what universal quantifier

means is that p of x is true for every single x so i just want that intuition

to stay with you that um the universal quantum quantification quantifier is is

is a generalization of the conjunction connective from you know propositional

calculus all right so let’s look at [Music] let’s look at an example real quick

let’s let’s move to the bottom here um this bottom here all right so what is

the truth value of the statement p of x is the statement x square is less than

five and the universe of discourse is a set of non as sorry is a set of negative

integers not less than three so if we look at the universe of

00:20

discourse right what are the negative integers not less than three right so

minus three minus two and minus one those are the only three values right

there so in this example right here the universe of discourse is finite it just

consists of these three uh integers here so if we’re going to look at this

universal quantification here we just need to look at this conjunction right

here this and statement right here and we can look at each one of these

right here and determine if it’s true or false so since the first one is false

so it follows that the whole statement right here is false so this universal

quantification right here is false so that’s the nice thing about the

universal quantification is is if if one of these is false then the whole

statement is false all right so let’s start now let’s talk

about the universal quantification so universal quantification is the

00:21

sentence here there exists x such that p of x

and it’s symbolized by this formula right here there exists an x such that p

of x and you know just like we said before this backwards e is the symbol that

we’re going to use for existential quantifier and

so let’s look at an example real quick so denote the statement x is less than 5

what is the truth value for this quantification

now the universe of discourse is the set of rational numbers so this is not a

finite set here the universal discourse is an infinite set here all the rational

numbers all the fractions right so in order for the sentence to be true

we only need to demonstrate at least one value right so that’s ex existence

so since two is a rational number and p of two is true two is less than five

we see that this uh quant uh quantification statement right here this

00:22

quantified statement right here is actually true all right so another example

and so let p of x be the sentence um x squared equals minus one

so what is the truth value of the quantification there exists right so

we’re naming what the propositional function is and then we’re going to

quantify it with either existence or or or universal and so for this example

we’re going to do existence so where where the universe of discourse again is

an infinite set the set of rational numbers and so this right here is false for

every rational number there is no rational number whose squared is minus one so

this right here is a false statement there is no um x

where x squared is is equal to minus one so that’s false

now you know rational numbers are fractions but you can talk about real

numbers or complex numbers but that’s changing the universe of discourse and

if you change the universe of discourse then you’re changing the the whole

00:23

statement right here so for this universe of discourse the statement is false

all right and so let’s look uh and get some more intuition about this right here

the universe of discourse is finite if if that’s the case

you know we just saw some examples where it wasn’t finite where we looked at the

rational numbers but if it is finite then this statement right here has the

same truth value as this logical or statement right here so this is very

similar to what we did with the universal except we had an and statement

here and so let’s jump back to the uh code here and look at some examples here

with the or so first thing is i want to refresh your memory here um about the or

so here’s um in this um set up here here’s how we represented

the or with the vertical bar here and if we execute this table right here

00:24

then we’re gonna get that um let’s see where to go yeah here we go so the p or q

is the same as q or p they’re logically equivalent to each other

and so they’re true and the only way you can get a false

with an or is if they’re both false um and then we can go with three

variables and say it doesn’t matter the order so we have communicativity and we

have associativity and so we have just the statement

without any parentheses in it q or p or r um and they’re all trues unless one

unless they’re all falses so they’re all trues here

unless they’re all falses in which case you get a false

and so i’ll just do this here on just some statement like this

and we’ll look and see just to give you so you can visualize it

they’re all trues when you have an or here they’re all trues

00:25

unless you have all falses all right and so let’s go back here so

the only way this is so these are this is always true

unless they’re all falses if all of these are falses if p of x1 is false p

of x2 is false and all of them are falses otherwise it’s true

and so when we look at an example here what is the truth value of their

existing x p of x where p of x is this uh x to the fourth minus one here and the

universe of discourse consists of negative integers

not less than negative five so when we look at negative integers not less than

five we can see that we have only a finite number of them right so we need

negative integers that are not less than five right so these right here and so

then to determine whether this is true or false we can just look at each one of

00:26

these individually we can look at p of p of minus five and which was we’re going

to say is minus five to the fourth less than one right and then we can look at

minus four to the fourth power is less than one

right and so we can check each one of these values out here and you’ll see

that they’re all false if you do minus five to the fourth power

you’re going to get a positive number and it’s not going to be less than one

right so if you try all of these right here

even minus 1 here minus 1 to the fourth that’s just 1 1 is not less than 1.

right so each one of these are false right so this conjunction right here is

always true unless every single one of them is false

which is the case here they’re all false so this existence statement right here

is false all right so what about an existence

quantifier here so let’s look at an existence quantifier here now all right so

00:27

um there exists a unique x such that p of x so this is more than

just existential so it says there exists one

and only one so this is more than just the existence quantifier and we’re going

to use this special symbol right here looks like a factorial symbol or an

exclamation mark here and it’s going to be used to represent um

uniqueness quantifier so it looks like a existence or backwards e with an

exclamation mark so this is the mathematical symbolism whenever you see

these two symbols right next to each other we’re representing these words

right here there exists a unique and so let’s look at this um value right here

there exists a unique x such that p of x holds where p of x is

the statement x to the fourth is less than or equal to one and the universe of

discourse is the same we looked at in the last example right so

00:28

negative integers not less than negative five so again we have just a finite

number of them and now we can go and check this one is false

minus four if you plug it in here it’s false minus three

plug in here is false minus two plug in here is false but minus 1 if you plug it

in here we’re going to get minus 1 times

-1 times -1 times -1 all that multiplied together is actually equal to 1 and it

could be equal so p of minus 1 is true so this statement right here is true

there exists one and only one where this is true

assuming that the universe of discourse consists of these numbers right here

so again i’d just like to reiterate if you change your universe of discourse

and but you leave your propositional function the same its truth value could

change and generally speaking it well all right so

how do we negate quantifiers so that’s the question now

00:29

how do we negate quantifiers and so now we have a better understanding of our

what a propositional function is we have a good understanding of the quant

quantifiers now let’s look at how to negate them so we’re going to discuss

the two logic rules that we talked about at the beginning

and so let’s formalize them a little bit better so p is a propositional function

and a is a set so we think about a as a universe of discourse here so then

how do we negate a unit a universal quantification and

then number two is how do you negate an existence quantifier

so the way we’re going to do that is we’re going to say the negation of a

universal is true if and only if there exists an x in a

where this is not true so in other words we’re going to change the quantifier

here and then we’re going to push the negation inside into the proposition

00:30

right here and the dual statement for that is there exists a

the negation of existence is a universal and then we’re going to negate the

propositional function here all right so let’s see some examples here

um well before we do that let’s look at um

let’s try to look at an argument as to why this is true here

just kind of rephrasing things back in terms of ordinary english

to kind of give you a reason to kind of believe in this right

here this is not a formal proof right so i’m going to look at number two here

and i’ll invite you to look at number one on your own and try to come up with

an argument and if you have any questions leave leave a comment below

and i can get to it in another video but let’s see let’s see about number two

here so i’m looking at the negation of an existence

so i’m going to assume that that’s a true proposition right here so let’s

just suppose that this is true so what does that mean

it means it’s not true that there exists

00:31

right so that means there is no a in and there is no x in a such that p of x is

true in other words this right here for for each x and a

this right here has to be false and so what that means is that this

right here is true for every x the negation is true for every x in the set a

and so this statement right here has to be true

and so you know if you think about it in terms of just everyday

uh english in which you use all these words you come to agree that you know

the negation of an existence is true exactly when

for all x and a universal the negation of the statement right here is true

now we can do conversely so assume that this right here right here this part

right here is a true proposition so how would we rewrite this in terms of

everyday words well this right here is true statement

00:32

and then we’re using universal so for every x in the set a

well how can we write rewrite this so in other words if if the negation is true

that means the negation of the negation is false and that that’s false for every

x in the set a so that means that that there does not exist

an element x in the set a such that p of x is true

so therefore we see that this right here the negation is a true proposition

and so what these two arguments here show is the if and only if if this one

is true if the negation of an ex of an existence is true

then the universal of the negation of the proposition has to be true and

conversely if this one is true then this negation over here has to also be true

so that’s these two arguments here so i hope that gives you some intuition as to

why number two is true and i highly recommend that you try to

follow this pattern here and see if you can make sense of it and try to write

00:33

your own intuitive argument in terms of why number one holds

all right so let’s look at um example now and so let’s go to

uh write the negation of the statements here so let’s practice using

these two one and two here and so we’re going to look at this statement right

here this is the set of natural numbers here meaning

0 1 2 3 and so on and so we’re going to look at this right here also so these

two statements are very different from each other this one is universal this

one is existence and then part c will look at a

unique uh quantifier here so the idea is to we have two mathematical statements

here and our goal is to write the negation so here are the negations right

so how do we negate a universal so which logic rule applies it’s number one

so we’re going to negate a universal so we’re going to negate this right here

and the way to do that is to change this

00:34

into an existence right here but then we need to negate the p of x so that this

is all this is all the p of x right here v of x is this whole statement right

here or this whole part right here the sentence

and so we’re going to just simply negate it so this is declaring equals here so

the way to negate that would be to say it’s not equal to each other

all right so let’s look at number two number two is

an existence so we’re going to change it to a universal

and then we’re going to negate the p of x so we just negate the p of x again so

those look straight forward there but now let’s look at c

so c says there exists a unique natural number where these two things are equal

to each other so here how do we write the um how do we

write the negation well first off it’s a good idea to unravel the hidden

quantifiers here so we want to write the negation of the statement here right so

00:35

your uniqueness says there is one and only one in such that this holds now if

you look at this right here there’s two parts to this it says there’s one where

this holds and there’s only one right so this is an

and right here so this point i’d like to try to remem uh remind you of de

morgan’s law which we covered in previous videos so if we have p and q

my marker would blank on me if we have an and how do we negate an end

right because we want to negate this and it has an and in it

and so how do we negate an end so the negation of an n

this is de morgan’s law is the negation of the p or the negation of the q

so when i write the negation of the sentence here i need to negate the one

00:36

and i need to change the and i need to change the and to an or

and then i need to negate the only one right so to do that we’re just going to

say the negation is there is no n right so

that’s negating there is one there is no n such that this holds

or so i’m changing n to an or or and then how do we negate there is only

one right or there is more than one n such that this holds so in both cases um

we’re going to um yeah so we’re negating the all right so

perfect so another way of saying this though is

you know not being so long you know another way saying this is that for each n

n is not equal to zero or there exists two natural numbers in

00:37

where it’s equal to zero all right and so you know when we negate the one here

we’re going to there’s no n where this is true or there is more than

one in where this is true so another way of saying this is for each n and n

it’s not true right so there is no n where it is true so there is no end

for each end it does not hold all right and so it it it can be written a little

bit of a of a different way there all right so and that kind of gives you

the working negation there so i hope that helps you understand um

you know universal quantification and existential quantification

and then we touched upon the uh existence quantifier also

so i look forward to watching you uh i look forward to seeing you in the next

video where we’re going to combine these multipliers together and we’re going to

get a lot better at it and so i’ll see you in the next video check you out then

00:38

if you like this video please press this

button and subscribe to my channel now i want to turn it over to you math can be

difficult because it requires time and energy to become skills i want you to

tell everyone what you do to succeed in your studies either way let us know what

you think in the comments