Chapter 6 — Discrete structures

Lesson map

Lesson 06 published. Map, example, EX016.

flowchart TD
  N0["Learning outcomes"]
  N1["6.1 Sets and relations"]
  N2["6.2 Transfers as a graph"]
  N3["6.3 Counting and bounds"]
  N4["Synthesis"]
  N0 --> N1 --> N2 --> N3 --> N4
  N4 --> EX["Worked example"]
  EX --> Q["Exercise EX016"]

Logical drawing

flowchart LR
  N0["Learning outcomes"]
  N1["6.1 Sets and relations"]
  N2["6.2 Transfers as a graph"]
  N3["6.3 Counting and bounds"]
  N4["Synthesis"]
  N0 --> N1 --> N2 --> N3 --> N4 --> Q["EX016"]

[Learning outcomes]
    |
    v
[6.1 Sets and relations]
    |
    v
[6.2 Transfers as a graph]
    |
    v
[6.3 Counting and bounds]
    |
    v
[Synthesis]
    |
    v
[Worked example] --> [Exercise EX016]

Learning outcomes

You will (1) use sets, relations and graphs; (2) model ownership as a mapping; (3) reason about transfers as a graph.

6.1 Sets and relations

A set is a collection of distinct items; a relation pairs items from sets. Sofia models the cooperative's members as a set of codes and its vouchers as amounts owned by those codes. Ownership is a function from member codes to non-negative whole numbers. Writing it this way makes rules precise: no member may have a negative balance, and the sum over all members must equal circulation. A relation records which members have approved shifts in a given week. Discrete structures sound abstract, but they let Sofia state exactly what a correct ledger state looks like and therefore what an incorrect one looks like.

6.2 Transfers as a graph

A graph has nodes connected by edges. Sofia draws members as nodes and voucher transfers as directed edges labelled with amounts. Most edges run from members to the shop, because vouchers are mostly spent there. A few run between members, for example when a parent gives vouchers to an adult child. The graph shows patterns at a glance: a member who sends vouchers to many new addresses in a short time stands out. Graph thinking underlies many blockchain monitoring tools. Sofia treats unusual shapes as questions to investigate politely, never as proof of wrongdoing.

6.3 Counting and bounds

Counting arguments give simple limits. With 900 members and a rule that each member can earn at most 20 vouchers a week, weekly issuance can never exceed 18,000. If records ever show more, something is wrong. Sofia also counts the possible keyholder combinations for a 2-of-3 treasury: three pairs can sign, so losing one keyholder still leaves one working pair. Small counting results like these become checks that software can run automatically. They are easy to explain to the board, which helps the controls earn trust and support from people who are not technical.

Worked example

Sofia models balances as a non-negative function, bounds weekly issuance at 18,000 and shows a 2-of-3 treasury has three signing pairs.

Synthetic case. Members, transfers and limits are synthetic.

Errors and limits

Treating an unusual graph pattern as proof of misuse can wrongly accuse a member.

Exercises

• EX016 — Ownership model. How is ownership modelled?
  Show marking criteria

  Rubric: 3 = a function from member codes to non-negative whole numbers;; 2 = a function;; 1 = a list of names;; 0 = none.
• EX017 — Weekly bound. What is the maximum weekly issuance?
  Show marking criteria

  Rubric: 3 = 18,000;; 2 = 900 times 20;; 1 = unlimited;; 0 = none.
• EX018 — Signing pairs. How many pairs can sign a 2-of-3 treasury?
  Show marking criteria

  Rubric: 3 = three;; 2 = 3;; 1 = one;; 0 = none.

Synthesis

Sets, graphs and counting turn ledger rules into precise, checkable bounds.

Continue studying — chapter 06 of 40

← Chapter 05 (draft) · Course chapter index · Chapter 07 (draft) →