00:00

hi everyone welcome back it’s dave uh today’s episode multiple quantifiers

how to combine quantifiers so in this episode you’ll practice using multiple

quantifiers and you’ll learn how to combine quantifiers especially uh we’ll

practice on the working negation and we’re going to be negating uh

statements with multiple quantifiers so it’s a lot of fun and let’s go ahead and

get started but first i want to talk about how this video is part of the

series logic and mathematical proofs in-depth tutorials for beginners so the

link is below for the full playlist uh series and i hope you check it out

in in the last video we talked about uh quantifiers we talked about the

universal quantifier existential quantifier and we also talked about the

uniqueness quantifier well today we’re going to be combining these quantifiers

together and we’re going to have a lot of fun so first we’re going to talk

00:01

about counter examples and then we’re going to talk about combining mult

quantifiers and how how do we do that and then we’re going to be working some

more on the working negation we started that last time and we’re going to kind

of continue that process now so i’m excited for today’s episode and well

let’s go ahead and get started [Music] okay so up first we’re going to look at

what are counterexamples uh so let’s go and combine these two together and let’s

go ahead and get started so we’re going to say that quantifiers here um

i’m encountering examples here you know how can we show that the statement of

the form for all x p of x is false right

so this is a universal quantifier so how can we show it’s false that for all

p of x right and so the way to do that is um to work with the negation and talk

00:02

about how that’s true so how can we show the negation is true

is this is the same thing as talking about how the original is false so

simply means we need to show that there exists a

x where the negation of p of x is true so we can show this as false by showing

that this right here is true right because they’re the negation of each other so

we can say that we have here a counter example if we can find a value x where

the negation is true then we have something called a counter example

so we can show something is is is for all x is false by coming up with the

counter example where the negation is true and so let’s look at an example so

suppose the predicate p is x is wearing a red shirt right so i i d we discussed

uh what predicates were in the last video right so um the predicate is is

00:03

wearing a red shirt right so then a counter example to the statement

everyone is wearing a red shirt so counter example is well we found someone

not wearing a red shirt so you can see how we have the negation right here

everyone that’s a for all right so how can we show a for all is false

well we can say well we found someone and then we have the negation right here

is true we found someone not wearing a red shirt so that would be an example of

a counter example all right so more formally

p of x is a propositional function uh we talked about propositional functions in

the previous episode so if we have a propositional function and x is a member

of the set a then a counter example is um a counter example to this

statement here is something in the set a right has to

come from the set a for example in our in our last example uh you know i was

00:04

talking about people wearing red shirts so you wouldn’t talk about someone

wearing a black shirt or a blue shirt right so it needs to be in the same set

and then the pfc is false right so the last example is not wearing a red shirt

so that that that’s the negation right so we want the false for p p of c

all right so example another example show that the statement all primes are odd

is false so how would you show that’s false well we can give a counter example

so the statement all primes are odd is written with universal quantification

for all x p of x where the universe of discourse are prime numbers

so p is the predicate uh is odd and um the universal discourse is the

set of all primes so it’s easy to see that two is a counter example because

two is in the domain of discourse in other words two is prime and it is not odd

00:05

so this statement right here is false and we showed it’s false by showing

um a counter example all primes are odd nope that’s not true

there is a prime that is not odd namely two all right

so let’s consider the following statements so um there exists an integer x

such that for every integer y x plus y equals five

so this is going to be combining multiple multipliers together

and here’s another statement for every integer y

there exists an integer x such that p plus y equals five x plus y equals five

so we can represent these in symbolic form

so number one is there exists an integer x so we have their existing integer x

00:06

such that for every integer y x plus y equals five excuse me

in the second statement we can uh write with quantifiers for every integer y

there exist an integer x right so i have these backwards here let’s just say

for every integer y sorry that should say for every integer x right here so um

let’s see if i can fix this real quick or every integer x

there exists an integer y all right so for every integer x

here and then there exists an integer y so there exists an integer y and then x

plus y equals five okay so these statements have very uh

00:07

different meanings one is existence and then there and then

