Predicate Formulas

“I believe there is one true soul mate for every person.”
“He must be very busy.”
—Scott Adams, Dilbert

Once we start talking about proofs in Predicate Logic, we’ll see that there’s often a close correspondence between the structure of formulas and the structure of their proofs. It is therefore important to be able to read an English-language (mathematical) statement and understand what sort of formula it corresponds to, since that tells us how to approach a proof of that statement.

Especially when it comes to predicate logic, we can’t always rely on the sentence to have obvious keywords like “if…then…“. Similarly, quantifiers are often left implicit.

The following examples show this in action:

Example

  1. Definition: S⊆TS\subseteq T if every element of SS is an element of TT.

    Translation:

    ∀S ∀T ( S⊆T⟷∀x (x∈S → x∈T) )\forall S\ \forall T\ \bigl(\,S\subseteq T \longleftrightarrow \forall x\,(x\in S\ \to\ x\in T)\,\bigr)

  2. Definition: Two sets are disjoint if they have no element in common

    Translation:

    ∀S ∀T ( disjoint(S,T)⟷¬∃x (x∈S ∧ x∈T) )\forall S\ \forall T\ \bigl(\,\mathrm{disjoint}(S,T) \longleftrightarrow \lnot \exists x\,(x\in S\ \land\ x\in T)\,\bigr)

or:

⟷∀x (x∉S ∨ x∉T) ) \longleftrightarrow \forall x\,(x\not\in S\ \lor\ x\not\in T)\,\bigr)

where x∉Sx\not\in S means ¬(x∈S)\lnot(x\in S).

  1. The union of two nonempty sets is nonempty.

    Translation:

    ∀S ∀T ( (∃x x∈S)∧(∃y y∈S) → (∃z z∈S∪T) )\forall S\ \forall T\ \bigl(\,(\exists x\ x\in S) \land (\exists y\ y \in S)\ \to\ (\exists z\ z\in S\cup T)\,\bigr)

Example

  1. Definition: A function ff is idempotent if f(x)=f(f(x))f(x) = f(f(x)).

    Translation:

    ∀f (idempotent(f)⟷∀x ( f(x)=f(f(x)) ))\forall f\ \biggl(\mathrm{idempotent}(f) \longleftrightarrow \forall x\ \bigl(\,f(x) = f(f(x))\,\bigr)\biggr)

  2. Definition: yy is a fixed point of ff if f(y)=yf(y) = y.

    Translation:

    ∀f ∀y ( fp(f,y)⟷f(y)=y )\forall f\ \forall y\ \bigl(\,\mathrm{fp}(f,y) \longleftrightarrow f(y) = y\,\bigr)

  3. (Notation: Rng(f)\mathrm{Rng}(f) is the range of ff, the set of possible outputs.)

    (Notation: Fix(f)\mathrm{Fix}(f) is the set of fixed points of ff.)

    Theorem: Every idempotent function has a range equal to its fixed points.

    Translation:

    ∀f ( idempotent(f)→Rng(f)=Fix(f) )\forall f\ \bigl(\,\mathrm{idempotent}(f) \to \mathrm{Rng}(f) = \mathrm{Fix}(f)\,\bigr)

Example

  1. Set SS is empty (contains no elements).

    Translation:

    ¬∃x x∈S\lnot \exists x\ x\in S

    or

    ∀x x∉S\forall x\ x\not\in S

    (where x∉Sx\not\in S means ¬(x∈S)\lnot(x\in S).)

  2. Set SS has at least one element.

    Translation:

    ∃x x∈S\exists x\ x\in S

    i.e., there exists something that is an element in SS.

  3. Set SS has exactly one element.

    Translation:

    ∃x (x∈S∧¬∃y (y∈S∧x≠y))\exists x\ \bigl(x\in S \land \lnot\exists y\ (y\in S \land x\not= y)\bigr)

    (where x≠yx\not= y means ¬(x=y)\lnot(x = y)), i.e., there is one element xx in SS and no element in SS is different from xx.

    Or,

    ∃x (x∈S∧∀y (y∈S→y=x))\exists x\ \bigl(x\in S \land \forall y\ (y\in S \to y=x)\bigr)

    i.e., there is an element is SS such that every element in SS is equal to it.

  4. Set SS has at least two elements.

    Translation:

    ∃x ∃y (x∈S∧y∈S∧x≠y)\exists x\ \exists y\ (x\in S\land y\in S\land x\not= y)

  5. Set SS has exactly two elements.

    Translation:

    ∃x ∃y (x∈S∧y∈S∧x≠y∧∀z (z∈S→z=x∨z=y))\exists x\ \exists y\ \bigl(x\in S \land y\in S\land x\not= y\land \forall z\ (z\in S\to z=x\lor z=y)\bigr)

    i.e., there are two elements xx and yy in SS that are different from each other, and every element in SS is either xx or yy.