The Zcash ArboretumI–IX The Complete Arboretum
Contents
PDF
Theme

1 Notation: sets, functions, and relations

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).

1.1 Sets

A set is a collection of distinct objects, its elements; one writes x∈A for membership and x∉A for its negation. A set may be given by listing, {a,b,c}, or by set-builder notation {x∈A:P(x)} (“the x in A such that P(x)”). One writes A⊆B when every element of A lies in B, and A=B exactly when A⊆B and B⊆A — so proving two sets equal means proving two inclusions. The usual operations are union A∪B, intersection A∩B, difference A∖B, and the empty set ∅. The Cartesian product is A×B={(a,b):a∈A,b∈B}, and An is the set of n-tuples over A. For a finite set A, |A| denotes its number of elements. The standard number systems are the naturals ℕ, the integers ℤ, the rationals ℚ, the reals ℝ, and the complex numbers ℂ, with ℕ⊂ℤ⊂ℚ⊂ℝ⊂ℂ; we construct the underlying arithmetic of the prime field 𝔽p in §2, certify it as a field—and first call it 𝔽p—in §4, and treat general finite fields 𝔽q in §6.

1.2 Functions

A function f:A→B assigns to each a∈A a unique value f(a)∈B; A is the domain and B the codomain. It is injective (one-to-one) if f(a)=f(a′) implies a=a′; surjective (onto) if every b∈B equals f(a) for some a∈A; and bijective if both. The composition of f:A→B and g:B→C is (g∘f)(a)=g(f(a)); composition is associative, h∘(g∘f)=(h∘g)∘f, both sides sending a to h(g(f(a))). The identity on A is idA:A→A, idA(a)=a.

Theorem 1.1 (Inverse functions).

A function f:A→B has a two-sided inverse f−1:B→A, meaning f−1∘f=idA and f∘f−1=idB, if and only if f is bijective. When it exists, the inverse is unique.

Proof.

Suppose a two-sided inverse g exists. If f(a)=f(a′), applying g gives a=g(f(a))=g(f(a′))=a′, so f is injective; and every b∈B satisfies b=f(g(b)), so f is surjective. Conversely, suppose f is bijective. Each b∈B has at least one preimage by surjectivity and at most one by injectivity, so we may define g(b) to be the unique a∈A with f(a)=b; then g(f(a))=a and f(g(b))=b hold by construction. Finally, if g and g′ are both two-sided inverses, associativity of composition gives g=g∘idB=g∘(f∘g′)=(g∘f)∘g′=idA∘g′=g′; the inverse is unique, and we write it f−1. □

For S⊆A the image is f(S)={f(a):a∈S}, and for T⊆B the preimage is f−1(T)={a∈A:f(a)∈T}, defined whether or not f is invertible. The two uses of f−1 agree: when the inverse function exists, the preimage of T under f is exactly the image of T under f−1.

1.3 Relations and equivalences

A binary relation on A is a subset R⊆A×A; one writes a∼b for (a,b)∈R. It is an equivalence relation if it is reflexive (a∼a), symmetric (a∼b⇒b∼a), and transitive (a∼b and b∼c imply a∼c). The equivalence class of a is [a]={x∈A:x∼a}, and the set of distinct classes is the quotient A/∼.

Proposition 1.2 (Classes partition the set).

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.

Proof.

Reflexivity gives a∈[a] for every a∈A, so each class is nonempty and every element lies in some class; the union of the classes is therefore A. For disjointness, suppose the classes [a] and [b] share an element x, and let y∈[a] be arbitrary. From y∼a and a∼x (the latter by symmetry from x∼a), transitivity gives y∼x; combining with x∼b gives y∼b, so y∈[b]. Thus [a]⊆[b], and exchanging the roles of a and b gives the reverse inclusion; two classes that meet coincide. □

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: a⪯b and b⪯a imply a=b. Four partial orders recur in the series: the usual ≤ on ℤ; inclusion ⊆ on the subsets of a fixed set, whose antisymmetry is the two-inclusions rule of §1.1; divisibility ∣ on ℕ (§2.2); and the prefix relation on finite sequences, under which a sequence precedes every sequence that extends it. Two elements are comparable if a⪯b or b⪯a, and a partial order under which every two elements are comparable is a total (or linear) order. The order ≤ on ℤ is total; the other three are not: {1} and {2} are incomparable under inclusion, as are 2 and 3 under divisibility and the one-term sequences (1) and (2) under prefix.

