A Graphical Introduction to Lattices

Here is my (extended) family tree:

Everyone in the tree shares at least one common ancestor and at least one common descendant. This makes my family tree a lattice, an important mathematical structure. While lattices are often presented in abstract algebraic form, they have a simple graphical representation called a Hasse diagram, which is similar to a family tree.

Because most lattice theory assumes a strong background in algebra, I think the results are not as well known as they should be. I hope to give a sampling of some lattices here, and a hint of their power.

What are Lattices?

A lattice is a structure with two requirements:

1. Every two elements have a "least upper bound." In the example above, this is the "most recent common ancestor".
2. Every two elements have a "greatest lower bound." In the example above, this is the "oldest common descendant".

Note that the bound of some elements can be themselves; e.g. the most recent common ancestor of me and my mother is my mother.

Lattices are a natural way of describing partial orders, i.e. cases where we sometimes know which element came "first", but sometimes don't. For example, because the most recent common ancestor of my mother and myself is my mother, we know who came "first" - my mother must be older. Because the least upper bound of my mother and my father is some third person, we don't know which one is older.

Shopping Carts

Here's an example of four different ways to fill your shopping cart:

The lines between two sets indicates preference: one apple is better than nothing, but one apple and one banana is even better than one apple. (Note that the arrows aren't directed, because every relation has a dual [e.g. the "better than" relation has a dual relation "worse than]. So whether you read the graph top-to-bottom or bottom-to-top, it doesn't really matter. By convention, things on the bottom are "less than" things on the top.)

Now, some people might prefer apples to bananas, and some might prefer bananas to apples, so we can't draw any lines between the "one apple" and the "one banana" situations. Nonetheless, we can still say that you prefer having both to just one, so this order is pretty universal.

