CS2050 L03 Predicates and Quantification
Watch on YouTube →
Overview
Abrahim Ladha introduces predicates as propositional functions with free variables, then shows how existential and universal quantifiers bind those variables to form propositions over a universe of discourse. Examples with numbers, ducks, elephants, sailors, and truth values develop quantifier order, negation rules, unique existence, and ways to express claims such as there being no largest number or exactly two objects.
Key takeaways
- A predicate such as P(n): n > 7 is not a proposition while n remains free; evaluating n or binding it with ∃ or ∀ produces a statement with a truth value.
- The universe of discourse determines what variables range over, so ∀n Even(n) means different things depending on whether n ranges over natural numbers, integers, or another collection.
- Quantifier order matters: ∀x∃y P(x,y) allows a different y for each x, while ∃y∀x P(x,y) requires one shared y that works for every x.
- A universal statement is false exactly when there is a counterexample: not (∀x P(x)) is equivalent to ∃x not P(x).
- Unique existence can be expressed with ordinary quantifiers by asserting one witness and ruling out every distinct second witness.
- The claim that there is no largest number is ∀x∃y(y > x), while exactly two objects exist requires two distinct witnesses and a universal condition excluding any third.
Chapters
- Derives the negation of P implies Q as P and not Q using material implication, De Morgan's law, and double negation.
- Demonstrates P and (P or Q) equivalent to P or (P and Q) using distribution and idempotency.
- Derives contraposition, P implies Q equivalent to not Q implies not P, through material implication and commutativity.
- Requires proofs to begin with the left side, apply only listed laws, and show each transformation rather than manipulate both sides at once.
- Defines a predicate as a propositional function whose truth value depends on its free variables, such as P(n): n is greater than 7.
- Evaluating P(10) makes a proposition that is true, while P(2) is false; evaluating the variable removes its freedom.
- Uses P(x,y) to mean that if x exceeds 0, then x + y equals 10, illustrating predicates with multiple arguments and vacuous truth.
- Explains that the universe of discourse, such as numbers, affects how a free variable is interpreted.
- Motivates quantification with the claim that there exists an even number, which basic propositional logic cannot express using only a predicate like Even(n).
- Introduces the existential symbol ∃ and reads ∃x Even(x) as there exists an x such that x is even.
- Explains that a variable can become non-free either by evaluating it to an object or binding it with a quantifier.
- Credits Gottlob Frege with developing modern quantification, distinguishing it from the older language-based logic associated with Aristotle.
- Defines P(x,y) as the duck x being heavier than the elephant y, with x ranging over ducks and y over elephants.
- Shows ∃x P(x,y) means some duck is heavier than the still-unspecified elephant y, so the result remains a predicate.
- Shows ∃y P(x,y) means duck x is heavier than some elephant, also leaving x free.
- Binds both variables in ∃x∃y P(x,y), a proposition meaning some duck is heavier than some elephant.
- Introduces ∀ for claims expressed by every, for all, and for each, contrasting it with existential quantification.
- Uses P(n): n is even to show ∀n P(n) means every number is even, a proposition that is false.
- Applies quantifiers to P(x,y): ∀x P(x,y) says every duck is heavier than elephant y, while ∀y P(x,y) says duck x is heavier than every elephant.
- Combines ∀x∀y P(x,y) to claim every duck is heavier than every elephant, false if a counterexample pair exists.
- Establishes that not (∀x P(x)) is equivalent to ∃x not P(x): one counterexample disproves a universal claim.
- Connects quantifier negation to De Morgan's law by treating a universal claim informally as an infinite conjunction and its negation as an existential disjunction.
- Warns that an infinitely long conjunction is an explanation aid, not a formula permitted by ordinary propositional logic.
- Distinguishes a proof that a universal statement is false from proving that a particular example fails.
- Contrasts ∃x∀y P(x,y), one duck heavier than every elephant, with ∀x∃y P(x,y), each duck heavier than some elephant.
- Uses a predicate over true and false values to show ∀x∃y R(x,y) can be true while ∃y∀x R(x,y) is false.
- Explains the sailor-and-hat example: every sailor can have a different hat, whereas a hat for all sailors requires one shared hat.
- Advises against rearranging quantifiers without justification because changing their order can change truth conditions.
- Introduces ∃!x P(x) to mean exactly one object satisfies P, adding uniqueness to the ordinary claim ∃x P(x).
- Distinguishes at least one even number from exactly one even number; ordinary existence does not imply uniqueness.
- Expresses unique existence using only ∃ and ∀: ∃x(P(x) and ∀y(x ≠ y implies not P(y))).
- Explains the uniqueness condition as ruling out every distinct y that also satisfies P.
- Translates the informal claim that there is no largest number into ∀x∃y(y > x).
- Highlights that the witness y may depend on each chosen x, so the quantifier order captures the intended unboundedness.
- Connects the formal statement to the idea that a larger number can always be found, for example by adding one.
- States the quantifier De Morgan laws: not (∃x P(x)) is equivalent to ∀x not P(x), and not (∀x P(x)) is equivalent to ∃x not P(x).
- Notes that the second equivalence can also be derived from the first using double negation.
- Shows ∀n(Even(n) or Odd(n)) differs from (∀n Even(n)) or (∀n Odd(n)).
- For natural numbers, every number is even or odd, but it is false that every number is even or that every number is odd.
- Starts with the negation of ∃!x P(x), expanding unique existence into existence plus a condition excluding every other satisfying object.
- Pushes negation inward using quantifier De Morgan laws, propositional De Morgan's law, implication equivalence, and double negation.
- Interprets the result as either no object satisfies P or at least two distinct objects satisfy P.
- Shows why negating uniqueness is more involved than simply negating an ordinary existential claim.
- Introduces prenex normal form, in which a proposition's quantifiers are arranged before its predicate, as in ∀x∃y∀z P(x,y,z).
- Explains that quantified statements can be reorganized into a form with the quantification first, even if the resulting expression is less natural.
- Connects the notation to ordinary language, where a claim often identifies an object before describing its properties.
- Builds an exactly-two claim from ordinary existential and universal quantifiers rather than relying on a special numeral quantifier.
- Requires two distinct witnesses, ∃x∃y with x ≠ y, to express that at least two objects exist.
- Adds ∀z(z = x or z = y) to require every object in the universe of discourse to be one of those two.
- Clarifies that equality depends on the chosen interpretation and that the claim concerns exactly two objects up to that equality.
Transcript excerpt
0:01 All right, let's get started. This is CS2050. Um before we get started on the actual topics today, let's just review kind of what we did last time. There are uh a big list of laws of thought and then for each one we kind of justified it. But you should justify them based on a truth table. We can do uh I'm not going to rewrite all the laws today, but let's just do some more examples before we get into a new topic. So for example, let's demonstrate that the negation of P implies Q is equivalent to the negation of P, sorry, P and the negation of Q, right? Now there is a big list of laws of thought on the PDF that you can look at and you should know which ones that you like based on the list of which ones you
0:47 can apply, which ones you can't apply. Again, um when you're on an exam or something, you'll be given the laws and on the homework it's expected you know which laws you could do, right? Uh let me just do this and then I'll just give some commentary on it, right? So what we do first is we write the left side. We do P implies Q. So it's equivalent to and then we need to choose uh a law and apply it here. Which one should we choose? Yeah. >> CDE >> CDE. So by CDE, this is equivalent to the negation of uh negation of P or Q. Another term for CDE you may see is called material implication, but uh CDE is what we use in this class. Um now what should I do? >> De Morgan's >> Yeah, so let's say I do De Morgan's.
1:35 >> [clears throat] >> And what do I get?
This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.
Related notes
Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Abrahim Ladha.