Every partial order has a strict companion, a≺b meaning a⪯b and a≠b.

Proposition 1.3 (Strict and non-strict orders).

If ⪯ is a partial order on A, its strict companion ≺ is irreflexive (a≺a holds for no a) and transitive. Conversely, if ≺ is irreflexive and transitive, then “a≺b or a=b” defines a partial order on A whose strict companion is ≺.

Proof.

Irreflexivity of the companion is the clause a≠a. For transitivity let a≺b≺c; then a⪯c because ⪯ is transitive, and a=c would give a⪯b⪯a, hence a=b by antisymmetry, contradicting a≺b. Conversely, the relation “a≺b or a=b” is reflexive by construction and transitive by cases: if either hypothesis is an equality, the conclusion follows from the other by substitution, and otherwise from transitivity of ≺. It is antisymmetric, since a≠b with both a⪯b and b⪯a would mean a≺b and b≺a, whence a≺a, against irreflexivity. Its strict companion is ≺ again: “(a≺b or a=b) and a≠b” reduces to a≺b, which already excludes a=b by irreflexivity. □

A strict order ≺ is a strict total order when its non-strict companion is total, equivalently when for all a,b exactly one of a≺b, a=b, b≺a holds (trichotomy): at least one holds by totality, and any two together would give a≺a, by substitution or by transitivity. The usual < on ℤ is the standard example. A function f:A→B between ordered sets is monotone (order-preserving) if a⪯a′ implies f(a)⪯f(a′), and strictly increasing if a≺a′ implies f(a)≺f(a′). The volume assumes only one further property of an order, the well-ordering of ≤ on ℕ, stated at the start of §2.1.

1.4 Logic and proof conventions

We employ the symbols ∀ (“for all”), ∃ (“there exists”), ∃! (“there exists a unique”), and “:” or “s.t.” for “such that”. Negation swaps the quantifiers: ¬(∀xP(x)) is ∃x¬P(x), and ¬(∃xP(x)) is ∀x¬P(x). The order of unlike quantifiers matters: ∀x∃yP(x,y) (the y may depend on x) is weaker than ∃y∀xP(x,y) (one y works for all x).

Throughout the series we prove an implication P⇒Q directly (assume P, derive Q), by contraposition (assume ¬Q, derive ¬P), or by contradiction; we prove a statement ∀xP(x) by taking an arbitrary x, and ∃xP(x) by exhibiting a witness. We prove statements about all natural numbers by induction.

1.5 Symbols and their pronunciation

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
ℕ blackboard N “natural numbers” the naturals
ℤ blackboard Z “the integers” the integers (German Zahlen)
ℚ blackboard Q “the rationals” the rationals (quotients)
ℝ blackboard R “the reals” the real numbers
ℂ blackboard C “the complexes” the complex numbers
𝔽q blackboard F “eff-cue” the finite field of q elements
𝔾 blackboard G “group G” an abstract group
𝔼 blackboard E “expectation” expectation of a random variable (§11)
ℙ blackboard P “the Pallas curve” the Pallas group (§10; protocol-spec notation)
Table 1: Blackboard-bold letters. “Blackboard bold” names the double-struck style itself; in speech one usually says only the letter or the system it denotes. Elliptic curves are written italic E or calligraphic ℰ, never blackboard bold. The squared ℙ2 of §10 is unrelated: it denotes the projective plane.
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]
Table 2: The 24 letters of the Greek alphabet in lower and upper case. The English names are given in the International Phonetic Alphabet, British (Received Pronunciation) and American (General American), as in the Cambridge, Collins and Oxford dictionaries and Wiktionary, the most widely attested form first; rarer variants are omitted. The last column gives the Modern Greek name in the simplified spelling of the Triantafyllidis dictionary, with its pronunciation; traditional spellings such as γάμμα, κάππα and μυ are also current. The capital Σ is also the summation sign and names the Σ-protocol family of later volumes; the capital Π is also the product sign and, in those volumes, a conventional name for a protocol or problem.
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 (modn)
amodn “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,log2⁡x,logg⁡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
Table 3: Relational and operator symbols. Every use of ⊕ in the series is the bitwise exclusive or. The encoding P⋆ is protocol-spec notation, defined in later volumes.