universal and then this is universal in other words the order matters right here

so in order for the first statement to be true

we need to come up with an at least one x so there exists an x

such that for any y this equation is true and we cannot do that

so no matter what x we choose this will not be a true statement right here for

all y so we can see that this statement is false

so if you think you have an x say say you think x is 2 right we put a 2 here

and that this statement will not be true for all y

because it’ll only be true for one y namely 3.

um and so no matter what x you choose this statement will not be true for all

y it’ll only be true for in fact one y so this right here is not true

00:08

um and then statement number two in order for the second statement to be

true we need to be able to specify for all x and then we have to be able to

come up with a y there exist a y no matter what x you give does there exist a y

and the answer is yes because no matter what x we’re given

we can find the y there exists a y we can find the y in fact we can just solve

for the y if someone gives me an x no matter what

it is no matter what integer x is i can move the x over that you give me

and say the y will be 5 minus x and that y will be an integer

so in order for the second statement to be true we need to specify an integer y

for any given integer x and we can specify an integer y when x is given

just use y equals 5 minus x 5 minus x is an integer that’s crucial

00:09

right there we have to take consideration the sets the universe of

discourse for each of the variables so um you know

x plus y will be x plus five minus x which would be five right

all right so we see the second statement is true all right very good

so what is the working negation and how do we find it

so the working negation of the statement

right here is find the negation now this is multiple quantifiers here

and this will be our p of x y this is our predicate right here

so the statement has the form there exist in x for all y

and so we’re going to find the um negation so our predicate is this uh x y

equals y x times y equals y we’re going to find the working negation here

so here we go so first off i’m going to negate this whole thing

00:10

to find the negation we just simply put negation and then the whole statement so

technically speaking that’s the negation right there all right so what we really

want is the working negation in other words we want something more useful than

just putting a negation around it all right so we’re going to negate

existence and we talked about how to do that in the last video

to negate an existence we change this to

a for all and then we’re going to negate this inside part right here

so now we’re going to negate a for all so as we can see here um combining

quantifiers and working with the negation is just going step by step well

we’re going to negate each quantifier one of them at a time first we negate an

existence and we get a for all and then we’re going to negate

and then we’re going to negate the frau so now we’re going to have changes to an

existence and then we’re going to negate the predicate right here

and so this right here will be the negation right here

00:11

so the negation is and so now we can say

what is the negation of x times y equals y and so we’ll just say it’s x times y

is not equal to y so here’s the negation so here’s the

original statement and here’s the negation now sometimes when you’re trying to

determine if a statement is true the working negation may help you it may

be easier to determine which one is true which one is false so having them both

in mind can be to your advantage in some cases

all right so now let’s do one that’s a little bit more complicated

so let’s go here and hopefully you’ll get to subscribe but let’s work at this um

nice uh fancy one here so again we have two quantifiers but in this case we have

an implication and actually then we also have a third

quantifier here so this one will be a lot of fun here so here we go

first step i’m going to do is try to make it a little bit more abstract so

00:12

i’m going to say this is p of x y right here x is less than y and i’m going to

say this is q right here x is less than z

and then i’m going to say this is my r r of x y right here

now actually this is with an x and y this is within x and z

and this should be z and y right here so that should be a z and a y so let’s see

if we can fix that real quick so this should be um [Music] z and x y so

we got our um here we go so this should be z right here just a small typo there

there we go so this is our our zy which is just this one right here all right so

00:13

now we can um realize the statement and let me get me out of the way here

statement has the form for all for all right for all for all and this is our p

implies and then we have the existence of z and then we have q

and r right here and are right here i just switched them right here

um to stay consistent it would probably be better to stay

consistent right here so let me see if i can go back and change that right here

to say y and z so i want this to say the same thing right here and right here

all right there we go so that looks much nicer so we have our

p implies there exists a z we have q and r so i’m just going to make it a little

bit more abstract so i can just focus on the form and not on the underlying

00:14

mathematics so all right now before we do the negation

so we’re we know we’re going to change this to an existence and to an existence

