This article was first published on IOTA - Medium
In any cryptocurrency, transactions are linked to one another using hashes. This unalterable relationship endows the set of transactions with a natural mathematical structure called a partial order. In this post, we discuss partial orders and how they are useful for IOTA.
Total vs Partial Orderings
The real numbers, ℝ, has a natural ordering denoted by ≤. As children, we learned that all numbers, x,y,z, and the relation ≤ satisfy the following conditions:
- Reflexivity: x≤x
- Antisymmetry: x≤y and y≤x implies x=y
- Transitivity: x≤y and y≤z implies x≤z
- Totality: Either x≤y or y≤x
Relations of this sort are pervasive in mathematics and are thus named: a total order is any relation ≤ satisfying these properties. A set with a total order is called a totally ordered set.
Moreover, every subset of ℝ is totally ordered, such as the natural numbers ℕ and the interval [0,1]. However, there are other more exotic examples of totally ordered sets. For instance a classroom X of children is totally ordered by height provided that no two children in X have identical height. Specifically, for children x and y in X, we may declare that x≤y if x is shorter than y. In fact various characteristics such as age, weight, or grades produce many different total orderings on X.
However, not all orders are total. For instance in ℝ² let (a,b)≤(c,d) if a≤c and b≤d. Although this relation satisfies Conditions (1)-(3), ℝ² is not totally ordered since, for example, the elements (2,3) and (3,2) are incomparable, because a<c while b<d. This example motivates a different type of order.
A partial order is a relation ≤ that satisfies all of the above conditions except Condition 4, and thus some elements can be incomparable. A poset (short for partially ordered set) is a set with a partial order. For ...
To keep reading, please go to the original article at:
IOTA - Medium