Predicates and quantifiers: ∀ is a loop that must always succeed, ∃ one that must succeed once¶

Level: 101 · for anyone who has met ∀ and ∃ and would like to know which ones can be swapped, and what "not everyone" means

One line: A predicate P(x) is a statement with a hole, filled from a universe of discourse; ∀x P(x) and ∃x P(x) are loops over that universe, which is why ¬ flips one into the other, why quantifiers of the same kind swap and mixed ones swap only one way, and why "everyone likes someone" and "someone is liked by everyone" are different claims.

Predicates¶

"x is prime" is not true or false until x is filled in; it is a predicate, a statement with a hole, written P(x). Fill the hole from a universe of discourse, the set x may range over, and each filling gives a statement: P(7) is true, P(8) is false. A two-place predicate has two holes, L(x, y) for "x likes y". The ∀ is an upside-down A for All and the ∃ a backwards E for Exists; Peano introduced ∃ in 1897 and Gentzen ∀ in 1935, and before that Russell wrote (x) for "for all x". (Dates from memory.)

∀x P(x) says that P(x) holds for every x in the universe. In code it is a loop that must succeed every time: all(P(x) for x in U). ∃x P(x) says some x satisfies P: a loop that must succeed at least once, any(P(x) for x in U). The bounded forms (∀x ∈ A)P(x) and (∃x ∈ A)P(x) run the loop over A instead, and are abbreviations for ∀x (x ∈ A → P(x)) and ∃x (x ∈ A ∧ P(x)). This is why reading a formula treats the axioms of set theory as programs: on a small universe the loops can be run.

Two quantifiers in a row¶

Section 1 of the program takes Cunningham's two small worlds of four people and the relation "x likes y", and evaluates five sentences in each. Same-type pairs do not care about order: ∃x∃y and ∃y∃x both say "someone likes someone", ∀x∀y and ∀y∀x both say "everyone likes everyone". The mixed pair does. ∀x∃y L(x, y) says everyone likes someone, with each person free to choose; ∃y∀x L(x, y) says one person y is liked by everyone. In world B everyone likes someone and nobody is liked by everyone, so the first is true and the second false, and the two sentences cannot be equivalent.

Section 2 checks the interchange laws on all 65 536 relations on four people: the same-type swaps always hold, ∃y∀x always implies ∀x∃y, and the converse fails in more than half the relations. The rule to remember: a quantifier that comes later may depend on the ones before it. In ∀x∃y, y is chosen after x and may depend on it; in ∃y∀x, y is chosen first and must work for every x. Example 4 of the book, in section 5, is the same thing on the integers: ∀x∃y (x + y = 0) is true, each x having its own y = −x, and ∃y∀x (x + y = 0) is false.

Negation flips the quantifier¶

"Not everyone passed" means "someone failed"; "nobody passed" means "everyone failed". Section 3 checks both laws on every predicate over a four-point universe, 16 predicates in all: ¬∀x P(x) ⇔ ∃x ¬P(x), and ¬∃x P(x) ⇔ ∀x ¬P(x). Pushing a ¬ through a quantifier flips it, and then it goes through the next one, so ¬∀x∃y L(x, y) is ∃x∀y ¬L(x, y): someone likes nobody. This is De Morgan's law for infinitely many conjuncts, and it is how every "there is no set such that…" in the axioms chapter is written.

Distribution: two laws hold, two fail¶

∃ distributes over ∨ and ∀ over ∧, and section 4 confirms both on all 256 pairs of predicates. The other two pairings fail, and the counterexamples are worth keeping: "everyone is P or Q" does not make everyone P or everyone Q (half the room can be each), and "someone is P and someone is Q" does not make one person both. Cunningham's Quantifier Distribution Laws 1.3.5 and 1.3.6 list exactly the ones that hold, plus the bounded versions, and the two that fail are the ones his list leaves out.

Section 5 ends with "exactly one", ∃!x P(x), written with the two quantifiers you have: some x has P, and any two that have it are equal. The axioms chapter uses this form for replacement.

What the program prints¶

Verified output of predicates_and_quantifiers.py — regenerated by tools/run_examples.py, never hand-typed.