but we’re also going to need need to know how to negate an implication

so let’s recall from the earlier videos earlier episodes where we did some

propositional uh logic and we talked about how the implication

is logically equivalent to not p or q so in other words anytime i have an

implication i can write it as an or now what we also want to do is because

we want to negate a negate we want to negate this implication

so we want to negate an or so how do we negate an or well we can use de morgan’s

law so the negation of this left hand side

which will be the same as the negation of the right of the right hand side here

so we want to negate a negated p which means we’ll have a p

00:15

and then we’ll change the order to an end and then we’ll negate the um the q

right here so that’s de morgan’s law right here

so i guess i could spell it out for you right here p implies q

and these are logically equivalent to each other if you haven’t

mastered the previous videos yet then you would just simply

make a true table here true false true false true true false false

and then negate the p so be false false true true

and then this right here is true false true true true and this one is true

false true true and so you can see these two columns right here the same

which means they’re logically equivalent to each other right here

now if i want to negate this if i negate the left hand side here

then i will negate the right hand side here which will be the negation of this

00:16

not p or q now by demorgans de morgan says to negate an or

we’re going to change that to an and and we’re going to negate so we’re going to

have negation negation and and then we’re going to negate this q here

and then negation negation here is just simply the p so p and not q

here i’ll put it down here so p and not q

and so that’s why i’m getting this right here so i’m just using de morgan’s law

so the point is this whenever you want to negate an implication

is just take that p change it to an and and then negate the q

all right so let’s remember that right there let’s remember that going forward

we’re going to use that not only in this example but in another one coming up

all right so let’s look at that real quick

00:17

all right so here we go let’s find the negation of the statement right here so

and again we’re going to be finding the working negation here

so boom there it is there’s the negation right there there’s the technical

negation but i want to find the working negation so i’m going to move this

negation and i want to change the for all to their exists and then i’m going

to push that negation into all the rest of it right there so i’m going to negate

all the rest of it right there then we’re going to negate the for all

right there so we’re going to change this to their exists

and then i wanted to negate all the rest of it right here so i’m going to put a

negation around all the rest of this right here

now the next step is to negate now we’re not negating an and or an or we’re

negating an implication so there’s no quantifier sitting out

here for the whole statement this quantifier right here is for just this

part of it it’s just the conclusion of this implication right here so i need to

think of this as negating the implication so how do we negate an

00:18

implication this is where we’re going to use this right here so negate an

implication we’re simply going to take that p

which in this case is just the capital p of x y

so we’re going to keep this the same keep this the same so to negate an

implication i take my p and and then remember we’re going to negate

the q right here so i’m negating the q so i’m going to negate all of this right

here so i’m going to negate all this right

here so we still got a little bit more work to do here so now i’m going to

change this i’m going to keep everything the same and i’m going to change this

negation of an existence to a for all and then i’m going to negate this part

right here and we still have more work to do

because we know how to negate an and so we can change this to negation of the q

and then we can use de morgan’s law to change this to an or and then we can

negate the r right there so now we can say what is the negation

of q so remember what our q was right here here’s our q

00:19

so the negation of x is less than y is to simply say x is greater than or equal

to z and then similarly we can change the negation right here for the r

so the working negation is and there we have it so i’ll move up

here so it’s there exists an x there exists a y

such that and then we have our p of x y here and we have an and and then for all

z and then we have negation with an or and then the negation of r and so

there’s our working negation so to go from here to here

it’s very valuable very valuable skill to have

if you’re having trouble determining the validity of the statement is it true is

it false it could be very much easier it could be very easier to

determine this one right here or vice versa

if you know that this one is easy the working negation may actually be hard so

it could be to your advantage to understand that just depending upon what

00:20

problem you’re working on all right so let’s do um one last

example here it’s going to have four different parts to it but let’s look at

this uh predicate right here p of x y so it’s an implication again and it’s

saying if x is less than y then sine x is less than sine y

so the domain of this discourse is going to be this interval right here minus pi

over 2 to pi over 2. and here are the um

statements that we’re going to work with double existence

