description/proof of that associativity for 3 items allows any association
Topics
About: structure
The table of contents of this article
Starting Context
- The reader knows a definition of structure.
Target Context
- The reader will have a description and a proof of the proposition that for any structure, the associativity for any 3 items allows any association.
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:
\(S\): \(\in \{\text{ the structures }\}\)
\(*\): \(\in \{\text{ the operations of } S\}\)
//
Statements:
\(\forall s_1, s_2, s_3 \in S ((s_1 * s_2) * s_3 = s_1 * (s_2 * s_3))\)
\(\implies\)
\(s_1 * ... * s_n := (...((s_1 * s_2) * s_3) * ... * s_{n - 1}) * s_n\) can be associated in any way
//
2: Note
Associativity is generally defined with respect to 3 items, which is being understood to allow any associativity. Let us confirm that that is indeed the case.
3: Proof
Whole Strategy: Step 1: for each \(1 \le j \le n - 1\), associate \(s_j\) and \(s_{j + 1}\) 1st; Step 2: conclude the proposition.
Step 1:
\(s_1 * ... * s_n := (...(((...((s_1 * s_2) * s_3) * ... * s_{j - 1}) * s_j) * s_{j + 1}) * ... * s_{n - 1}) * s_n\).
Letting \(a := (...((s_1 * s_2) * s_3) * ... * s_{j - 1})\), it is \((...((a * s_j) * s_{j + 1}) * ... * s_{n - 1}) * s_n\).
Applying the associativity for 3 items to \((a * s_j) * s_{j + 1}\), \(= (...(a * (s_j * s_{j + 1})) * ... * s_{n - 1}) * s_n = (...((...((s_1 * s_2) * s_3) * ... * s_{j - 1}) * (s_j * s_{j + 1})) * ... * s_{n - 1}) * s_n\).
So, any \(s_j\) and \(s_{j + 1}\) can be associated.
Step 2:
Letting \(b := s_j * s_{j + 1}\), it is \((...((...((s_1 * s_2) * s_3) * ... * s_{j - 1}) * b) * ... * s_{n - 1}) * s_n\).
By Step 1, its any neighboring 2 items can be associated.
That is what it means by \(s_1 * ... * s_n\) "can be associated in any way".
