Discrete! #11: Discrete Mathematics and Its Applications 1.3B

Quantifiers

HOT DAMN. Guess what, dear readers? You get two new symbols today. The universal quantifier and the existential quantifier.

Quantifiers are aptly named, since they’re essentially a way to take what we’ve already learned and attach quantities. The first version of this is ∀, the universal quantifier.

Let’s start with an example.

Say you have a statement P(x). All values of x are animals. P(x) means “x is delicious.”

So, for x=chicken, P(x) means “Chicken is delicious.” So long as chicken is delicious, P(x) is true. If we’re in some world where chicken is not delicious, we would say P(x) is false.

But say we wanted to make a bigger statement about the deliciousness of animals. Say we wanted to say “All animals are delicious.” From all you know so far, you’d have to write out the function of every animal and put a conjunction between. So, something like P(Aardvark)∧P(Aardwolf)∧P(Armadillo)… ∧P(Zebra). It could be done, but it’s a bit clunky. Instead, we can just write this:

∀xP(x)

The way I like to read that is as follows: “For all of x, it is true that P(x)”

Or, in plain English “All animals are delicious.”

Or, in brief, “For every x, P(x)”

This is the sense in which ∀ is “universal.” It means that some statement is true in all cases. More rigorously, you could say “for the domain in question, aka the domain of discourse, every value of the statement P is true.”

The book also gives a few interesting, but relatively obvious points. For example, if you have a statement P(x) that means “x is equal to 1, 2, 3, or 4″ and you restrict the domain to 1, 2, 3, and 4, then you can say ∀xP(x). I think this stuff is fairly straightforward, so I won’t linger. But, if you’re still a little confused, give it a look.

Got it?

Next, we get the existential quantifier, ∃. It’s a backward E because drawing Sartre was too difficult (HEYO!)

I like to pronounce ∃x as “there is at least one x for which…”

So, to use another example. Let’s say G(x) means “x loves gingers.” We know for sure that ginger love is not universal. In fact, it’s very rarely observed. However, I know that at least my mom likes me. That is, I don’t know how many people love gingers, but I know there is a minimum of 1 such person. There may be more, but there is at least 1.

Mathematically, we’d write it thus:

∃xG(x)

I read that as “There is at least one x for which G(x) is true.

In plain English, “At least one person loves gingers.”

In brief, “For some x, G(x).”

I prefer using the phrase “at least” because it clearly suggests that we don’t know how many there are.

Much like with the P(x) example, in theory you COULD write this out using the symbols we learned earlier. In this case, it’d be a disjunction of every sentient individual in the universe that’d go something like this “Amy loves gingers OR Andy loves Gingers OR Asmodeus loves gingers… OR Zoroaster loves gingers.” In both cases, you’re saying “For this statement to be true, at least 1 person must love gingers.”

BONUS: Other quantifiers.

Oh yes, you get a couple extensions.

One super useful one is the uniqueness quantifier: ∃!. You can read ∃!x as “there is exactly 1 x for which…”

So, for the ginger statement, ∃!xG(x) would mean “There is exactly one person who loves gingers.” You can also stipulate an amount by writing the number below the ∃, so that you can say “there are exactly 2″ or “there are exactly 42.” However, as the book notes, this is generally bad because there are lots of nice rules worked out for plain old ∃, which don’t necessarily apply elsewhere. Plus, as we’ll see later, the uniqueness (or twoness or threeness) quantifiers can all be expressed in terms of the existential and universal quantifiers.

I’m gonna go ahead and clip the lesson there. Next we’ll get into how you can push these things around and add specifications to them.

Next stop: How to use these things!

 

This entry was posted in Autodidaction, Discrete Math. Bookmark the permalink.

2 Responses to Discrete! #11: Discrete Mathematics and Its Applications 1.3B

  1. Harold Tessmann III says:

    I don’t know how widely people use the uniqueness or, uh, quantity quantifiers. The class I took around ten years ago did not use them. I remember specifically one test where you had to write something like “exactly two people like Jim Belushi” using the symbols. I wrote the equivalent of “the cardinality of the subset of people who like Jim Belushi is two”, which the professor didn’t like. The correct answer, which you’ll probably cover in the next section, went something like “there exists an A and B for which A likes Jim Belushi and B likes Jim Belushi and A is not B and also there does not exist a C which likes Jim Belushi unless C is A or C is B”. Or something like that. I haven’t used this type of logic in this form since then.

  2. fletcher says:

    i pronounce ∃!x as “highlander x”

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>