Multiple Quantifiers (How to Combine Quantifiers)

Video Series: Logic and Mathematical Proof (In-Depth Tutorials for Beginners)

(D4M) — Here is the video transcript for this video.

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

About The Author
Dave White Background Blue Shirt Squiggles Smile

David A. Smith (Dave)

Mathematics Educator

David A. Smith is the CEO and founder of Dave4Math. His background is in mathematics (B.S. & M.S. in Mathematics), computer science, and undergraduate teaching (15+ years). With extensive experience in higher education and a passion for learning, his professional and academic careers revolve around advancing knowledge for himself and others. His work helps others learn about subjects that can help them in their personal and professional lives.

Let's do some math together, today!

Contact us today.

Account

Affiliates

About Us

Blog

© 2022 DAVE4MATH.com

Privacy Policy | Terms of Service