and we’re going to look for existence and then a for all

and then a for all there exists and we’re going to look at it for all for all

so generally speaking each of these could be very are very different statements

and some of them can be true some of them can be false they all could be true

they all could be false it just depends upon your predicate

so we’re going to look at each one of these one by one and we want to

00:21

determine if it’s true or false and we want to find the working negation

all right so here we go so let’s look at the first statement here let me go

down here so the first statement right here exists exists

and i claim that that is true so why would that be true so to be true

this right here is going to need um we’re going to need to come up with the

existence here so we’re going to need to find an x and a y now

before i do this some more for those of you who aren’t remembering what that is

let’s just draw a quick sketch right here and so i’m going to just say here

oops nope sorry let’s draw it about right here

and then now this looks like something like this

00:22

all right and so this is going to be pi over two to minus pi over two [Music]

and the height here is one so it’s it’s curving up here to one and that’s the

highest and this is falling down right here to minus one all right

and so let’s keep this right here in mind let’s keep this graph right here in

mind uh to give us some kind of intuition in terms of this statement

right here so this statement right here says um

there exists an x and there exists a y where this statement is true

for this statement right here so we’re asking is number one true

can we find an x and can we find a y so if we find this x right here is 0

right here and then we find this y right here which is pi over 2 right here

so here i’m not thinking about this is the x and y axis i’m thinking of x and y

00:23

along the x axis here so anyways i find and two inputs x and y

where the output x sine x and the output sine y that’s the height right

so for this x and this y right here i find this right here height is one so the

output is zero and the output here is one

and so zero is less than one so we found an x and we found a y where the outputs

um are less than e are less than each other right zero is less than one

so this is true here so the so the working so you can see

that it’s true so the working negation is so i’m going to change there exists

there exists i’m going to change it to for all for all

now remember how we’re going to negate an implication so let’s just re-quickly

remember that so whenever we want to negate an implication [Music]

00:24

that was logical equivalent to p and not q right so when i want to negate this

implication right so to find the negation of one i change this to a fraud

to a fraud and then i want to take the p which is x is less than y and i want to

change it to an and and then i want to negate the q

so the q is this part right here so negating that means sine x is greater

than or equal to the sine y so given that the original statement is true

the working negation or the negation is false so this statement right here has

to be false can you see that this statement right here is false

and so the answer is if you give me any x and any y in this interval here so it

can be any x and any y so i could choose

the x to be pi over 2 and i could choose the y to be pi over 2 and this isn’t

even going to hold so if i choose any x and any y in here it’s not true

00:25

that this part right here is true so the whole conjunction right here is false

right so to have a conjunction true you need to have every one of them true but

this one’s not true for these two quantifiers here so

um the negation is this right here and the negation is false and the original

statement is true all right so let’s look at statement number two now

all right so statement number two for the second statement there exists an x um

did i have r’s up there before no i had i’s so i should have

eyes right here and here so let’s see if we can go back and fix that real quick

because we’re not using that as our um [Music] the universe of discourse

it’s just an i so i’m going to change that real quick and see if i can change

00:26

that real quick all right so this is our universe of

discourse right here we’re only restricting this right here if you

restrict it to something else sine x and sine y they repeat over and over again

so you have different conclusions for these statements here all right so

anyways does there exist an x such that for all y that this right here p of x y

is true so i claim that this whole statement right here is true

now let’s see why so i need to come up with the existence

of an x so you have to explicitly say it here’s what the x is it’s minus pi over

2 and so what i’m saying is for that x i’m

saying that there does exist an x here it is now no matter what the y is

notice for all y that if you input this x and that y i

get a true statement because sine of x for this x is the height is -1

00:27

and no matter what else the y is no matter what other input you choose the

height will be greater and that’s because this is increasing

so i choose the lowest height here the x

for the lowest height and then no matter

whatever the y is the height is going to be greater

so this is the these are the heights these are the inputs and these are the

heights all right so this is a true statement

um and so this is no matter what the y is no matter which y i choose greater

than that x then the sign y is greater than the minus one

