12,080
edits
Changes
Directory:Jon Awbrey/Papers/Inquiry Driven Systems : Part 6 (view source)
Revision as of 20:32, 14 August 2011
, 20:32, 14 August 2011→6.6. Basic Notions of Group Theory: + raw text
===6.6. Basic Notions of Group Theory===
===6.6. Basic Notions of Group Theory===
<pre>
Many of the most salient themes that have a call to be played out in this work — the application of generic forms of operation to themselves and to each other, the relationship of invariant forms to their variant presentations, and the relationship of abstract forms to their concrete representations — all of these topics arise in a very instructive way within the mathematical subject of group theory. This is most likely due to the fact that group theory, as a mathematical tool, got its start and much of its later sharpening in the process of trying to clarify the physical and formal phenomena that involve these very same issues.
In group theory, fortunately, these themes arise in a slightly plainer fashion, and the otherwise mystifying questions they involve have been studied to the point that their original mysteries are barely observed. Thus, a good way to approach the construction of a RIF is to study the well understood versions of self application and self explanation that turn up in group theory. Given the simpler character and the familiar condition of these topics in that area, they supply a convenient basis for subsequent extensions and help to arrange a staging ground for the types of sign theoretic generalizations that are ultimately desired.
This section develops the aspects of group theory that are needed in this work, bringing together a fundamental selection of abstract ideas and concrete examples that are used repeatedly throughout the rest of the project. To start, I present an abstract formulation of the basic concepts of group theory, beginning from a very general setting in the theory of relations and proceeding in quick order to the definitions of groups and their representations. After that, I describe a couple of concrete examples that are designed mainly to illustrate the abstract features of groups, but that also appear in different guises at later stages of this discussion.
A "series of domains" (SOD) is a nonempty sequence of nonempty sets. A declarative indication of a sequence of sets, typically offered in staking out the grounds of a discussion, is taken for granted as a SOD. Thus, the notation "<Xi>" is assumed by default to refer to a SOD <Xi>, where each Xi is assumed to be a nonempty set.
Given a SOD <Xi>, its cartesian product, notated as "Xi <Xi>" or "Xi Xi", is defined as follows:
Xi <Xi> = Xi Xi = {<xi> : xi C Xi}.
A "relation" is defined on a SOD as a subset of its cartesian product. In symbols, R is a relation on <Xi> if and only if R c Xi Xi.
An "n ary relation" or an "n place relation" is a relation on an ordered n tuple of nonempty sets. Thus, R is an n place relation on the SOD <X1, ..., Xn> if and only if R c X1x...xXn. In various applications, the n tuple elements <x1, ..., xn> of R are called its "elementary relations", "individual transactions", "ingredients", or "effects".
Before continuing with the chain of definitions, a slight digression is needed at this point to loosen up the interpretation of relation symbols in what follows. Exercising a certain amount of flexibility with notation, and relying on a discerning interpretation of equivocal expressions, one can use the name "R" or any other indication of an n place relation R in a wide variety of different fashions, both logical and operational.
First, R can be associated with a logical predicate or a proposition that says something about the space of effects, being true of certain effects and false of all others. In this way, "R" can be interpreted as naming a function from Xi Xi to the domain of truth values B = {0, 1}. With the appropriate understanding, it is permissible to write "R : X1x...xXn > B" to indicate this interpretation.
Second, R can be associated with a piece of information that allows one to complete various sorts of partial data sets in the space of effects. In particular, if one is given a partial effect or an incomplete n tuple, say, one that is missing a value in the jth place, as indicated by the notation "<x1, ..., j, ..., xn>", then "R" can be interpreted as naming a function from the cartesian product of the domains at the filled places to the power set of the domain at the missing place. With this in mind, it is permissible to write "R : X1x...x jx...xXn > Pow(Xj)" to indicate this use of "R". If the sets in the range of this function are all singletons, then it is permissible to write "R : X1x...x jx...xXn > Xj" to specify the corresponding use of "R".
In general, the indicated degrees of freedom in the interpretation of relation symbols can be exploited properly only if one understands the consequences of this interpretive liberality and is prepared to deal with the problems that arise from its "polymorphic" practices, from using the same sign in different contexts to refer to different types of objects. For example, one should consider what happens, and what sort of IF is demanded to deal with it, when the name "R" is used equivocally in a statement like "R = R 1(1)", where a sensible reading requires it to denote the relational set R c Xi Xi on the first appearance and the propositional function R : Xi Xi > B on the second appearance.
A "triadic relation" is a relation on an ordered triple of nonempty sets. Thus, R is a triadic relation on <X, Y, Z> if and only if R c XxYxZ. Exercising a proper degree of flexibility with notation, one can use the name of a triadic relation R c XxYxZ to refer to a logical predicate or a propositional function, of the type XxYxZ >B, or any one of the derived binary operations, of the types XxY >Pow(Z), XxZ >Pow(Y), YxZ >Pow(X).
A "binary operation" or "law of composition" (LOC) on a nonempty set X is a triadic relation * c XxXxX that is also a function * : XxX >X. The notation "x*y" is used to indicate the functional value *(x, y) C X, which is also referred to as the "product" of x and y under *.
A binary operation or LOC * on X is "associative" if and only if (x*y)*z = x*(y*z) for every x, y, z C X.
A binary operation or LOC * on X is "commutative" if and only if x*y = y*x for every x, y C X.
A "semigroup" consists of a nonempty set with an associative LOC on it. On formal occasions, a semigroup is introduced by means a formula like "X = <X, *>", read "X is the ordered pair <X, *>". This form specifies X as the nonempty set and * as the associative LOC. By way of recalling the extra structure, this specification underscores the name of the set X to form the name of the semigroup X. In contexts where there is only one semigroup being discussed, or where the additional structure is otherwise understood, it is common practice to call the semigroup by the name of the underlying set. In contexts where more than one semigroup is formed on the same set, one can use notations like Xi = <X, *i> to distinguish them.
A "unit element" in a semigroup X = <X, *> is an element e in X such that x*e = x = e*x for all x C X. In other words, a unit element is a two sided identity element. If a semigroup X has a unit element, then it is unique, since if e' is also a unit element, then e' = e'*e = e.
A "monoid" is a semigroup with a unit element. Formally, a monoid X is an ordered triple <X, *, e>, where X is a set, * is an associative LOC on the set X, and e is the unit element in the semigroup <X, *>.
An "inverse" of an element x in a monoid X = <X, *, e> is an element y C X such that x*y = e = y*x. An element that has an inverse in X is said to be "invertible" (relative to * and e). If x C X has an inverse, then it is unique to x. To see this, suppose that y' is also an inverse of x. Then it follows that:
y' = y'*e = y'*(x*y) = (y'*x)*y = e*y = y.
A "group" is a monoid all of whose elements are invertible. That is, a group is a semigroup with a unit element in which every element has an inverse. Putting all the pieces together, then, a group X = <X, *, e> is a set X with a binary operation * : XxX >X and a designated element e that is subject to the following three axioms:
G1. (associative) x*(y*z) = (x*y)*z, for all x, y, z C X.
G2. (identity) e*x = x = x*e, for some e C X.
G3. (inverses) x*y = e = y*x, for some y C X,
for all x C X.
It is customary to use a number of abbreviations and conventions in discussing semigroups, monoids, and groups. A system X = <X, *> is given the adjective "commutative" if and only if * is commutative. Commutative groups, however, are traditionally called "abelian groups". By way of making comparisons with familiar systems and operations, the following usages are also common.
1. When one says that X is "written multiplicatively" it means that a raised dot "." or concatenation is used instead of a star for the LOC. In this case, the unit element is commonly written as a one "1", while the inverse of an element x is written as "x 1". The multiplicative manner of presentation is the one that is usually taken by default in the most general types of situations. In the multiplicative idiom, the following definitions of "powers", "cyclic groups", and "generators" are also common.
The "nth power" of x in a semigroup X = <X, .>, for positive integer n, is notated as "xn" and defined as follows. Proceeding recursively, for n = 1, let x1 = x, and for n > 1, let xn = x(n 1).x.
The "nth power" of x in a monoid X = <X, ., 1>, for natural number n, is defined the same way for n > 0, letting x0 = 1 when n = 0.
The "nth power" of x in a group X = <X, ., 1>, for arbitrary integer n, is defined the same way for n > 0, letting xn = (x 1)( n) for n < 0.
A group X = <X, ., 1> is "cyclic" if and only if there is an element g C X such that every x C X can be written as x = gn for some n C Z. In this case, an element such as g is called a "generator" of the group.
2. When one says that X is "written additively" it means that a plus sign "+" is used instead of a star "*" for the LOC. In this case, the notation "x + y" indicates a value in X called the "sum" of x and y. This involves the further conventions that the unit element is written as a zero "0", and may be called the "zero element", while the inverse of an element x is written as " x", and may be called the "negative of x". Usually, but not always, this manner of presentation is reserved for commutative systems and abelian groups. In the additive idiom, the following definitions of "multiples", "cyclic groups", and "generators" are also common.
The "nth multiple" of x in a semigroup X = <X, +>, for integer n > 0, is notated as "nx" and defined as follows. Proceeding recursively, for n = 1, let 1x = x, and for n > 1, let nx = (n 1)x + x.
The "nth multiple" of x in a monoid X = <X, +, 0>, for integer n > 0, is defined the same way for n > 0, letting 0x = 0 when n = 0.
The "nth multiple" of x in a group X = <X, +, 0>, for any integer n, is defined the same way for n > 0, letting nx = ( n)( x) for n < 0.
A group X = <X, +, 0> is "cyclic" if and only if there is an element g C X such that every x C X can be written as x = ng for some n C Z. In this case, an element such as g is called a "generator" of the group.
Mathematical systems, like the R's and X's encountered above, are seldom comprehended in perfect isolation, but need to be viewed in relation to each other, as belonging to families of comparable systems. Systems are compared by finding or making correspondences between them, and this can be formalized as a task of setting up and probing various types of mappings between the sundry appearances of their objective structures. This requires techniques for exploring the spaces of mappings that exist between families of systems, for inquiring into and demonstrating the existence of specified types of functions between them, plus technical concepts for classifying and comparing their diverse representations. Therefore, in order to compare the structures of different objective systems and to recognize the same objective structure when it appears in different phenomenal or syntactic disguises, it helps to develop general forms of comparison that can organize the welter of possible associations between systems and single out those that represent a preservation of the designated forms.
The next series of definitions develops the mathematical concepts of "homomorphism" and "isomorphism", special types of mappings between systems that serve to formalize the intuitive notions of structural analogy and abstract identity, respectively. In very rough terms, a "homomorphism" is a "structure preserving mapping" between systems, but only in the sense that it preserves some part or some aspect of the structure mapped, whereas an "isomorphism" is a correspondence that preserves all of the relevant structure.
The "induced action" of a function f : X >Y on the cartesian power Xn is the function f' : Xn >Yn defined by:
f'(<x1, ..., xn>) = <f(x1), ..., f(xn)>.
Usually, f' is regarded as the "obvious", "trivial", or "tacit" extension that f : X >Y possesses in the space of functions Xn >Yn, and is thus allowed to go by the same name. This convention, assumed by default, is expressed by the formula:
f(<x1, ..., xn>) = <f(x1), ..., f(xn)>.
A "relation homomorphism" from an n place relation P c Xn to an n place relation Q c Yn is a mapping between the underlying sets, h : X >Y, whose induced action h : Xn >Yn preserves the indicated relations, taking every element of P to an element of Q. In other words:
<x1, ..., xn> C P => h(<x1, ..., xn>) C Q.
Applying this definition to the case of two binary operations or LOC's, say *1 on X1 and *2 on X2, which are special kinds of triadic relations, say *1 c X13 and *2 c X23, one obtains:
<x, y, z> C *1 => h(<x, y, z>) C *2.
Under the induced action of h : X1 >X2, or its tacit extension as a mapping h : X13 >X23, this implication yields the following:
<x, y, z> C *1 => <h(x), h(y), h(z)> C *2.
The left hand side of this implication is expressed more commonly as:
x *1 y = z.
The right hand side of the implication is expressed more commonly as:
h(x) *2 h(y) = h(z).
From these two equations one derives, by substituting x *1 y for z in h(z), a succinct formulation of the condition for a mapping h : X1 >X2 to be a relation homomorphism from a system <X1, *1> to a system <X2, *2>, expressed in the form of a "distributive law" or "linearity condition":
h(x *1 y) = h(x) *2 h(y).
To sum up the development so far in a general way: A "homomorphism" is a mapping from a system to a system that preserves an aspect of systematic structure, usually one that is relevant to an understood purpose or context. When the pertinent aspect of structure for both the source and the target system is a binary operation or a LOC, then the condition that the LOC's be preserved in passing from the pre image to the image of the mapping is frequently expressed by stating that "the image of the product is the product of the images". That is, if h : X1 >X2 is a homomorphism from X1 = <X1, *1> to X2 = <X2, *2>, then for every x, y C X1 the following condition holds:
h(x *1 y) = h(x) *2 h(y).
Next, the concept of a homomorphism or "structure preserving map" is specialized to the different kinds of structure of interest here.
A "semigroup homomorphism" from a semigroup X1 = <X1, *1> to a semigroup X2 = <X2, *2> is a mapping between the underlying sets that preserves the structure appropriate to semigroups, namely, the LOC's. This makes it a map h : X1 >X2 whose induced action on the LOC's is such that it takes every element of *1 to an element of *2. That is:
<x, y, z> C *1 => h(<x, y, z>) = <h(x), h(y), h(z)> C *2.
A "monoid homomorphism" from a monoid X1 = <X1, *1, e1> to a monoid X2 = <X2, *2, e2> is a mapping between the underlying sets, h : X1 >X2, that preserves the structure appropriate to monoids, namely, the LOC's and the identity elements. This means that the map h is a semigroup homomorphism from X1 to X2, where these are considered as semigroups, but with the extra condition that h takes e1 to e2.
A "group homomorphism" from a group X1 = <X1, *1, e1> to a group X2 = <X2, *2, e2> is a mapping between the underlying sets, h : X1 >X2, that preserves the structure appropriate to groups, namely, the LOC's, the identity elements, and the inverse elements. This means that the map h is a monoid homomorphism from X1 to X2, where these are viewed as monoids, with the extra condition that h(x 1) = h(x) 1 for all x C X1. As it happens, the inverse elements are automatically preserved if the LOC's and the identity elements are, so a monoid homomorphism suffices to constitute a group homomorphism for a monoid that is also a group. To see why this is so, consider the following chain of equalities:
h(x) *2 h(x 1) = h(x *1 x 1) = h(e1) = e2.
An "isomorphism" is a homomorphism that is one to one and onto, or bijective. Systems that have an isomorphism between them are called "isomorphic" to each other and belong to the same "isomorphism class". From an abstract point of view, isomorphic systems are tantamount to the same mathematical object, differing at most in their manner of presentation and the details of their representation. Usually these differences are regarded as purely notational, a mere change of names. Thus, they are seen as accidental or accessory features of the object, corresponding to different ways of grasping the objective structure that is the main interest of the study but not considered as essential parts of its ultimate constitution or even necessary to its final comprehension.
Finally, to introduce two pieces of language that are often useful: an "endomorphism" is a homomorphism from a system into itself, while an "automorphism" is an isomorphism from a system onto itself.
If nothing more succinct is available, a group can be specified by means of its "operation table", usually styled either as an "addition table" or as a "multiplication table". Table 32.1 illustrates the general scheme of a group operation table. In this case the group operation, treated as a "multiplication", is formally symbolized by a star "*", as in x*y = z. In contexts where only algebraic operations are formalized it is common practice to omit the star, but when logical conjunctions (symbolized by a raised dot "." or by concatenation) appear in the same context, then the star is retained for the group operation.
Another way of approaching the study or presenting the structure of a group is by means of a "group representation", in particular, one that represents the group in the special form of a "transformation group". This is a set of transformations acting on a concrete space of "points" or a designated set of "objects". In providing an abstractly given group with a representation as a transformation group, one is seeking to know the group by its effects, that is, in terms of the action it induces, through the representation, on a concrete domain of objects. In the type of representation known as a "regular representation", one is seeking to know the group by its effects on itself.
Tables 32.2 and 32.3 illustrate the two conceivable ways of forming a regular representation of a group G.
The "ante representation" of xi in G is a function from G to G that is formed by considering the effects of xi on the elements of G when xi acts in the role of the first operand of the group operation. Notating this function as "h1(xi) : G >G", the "regular ante representation" of G is a map h1 : G > (G >G) that is schematized in Table 32.2. Here, each of the functions h1(xi) : G >G is represented as a set of ordered pairs of the form <xj, xi*xj>.
The "post representation" of xi in G is a function from G to G that is formed by considering the effects of xi on the elements of G when xi acts in the role of the second operand of the group operation. Notating this function as "h2(xi) : G >G", the "regular post representation" of G is a map h2 : G > (G >G) that is schematized in Table 32.3. Here, each of the functions h2(xi) : G >G is represented as a set of ordered pairs of the form <xj, xj*xi>.
Table 32.1 Scheme of a Group Multiplication Table
* x0 ... xj ...
x0 x0*x0 ... x0*xj ...
... ... ... ... ...
xi xi*x0 ... xi*xj ...
... ... ... ... ...
Table 32.2 Scheme of the Regular Ante-Representation
Element Function as Set of Ordered Pairs of Elements
x0 { <x0, x0*x0>, ..., <xj, x0*xj>, ..., }
...
xi { <x0, xi*x0>, ..., <xj, xi*xj>, ..., }
...
Table 32.3 Scheme of the Regular Post-Representation
Element Function as Set of Ordered Pairs of Elements
x0 { <x0, x0*x0>, ..., <xj, xj*x0>, ..., }
...
xi { <x0, x0*xi>, ..., <xj, xj*xi>, ..., }
...
In following these maps, notice how closely one is treading in these representations to defining each element in terms of itself, but without quite going that far. There are a couple of catches that save this form of representation from falling into a "vicious circle", that is, into a pattern of self reference that would beg the question of a definition and vitiate its usefulness as an explanation of each group element's action. First, the regular representations do not represent that a group element is literally "equal to" a set of ordered pairs involving that very same group element, but only that it is "mapped to" something like this set. Second, careful usage would dictate that the "something like" that one finds in the image of a representation, being something that is specified only up to its isomorphism class, is a transformation that really acts, not on the group elements xj themselves, but only on their inert tokens, inactive images, partial symbols, passing names, or transitory signs of the form "xj".
These reservations are crucial to understanding the form of explanation that a regular representation provides, that is, what it explains and what it does not. If one is seeking an ontological explanation of what a group and its elements "are", then one would have reason to object that it does no good to represent a group and its elements in terms of their actions on the group elements themselves, since one still does not know what the latter entities "are". Notice that the form of this objection is reminiscent of a dilemma that is often thought to obstruct the beginning of an inquiry into inquiry. A similar pattern of knots occurs when one tries to explain the process of formalization in terms of its effects on the term "formalization". In each case, the resolution of the difficulty turns on recognizing a distinction between the active and passive modes of existence that go with each nameable objective.
In order to have concrete materials available for future discussions of group theoretic issues, the remainder of this section takes up a pair of small examples, the groups of order 4, and uses them to illustrate the chain of definitions and the forms of representation given above.
There are just two groups of order 4. Both are abelian (commutative), but one is cyclic and the other is not. The cyclic group on 4 elements is commonly referred to as "Z4". (The German words "Zahl" = "number" and "Zyklus" = "cycle" together make the notation "Zn" suggestive of the integers mod n, which form a cyclic group of order n under the addition operation.) The acyclic group on 4 elements is usually called the "Klein 4 group" and notated as "V4". (The German name "Vierbein" is the substantive form of an adjective that means "four legged".)
For the sake of comparison, I give a discussion of both these groups. However, because it figures more prominently in another part of the present construction, I discuss V4 first and foremost.
The next series of Tables presents the group operations and regular representations for the groups V4 and Z4. If a group is abelian, as both of these groups are, then its h1 and h2 representations are indistinguishable, and a single form of regular representation h : G > (G >G) will do for both.
Tables 33.1 shows the multiplication table of the group V4, while Tables 33.2 and 33.3 present two versions of its regular representation. The first version, somewhat hastily, gives the functional representation of each group element as a set of ordered pairs of group elements. The second version, more circumspectly, gives the functional representative of each group element as a set of ordered pairs of element names, also referred to as "objects", "points", "letters", or "symbols".
Table 33.1 Multiplication Operation of the Group V4
* 1 r s t
1 1 r s t
r r 1 t s
s s t 1 r
t t s r 1
Table 33.2 Regular Representation of the Group V4
Element Function as Set of Ordered Pairs of Elements
1 { <1, 1>, <r, r>, <s, s>, <t, t> }
r { <1, r>, <r, 1>, <s, t>, <t, s> }
s { <1, s>, <r, t>, <s, 1>, <t, r> }
t { <1, t>, <r, s>, <s, r>, <t, 1> }
Table 33.3 Regular Representation of the Group V4
Element Function as Set of Ordered Pairs of Symbols
1 { <"1", "1">, <"r", "r">, <"s", "s">, <"t", "t"> }
r { <"1", "r">, <"r", "1">, <"s", "t">, <"t", "s"> }
s { <"1", "s">, <"r", "t">, <"s", "1">, <"t", "r"> }
t { <"1", "t">, <"r", "s">, <"s", "r">, <"t", "1"> }
Tables 34.1 and 35.1 show two forms of operation table for the group Z4, presenting the group, for the sake of contrast, in multiplicative and additive forms, respectively. Tables 34.2 and 35.2 give the corresponding forms of the regular representation.
The multiplicative and additive versions of what is abstractly the same group, Z4, can be used to illustrate the concept of a group isomorphism.
Let the multiplicative version of Z4 be formalized as:
Z4(.) = X1 = <X1, *1, e1> = <{1, a, b, c}, ., 1>,
where "." denotes the operation in Table 34.1.
Let the additive version of Z4 be formalized as:
Z4(+) = X2 = <X2, *2, e2> = <{0, 1, 2, 3}, +, 0>,
where "+" denotes the operation in Table 35.1.
Then the mapping h : X1 >X2 whose ordered pairs are given by:
h = {<1, 0>, <a, 1>, <b, 2>, <c, 3>}
constitutes an isomorphism from Z4(.) to Z4(+).
This fact can be verified in several ways: (1) by checking that the map h is bijective and that h(x.y) = h(x) + h(y) for every x and y in Z4(.), (2) by noting that h transforms the whole multiplication table for Z4(.) into the whole addition table for Z4(+) in a one to one and onto fashion, or (3) by finding that both systems share some collection of properties that are definitive of the abstract group, for example, being cyclic of order 4.
Table 34.1 Multiplicative Presentation of the Group Z4(.)
. 1 a b c
1 1 a b c
a a b c 1
b b c 1 a
c c 1 a b
Table 34.2 Regular Representation of the Group Z4(.)
Element Function as Set of Ordered Pairs of Elements
1 { <1, 1>, <a, a>, <b, b>, <c, c> }
a { <1, a>, <a, b>, <b, c>, <c, 1> }
b { <1, b>, <a, c>, <b, 1>, <c, a> }
c { <1, c>, <a, 1>, <b, a>, <c, b> }
Table 35.1 Additive Presentation of the Group Z4(+)
+ 0 1 2 3
0 0 1 2 3
1 1 2 3 0
2 2 3 0 1
3 3 0 1 2
Table 35.2 Regular Representation of the Group Z4(+)
Element Function as Set of Ordered Pairs of Elements
0 { <0, 0>, <1, 1>, <2, 2>, <3, 3> }
1 { <0, 1>, <1, 2>, <2, 3>, <3, 0> }
2 { <0, 2>, <1, 3>, <2, 0>, <3, 1> }
3 { <0, 3>, <1, 0>, <2, 1>, <3, 2> }
Standard references for the above material are:
Jacobson, N. Basic Algebra I.
W.H. Freeman, San Francisco, CA, 1974.
Lang, S. Algebra, 2nd ed.
Addison Wesley, Menlo Park, CA, 1984.
Rotman, J.J. An Introduction to the Theory of Groups, 3rd ed.
Allyn & Bacon, Boston, MA, 1984.
When it comes to the subject of systems theory, a particular POV is so widely propagated that it might as well be regarded as the established, received, or traditional POV. The POV in question says that there are dynamic systems and symbolic systems, and never the twain shall meet. I naturally intend to challenge this assumption, preferring to suggest that dynamic ... [possible buffer fragment]
</pre>
===6.7. Basic Notions of Formal Language Theory===
===6.7. Basic Notions of Formal Language Theory===