Ternary Magmas for Dummies
This article is a retelling of the previous article, written for an audience without a higher-math background. If you're familiar with math jargon, go read that one.
Before We Start
In this article I'm going to be talking about sets and functions, so before we start I want to make it clear what exactly the words "set" and "function" mean in a math context. (If you already have a handle on this, you can skip to the next section.)
A set is any collection of distinct values. You're already familiar with a lot of sets from grade-school math. The integers, the real numbers, and the complex numbers are all sets. But a set can contain any values, not just numbers. For example, the set of booleans {true, false}, or the set of uppercase letters {'A', 'B', 'C', ...}. We write a set out by listing its values between curly braces. It's important, though, that all of the values in a set be distinct. {3, 6, 2, 3} isn't a set, because the value 3 is repeated multiple times.
A function is a process that takes one or more input values, and gives a value as output. If we run the process multiple times on the same input, it has to always give us the same ouput; in other words, there can't be any randomness involved. It's common to define functions in terms of mathematical operations; e.g. the function a(x) = x^2 squares its input, and the function b(x,y,z) = x+y+z adds its inputs together. But that's far from the only way to do it. We could, for example, define a function c(x) that takes as its input x a person's birthday and figures out that person's zodiac sign, or a function d(x) that looks up its input word x in a dictionary and gives us that word's definition.
Let's Play a Game
Let's say we have some set of values; it could be any set. You get to define a function (let's call it f(x,y,z)) that takes as its inputs three elements of this set, and gives as its output another element. Then I define two other functions (g(w,z) and h(x,y)). If the equation f(x,y,z) = g(h(x,y),z) is true no matter what values we choose for x, y, and z, then I win. But if you can find any three values that make the equation untrue, then you win.
One more thing: when I say "define a function", I mean any function. It doesn't have to have a nice neat definition. You could even define it by listing out every possible input and the corresponding output for each.
Now that you know the rules, let's play.
Round One: a Set with One Element
This one is easy. Let's call the single element of our set unit. If there's only one possible value, then that means that there's only one possible output of any function. f(x,y,z) and g(h(x,y),z) will both be unit, so f(x,y,z) = g(h(x,y),z). I win.
Round Two: a Set with Three Elements
Let's imagine listing out every possible input to f(x,y,z). There are three variables, each of which can be any one of three possible values, which means that there are 3•3•3 = 27 possible inputs. For each of these 27 inputs, you can choose any one of three outputs, so over all there are 3^27 possible functions you can choose. That's more than 7 trillion functions! Now let's do the same thing for g(w,z) and h(x,y). These functions have two variables, so they have 3•3 = 9 possible inputs. That means that there are 3^9 possible ways to pick each function, and over all there are (3^9)•(3^9) ways I can choose g and h, or a bit less than 400 million; still a lot, but much less than the number of choices of f. But if you can choose f in more ways than I can choose g and h, then that means that you must have at least one option that I don't. If you choose the right function, you can always win.
Round Three: The Natural Numbers
For this round our set is the set of natural numbers, {0, 1, 2, 3, ...}. Let me start by choosing my function h(x,y). Here's how it works: I'll write down x and y as numbers, and look at their digits. So x = xₙ...x₃x₂x₁, and y = yₙ...y₃y₂y₁. If x and y have different numbers of digits, I'll add some zeros to the start of the shorter one until they match. Then I'll interleave the digits, so that h(x,y) = yₙxₙ...y₃x₃y₂x₂y₁x₁. But look: I can always find the inputs that I started with based on the output. For example, if h(x,y)= 20607341, then I can un-interleave the digits to figure out that x = 31 and y = 2674.
Now you can choose f to be whatever you want. I'll define my function g(w,z) so that it un-interleaves w to get values of x and y, and then gives as its output the value of f(x,y,z). Now look at the expression g(h(x,y),z). h(x,y) interleaves x and y, and then g un-interleaves them, making the whole expression equal to f(x,y,z). This strategy works no matter which function you chose as your f. In other words, I can always win.
But Why?
Okay, sure. We've proved that I have a winning strategy when our set is the set of natural numbers, and you have a winning strategy when our set has three elements. But we don't really understand why that's true. Having a deep understanding of why something is the case is very valuable to a mathematician, because it informs intuition, and a mathematician's intuition is what guides them to pick the interesting and useful results out of the infinite sea of possible theorems. For this particular game, I think the best way to intuitively explain the difference between Round Two and Round Three is in terms of information theory.
In Round Two, my function h has 9 possible inputs, but only 3 possible outputs. So when we put x and y through h, we're losing information. There's no way to know exactly which values of x and y we put into the function just by looking at the output. That means that g is working off of incomplete information about the variables x and y when it tries to recreate f(x,y,z). But in Round Three, h has infinity possible inputs and infinity possible outputs.1 Even though we're condensing two numbers into one, we're not necessarily losing any information. I like this framing because it gives a good intuition for how this result generalizes to other sets. Using the same informal reasoning about information, you might correctly guess that you always have a winning strategy for finite sets with more than one element, and I always have a winning strategy for infinite sets.2
But Why Do We Care?
If you don't know much about abstract algebra, the significance of this is probably not immediately obvious to you. Why should we care who wins this contrived game? Well, it turns out that the statement that I can always win is equivalent to the statement that any function of three variables (your function f) can be broken down into two functions of two variables (my functions g and h). In fact, by a similar argument as in Round Three, any function of three or more variables (on an infinite set) can be broken down into two functions of two variables. This means that in many cases, if we want to study all possible functions of many variables, it's enough to study all possible pairs of functions of two variables. And that, I think, is a pretty cool result.
- Specifically this is the infinite cardinal number aleph-zero (written ℵ₀). Aleph-zero squared is itself, so the number of ways of choosing inputs to h is the same as the number of possible outputs. ^1
- More precisely, I have a winning strategy for all infinite sets that are well-orderable. All the sets of numbers we're familiar with from grade-school math are well-orderable. If we assume that the axiom of choice is true, then all sets are well-orderable. ^2