Notes on well-ordering

(Content warning: maths. This was written as an exercise in approaching the underlying ideas with rigour and understanding. If it's of any help to other people, this is a happy side effect.)

In discrete mathematics, the Well-Ordering Principle for natural numbers states that any non-empty set of natural numbers contains a least element of itself.

Slightly more formally: \[\forall S \subseteq \mathbb{N} : \; S = \emptyset \lor \exists x \in S (\forall y \in S (x \leq y))\]

Example: Let \(S = \{12,3,189,40,25\}\). Then the least element of \(S\) is \(3\).

Example: Let \(S = \{\}\). The Well-Ordering Principle doesn't apply because \(S\) is empty.

Example: Let \(S = \mathbb{N}\). Then the least element of \(S\) is \(0\).

Example: Let \(S = \{n \in \mathbb{N} \;|\; n\textrm{ odd}\} = \{1,3,5,\ldots\}\). Then the least element of \(S\) is \(1\).

The interesting thing here is that this applies to every subset of \(\mathbb{N}\), of which there are uncountably many. Some of them we can't compute membership for, e.g. the image of the busy beaver function. Most of them we can't even give a finite description for.

[Review] Welcome to Your New Life, by Anna Goldsworthy

I recently read Anna Goldsworthy's Welcome to Your New Life, a memoir addressed from mother to firstborn child, detailing their story, from conception to first birthday.

In many ways the book is an honest, unabashed look into Goldsworthy's mind, an unerringly human account of how her heart and mind open and mould themselves around the entrance of her (spoiler:) son into her life. Her account of the pregnancy, for instance, lingers around a theme of anxiety — of all the little ways things could go wrong. In one particularly poignant passage she expresses the full extent of this fear:

It is a clear winter morning when we drive to the clinic, and on the radio a Finnish violinist plays a glistening Vivaldi. For the first time, I allow myself to admit the scale of my ambition. To have a good pregnancy and a safe delivery. For you to be a healthy child. For you to have a happy and successful and long life. For there to be no apocalypse in your lifetime, or in the lifetime of your children, or grandchildren. Is there no end to my greed?

Welcome to Your New Life, by Anna Goldsworthy (2013)

Parenthood comes with its own foreign set of concerns and neuroses. In one memorable chapter Goldsworthy recounts a trip that she, her partner and their child take to a farmhouse near the coast. A weekend that begins with them settling into an idyllic farmhouse for the night takes a dark turn when Goldsworthy discovers that the house's toilet is an outhouse. Her mind instantly turns to fears for her baby's mortality.

I have seen how you would fall, she writes. That moment in which clumsiness ticks over into disaster.

As the night continues, Goldsworthy recounts how she is kept awake by constant fears of all the possible permutations of misfortune that might lead to tragedy.

You are incapable of locomotion... The only people of capable of taking you into the composting toilet are me and Nicholas... I repeat these statements in my head as though counting sheep. You are incapable of locomotion... The only people of capable of taking you into the composting toilet are me and Nicholas... I will not take you into the composting toilet... Therefore, the person who will take you into the composting toilet is Nicholas.

It is in this way that Goldsworthy maps out the changes in her mind like an expert cartographer. The everyday becomes sinister; the mundane becomes deadly; every word spoken near her becomes an implicit judgement on her worth as a parent and her son's worth as a human being.

And yet amidst all the worry, there are moments of unqualified joy:

Every day you acquire more purchase over the world, so that there are places now where I can meet you in wonder. At night in your nursery, I switch on the magic lantern and track the blurry lamb’s passage across the ceiling, absorbing the great weight of your silence in my lap. When you wake in the morning, we count the animals in your farmyard book, your miniature forefinger in my hand like a pencil, guiding me, teaching me how to look.

Ibid.

It's in moments like these that Goldsworthy's earnestness shines brightest. Newborns, as she puts it, are transient, and amidst all the tumult and trouble she describes her new world as, she certainly doesn't hide her joy in watching that world go by.

Monster

Gregor Samsa wakes up to discover he has become a monster. You, on the other hand, wake up day after day, gradually realising that you always have been a monster.

---

Imagine you were born with a special power: the power to make others do anything you ask them to.

Your power is not foolproof: it works not by magic nor mind control, but instead simple things like charisma and social norms and subconscious terror. Your power has little effect on those deemed your superiors, but works without fail on your peers. You ask for someone’s hand and the implicit lines of obligation and normalcy and shift around the two of you like tangled vines until they cannot refuse you without demeaning themselves. You ask them to betray their friends’ secrets and their tongues are unbound by the unspoken ancient warnings against lying to you.

Thus you cannot bend others’ minds; only actions. You cannot make someone see you as a friend, but by merely treating them as one you can force them to reciprocate.

Now imagine this: you cannot control the power. It is always on.

(Were this truth couched in storytelling, this would be metaphor. This is the reverse. This is storytelling couched in truth. You have a collection of facts; between what lines is the narrative hiding?)

You weren’t always aware of this power. Once upon a time you thought you existed in a world of free information flow, where if you asked someone “Want a game?” they would respond with “Yes” if and only if the answer was yes. You asked questions, you asked people for favours, you suggested favourite books to friends, and sometimes the outcomes weren’t the best possible ones, but more often than not they were. You thought this was normal.

When you begin to realise that people subliminally acquiesce to you, the thought weighs upon your every interaction. You can’t distinguish friend from serf with any real conviction; what stock can you put in anything? Sometimes you drift away from people because you were heading different directions in life; sometimes you drift away from people because they were terrified of you and had no other way of escaping your influence. Whenever this happens, you cannot ascertain the difference. You can only conjecture.

---

“Do I make you uncomfortable?” you ask your best friend, who you’ve known since middle school.

He looks up at you, countenance equal parts baffled and offended by the question. “Of course,” he jokes without missing a beat, “Who wouldn’t be uncomfortable looking at a mug like that?”

You have the answer you wanted to hear; you have no answer at all.

---

You could try to change the way you talk, the way you imply. You could swap your “Let’s grab a drink after work”s with “Want to grab a drink after work?”s. You could swap your “Want to grab a drink after work?”s with “Would you be comfortable grabbing drinks after work?, just briefly, no pressure”s. You could swap those with very carefully worded invitations stuffed full of gracefully-decline options, delivered through a neutral third party.

Perhaps it works. Perhaps if you relate to them gently enough, the people around you will be acting of their own free will. But perhaps no amount of equivocation infallibly turns an imperative into a request.

---

You meet someone you want to grow to trust: a potential new friend, or partner, or mentee, or anything in between.

You make the first move—

“About not needing to say something to make it real...”

Later she thought about what he’d said. About not needing to say something to make it real. This contradicted what she’d been taught. The brain used language to frame concepts: it employed words to identify and organize its own chemical soup. A person’s tongue even determined how they thought, to a degree, due to the subtle logical pathways that were created between concepts represented by similar-looking or -sounding words. So, yes, words did make things real, in at least one important way. But they were also just symbols. They were labels, not the things they labeled. You didn’t need words to feel. She decided he had a point. But it felt so strange.

Lexicon, by Max Barry

"One who can do anything..."

You thought, as a boy, that a mage is one who can do anything. So I thought, once. So did we all. And the truth is that as a man’s real power grows and his knowledge widens, ever the way he can follow grows narrowed; until at last he chooses nothing, but does only and wholly what he must do...

A Wizard of Earthsea, by Ursula Le Guin

Range trees and profiling in Haskell

Range trees. Those of my friends who've had a lot of programming competition experience would be well-acquainted with them. They're neat recursive data structures which I thought would make an excellent toy project for me to learn a bit more about performance profiling in Haskell.

...range trees?

A range trees is a binary-tree-based data structure used to implement range queries.

1D range query problem. Given a semigroup (i.e. an associative binary operator \(\bullet\) over a domain \(S\)), we seek a data structure that implements the following operations over some virtual array a:

\(\textrm{update}(x,v)\): set \(\texttt{a}[x] := v\)

\(\textrm{query}(x_1,x_2)\) [given \(x_1 \leq x_2\)]: return \(\texttt{a}[x_1] \bullet \texttt{a}[x_1+1] \bullet \cdots \bullet \texttt{a}[x_2-1]\)

For example, the range minimum query problem requires a data structure that updates integers in an array and answers queries of the form What is the lowest element in the range \([x_1,x_2)\)?. The range sum query problem requires a data structure answering queries like what is the sum of elements 4 to 17 inclusive?, and so on.

Range trees offer us \(O(\lg W)\) updates and queries using \(O(W)\), where \(W\) is the size of the array. They're constructed as balanced binary trees where each leaf corresponds to an element in the array (ordered left to right, sensibly enough), and where each non-leaf node contains the sum of all the leaves underneath it.

Schematic of a range tree that calculates range sums for an array a[7].

The root node contains the sum of the entire array, its children contain the sums of the left and right halves respectively, and so on. The leaves contain the values (sums, if you will) of individual array elements.

When the value of an array element changes, only \(O(\lg W)\) tree nodes need to be updated. Likewise, querying for the sum of a range of elements also only requires looking at the values stored in \(O(\lg n)\) nodes. (In the example diagram above, finding the sum from a[1] to a[4] inclusive requires looking at three nodes: the ones storing the sums for a[1], a[2] + a[3], and a[4].)

Haskell implementation

Here’s a first pass attempt at implementing a range tree in Haskell:

data RangeTree = RangeTree {width :: Int, tree :: RangeTreeNode}

newRangeTree w = RangeTree {width = w, tree = newRangeTreeNode 0 w}

update :: RangeTree -> Int -> Int -> RangeTree
update rt x v = rt {tree = updateRangeTreeNode (tree rt) 0 (width rt) x v}

query :: RangeTree -> Int -> Int -> Int
query rt = queryRangeTreeNode (tree rt) 0 (width rt)

-- Internals

data RangeTreeNode =
    Leaf Int
  | Branch RangeTreeNode Int RangeTreeNode

rtnValue :: RangeTreeNode -> Int
rtnValue (Leaf v) = v
rtnValue (Branch _ v _) = v

newRangeTreeNode :: Int -> Int -> RangeTreeNode
newRangeTreeNode x1 x2
  | x1 == x2-1 = Leaf 0
  | otherwise = Branch
    (newRangeTreeNode x1 ((x1+x2) `div` 2))
    0
    (newRangeTreeNode ((x1+x2) `div` 2) x2)

updateRangeTreeNode :: RangeTreeNode -> Int -> Int -> Int -> Int -> RangeTreeNode
updateRangeTreeNode rtn x1 x2 x' v
  | x1 > x' || x2 <= x'
                = rtn
  | otherwise   = case rtn of
                    Leaf _ -> Leaf v
                    Branch l _ r -> Branch l' (rtnValue l' + rtnValue r') r'
                      where
                        l' = updateRangeTreeNode l x1 ((x1+x2) `div` 2) x' v
                        r' = updateRangeTreeNode r ((x1+x2) `div` 2) x2 x' v

queryRangeTreeNode :: RangeTreeNode -> Int -> Int -> Int -> Int -> Int
queryRangeTreeNode rtn x1 x2 x1' x2'
  | x1' >= x2 || x1 >= x2'
      = 0
  | x1' <= x1 && x2' >= x2
      = rtnValue rtn
  | otherwise 
      = queryRangeTreeNode l x1 ((x1+x2) `div` 2) x1' x2'
        + queryRangeTreeNode r ((x1+x2) `div` 2) x2 x1' x2'
        where
        Branch l _ r = rtn

The implementation is quite standard. The module exposes the functions update and query, which are wrappers for the recursive functions updateRangeTreeNode and queryRangeTreeNode.

Let's see how this runs on some random data sets:

Utility and Equivalence

Credit: deviantART / sekeroglu

In a previous post, I outlined the four von Neuman-Morgenstern axioms for preferences (completeness, transitivity, continuity and independence), discussed my interpretation of the outcome consequentialism that underlies sensible interpretations of the axiom, and finished by talking about how they imply the existence of utility functions:

Theorem (von Neumann–Morgenstern utility theorem): Assuming the VNM axioms, there exists some linear (weighted-average preserving) function \(u: \mathcal{O} \rightarrow \mathbb{R}\) such that: \[o_1 \prec o_2 \Leftrightarrow u(o_1) < u(o_2)\]

These functions aren't unique: given any such function you can translate it or multiply it by a positive scalar to get another function that represents the same preference relation \(\prec\). In fact, for all intents and purposes, utility functions can be considered invariant under positive affine transformations.