Mathematics of Ringiana and Ringsanity III: Improving Infinities with Sets

Previous entry II: Solving x + x = x, first entry I: Moves of self-similarity.

To make sense out of our solution x = ∞ and upgrade it to a statement about the object X with the measurement x, we introduce sets. Rigorous axiomatic treatment of sets is long; instead, we follow our intuition and define a set as a collection of elements. Here is a set of 3 people

   S = { Ann, Bob, Carl }.

We list elements of a set inside parenthesis, separated by a comma. Order does not matter, and we can also write 

S = { Carl, Ann, Bob }.

 Exercise: In how many ways can you order elements of this set S? How many ways are there to list elements of a set of 5 people? Can you find a general formula if there are n elements in a set, for n = 1, 2, 3, 4, ... ? 

The number of elements in a set is called its cardinality (it's ok to use "size" if you think "cardinality" is too long). We write cardinality of S as | S |. For our set S above, | S | = 3. 

The empty set with no elements is allowed and denoted ∅.  Listing its elements does not take much space:

  ∅ = { }

and there is a pleasant formula 

     | ∅ | = 0

saying that the cardinality (size) of the empty set ∅ is zero. We won't go  below zero - there are no sets of size -1, -2, and so on. (To interpret the notion of a set of negative size, one needs to do much more - first linearize the concept of a set, then linearize the notion of the boundary of a shape. Some day we'll get to that story.)

Sets can contain various objects; consider this set T of three fruits T = { apple, melon, strawberry }. Set T has cardinality three, | T | = 3, just like S. Let's write S and T side by side: 

S = {Ann, Bob, Carl}   T = {apple, melon, strawberry} 

S and T have the same number of elements. We can match their elements, for instance, by giving apple to Ann, melon to Bob, and strawberry to Carl. A matching between elements of S and T is called an isomorphism between S and T; we denote isomorphism property by the congruence sign 

    S ≅ T 

and say "S is congruent to T" or  "S and T are isomorphic".  