1. 'x LIKES y' IN TWO SMALL WORLDS (CUNNINGHAM, FIGURES 1.3 AND 1.4)
   world A: a likes a, a likes c, b likes a, b likes c, c likes c, d likes c
   world B: a likes a, b likes c, c likes b, d likes c
   sentence       in English                      world A  world B
   ∃x∃y L(x,y)    someone likes someone              True     True
   ∃y∃x L(x,y)    someone is liked by someone        True     True
   ∀x∀y L(x,y)    everyone likes everyone           False    False
   ∀x∃y L(x,y)    everyone likes someone             True     True
   ∃y∀x L(x,y)    someone is liked by everyone       True    False
   The mixed pair differs in world B: everyone likes someone, but nobody
   is liked by everyone. ∀x∃y and ∃y∀x are different sentences.

2. INTERCHANGE LAWS, CHECKED ON ALL 65,536 RELATIONS ON FOUR PEOPLE
   ∃x∃y ⇔ ∃y∃x: True     ∀x∀y ⇔ ∀y∀x: True     ∃y∀x ⇒ ∀x∃y: True
   ∀x∃y ⇒ ∃y∀x fails in 35714 of 65536 relations; world B is one of them.
   Same-type quantifiers swap freely; a mixed pair swaps one way only.

3. NEGATION LAWS, ON EVERY PREDICATE OVER {a, b, c, d}
   ¬∀x P(x) ⇔ ∃x ¬P(x): True      ¬∃x P(x) ⇔ ∀x ¬P(x): True   (16 predicates)
   bounded: ¬(∀x∈A)P(x) ⇔ (∃x∈A)¬P(x), every A and P: True
   Pushing ¬ through a quantifier flips it: 'not everyone' is 'someone not'.

4. DISTRIBUTION LAWS: TWO HOLD, TWO FAIL
   ∃x(P∨Q) ⇔ ∃xP ∨ ∃xQ      holds for all 256 pairs: True
   ∀x(P∧Q) ⇔ ∀xP ∧ ∀xQ      holds for all 256 pairs: True
   ∀x(P∨Q) ⇔ ∀xP ∨ ∀xQ      holds for all 256 pairs: False   e.g. P true on {a}, Q true on {b, c, d}
   ∃x(P∧Q) ⇔ ∃xP ∧ ∃xQ      holds for all 256 pairs: False   e.g. P true on {a}, Q true on {b}
   'Everyone is P or Q' does not make everyone P or everyone Q; 'someone is
   P and someone is Q' does not make one person both.

5. 'EXACTLY ONE' FROM ∃ AND ∀, AND EXAMPLE 4 ON THE INTEGERS
   ∃!x P(x) ⇔ ∃xP(x) ∧ ∀x∀y((P(x)∧P(y)) → x = y), every P: True
   over the integers −5..5:  ∀x∃y (x + y = 0): True     ∃y∀x (x + y = 0): False
   Every x has its own y = −x; no single y works for all x.

Po polsku, w skrócie¶

Predykat P(x) to zdanie z luką, która wypełnia się elementem uniwersum; P(7) „7 jest pierwsza" jest prawdą, P(8) fałszem. ∀x P(x) (odwrócone A od All) mówi, że P zachodzi dla każdego x: pętla, która musi się udać za każdym razem, w Pythonie all(P(x) for x in U). ∃x P(x) (odwrócone E od Exists) mówi, że dla jakiegoś x: pętla, która musi się udać raz, any(...). Kwantyfikatory tego samego rodzaju można zamieniać, mieszanych nie: ∀x∃y „każdy kogoś lubi" i ∃y∀x „ktoś jest lubiany przez wszystkich" to różne zdania, i program sprawdza na wszystkich 65 536 relacjach na czterech osobach, że drugie pociąga pierwsze, ale nie odwrotnie. Negacja odwraca kwantyfikator: „nie każdy" to „ktoś nie", „nikt" to „każdy nie". ∃ rozdziela się względem ∨, a ∀ względem ∧; dwa pozostałe „prawa" są fałszywe i program podaje kontrprzykłady. „Dokładnie jeden" (∃!) zapisuje się przez ∃ i ∀: ktoś ma własność P, a każdych dwóch, którzy ją mają, to ta sama osoba.

Auf Deutsch: Stichwörter¶

∀ ist eine Schleife, die immer gelingen muss, ∃ eine Suche, die einmal fündig wird; Negation vertauscht die beiden.

Stichwörter: Prädikat, Allquantor ∀, Existenzquantor ∃, Variable, Grundbereich, Negation von Quantoren, Reihenfolge der Quantoren, Schleife und Suche.

Run it yourself¶

From the root of your clone of this repository:

python3 11_Logic/predicates_and_quantifiers/examples/predicates_and_quantifiers.py