## Tic-Tac-Toe and Homomorphism

The figure to the right illustrates the mappings involved in establishing a homomorphism between two systems. At the top we have a set, X and a function, . which maps X x X into X. For example, the function might be addition defined over the set of integers. At the bottom is another set, Y and another function, *. The arrows labeled with f indicate that there exists a map from each element of X to some element of Y. Note that the map is preserved under application of the function. Also, note that the arrows go from X to Y. If the arrows also went from Y to X then we would have an isomorphism. That is, there would also be a map from each element of Y to each element of X and the mapping would be referred to as a one-to-one mapping.

The animation below is another variation on the Tic-Tac-Toe game. The familiar 3 x 3 matrix provides the locations for the moves. However, the moves have been altered.

Notice that each move begins as a vertical stroke. This vertical stroke is then rotated either 45 degrees clockwise from the vertical or 45 degrees counterclockwise from the vertical. The resulting angled lines correspond to the two different players moves; X and O in the standard version of Tic-Tac-Toe.

Let S stand for the vertical stroke; c45 for the clockwise rotation; and cc45 for the counterclockwise rotation. Let c45(S) stand for the composition of the vertical stroke and clockwise rotation move and analogously cc45(S) stand for the composition of the vertical stroke and counterclockwise rotation move.

Note that despite this change, you and I would probably agree that the games are functionally the same. Your knowledge of how to play the standard version would transfer directly to this new setting

Standard Tic-Tac-Toe and this stroke-rotate version are not isomorphs but clearly they are closely related. However, consider creating a new version exactly as the old except that it is now played over a 3 x 4 matrix rather that a 3 x 3 matrix. Such a setting is illustrated in the image on the right.

Note that it isn't obvious that knowledge of how to play the 3 x 3 game will transfer to the 3 x 4 game because they clearly are not isomorphs. For example, in this 3 x 4 game an even number of moves is involved whereas the 3 x 3 involves an odd number of moves.

Finally, consider the setting depicted in this last image. The 3 x 3 matrix has been altered and only seven positions remain. This version involves an odd number of moves, but it is not obvious that there is a map between the 3 x 3 and this version that constitutes a homomorphism.

Hopefully, these examples have sharpened your intuitions concerning the ideas of isomorphism, homomorphism and functional equivalence. If it hasn't already occurred to you, let me point out that determining whether or not any of these relations hold between two systems is usually not a simple matter.

And, if the systems under study have not already been appropriately characterized mathematically, we can't even ask the question. And, even then answering the question is nontrivial.