Predicates

We had a problem before with the truth of “That guy is going to the store.”
- The problem was that we couldn't decide if it was true or false, because the sentence didn't specify who “that guy” is. Some are going to the store, and some are not.
We also have similar things elsewhere in mathematics.
- We say things like “\(x/2\) is an integer”. That is true for some \(x\) but not others.
- It's not a proposition either.
A predicate is a statement with variables.
- Written with a capital letter and the variables listed as arguments, like \(P(x,y,z)\).
We can express these two things using predicates.
- Let \(P(x)\) be true if \(x\) is going to the store.
- Let \(Q(x)\) be true if \(x/2\) is an integer.
Now we have something that can get a truth value. In other words, be a proposition.
- Once the variable has a value fixed, it is a proposition.
- e.g. \(Q(8)\) is a true proposition and \(Q(9.3)\) is a false proposition.
The same logical manipulations can be done with predicates.
- Let \(R(x,y)\) be \(P(x)\wedge Q(y)\).
- Then \(R(5, \mathrm{John})\) is false (no matter what John is doing now, because of the domination law).

Quantifiers

Two more sentences that we can't express logically yet:
- “Everyone in this class will pass the midterm.”
- “Someone in this room is sleeping now.”
We can express the simpler versions about one person
- “\(x\) will pass the midterm.” and “\(y\) is sleeping now.”
The universal quantifier is used to denote sentences with words like “all” or “every”.
- The notation is \(\forall x P(x)\), meaning “for all \(x\), \(P(x)\) is true.”
- When specifying a universal quantifier, we need to specify the domain of the variable. (Or universe of discourse if you want another term.)
- e.g. Let \(P(x)\) be true if \(x\) will pass the midterm. The statement “everyone in this class will pass the midterm” can be translated as \(\forall x P(x)\) where the domain of \(x\) is people in this class.
The existential quantifier is used to denote sentences with words like “some” or “there is a”.
- The notation is \(\exists x P(x)\), meaning “there is at least one \(x\) where \(P(x)\) is true.”
- Again, we need to specify the domain of the variable.
- e.g. Let \(Q(x)\) be true if \(x\) is sleeping now. “Someone in this room is sleeping now” can be translated as \(\exists x Q(x)\) where the domain of \(x\) is people in this room.
The \(\forall\) and \(\exists\) are in some ways like \(\wedge\) and \(\vee\).
- That is, we we could make a list of everyting in the domains (\(a_1,a_2,a_3,\ldots\)), we would have these: \[\forall x P(x) \equiv P(a_1) \wedge P(a_2) \wedge P(a_3) \wedge \cdots\\ \exists x P(x) \equiv P(a_1) \vee P(a_2) \vee P(a_3) \vee \cdots \]
For example, if we let \(P(x)\) be the predicate “\(x\) is a person in this class”, \(D(x)\) be “\(x\) is a DDP student”, and \(F(x,y)\) be “\(x\) has \(y\) as a friends”. The domain for them will be all people. How would we translate these?
- “There is someone in the DDP program.”
- “Everyone in this class is a DDP student.”
- “Someone in this class is a DDP student.”
- “Everyone is their own friend.”
- “Everyone has a friend who is a DDP student.”
- “Nobody is both in this class and a DDP student.”
- \(\exists x D(x)\)
- \(\forall x \exists y F(x, y)\)
- \(\exists y \forall x F(x, y)\)
When translating to Enlish, “For every person \(x\), \(x\) is…” is a bad answer.
- “Everyone is…” is good.
- Try make natural-sounding sentences. Don't just transcribe the logic.
We have versions of De Morgan's Laws for quantifiers: \[ \neg\exists x P(x) \equiv \forall x \neg P(x)\\ \neg\forall x P(x) \equiv \exists x \neg P(x) \]
- For example, “There are no DDP students” and “Everyone is not a DDP student” are equivalent: \(\neg\exists x D(x) \equiv \forall x \neg D(x)\).

Nested Quantifiers

When we have one quantifier inside another, we need to be a little careful.
- Consider these two propositions about arithmetic (over the integers): \[ \forall x \exists y(x+y=0)\\ \exists y \forall x(x+y=0) \]
- The first is true: if you pick any \(x\), I can find a \(y\) that makes \(x+y=0\) true.
- The second is false: there is no \(y\) that will make \(x+y=0\) true for every \(x\).
- So the order of the quantifiers must matter, at least sometimes.
But it turns out these are equivalent: \[\forall x \forall y P(x,y)\equiv \forall y \forall x P(x,y) \\ \exists x \exists y P(x,y)\equiv \exists y \exists x P(x,y)\]
- i.e. you can swap the same kind of quantifier (\(\forall,\exists\)).
- Informally: \(\forall\) is essentially a bunch of \(\wedge\)s, and \(\exists\) is essentially a bunch of \(\vee\)s. By the commutative law, we can re-order those as much as we want, as long as they're the same operator.