Existential Quantifier (∃)

Math for CS · Axiom Academy

"There exists" — proving that at least one element satisfies a property The symbol is a backwards "E" — think E for "Exists." The claim is satisfied even if only a single element works; it does not need to be true for all elements. Let the domain be (all integers). x\,(x^2 = 4) — True. Witness: x = 2 (or x = -2 ). x\,(x^2 = 3) — False over (no integer squared gives 3). But True over since x = works. x\,(x > x + 1) — False. No number is greater than itself plus one. To prove x\, P(x) , you just need to find one witness — a specific value of x that makes P(x) true. This is called a constructive proof — you exhibit the witness directly. Sometimes non-constructive proofs show a witness must exist without finding it explicitly. To show x\, P(x) is false , you must show that no element in the domain satisfies P . In other words, you must prove x\, P(x) . This is one of the most important rules in predicate logic: In English: "There does NOT exist an x with property P " means the same as "For ALL x , property P fails." Existential claims appear throughout computing: Search algorithms: array.some(x => x > 10) checks x ,\; x > 10 SQL: SELECT * FROM users WHERE EXISTS (SELECT 1 FROM orders WHERE orders.user_id = users.id) Regular expressions: A regex match on a string is an existential claim — "there exists a substring matching this pattern" SAT solvers: "Does there exist an assignment of variables that satisfies this Boolean formula?"

This is the written version of the interactive lesson above. See the full Math for CS course.