description/proof of that for tiles whose sides are right or down maps, hole-less configuration of tiles is commutative iff each tile is commutative
Topics
About: set
The table of contents of this article
Starting Context
- The reader knows a definition of map.
Target Context
- The reader will have a description and a proof of the proposition that for any tiles whose sides are any right or down maps, any hole-less configuration of the tiles is commutative iff each tile is commutative.
Orientation
There is a list of definitions discussed so far in this site.
There is a list of propositions discussed so far in this site.
Main Body
1: Structured Description
Here is the rules of Structured Description.
Entities:
\(\{T^j_l\}\): where \(T^j_l\) is a tile whose left-top, right-top, left-bottom, and right-bottom vertexes correspond to any sets, \(S^j_l, S^j_{l + 1}, S^{j + 1}_l, S^{j + 1}_{l + 1}\), and whose top, bottom, left, and right sides correspond to any maps, \(r^j_l: S^j_l \to S^j_{l + 1}, r^{j + 1}_l: S^{j + 1}_l \to S^{j + 1}_{l + 1}, d^j_l: S^j_l \to S^{j + 1}_l, d^j_{l + 1}: S^j_{l + 1} \to S^{j + 1}_{l + 1}\), where \(\{T^j_l\}\) is not necessarily rectangle but is hole-less
//
Statements:
\(\{T^j_l\}\) is commutative
\(\iff\)
\(\forall T^j_l \in \{T^j_l\} (T^j_l \text{ is commutative })\)
//
"hole-less" here means that for any map-connected ordered pair of vertexes, any path can be continuously transformed to the standard path (which means that at each vertex on the path, the path goes right if possible). This proposition does not particularly claim or prove that that "hole-less"-ness equals the geometrical hole-less-ness.
Being "commutative" means that for each map-connected ordered pair of vertexes, the possible maps are the same. For the \((S^j_l, S^{j + 1}_{l + 1})\) pair, that means that \(d^j_{l + 1} \circ r^j_l = r^{j + 1}_l \circ d^{j, l}\).
The \((S^{j + 1}_{l + 1}, S^j_l)\) pair (among others) is not map-connected, because there is no map that maps \(S^{j + 1}_{l + 1}\) into \(S^j_l\): there is no left or up map.
2: Note
This proposition is hard to express in words but graphically, it is not particularly hard.
A typical configuration is a rectangle with \(m \times n\) tiles. In fact, we do not see any immediate necessity for any non-rectangular case, and not-ruling-out non-rectangular cases is just for "just in case".
"hole-less"-ness here may seem not easy to check generally, but any rectangular configuration is definitely hole-less and most practical cases will be clear to be hole-less.
The motivation for this proposition is that when we need to check the commutativity of a diagram, do we need to check all the possible paths?
3: Proof
Whole Strategy: Step 1: see that if \(\{T^j_l\}\) is commutative, each \(T^j_l\) is commutative; Step 2: for each map-connected ordered pair of vertexes, choose the standard path; Step 3: see that the map of each path equals the map of the standard path.
Step 1:
If \(\{T^j_l\}\) is commutative, each \(T^j_l\) is commutative, because it is just a special case of that the map-connected ordered pair of vertexes is on the single \(T^j_l\).
Step 2:
Let \((S^j_l, S^m_n)\) be any map-connected ordered pair of vertexes.
Among the paths that map \(S^j_l\) into \(S^m_n\), let us choose the unique standard path.
Starting from \(S^j_l\), at each vertex on any path, let the path go 1 right if possible and go 1 down if not possible: "possible" means that the path keeps an option of reaching the destination if it goes 1 right at the vertex, does not mean that the path can just go right without any consideration for keeping an option of reaching the destination.
That rule determines the standard path uniquely, because at each vertex, whether it is possible to go 1 right is uniquely determined.
For example, when the configuration is a rectangle, the path goes right straight from \(S^j_l\) to \(S^j_n\) and goes straight down to \(S^m_n\); when the configuration is not any rectangle, the path may not be so straight forward (the path may not be able to go right straight to \(S^j_n\) because there may not be such a path, and even if there is such a path, there may not be the straight down path from \(S^j_n\) to \(S^m_n\)).
Step 3:
If the map of each possible path equals the map of the standard path, the proposition will hold, so, let us see that.
Let \(\lambda\) be any possible path.
When \(\lambda\) equals the standard path, the map of \(\lambda\) equals the map of the standard path.
Let us suppose that \(\lambda\) does not equal the standard path.
That means that \(\lambda\) goes 1 down at a vertex where going 1 right is possible.
\(\lambda\) takes the missed going 1 right at a vertex afterward.
That part of the path is L-shaped down-right.
That L-shape is the left-side-bottom-side of a tile: that guarantee is the supposition of "hole-less"-ness.
As the tile is commutative, the L-shape can be replaced by the top-side-right-side of the tile.
So, the path can be transformed to the top-right direction.
If the new path equals the standard path, it is finished.
Otherwise, the new path can be transformed likewise to the top-right direction.
And so on. This process cannot go forever, because the path keeps being transformed to the top-right direction but cannot go beyond the standard path, and so, it will equal the standard path eventually.
