Appendix A

Mathematical Notation

We use the symbol to mean “equals by definition.”

If P and Q are propositions, so too are ¬P (read as “not P”), P Q (“P or Q”), P Q (“P and Q”), P Q (“P implies Q”), and P Q (“P is equivalent to Q”). For equivalence, we often write “P if and only if Q”.

If P is a proposition and x is a variable, (∃x)P is a proposition (read as “there exists x such that P”). If P is a proposition and x is a variable, (∀x)P is a proposition (read as “for all x, P”); (∀x)P (¬(∃x)¬P).

We use this vocabulary from set theory:

a X (“a is an element of X”)

X ⊂ Y (“X is a subset of Y”)

{a₀, ..., a_n} (“the finite set with elements a₀, ..., and a_n”)

{a X|P(a)} (“the subset of X for which the predicate P holds”)

X ∪ Y (“the union of X and Y”)

X ∩ Y (“the intersection of X and Y”)

X × Y (“the direct product of X and Y”)

f : X → Y (“f is a function from X to Y”)

f : X₀ × X₁ → Y (“f is a function from the product of X₀ and X₁ to Y”)

x ε (x)(“x maps to ε(x)”, always given following a function signature)

A closed interval [a, b] is the set of all elements x such that a ≤ x ≤ b. An open interval (a, b) is the set of all elements x such that a < x < b. A half-open-on-right interval [a, b) is the set of all elements x such that a ≤ x < b. A half-open-on-left interval (a, b] is the set of all elements x such that a < x ≤ b. A half-open interval is our shorthand for half-open on right. These definitions generalize to weak orderings.

We use this notation in specifications, where i and j are iterators and n is an integer:

i j (“i precedes j”)

i j (“i precedes or equals j”)

[i, j) (“half-open bounded range from i to j”)

[i, j] (“closed bounded range from i to j”)

(“half-open weak or counted range from i for n ≥ 0”)

(“closed weak or counted range from i for n ≥ 0”)

We use this terminology when discussing concepts:

Weak refers to weakening, which includes dropping, an axiom. For example, a weak ordering replaces equality with equivalence.

Semi refers to dropping an operation. For example, a semigroup lacks the inverse operation.

Partial refers to restricting the definition space. For example, partial subtraction (cancellation) a – b is defined when a ≥ b.