This section fixes the set-theoretic and logical language of the series. It defines sets, functions and relations; proves that a function has a two-sided inverse exactly when it is bijective (Theorem 1.1), that the classes of an equivalence relation partition the set (Proposition 1.2), and that a partial order and its strict companion determine each other (Proposition 1.3); fixes the conventions of proof; and closes with three tables giving the spoken form of every recurring symbol (§1.5).
A set is a collection of distinct objects, its elements; one
writes
A function
A function
Suppose a two-sided inverse g exists. If
For
A binary relation on A is a subset
Let ∼ be an equivalence relation on a set A . The distinct equivalence classes partition A : they are nonempty, pairwise disjoint, and their union is A .
Reflexivity gives
The volume uses this construction to form the integers modulo n (§2) and the cosets of a subgroup (§3).
A second kind of relation orders elements rather than identifying them. A
partial order on A is a relation ⪯ that is reflexive,
transitive, and antisymmetric:
Every partial order has a strict companion,
If ⪯ is a partial order on A , its strict companion ≺
is irreflexive (
Irreflexivity of the companion is the clause
A strict order ≺ is a strict total order when its non-strict
companion is total, equivalently when for all
We employ the symbols ∀ (“for all”), ∃ (“there exists”), ∃ ! (“there exists a unique”), and “ : ” or “s.t.” for “such that”. Negation swaps the quantifiers: ¬ (∀ x P (x)) is ∃ x ¬ P (x) , and ¬ (∃ x P (x)) is ∀ x ¬ P (x) . The order of unlike quantifiers matters: ∀ x ∃ y P (x, y) (the y may depend on x ) is weaker than ∃ y ∀ x P (x, y) (one y works for all x ).
Throughout the series we prove an implication
Tables 1–3 list the three alphabets of the series—blackboard-bold letters for the standard number systems and structures, Greek letters such as λ and ρ for parameters and challenges, and relational and operator symbols—with their English readings: the Greek letters in the International Phonetic Alphabet, the other symbols as the words read aloud. Readings vary between speakers and regions; the alternatives shown are not exhaustive. Each symbol is defined where it is first used; the notes here are reminders, not definitions.
| Symbol | Name | Said | Typical role in the series |
|---|---|---|---|
| N | blackboard N | “natural numbers” | the naturals |
| Z | blackboard Z | “the integers” | the integers (German Zahlen) |
| Q | blackboard Q | “the rationals” | the rationals (quotients) |
| R | blackboard R | “the reals” | the real numbers |
| C | blackboard C | “the complexes” | the complex numbers |
| F q | blackboard F | “eff-cue” | the finite field of q elements |
| G | blackboard G | “group G” | an abstract group |
| E | blackboard E | “expectation” | expectation of a random variable (§11) |
| P | blackboard P | “the Pallas curve” | the Pallas group (§10; protocol-spec notation) |
| Lower | Capital | Name | British | American | Greek |
|---|---|---|---|---|---|
| α | A | alpha | /ˈælfə/ | /ˈælfə/ | άλφα [ˈalfa] |
| β | B | beta | /ˈbiːtə/ | /ˈbeɪtə/ | βήτα [ˈvita] |
| γ | Γ | gamma | /ˈɡæmə/ | /ˈɡæmə/ | γάμα [ˈɣama] |
| δ | Δ | delta | /ˈdɛltə/ | /ˈdɛltə/ | δέλτα [ˈðelta] |
| ε, ε | E | epsilon | /ˈɛpsɪlɒn, ɛpˈsaɪlən/ | /ˈɛpsəlɑːn, ˈɛpsɪlɑːn/ | έψιλον [ˈepsilon] |
| ζ | Z | zeta | /ˈziːtə/ | /ˈzeɪtə, ˈziːtə/ | ζήτα [ˈzita] |
| η | H | eta | /ˈiːtə/ | /ˈeɪtə, ˈiːtə/ | ήτα [ˈita] |
| θ | Θ | theta | /ˈθiːtə/ | /ˈθeɪtə, ˈθiːtə/ | θήτα [ˈθita] |
| ι | I | iota | /aɪˈəʊtə/ | /aɪˈoʊtə/ | γιώτα [ˈʝota] |
| κ | K | kappa | /ˈkæpə/ | /ˈkæpə/ | κάπα [ˈkapa] |
| λ | Λ | lambda | /ˈlæmdə/ | /ˈlæmdə/ | λάμδα [ˈlamða] |
| μ | M | mu | /mjuː/ | /muː, mjuː/ | μι [mi] |
| ν | N | nu | /njuː/ | /nuː, njuː/ | νι [ni] |
| ξ | Ξ | xi | /saɪ, zaɪ, ksaɪ/ | /saɪ, zaɪ, ksaɪ/ | ξι [ksi] |
| o | O | omicron | /əʊˈmaɪkrɒn, ˈɒmɪkrɒn/ | /ˈoʊmɪkrɑːn, ˈɑːmɪkrɑːn/ | όμικρον [ˈomikron] |
| π | Π | pi | /paɪ/ | /paɪ/ | πι [pi] |
| ρ | P | rho | /rəʊ/ | /roʊ/ | ρο [ro] |
| σ | Σ | sigma | /ˈsɪɡmə/ | /ˈsɪɡmə/ | σίγμα [ˈsiɣma] |
| τ | T | tau | /taʊ, tɔː/ | /taʊ, tɔː/ | ταυ [taf] |
| υ | Υ | upsilon | /juːpˈsaɪlən, ˈʌpsɪlɒn/ | /ˈʌpsəlɑːn, ˈʊpsɪlɑːn/ | ύψιλον [ˈipsilon] |
| φ, φ | Φ | phi | /faɪ/ | /faɪ, fiː/ | φι [fi] |
| χ | X | chi | /kaɪ/ | /kaɪ, kiː/ | χι [çi] |
| ψ | Ψ | psi | /psaɪ, saɪ/ | /saɪ, psaɪ, psiː/ | ψι [psi] |
| ω | Ω | omega | /ˈəʊmɪɡə, əʊˈmiːɡə/ | /oʊˈmeɪɡə, oʊˈmɛɡə/ | ωμέγα [oˈmeɣa] |
| Symbol | Said | Meaning |
|---|---|---|
| ∈, ∉ | “in”, “not in” | set membership |
| ⊆, ⊂ | “subset of” | (proper) inclusion |
| ∪, ∩ | “union”, “intersect” | set union and intersection |
| A ∖ B | “A minus B” | set difference |
| × | “times” / “cross” | Cartesian product |
| ∣, ∤ | “divides”, “does not divide” | divisibility |
| ⪯, ≺ | “precedes” | partial order, strict companion |
| ≡ | “congruent to” | congruence, qualified (mod n) |
| a mod n | “a mod n” | remainder of division by n |
| :=, = : | “is defined as” | definitional equality |
| ↦ | “maps to” | the action of a function |
| g ∘ f | “g after f” | function composition |
| ⌊ x ⌋, ⌈ x ⌉ | “floor”, “ceiling” | round down, round up |
| log x, log 2 x, log g h | “log”, “log base two”, “log base g ” | natural, base- 2 , and discrete (base g ) logarithm |
| ⟨ a, b ⟩ | “inner product” | inner product; ⟨ g ⟩ the subgroup generated by g |
| ⊕ | “x-or” | bitwise exclusive or |
| x ∥ y | “x concat y” | concatenation of bit or byte strings |
| x ← D, x ← $ S | “drawn from” | sampling ( $ marks uniform); also assignment |
| [k] P | “k times P” | scalar multiplication of a point (§10) |
| P ⋆ | “P star” | canonical bit-encoding of a point or element |
| ⋅ | “dot” | product; argument placeholder, as in F (⋅) |
| | A | | “size of A” / “order of A” | cardinality |