An isomorphism is also called a bijection between elements of S and T. To each element of S we assign an element of T so that different elements of T are assigned to different elements of S (we don't want Bob and Carl to fight over a single strawberry), and each element of T is assigned to some (and unique) element of S. 

If two sets are isomorphic, S ≅ T, they have the same size: 

| S | = | T |  

  

On a deeper level, if two sets are isomorphic, there are many isomorphisms between them unless the sets are really really small (in which case there is only one isomorphism). For our sets S and T,  we can instead choose an isomorphism that gives melon to Ann, apple to Carl, and strawberry to Bob. And there a few other isomorphisms. By the way, the number of isomorphisms between two sets with n elements each is also the number of ways to order elements of either set (this is just me reminding you about the exercise above). 

There is a difference between saying that two sets are isomorphic and choosing a particular isomorphism between them. Ann, Bob, and Carl, the good inhabitants of S, would surely prefer to choose an isomorphism, any isomorphism, between S and T and start eating, rather than spend time staring at elements of T knowing that an isomorphism between them and the set of fruits exists, and more than one.   

In our more advanced examples and manipulations on sets, we will downplay the emotional side of set theory and for the most part will stick to sets of numbers, sequences and points. 

Mathematicians allow infinite sets. In an earlier post we've encountered the infinite set of natural numbers 

N = { 0, 1, 2, 3, ... } .

If a set T is finite, and we create a bigger set U by adding more elements to T, then sets T and U cannot be isomorphic since U has bigger cardinality that T. Interestingly, that is not the  case with infinite sets. 

Infinite sets are strange - we can add elements to them without changing their size. For instance, let's enlarge natural numbers N by adding -1 and calling the resulting set M: 

M = { -1, 0, 1, 2, ... }. 

M properly contains N. That is, every element of N is also an element of M, and some element of M is not in N. In this sense, M is strictly bigger than N. But actually M and N are isomorphic. To construct an isomorphism, we need to assign elements of M to elements of N in a nice (bijective) way. One such bijection is easy to guess if we put N and M next to each other:  

N = { 0,  1, 2, 3, ... }

M = { -1, 0, 1, 2, ... }.

Simply shift every element of N down by 1, that is, assign -1 to 0, 0 to 1, 1 to 2 and so on. To element n of N we assign element n-1 of M, for n = 0, 1, ... This is a sort of infinite shift, and this neat game can only be played with infinite sets. We do get a bijection between N to M this way, even though M contains all elements of N and an extra element. 

Now we come back to our task from the first post, looking for an object X isomorphic to two copies of itself. Let's take an infinite set as X, and, specifically, the set N of natural numbers. Is there a bijection between N and two copies of N? To construct one, we split N into two infinite sets. Any splitting would do, and to keep it simple split N into sets of even and odd integers: 

Even = { 0, 2, 4, 6, 8, ... }  

Odd = { 1, 3, 5, 7, ... } .  

We can write 

N = Even ∪ Odd

to denote that N is a union of two sets, Even and Odd. 

A brief side trip into difference between the usual union of sets and the disjoint union is needed. The usual union 

  X ∪ Y 

of sets X and Y consists of elements of X and elements of Y. If the same element b appears in both X and Y we list it only once in the union. For instance, 

{ a, b, c }  ∪ { b, c, d, e}  = { a, b, c, d, e}.

b appears in both sets, and then once in the union, ditto for c. An element cannot appear in a set more than one. 

Sometimes, we need to engineer an artificial union of two sets and keep track of both copies of each element that appears in X and Y. It's called the disjoint union of X and Y and denoted 

  X ⨆ Y

To implement the disjoint union, for each b that's in both X and Y we add additional labels to signify that it came from a particular set. Relabel b in X by b₀ and b in Y by b₁ to create two different copies of b and same for c in X and Y. Then, 

for the disjoint union of X and Y as above we get 

{ a, b, c }  ⨆ { b, c, d, e}  = { a, b₀, b_1, c₀, c₁, d, e}.

The size of the disjoint union X ⨆ Y is the sum of sizes of X and Y 

  | X ⨆ Y | = | X | + | Y | ,

a simpler formula when compared to  the more familiar case of just the union of sets, where an additional term, the size of the intersection X ∩ Y, enters the equation: 

| X ∪ Y | = | X | + | Y | - | X ∩ Y | .

Since Even and Odd sets in the decomposition of natural numbers N have no elements in common (no number is both even and odd), we can rewrite the union as the disjoint union 

N = Even  ⨆  Odd

where, recall, 

Even = { 0, 2, 4, 6, 8, ... } 

Odd = { 1, 3, 5, 7, ... }.  

There are many bijections between Even and N and between Odd and N. For a bijection between Even and N we choose the one taking 0 to 0, 2 to 1, 4 to 2, 6 to 3, etc. In general, even number 2n is taken to natural number n. Ditto to get a bijection between Odd and N. Take 1 to 0, 3 to 1, 5 to 2, 7 to 3 and so on. Odd number 2n+1 goes to natural number n, for n = 0, 1, 2, ... These bijections give us isomorphisms between sets

  Even  ≅  N   and  Odd  ≅  N

Combining the decomposition N = Even ⨆ Odd with these isomorphisms, we get an isomorphism between N and two copies of N :

  N  ≅  N ⨆ N   

giving us a desired object X isomorphic to two copies of itself together with a particular isomorphism. What about the measurement x of X  that must equal infinity? That measurement is the cardinality (number of elements) of N. It is indeed infinite, and we write 

| N |  =  ∞ 

Actually, cardinalities of infinite sets constitute a sophisticated hierarchy, but for now we observe that N is an infinite set carrying an appropriate label ∞ for its size. 

To summarize the fruits of today's labor, other than those in the set T, we did find a solution to the equation X = X + X  in the world of infinite sets and isomorphisms between them. The next couple of posts will consider ways to prettify and further improve this answer. 

Mathematics of Ringiana and Ringsanity II: Solving x + x = x

This post continues part I: Moves of self-similarity.

Ringiana (for Android and iPhone), Ringsanity (for iPhone), and the math behind these games are based on the idea of manipulating objects that are identical to two copies of themselves. Imagine an abstract object X that can be identified with the double of itself. For lack of notation and clear notion of doubling an object we are going to be informal and denote the double by X+X. Then we are looking for X such that 

X + X = X 

Imagine that X, however abstract, admits some tangible invariant or measurement, such as size, area, length, or volume. Denote the invariant by x. Presumably, the equation X + X = X should translate into the corresponding property of the invariant 

x + x = x 

Say x is a number, then we are trying to solve the equation

2x = x 

Cracking it is not too hard, but, sadly, gives us a not-too-useful unique solution 

x = 0  

telling us that the measurement is zero. At this point it's ok to give up - our object X will have no useful measurements or nontrivial invariants to show. Or we can become creative and set x to infinity 

x = ∞   

Not trying to be too clever, let's think of infinity as a very large number, or better a sequence of numbers that get bigger and bigger. If we can operate on infinity as on a usual number, adding ∞ and a number should be possible - and the answer is easy to guess: 

  ∞ + 10 = ∞ 

and, more generally,

∞ + n = ∞

for any number n. Making n larger and larger, we should get

  ∞ + ∞  = ∞

and suddenly rejoyce in our Eureka moment -- a nontrivial solution is at hand, for our mysterious measurement x is infinity: 

x =  ∞

Whether infinity can be treated as a legitimate number is a tricky question. Examine the simplest popular number system - integers, usually denoted Z. You can add and subtract integers, with these operations satisfying lots of important properties (axioms). Once you add infinity to Z, the structural beauty of integers breaks down. What is ∞ - ∞, infinity minus infinity? It can potentially be anything. Both infinities in the expression 

∞ -  ∞

can be thought of as limits of large numbers. If I choose the sequence of increasing numbers 1,2,3,4, ... for the first infinity and a faster growing sequence 1,2,4,8,16,...,2048,... for the second, hopefully the difference ∞ - ∞ should correspond to the sequence of differences: 

1 - 1 = 0,  2 - 2 = 0, 3 - 4 = -1, 4 - 8 = -4, ..., 

10 - 2048 = - 2038, ... ,

a sequence of negative numbers which should describe -∞, minus infinity. Do we get that ∞ - ∞ = - ∞ ? Not really, for if we swap the sequences and examine the differences, the numbers will be positive and large, and one can as well say that ∞ - ∞ = ∞. With a tiny amount of extra work you can set up the sequences to get ∞ - ∞ = n, for any number n. The difference of two infinities behaves pretty democratically and can take on any value. This teaches us to treat infinities carefully and don't extend the familiar operations on numbers to them in a cavalier way.

Allowing infinity into our world to get a nontrivial solution to the equation 

 x + x = x 

is not a bad idea, however. Something has to give, and we choose to disallow subtraction from our system. Let's keep addition and multiplication, to at least have something. Without subtraction, we can as well downsize from integers to natural numbers, denoted N. They are 0, 1, 2, 3, 4, ... Due to historical and cultural differences in teaching mathematics, some people consider 0 a natural number and some do not. You do get a richer structure if you include 0, and we follow this convention. 

After adding infinity ∞ to natural numbers N both addition and multiplication can still be defined on this larger system and will share many properties with the corresponding operations on natural numbers. Some other properties will fail, though, and the union of infinity and natural numbers is not a particularly beautiful mathematical structure.   

Luckily, the day can be saved: the union of natural numbers and infinity is a shadow of a better and healthier structure that will be revealed in the next installment of the series. 

 

Mathematics of Ringiana and Ringsanity I: Moves of self-similarity

My background is in math, and I do research in pure mathematics at Columbia University. Recently, as a side gig, I and a couple of friends (Nikolay Gromov and Sergey Nemirovsky) developed two mobile games, Ringiana and Ringsanity. Ringiana is available for both iPhone and android, while Ringsanity you can get for iPhone, with  android version in the works. 

These are puzzle-like games, with easy to describe moves but unusual building blocks. Actually, there are no minimal building blocks in these games. Any object can be split into two objects and any two consecutive objects can be merged into a single one. We chose to keep the number of objects constant and equal to four, to match the number of colors in the Ringiana game. To keep the number of objects the same, every time you split an object, two other objects merge, and every time you merge two objects, one of the remaining objects breaks into two, with the total of four objects at any moment. 

Here's the Youtube tutorial for Ringiana, to show you what these convoluted operations are: 

Secretly, we're hoping you are ready to try the real thing and download the game. And, after managing to invent two nouns to name the games, we are still at a loss for a new verb to describe these simultaneous merge-split moves - suggestions are very welcome! 

The unusual feature of our modest contributions to the overcrowded game sections of mobile app stores is this absence of elementary blocks. Think of the games you've played - they all have characters or elementary objects in the background, like atoms, that cannot be decomposed any further. In Tetris, these are the four-square blocks that drop down and the little squares of the grid, in Pac-Man it's the main character, its chasers or groupies, the background grid pieces, and the food the character consumes. These objects may vanish, may reappear, may perhaps merge in pairs into a different basic object (think 2048 or Triple Town), but they don't have any infinite hierarchical or self-similar structure that we've created for the basic objects of our puzzles. 

Once you learn the moves, the games are easy to play. In Ringiana, you'll quickly see that a target configuration (making each piece monochromatic) can be eventually reached no matter what the starting position is, and the challenge becomes finding a short solution. Well, more carefully speaking, the really hard problem is finding a solution with the minimal number of steps. This problem is a great topic for another blog post, and some day we'll come back to it. Ringiana is not only about math research, of course, and we are also hoping that people can simply enjoy playing it and solving the puzzles without exerting themselves to find the shortest way.

With Ringsanity we've decided to be meaner. There are fewer moves available compared to Ringiana (the really interesting ones stayed, of course), and the target configurations are more varied. Ringsanity is a tougher game than Ringiana, unless you're on a hunt for the shortest solutions, in which case both games should prove hard. 

Friends we've shown the game to often take their time to get used to the merge-split moves, but all eventually master them. The same moves are behind some pretty fundamental yet mostly mysterious and poorly understood mathematical structures that go under the name Thompson groups. Some researchers have apparently been so frustrated by the difficulties these groups represent even to the best and brightest of us that they've taken to calling them vagabond groups and chameleon groups. 


The creators of Ringiana and Ringsanity did not fare any better than those researchers and have not proved any magic theorems uncovering the deep structure of Thompson groups. But we did make the games. We hope that releasing Ringiana and Ringsanity will attract more attention to the math behind Thompson groups and speed up progress in unvagabonding them.

Starting in part II, we delve into Ringianity math.