[HD] EECS3342 F26 - 2026-09-22 (Tuesday) - Lecture 4

Overview

Jackie Wang reviews proof and disproof strategies for universal, existential, and nested quantifiers, then introduces set notation, set comprehension, and counting subsets with the choose operator. Examples include disproving a universal claim with a counterexample, explaining why one failed case cannot disprove an existential claim, and deriving that choosing 3 elements from 5 gives 5·4·3/3! = 10 sets.

Key takeaways

To disprove a universal implication, give one in-range value that makes the antecedent true and the consequent false; x = 1 refutes the claim that every integer from 1 to 10 is greater than 1.
To disprove an existential claim, one failed example is insufficient: show the range is empty or show that every in-range value fails the property.
Nested quantifiers require handling each layer separately: an outer counterexample i = 1 makes “there exists a natural j with 1 + j = 0” false because the required j = −1 is not natural.
In set comprehension, the constraint selects values to consider while the expression before the vertical bar determines the actual members; mapping x to 2x for x ∈ {0,1,2} yields {0,2,4}.
The number of size-i subsets of n elements is n! / ((n − i)!i!): count ordered selections, then divide by i! to remove order.
Complement symmetry can simplify calculations: 10 choose 8 equals 10 choose 2, which evaluates to 45.

Chapters

0:00 Lab Deadlines and the Rodin Programming Test

Lab 1 is due September 23 at 11:59 p.m.; students need to submit it to receive credit.
Lab 2 is due September 30, and its English requirements and individual steps are relevant practice for the programming test.
The sole programming test is scheduled for November 7 during each student's live-session slot in Lassonde Building 102.
Jackie Wang emphasizes practicing specification entry in Rodin, not just understanding the material; an Event-B summary and sample test are planned.

2:36 Reviewing Proof Strategies for Universal and Existential Claims

For a universal implication, a proof can be vacuous if its range constraint is always false.
Otherwise, proving a universal implication means showing that every value satisfying the range constraint also satisfies the property.
To prove an existential claim, provide one witness that satisfies both the range and the property.

4:38 Counterexamples for Universals and Disproofs of Existentials

A universal implication is false when one in-range witness makes the antecedent true and the consequent false.
An existential conjunction is false if its range is empty, or if every in-range value makes the property false.
The truth-table case true implies false is the counterexample pattern for a universal implication.

10:55 Testing Quantifier Strategies with Integer Intervals

For integers from 1 through 10, the claim that every value is greater than 0 is true because each in-range integer satisfies the property.
The claim that every integer from 1 through 10 is greater than 1 is false; x = 1 is a counterexample.
The existential claim that some integer from 1 through 10 is greater than 1 is true, with x = 2 as a witness.
The same x = 1 failure does not disprove that existential claim; disproof requires showing every in-range value fails.

20:24 Disproving a Nested Quantifier with Natural Numbers

In the example, the outer variable i ranges over integers and the inner existential variable j ranges over natural numbers.
Choosing i = 1 makes the inner condition “there exists a natural j such that 1 + j = 0” false.
No natural number j can equal −1, so this single outer witness disproves the universal claim.
A written justification can state either the formal range condition or explain in words why the required negative j is unavailable.

27:33 Deriving a Quantifier Equivalence with De Morgan's Laws

Jackie Wang proves that for all x, R(x) implies P(x) is equivalent to saying there does not exist an x for which R(x) and not P(x).
The derivation applies the axiom “for all x, Q(x)” iff “not exists x, not Q(x)” to the implication.
Expanding implication as not R(x) or P(x), then applying De Morgan's law and double negation, yields the counterexample form.
The second quantifier-conversion identity is assigned as an exercise; additional axioms needed for later proofs will be supplied.

38:48 Set Basics: Order, Duplicates, and Cardinality

Sets have no ordering: {1, 2, 3} and {2, 3, 1} denote the same set.
Sets have no duplicates, so an element is counted only once even if repeated in a written list.
Cardinality, written with vertical bars such as |{1, 2, 3}|, is the number of distinct members; here it is 3.

42:11 Set Comprehension: Constraints and Member Expressions

Set comprehension uses braces with a vertical bar to separate a member expression from a constraint.
The constraint specifies which values to consider; it can be a proposition, predicate, implication, or quantified condition.
The expression to the left of the bar specifies the form of the members included in the resulting set.

45:48 Evaluating Set Comprehension for Numbers and Pairs

For natural x with 0 ≤ x ≤ 2, the expression x produces {0, 1, 2}, while the expression 2x produces {0, 2, 4}.
The values satisfying the constraint need not themselves be the final members; the left-side expression transforms them.
With x ∈ {1, 2} and y ∈ {3, 4}, the pair expression (x, y) generates four members: (1,3), (1,4), (2,3), and (2,4).
The pair set has cardinality 2 × 2 = 4.

50:40 Counting Three-Element Sets from Five Values

To count size-3 sets chosen from {1, 2, 3, 4, 5}, first count ordered sequences of length 3 without repetition.
There are 5 choices for the first position, 4 for the second, and 3 for the third.
The sequence count is 5 × 4 × 3; a separate adjustment is needed because sets do not preserve order.

52:46 Removing Sequence Order to Count Distinct Sets

Each fixed three-element set appears as 3! = 6 different sequences, such as the six orderings of {1, 3, 5}.
Dividing the 5 × 4 × 3 sequences by 3! removes the ordering duplicates.
The resulting count of distinct three-element sets is 5 × 4 × 3 / 3! = 10.

57:17 The Choose Operator and Its Factorial Formula

The choose operator n choose i counts the number of size-i sets formed from n distinct elements, where n ≥ i ≥ 0.
Its formula is n! / ((n − i)! i!).
The numerator after cancellation contains i descending factors, counting ordered selections; division by i! removes their order.
For example, 10 choose 8 can be simplified using symmetry to 10 choose 2.

1:02:43 Special Choose Identities and Complement Counting

For any n, n choose n = 1 because there is only one way to select all n elements.
For any n, n choose 0 = 1 because there is only one empty set.
The symmetry identity n choose i = n choose (n − i) counts a selection by instead choosing the elements to exclude.
For a class of 50 students, selecting 45 is equivalent to choosing the 5 students not selected.

1:08:49 Calculating 10 Choose 8 and Preparing for Power Sets

Using symmetry, 10 choose 8 = 10 choose 2 = (10 × 9) / 2! = 45.
Jackie Wang recommends reviewing both the choose formula and its sequence-counting derivation before the next lecture.
The upcoming material moves toward power sets, relations, and further counting applications.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Jackie Wang.