all right so and and so i’m just you know looking at this graph right here to

get my intuition about this statement here but here’s the working negation so

remember we have this uh negation right here we take the p and and then we

negate the the the this part right here the q and so we have a for all and there

exists so we have a for all x and there exists so this is the working negation

00:28

of number two and it has to be false because the original is true

all right so now let’s look at the third let’s look at the third now

so the third statement is for all there exists so you may want to pause the

video and see if you can do number three on your own um and then so let’s pause

it right now all right very good i hope you gave it a good try

let’s see what i come up with all right so the third statement is for all x and

i there exists a y and i such that p of x is true

so i say it’s true let’s see why so we cannot prove the statement is true

with one value for y right because it’s there it’s for all

for all x here for all for one value of x right so we need for all so what we’re

going to do is we’re going to say let x be an arbitrary element

so now we’re not going to put any condition at all on x and that’s because

we have a universal quantifier here so now that x is given we can set y to

00:29

be equal to the x so in other words i’m going to come up with a y in other words

any x you give me i’ll say the y is the same thing

well then p of x is a true implication here because the hypothesis right here

will be false remember your implication is true whenever you have a false

hypothesis so if you give me an x i’ll come back with a y for example maybe you

give me x is 2 or sorry 2 is not in here maybe you give me x is 0 or x is 1

or whatever and then i’ll reply back with the same number and then the hypot

then the hypothesis will be false which means the predicate will be true

um okay so the working negation is i’m going to change this to

there exists i’m going to change this to a for all

and then we have the same p and not q and this has to be false because the

00:30

third statement is true can we see that this would be false

just directly by looking at this statement so there has to exist an x

such that for all y it’s bigger so no matter what x you give me

um if if i start with say x is zero will there be a

you know zero is greater than or equal to for all y

so yeah i don’t see that happening right so

this is true this has to be false here all right so

you could write an argument out for this just like we did for the original or if

you don’t understand the original then try to write an argument out for

the negation in either case you should be able to convince yourself

let’s look at the fourth statement it’s much more involved here

because we have a fraud and a for all here and so

00:31

we’re going to say this is also true so we cannot prove the statement is true

with one value for x because this says for all here

so we have to start with um let x be arbitrary

so for any given value of x the value of y must also be arbitrary

so i’m going to start off by saying let x be arbitrary and then i’m going to try

to look at all the possible cases for y so so let x be an arbitrary element

now i’m going to have two cases so this will be case number one right here

case number one because remember we have to do this for all y

so the first case for y is that is in fact less than or equal to the x that

we’re given so if if y is less than or equal to x then the implication p of x y

is true because um by false hypothesis right so if this is if this is uh

00:32

this is true right here then that is false

which means the whole implication would be true so in that case

the um whole statement right here is true in this case that’s that case right

there now for the second case right here

if x is less than or equal to if if x is

strictly less than y then the hypothesis is true but in fact the conclusion is

also true because the sine function is increasing

so if i choose x is less than y say here’s my x and here’s my y no matter

what y i choose right so the heights so this height right here will be less

than the height of the y so that’s just simply because it’s increasing so

no matter what x is whether so no matter what x is i can give you uh

00:33

and no matter what the y is so that we see that p of x y is true for all y

so now the working negation is we’re going to change this to existence into

existence and then we’re going to have x is less than y

and and then we’re going to negate the the second part right here negate that

and so since this one is true the negation must be false so very

similar to the other example so you have to go case by case when working with

these uh combining these quantifiers because in this example it turned out

a certain way for each of these but you have to look at them case by case

because generally speaking these are going to lead to very different type of

statements and it leads to very different type of arguments

okay so that’s it for this video and the uh next uh episode we’re gonna start

00:34

working with mathematical proofs um so so far in this series we’ve talked about

propositional logic we talked about predicate logic and we gave an

introduction to both of those so now we’re going to start

something very exciting we’re going to start writing proofs so that will be

very exciting i hope you continue to watch the series and i’ll check you out

and i’ll see you in the next video bye-bye 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