The least upper bound in this case is "the worst shopping cart which is still preferred or equal to both things" (doesn't quite roll of the tongue, does it?), and the greatest lower bound is "the best shopping cart which is still worse than or equal to both things". Because these two operations exist, this means that shopping carts (or rather the goods that could be in shopping carts) make up a lattice.

A huge swath of economic and ethical problems deal with preferences which can be put into lattices like this, which makes lattice theory a powerful tool for solving these problems.

Division

This is a more classical "math" lattice:

Here a line between two integers indicates that the lower one is a factor of the higher one. The least upper bound in this lattice is the least common multiple (lcm) and the greatest lower bound is the greatest common divisor (gcd, some people call this the "greatest common factor").

The greatest common divisor of 4 and 10 is 2, and the least common multiple of 2 and 3 is 6.
Again we don't have a total ordering - 2 isn't a factor of 3 or vice versa - but we can still say something about the order.

An important set of questions about lattices deal with operations which don't change the lattice structure. For example, $k\cdot\gcd(x,y)=\gcd(kx,ky)$, so multiplying by an integer "preserves" this lattice.


Multiplying the lattice by three still preserves the divisibility relation.
A lot of facts about gcd/lcm in integer lattices are true in all lattices; e.g. the fact that $x\cdot y=\gcd(x,y)\cdot \text{lcm}(x,y)$.

Boolean Logic

Here is the simplest example of a lattice you'll probably ever see:

Suppose we describe this as saying "False is less than True". Then the operation AND becomes equivalent to the operation "min", and the operation OR becomes equivalent to the operation "max":

• A AND B = min{A, B}
• A OR B = max{A, B}

Note that this holds true of more elaborate equations, e.g. A AND (B OR C) = min{A, max{B, C}}. In fact, even more complicated Boolean algebras are lattices, so we can describe complex logical "gates" using the language of lattices.

Everything is Addition

I switch now from examples of lattices to a powerful theorem:

[Holder]: Every operation which preserves a lattice and doesn't use "incomparable" objects is equivalent to addition.¹

The proof of this is fairly complicated, but there's a famous example which shows that multiplication is equivalent to addition: logarithms.

The relevant fact about logarithms is that $\log(x\cdot y)=\log(x)+\log(y)$, meaning that the problem of multiplying $x$ and $y$ can be reduced to the problem of adding their logarithms. Older readers will remember that this trick was used by slide rules before there were electronic calculators.

Holder's theorem shows that similar tricks exist for any lattice-preserving operation.

Everything is a Set

Consider our division lattice from before (I've cut off a few numbers for simplicity):

Now replace each number with the set of all its factors:

We now have another lattice, where the relationship between each node is set inclusion. E.g. {2,1} is included in {4,2,1}, so there's a line between the two. You can see that we've made an equivalent lattice.

This holds true more generally: any lattice is equivalent to another lattice where the relationship is set inclusion.²

Max and Min Revisited

Consider the following statements from various areas of math:
$$\begin{eqnarray}
\max\{x,y\} & = & x & + & y & - & \min\{x,y\} &\text{ (Basic arithmetic)} \\
P(x\text{ OR } y) & = & P(x) & + & P(y) & - & P(x\text{ AND } y) & \text{ (Probability)} \\
I(x; y) & = & H(x) & + & H(y) & - & H(x,y) & \text{ (Information theory)} \\
\gcd(x,y) & = & x & \cdot & y & \div & \text{lcm}(x,y) & \text{ (Basic number theory)} \\
\end{eqnarray}$$When laid out like this, the similarities between these seemingly disconnected areas of math is obvious - these results all come from the basic lattice laws. It turns out that merely assuming a lattice-like structure for probability results in the sum, product and Bayes' rule of probability, giving an argument for the Bayesian interpretation of probability.

Conclusion

The problem with abstract algebraic results is that they require an abstract algebraic explanation. I hope I've managed to give you a taste of how lattices can be used, without requiring too much background knowledge.

If you're interested in learning more: Most of what I know about lattices comes from Glass' Partially Ordered Groups, which is great if you're already familiar with group theory, but not so great otherwise. Rota's The Many Lives of Lattice Theory gives a more technical overview of lattices (as well as an overview of why everyone who doesn't like lattices is an idiot) and J.B. Nation has some good notes on lattice theory, both of which require slightly less background. Literature about specific uses of lattices, such as in computer science or logic, also exists.

Footnotes

1. Formally, every l-group with only trivial convex subgroups is l-isomorphic to a subgroup of the reals under addition. Holder technically proved this fact for ordered groups, not lattice-ordered groups, but it's an immediate consequence.
2. By "equivalent" I mean l-isomorphic.

How to Create a Donor-Advised Fund

There are a lot of charities. So many, in fact, that some would-be altruists are struck with the alliterative analysis paralysis and end up not donating at all.

A tax vehicle known as a "Donor-advised fund" (DAF) allows you to get the best of both worlds: you can donate to charity, with all the psychological and tax benefits that go along with that decision, while still holding off on your decision as to which charity is best.

You can create your own DAF in about 15 minutes online. (Be sure to give it an awesome name like "The Jane Doe Fund for Paperclip Maximization" because how many chances do you have to name an organization after yourself?)  Once created, you can contribute money when you feel like it and deduct those contributions from your taxes. Your contributions will sit in an account accruing interest until you decide to write a grant to a specific charity.

There are interesting questions about when to put money in a DAF vs. donate directly, but if you are uncertain about the most effective charity, especially if you're so uncertain that you might not donate at all, you should create a DAF.

Creating Your DAF

Most major investment organizations allow you to create a DAF, such as Fidelity, Charles Schwab and Vanguard as well as most local community foundations (if you search for "community foundation" in a standard search engine, you should be able to find one near you). Be sure that you're able to invest in a no-load index fund (professional investors don't do better than chance, so it's not worth paying them a management fee). The major DAF hosts all provide this, so the only real consideration is the management fee they charge. I've found them to be pretty similar, so I just chose Fidelity since my retirement account is already there.

Put a few key details into their form and Voilà! You have your own fund!

What if I don't have $5,000?

The main reason why a DAF might not be right for you is that they require a minimum starting donation of $5,000. If you aren't able to put in $5,000 right away, look into other options that community foundations provide. For example, the foundation near me has an "Acorn fund", which allows you to donate smaller amounts of money over a longer period of time. 

Conclusion

I consider myself to be more informed than average about the subject of charity effectiveness, but if you look at my 80,000 Hours profile you can see I put all my donations into a DAF. Because even similar-sounding charities can vary in effectiveness by orders of magnitude, it's extremely important to think through your decisions. By using a DAF you can build the "habit" of altruism and take the tax advantages while still ensuring that your money goes to the most effective causes.

Why Classical Utilitarianism is the only (Archimedean) Ethic

Probably the most famous graph in ethics is this one of Parfit's:



He's constructing a series of worlds where each one has more people, but those people have a lower level of welfare. The question is whether the worlds are equivalent, i.e. whether it's equivalent to have a world with a huge number of barely happy people or a world with a small number of ecstatic individuals.

Classical utilitarianism answers "Yes", but some recent attempts to avoid unpleasant results (such as the "repugnant conclusion") have argued "No". For example, Parfit says:

Suppose that I can choose between two futures. I could live for another 100 years, all of an extremely high quality. Call this the Century of Ecstasy. I could instead live for ever, with a life that would always be barely worth living. Though there would be nothing bad in this life, the only good things would be muzak and potatoes. Call this the Drab Eternity. I believe that, of these two, the Century of Ecstasy would give me a better future.

The belief that the "Century of Ecstasy" is superior to the "Drab Eternity", no matter how long that eternity lasts, has been called "Non-Archimedean" by Arrhenius, in reference to the Archimedean Property of numbers, which says roughly that there are no "infinitely large" numbers.¹ Specifically, a group is Archimedean if for any $x$ and $y$ there is some $n$ such that $$\underbrace{x+x+\dots+x}_{\text{n times}}>y$$
The following remarkable fact is true:

Classical Utilitarianism is the only Archimedean ethic.

This means that if we don't accept that the briefest instant of a "higher" pleasure is better than the longest eternity of a "lower" pleasure, then we must be classical utilitarians.

Proof

First, define the terms. As always, we assume that there is some set $X$ which contains various welfare levels. There is an operation $\oplus$ which combines welfare levels; the statement $x\oplus y=z$ can be read as "A life with welfare $x$ and then welfare $y$ is equivalent to having a life with just welfare $z$."² It is assumed that this constitutes a group, i.e. the operation is associative and inverses and an identity exist.

In order to make decisions, we need some ranking; the statement $x>y$ means "The welfare level $x$ is morally preferable to $y$." We require $>$ to agree with our operation, i.e. if $x>y$ then $x\oplus c > y\oplus c$ for all $c$.

With the stipulation that our group is Archimedean, this reduces to a theorem of Hölder's, which states that all Archimedean linearly ordered groups are isomorphic to a subgroup of the reals under addition, i.e. classical utilitarianism. The proof is rather involved, but a fairly readable version can be found here.∎

Discussion

In order to be useful, non-Archimedean theories can't just say that there is some theoretical amount of welfare which is lexically superior - this level of welfare must exist in our day-to-day lives. Personally, when comparing a brief second of happiness on my happiest day to years of moderate happiness, I would choose the years. This leaves me with no choice but to accept classical utilitarianism.

Footnotes

1. Ethics with this property have also been called "discontinuous" or having a "lexical" priority.
2. Unlike in past blogs where I used $\oplus$ to be a population ethic, here I define it in terms of intra-personal welfare to fit more in line with Parfit's quote.

Group Theory and the Repugnant Conclusion

A fundamental question in population ethics is the tradeoff between quantity and quality. The world has finite resources, so if we promote policies that increase the population, we do so at the risk of decreasing quality of life.

Derek Parfit is credited with popularizing the importance of this problem when he pointed out that any population ethic which obeys some seemingly reasonable constraints must end up with what he called "the repugnant conclusion" - the conclusion that a world full of miserable people is better than a sparsely-populated world full of happy people. Since Parfit, there have been a range of theories seeking to preserve our intuitions about ethics while still avoiding this conclusion.

One discovery of abstract algebra is that we can understand the limitations of systems based solely on the questions they are able to answer, even if we don't know what the answers are.

Here, I'll consider any system capable of answering a question like "Are two people who each live 50 years morally equivalent to one person who lives 100 years?" (Again, we don't require that the answer be "Yes" or "No", but merely that there be some answer.) For notational ease, I use the symbol $\oplus$ to be the "moral combination", e.g. the above question can be written $$(50\text{ years})\oplus(50\text{ years})=100\text{ years?}$$ Such a system I will call a "moral group" and require that it obey a few standard requirements. These are:

1. Any two people can be replaced with one who is (significantly) better off
2. There is some level of welfare which is "morally neutral", i.e. a person of that welfare neither increases nor decreases the overall moral desirability of the world.
3. For any level of welfare, no matter how high, there is some level of welfare which is so negative that the two cancel out

With this definition, we have an impossibility theorem:

Theorem: In any "moral group", the repugnant conclusion holds.

Proof: Suppose that $x$ is a welfare level that is better than "barely worth living". Formally, say that there must be some $y$ where $0 < y < x$, i.e. it's possible to be worse off than $x$ and still have a "life worth living". We'll show that a world with just $x$ is morally equivalent to a world with two people who are both worse off than $x$. Repeating this ad infinitum leads to the conclusion that a world with a few happy people is equivalent to a world with a large number of people whose lives are "barely worth living."

Choose some $y$ between $0$ and $x$ (one exists, by the definition of $x$). Note that $x=y\oplus z$ where $z=y^{-1}\oplus x$, so we just need to show that $z<x$. Since $y>0$, $y^{-1} < 0$ because if it weren't then we'd have $y^{-1} > 0$; adding $y$ to both sides results in $0>y$ which contradicts the assumption that $y>0$. Therefore $y^{-1} \oplus x < x$, or to write it another way: $z < x$. So $x=y\oplus z$, with $y$ and $z$ both worse than $x$.

This means that for any world with people $x_1,x_2,\dots$ of high welfare, there is an equivalent world $y_1,y_2,\dots$ with more people, each of whom have lower welfare. By adding some person of low (but still positive) welfare $y_{n+1}$ to the second world, it becomes better than the first, resulting in the repugnant conclusion.∎

Algebra and Ethics

Symmetry is all around us. The kind of symmetry that most people think of is geometric symmetry, e.g. an equilateral triangle has rotational symmetry:

I've rotated the triangle by 1/3 of a rotation, but it remains the "same", just with a "relabeling" of the points. Hence this rotation is a symmetry of the triangle.

Ethical positions generally express another type of symmetry; when someone argues for "marriage equality" what they mean is that the gender of partners is merely a "relabeling" that keeps the important aspects like love and commitment the same. Symmetries in pain processing between humans and other animals has lead thinkers like Richard Dawkins to declare that species is merely a relabeling, and that causing pain to a cow is "morally equivalent" to causing pain to a human, calling our eating practices into question.

In 1854 Arthur Cayley gave the first modern definition of what mathematicians call a "group", and showed that groups are essentially permutations, thus establishing the theory of groups as the language of symmetry. Despite the importance of groups to symmetry and the importance of symmetry to ethics, I'm not able to find any ethical works based on group theory. So I hope to give what may be the first ever group-theoretical proof of ethics.

"Group-like" Ethics
I'm going to be concerned with questions like "is having two people, each of whom live 50 years, equivalent to having one person who lives 100 years?" I don't require that this question be answered either "yes" or "no", but only that the question has some answer.

So that this post doesn't take up a huge amount of space, I'm going to define the symbol $\oplus$ to mean "moral combination" and $=$ to mean moral equivalence, so the statement "two people, each of whom live fifty years, is equivalent to one person living 100 years" can be written as $$(50 \text{ years})\oplus(50 \text{ years})=100 \text{ years}$$ There are many different ways to define $\oplus$. For example, we might care only about the worst-off person - in this case $(50 \text{ years})\oplus(50 \text{ years})=50 \text{ years}$ as the worst-off person on the left-hand side of the equation has the same length of life as the worst-off person on the right. Alternatively, we might point out that quality of life degrades as you get older, so in fact maybe $(50 \text{ years})\oplus(50 \text{ years})=150 \text{ years}$ since the two young people get so much more joy out of their life. The World Health Organization follows this model and weights lives like this:

According to their formula, old age is so awful that $(40 \text{ years})\oplus(40 \text{ years})=125 \text{ years}$ and one person would have to live for thousands of years to be equivalent to two 50 year lifespans.

In addition to requiring that statements like $(50 \text{ years})\oplus(50 \text{ years})$ have some answer, I will also require that there is an "identity", i.e. there is some quality of life such that adding a person with that quality of life doesn't change the overall value of the world. This is a reasonable assumption because:

1. Sometimes increasing the population is a good idea, i.e. there is some $y$ such that $x\oplus y > x$
2. Sometimes increasing the population is a bad idea, i.e. there is some $z$ such that $x\oplus z < x$
3. By the intermediate value theorem, there must therefore be some value which I'll call $0$ such that $x\oplus 0 = x$

Any ethical system which has an operation like $\oplus$ I will call "group-like" (although observant readers will note that I'm making fewer assumptions than what groups require - technically this is a "unital magma").

"Utilitarian-like" Ethics
The classic definition of "utilitarianism" is to look only at happiness and to define $\oplus=+$, e.g. two people with five "units" of happiness is equivalent to one person with ten units of happiness.

There are a plethora of "utilitarian-like" ethical theories which define $\oplus$ as being sort of like addition, but not really. For example, negative utilitarians would first discard any pleasure, and look only at the pain of each individual before doing the addition. Prioritarians wouldn't completely disregard pleasure, but they would weight helping those in need more strongly. The Sen social welfare function weights income by inequality before doing the addition. And so on.

I will describe an ethical system as "utilitarian-like" if it is equivalent to doing addition with some appropriate transformation applied first. Formally, utilitarian-like operations are of the form $x\oplus y = f(x)+f(y)$.

The Theorem
With these definitions in mind, we can state our theorem:

The only ethical system which is both group-like and utilitarian-like is classical ("Benthamite") utilitarianism.

Observant readers will notice that my examples in the "group-like" section were different than the examples in the "utilitarian-like" section. This theorem proves that this is not an accident.

Proof: $x\oplus 0 = f(x)+f(0)$ so $x = f(x)+f(0)$ or to rewrite it another way, $f(x)=x - f(0)$ where $f(0)$ is some constant. This means that all group-like and utilitarian-like functions are equivalent, just shifted slightly. To use a formal definition of "equivalent", the homomorphism $\phi(x) = x + f(0)$ can be easily seen via the first isomorphism theorem to be an isomorphism $(\mathbb{R},\oplus)\to(\mathbb{R},+)$.∎

Discussion
The reason why Prioritarians et al. fail to be group-like is something I haven't seen discussed much in the literature: a lack of an identity element.

For example, suppose $x\oplus y = f(x)+f(y)$ where $$f(x) = \left\{
\begin{array}{lr}
2x & x < 0\\
x & else \end{array} \right.$$ This is a negative utilitarian-type ethics which weights suffering (i.e. negative experience) more strongly.

Consider a few possible worlds in which we add someone of utility 2:

1. $-1\oplus 2 = 0$
2. $-2\oplus 2 = -2$
3. $-3\oplus 2 = -4$

In the first case, adding someone of utility two improves the world. In the second, it keeps the world the same and in the third it makes the world worse.

That negative utilitarianism requires this isn't immediately obvious to me, and I believe it to be a non-trivial result of using group theory.

Conclusion
We might view negative utilitarianism or prioritarianism as a form of "pre-processing". For example, we might say that painful experiences affect utility more than positive ones. But when it comes to comparing utility to utility, it must be "each to count for one and none for more than one" with all the counter-intuitive results that implies.

Why there must be universal grammar

The guardian ran an interview with Daniel Everett yesterday. Everett is a linguist most famous for his claim that universal grammar (the belief that some rules of grammar are "hard wired" into the brain) as popularized by Chomsky, is false. Specifically, he believes that the Pirahã language lacks recursion.

His claims are quite controversial, but one thing which is worth mentioning is that universal grammar is (for a reasonable definition of "proof") provably correct. By this I mean:

Theorem: Learning grammar is so hard that the only way humans (or anyone) can do it is if they have innate structures.

This is related to Chomsky's poverty of the stimulus argument.

It can be proven in the following way: suppose we restrict ourselves to just the subset of English sentences consisting only of nouns and verbs. "I like John" and "You are here" would be two examples. These both follow the pattern "noun verb noun". A sentence like "jump run you" is non-grammatical, because "verb verb noun" is not an acceptable pattern in English.

Now let's consider how long it would take a learner to learn these patterns. There are 2³ = 8 possible patterns of length three, so if a learner thinks they're all possible, it will have to test out all eight of them. ("Mommy, is 'jump run you' a sentence?")

Most sentences have much more than three words of course, so a learner will need to test out the 2⁴ = 16 four word patterns, the 2⁵ = 32 five word patterns, etc. In general, there are 2ⁿ possible sentences with n words, meaning that the number of tests that the learner will need to run is exponential in the number of words.

The Cobham-Edmonds thesis states that any problem which takes exponential time is, in practice, unsolvable.

Why is this true? There are, depending on your definition of "part of speech", about 20 parts of speech in English. If you tested one grammar per second, it would take you about a month to learn all the five word grammars. The six word grammars would take you two years, and you would be forty before you learned all the seven word grammars. That last sentence had 22 words, and it would take you 10²¹ years to test all of the 22-word-grammars. The universe is only 10¹³ years old.

So who knows whether all languages are recursive. But it seems unlikely that human children consider all possible grammars equally. They must use some shortcuts and those shortcuts must, by definition, be innate.

A Simple Proof: Occam's Razor

How do you know that I'm not a robot? How do you know we're not living in the matrix?

The usual resolution is some form of Occam's razor: sure, it's possible that I'm a robot, but the simpler explanation is that I'm human, and simpler explanations are preferable.¹

This just pushes the question back: why are simpler explanations better?

There is a straightforward proof that comes from Computer Science, of all places, which I hope to explain here.

---

Suppose I enter the world as a blank slate - I have a "bag" of hypotheses about how things work, and I consider them all equally probable. As I perform experiments, I disprove some of my hypotheses, while others remain. As time goes on, my bag of plausible hypotheses gets smaller and smaller.

If I eventually reach a point at which I only have two hypotheses remaining and I randomly choose one to believe, I'm 50% certain that I've got the right one. But if I randomly believe one out of a hundred possible hypotheses, I've almost certainly chosen wrong (i.e. I've probably selected a hypothesis that by luck happened to fit with all the observed data, even though it's in fact wrong).

Believe it or not, this concludes the proof.

If I have a simple hypothesis ("fire is hot") there's really only one other hypothesis that could be in my bag ("fire is not hot"), so I can rapidly determine which is the right one. If my hypothesis is complicated ("fire is hot, provided it's the first full moon of a year with zodiac symbol ...") there are tons of equally complex hypotheses, and some of them are bound to fit the data, so I'm unlikely to have chosen the right one.

---

In my job, I spend some time in the back rooms at medical offices, which means I hear nurses complain about doctors, and doctors complain about patients. One conversation I had with a dietition sticks into my memory: she was complaining about patients who expect the faddish, complicated dietary advice you hear on TV - "good" carbs, antioxidants etc. - but all she does is give people a calorie target, and recommend eating more fresh fruits and vegetables.

I told her to give her patients a brochure on Occam's razor. I doubt they've implemented my suggestion.

Postscript: This proof is a vague mishmash of the motivation for Bonferroni correction and VC theory. Any book on computational learning theory will have a better one, but you can see de Wolf's thesis for an explicit application of PAC learning to Occam's razor. You might also like my post why you will never see an eight-sided snowflake.

1. That's not true. The usual resolution is to ignore the problem.