Quantified Statements

These are known as quantifiers

Universal Statement

Definition

Let $Q(x)$ be a predicate and $D$ the domain of $x$ A universal statement is a statement of the form "$\forall x\in D,Q(x)$" i.e. Says that a certain property is true for ALL elements in a set

Example

All positive integers are greater than zero

Keywords

• All
• Every
• Any

Symbol

$\forall$

Negation

Negation of a universal statement (“all are”) $\equiv$ existential statement (“some are not” / “there is at least one that is not”) $\sim (\forall x\in D,P(x))\equiv \exists x\in D\text{ such that}\sim P(x)$

Notes

A value for $x$ for which $Q(x)$ is false is called a counterexample Implicit Quantification: Sometimes, quantification has to be inferred from context

• If $x>2$ then $x^2>4$
• Is interpreted to mean: $\forall$ real numbers $x$, (if $x>2$ then $x^2>4$)

Conditional Statement

Definition

Says that IF one thing is true, THEN another thing also has to be true

Example

If 378 is divisible by 18, then 378 is divisible by 6

Keyword

if … then

Symbol

$\to$

Universal Conditional Statement

Definition

$\forall x(P(x)\to Q(x))$ $\forall x(\text{if }P(x)\text{ then }Q(x))$ Note: if not specified, “for all” is for the whole domain: $\forall x\in D$, where $D$ is the domain of $x$

Equivalent Forms

By changing the domain, a universal conditional statement can be converted to a universal statement: Suppose $\forall x\in U(P(x)\to Q(x))$ By narrowing $U$ to be the set of all values that make $P(x)$ true, set $D$, $\forall x\in D,Q(x)$

Negation

$\sim (\forall x(P(x)\to Q(x)))\equiv \exists x\text{ such that}\sim (P(x)\to Q(x))$ -(A) $\sim (P(x)\to Q(x))\equiv P(x)\wedge \sim Q(x)$ -(B) Substitute (B) into (A) $\sim (\forall x(P(x)\to Q(x)))\equiv \exists x\text{ such that}(P(x)\wedge \sim Q(x))$

Vacuous Truth

$\forall x\in D(P(x)\to Q(x))$ is vacuously true or true by default iff $P(x)$ is false for every $x$ in $D$ (or $D$ is an empty set)

Variants

Variants mentioned in Logical Conditional Statements can be extended to universal conditional statements They follow the same relations to each other (statement $\equiv$ contrapositive etc.)

Existential Statement

Definition

Let $Q(x)$ be a predicate and $D$ the domain of $x$ An existential statement is a statement of the form "$\exists x\in D\text{ such that }Q(x)$" Says that there is at least one thing for which the property is true

Example

There is a prime number that is even

Keywords

• There exists
• There is
• Some

Symbol

$\exists$

Negation

Negation of an existential statement (“some are”) $\equiv$ universal statement (“none are” / “all are not”) $\sim (\exists x\in D\text{ such that }P(x))\equiv \forall x\in D,\sim P(x)$

Notes

$\exists !$ denotes “there exists a unique” or “there is one and only one”

Multiply Quantified Statements

Multiple quantifiers can be used for a single statement e.g. $\forall x\in D,\exists y\in D\text{ such that }P(x,y)$

Negation

Negate statements “from outside in” $\sim (\forall x\in D,\exists y\in E\text{ such that }P(x,y))$ $\equiv \exists x\in D\text{ such that}\sim (\exists y\in E\text{ such that }P(x,y))$ $\equiv \exists x\in D\text{ such that }\forall y\in E,\sim P(x,y)$