Page 7 of 8 FirstFirst ... 5678 LastLast
Results 61 to 70 of 80

Thread: How many groups and semigroups and rings and the like - abstract algebra

  1. Top | #61
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    16,221
    Archived
    16,829
    Total Posts
    33,050
    Rep Power
    97
    Another one we may call the maximum semigroup. Consider a set S of completely ordered entities like real numbers or their subsets. Use operation

    a*b = max(a,b)

    It is a semigroup with identity min(S) and zero max(S) if they exist. It is idempotent: max(a,a) = a, making it a band. It is commutative, making it a semilattice.


    Now consider the bicyclic semigroup: (A,A) for a set A of completely ordered numbers (real numbers and their subsets, some selections of complex numbers). The operation is

    (a,b)*(c,d) = (a - b + t, d - c + t) where t = max(b,c)

    Its identity is (min(A),min(A)) if min(A) exists and its zero is (max(A),max(A)) if max(A) exists.


    Another property: the cancellative property. Left cancellativity: a*b = a*c implies b = c. Right cancellativity: b*a = c*a implies b = c. Two-sided cancellativity is plain cancellativity. All groups have it, but many semigroups don't. The null semigroup, for instance. The left-zero semigroup is right cancellative but not left cancellative, having only partial cancellativity.

  2. Top | #62
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    16,221
    Archived
    16,829
    Total Posts
    33,050
    Rep Power
    97
    About idempotence, every semigroup element can be idempotent, but only one group element can be: the identity.

    Let us see what happens to a ring when all its elements are idempotent. That makes it a "Boolean ring", related to how Boolean functions are idempotent: f(x,x) = x where f is "and" or "or" and x = "true" or "false".

    Consider the idempotence of x + x:

    x + x = (x + x)^2 = x^2 + x^2 + x^2 + x^2 = x + x + x + x
    Thus, x + x = 0 and the ring has characteristic 2 -- 2*(everything) = 0

    Now consider multiplication:
    x + y = (x + y)^2 = x^2 + x*y + y*x + y^2 = x + y + x*y + y*x
    Thus, 0 = x*y + y*x
    Add x*y to both sides: x*y = x*y + x*y + y*x = y*x from having char 2.
    Thus, an idempotent ring is commutative.

    This means that some semigroups cannot be multiplication semigroups for rings.

    Proofs from Idempotent Ring has Characteristic Two - ProofWiki and Idempotent Ring is Commutative - ProofWiki

    ProofWiki is a big compendium of proofs of a lot of mathematical propositions.


    An idempotent semigroup is not nilpotent, because an idempotent entity raised to an arbitrary power gives itself, and for nilpotence, some power of every element must be the semigroup's zero.

    For a ring, something similar applies, though the idempotence and nilpotence apply to multiplication and though the nilpotence convergent point is 0, the additive identity.

  3. Top | #63
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    16,221
    Archived
    16,829
    Total Posts
    33,050
    Rep Power
    97
    Now to ideals of semigroups.
    For semigroup S,
    Left ideal: S*J <= J
    Right ideal: J*S <= J
    Two-sided (plain) ideal: union(S*J,J*S) <= J

    S itself is an ideal, the trivial ideal, and S is "simple" if it only contains that ideal. Every ideal is a subsemigroup, and semigroup powers are also ideals: S*S, S*S*S, ...

    S is "zero-simple" if it contains a zero z, if S^2 != {z}, and if its only ideals are S itself and {z}.

    For instance, the ideals of (N0,+) are, for each a in N0, {a, a+1, a+2, a+3, ...}

    Turning to the left-zero semigroup, its only left ideal is S, while its right ideals are S and all its subsets.

    One can simplify the task of finding ideals by looking at "principal ideals", ideals generated by semigroup elements. One can then find other ideals by taking unions of those for different elements. For them, we use S1 = semigroup + added-on identity if not already present.

    Left: L(a) = S1*a = union(S*a,{a})
    Right: R(a) = a*S1 = union(a*S,{a})
    Two-sided: J(a) = S1*a*S1 = union(S*a*S,S*a,a*S,{a})

    For Green's relations, we need the intersection of left and right:
    Intersection: H(a) = intersect(L(a),R(a))

    Green's relations are: a L b = L(a) equal to L(b), a R b = R(a) equal to R(b), a J b = J(a) equal to J(b), a H b = H(a) equal to H(b), and an extra one, a D b if there is some c that makes a L c and c R b. For finite semigroups, a D b = a J b. These relations split up S into classes whose members satisfy these relations relative to each other.

    Let's look at these semigroups.

    The principal ideals of (N0,+) are J(a) = {a, a+1, a+2, ...} Since this semigroup is commutative, J(a) = L(a) = R(a) = H(a).

    The principal ideals of (N1,*) are J(a) = {a, 2a, 3a, ...} Those of (N0,*) are J(a) = {0, a, 2a, 3a, ...} and for a = 0, {0} the zero ideal.

    For the rectangular band, L((i,j)) = {(x,j) for all x in I}, R((i,j)) = {(i,y) for all y in J}, J((i,j)) = S, H((i,j)) = {(i,j)}

    For the maximum semigroup (band, semilattice), J(a) = {x in S for x >= a}

    For the bicyclic semigroup
    (a,b)*(c,d) = (a - b + t, d - c + t) where t = max(b,c)

    L((a,b)) = {((min)+x,b+y) for x,y >= 0}
    R({a,b}) = {(a+x,(min)+y) for x,y >= 0}
    J({a,b}) = S
    H({a,b}) = {(a+x,b+y) for x,y >= 0}

  4. Top | #64
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    16,221
    Archived
    16,829
    Total Posts
    33,050
    Rep Power
    97
    There's a result called Green's theorem, one that can find us the subgroups that a semigroup contains. Not just semigroups but full-scale groups.

    If a H a^2 or H(a) = H(a^2) then a is the identity of a group whose elements b satisfy a H b or H(a) = H(b).

    Let's see how this works for integers under multiplication: (Z,*).

    Its principal ideals J(a) are {0} for a = 0 and |a|*Z for a != 0. Both positive and negative a produce the same ideals. For commutative semigroups, L(a) = R(a) = J(a) = H(a).

    Let us now look for values of a where J(a^2) = J(a). This gives us a^2*Z = |a|*Z with solutions a = +-1. So we find an identity, 1, with ideal J(1) = Z. The other semigroup element with that ideal is -1: J(-1) = Z also. Thus, we have found a group, {1,-1}. Also, J(0) = {0} the only element to have that ideal, and 0^2 = 0, so there is a second group, {0} - the trivial group.

    Gaussian integers are similar, with the principal ideal for (a+b*i) having the form {(a*u-b*v) + (a*v+b*u)*i for integer u, v}. The absolute square has value (a^2+b^2)*(u^2+v^2). Its minimum nonzero value is (a^2+b^2). Checking on whether H(a^2) = H(a), this means that the minimum nonzero values must be equal: (a^2+b^2)^2 = (a^2+b^2). That is only possible if a^2+b^2 = 0 or 1, giving solution a = b = 0 (the semigroup's zero), a = +-1 and b = 0, and a = 0 and b = +-1. Thus, this semigroup contains group parts {1,i,-1,-i} and {0}.

    Another case is the Eisenstein integers, a+b*w where w = (-1+sqrt(-3))/2 making a triangular grid; the Gaussian integers make a square grid. Here also, one finds group parts {1,1+w,w,-1,-1-w,-w} and {0}. Note that w^2+w+1 = 0

  5. Top | #65
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    16,221
    Archived
    16,829
    Total Posts
    33,050
    Rep Power
    97
    That document mentions the "Rees matrix semigroups" - all finite zero-simple semigroups and some infinite ones have that form. Their construction is a bit complicated. Consider group G, sets I, U, and matrix P with values P(u,i) (u in U, i in I) either being z or a member of G. Every row and column of P contain at least one element other than z.

    The semigroup's elements are the zero, z, and (i,a,u) with i in I, a in G, and u in U. The semigroup operation is

    (i,a,u)*(j,b,v) = z if P(u,j) = z or else (i,a*P(u,j)*b,v) otherwise

    All the elements are "regular", for element a, there is some x such that a = a*x*a. The zero z is regular, and for (i,a,u), the corresponding values are (j, nv(p(u,j))*inv(a)*inv(p(v,i)), v) for some j, v.

    (i,a,u) is idempotent eqv p(u,i) != z and a = inv(p(u,i))
    eqv = is equivalent to

    Green's relations:
    (i,a,u) R (j,b,v) eqv i = j
    (i,a,u) L (j,b,v) eqv u = v
    (i,a,u) H (j,b,v) eqv i = j and u = v
    The only two-sided ideals are the semigroup itself and {z}.

    The rectangular property:
    a*b D a eqv a*b R a
    a*b D b eqv a*b L b

    Rees matrix semigroups are "completely zero-simple", meaning that they don't have infinite chains of left or right ideals, each one being a sub-ideal of a neighbor. (N0,+) has an infinite chain of ideals, for instance. Finite semigroups don't have infinite chains, of course.

    Likewise, for rings, an "Artinian ring" is one without some infinite chain of ideals. Every finite ring is Artinian, of course.

  6. Top | #66
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    16,221
    Archived
    16,829
    Total Posts
    33,050
    Rep Power
    97
    Then this document gets into "regular semigroups". A semigroup element a is regular if there exists some x such that a = a*x*a. x need not be unique. If all a semigroup's elements are regular, then that semigroup is regular.

    Bands are regular, but semigroups like (N0,+) and (Z,*) are not.

    Elements a and b are inverse if a = a*b*a and b*a*b. Inverses need not be unique. Consider a rectangular band:

    (i,j)*(k,l)*(i,j) = (i,j)
    (k,l)*(i,j)*(k,l) = (k,l)

    Every pair of elements is an inverse pair.

    Rees matrix semigroups are also regular, as are groups.

    If inverses are unique, then the semigroup is an "inverse semigroup".

    The bicyclic semigroup is regular: (a,b)*(b,a)*(a,b) = (a,b) and it is also inverse. Its idempotents are (a,a) and their products (a,a)*(b,b) = (t,t) where t = max(a,b).

    Inverse-semigroup theorem: being inverse <-> regular with the idempotents forming a semilattice (commutative subsemigroup).

    The document ended about there.

    -

    Nil-3 semigroups are not regular, except for the trivial one, {z}. Their only regular element is their zero: S^3 = {z}. Thus, most semigroups are not regular.

  7. Top | #67
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    16,221
    Archived
    16,829
    Total Posts
    33,050
    Rep Power
    97
    We have counts of nil-2 semigroups -- 1 -- and of nil-3 semigroups, and they seem to be nearly all semigroups. But what of the remainder?

    Groups are a subset of monoids, and most monoids are trivial-action ones: (group part) * (semigroup part) = (no-change permutation of semigroup part). Nontrivial action: permutation with changes, like (1,2) -> (2,1). Since semigroups increase roughly as (n/(2*log(n)+1))^(n^2), they increase much faster than groups, and the most common kind of monoid is (semigroup) + (identity).


    Idempotent semigroups or bands are semigroups with all elements idempotent: x*x = x. They are obviously not nilpotent, since S*S = S.

    In my researches, I found counts of semilattices by number of generators. A semilattice is a commutative idempotent semigroup. However, those numbers do not well into counts of semilattices by number of elements.

    Let us consider all the sets of subsets of some set, sets of subsets that are closed under union or intersection of those subsets. Of the subsets, I'll write {1,2,3} as 123 and {} as _ If nothing is in some set, I'll write .

    0: . , _
    1: . , _, 1, _ 1
    2: . , _, 1, 2, 12, _ 1, _ 2, _ 12, 1 2, 1 12, 2 12, _ 1 2, _ 1 12, _ 2 12, 1 2 12, _ 1 2 12
    (semilattices: all)

    Empty set present:
    0: _
    1: _, _ 1
    2: _, _ 1, _ 2, _ 12, _ 1 2, _ 1 12, _ 2 12, _ 1 2 12
    (semilattices: no identity)

    Empty set absent:
    0: .
    1: . , 1
    2: . , 1, 2, 12, 1 2, 1 12, 2 12, 1 2 12
    (semilattices: no zero)

    Complete set present:
    0: _
    1: 1, _ 1
    2: 12, _ 12, 1 12, 2 12,_ 1 12, _ 2 12, 1 2 12, _ 1 2 12
    (semilattices: no identity)

    Complete set absent:
    0: .
    1: . , _
    2: . , _, 1, 2, _ 1, _ 2, 1 2, _ 1 2
    (semilattices: no zero)

    Empty and complete sets both present:
    0: _
    1: _ 1
    2: _ 12, _ 1 12, _ 2 12, _ 1 2 12
    (semilattices: neither identity nor zero)

    Empty set present, complete set absent:
    0: (contradiction)
    1: _
    2: _, _ 1, _ 2, _ 1 2

    Empty set absent, complete set present:
    0: (contradiction)
    1: 1
    2: 12, 1 12, 2 12, 1 2 12

    Empty set absent, complete set absent:
    0: .
    1: .
    2: . , 1, 2, 1 2
    (semilattices: neither identity nor zero)

    For n generators, the limiting number of labeled ones is is 2^(2^n/sqrt(n*pi/2)) and that number for unlabeled ones is the labeled-ones number divided by n!

    Subsets of subsets of n entities grows as 2^(2^n)

  8. Top | #68
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    16,221
    Archived
    16,829
    Total Posts
    33,050
    Rep Power
    97
    Semilattice
    Semi-lattice - Encyclopedia of Mathematics

    That's related to:

    Lattice (order)
    Lattice - Encyclopedia of Mathematics

    A lattice is defined on a partially ordered set or poset. Its ordering goes into two operations:
    • Join - maximum - supremum - least upper bound
    • Meet - minimum - infimum - greatest lower bound

    A semilattice has only one of these operations, and is either an upper one or a lower one depending on which one it has.

    Considering an upper or join semilattice for definiteness, if it has a unique minimum element, then that element is the identity, and the semilattice is bounded. But a finite one has a unique maximum element, and that element is its zero.


    Examples:

    Nonnegative integers, rational numbers, real numbers between 0 and 1, other sets of numbers
    • Join: maximum
    • Meet: minimum
    • Top: the overall maximum if it exists
    • Bottom: the overall minimum if it exists

    Positive integers
    • Join: least common multiple
    • Meet: greatest common divisor
    • Top: (none)
    • Bottom: 1

    Boolean algebra: {false, true}
    • Join: Or
    • Meet: And
    • Top: true
    • Bottom: false

    Subsets of some set:
    • Join: union
    • Meet: intersection
    • Top: that set
    • Bottom: the empty set

    ...

  9. Top | #69
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    16,221
    Archived
    16,829
    Total Posts
    33,050
    Rep Power
    97
    I will return again to the issue of subalgebras and homomorphisms / mappings of algebras onto other algebras.

    The unary-function case is fairly simple.

    Every finite algebra can be divided up into disjoint algebras that contain a limit cycle with optional approach trees that feed into it. An infinite algebra can also contain approach trees that have no limit cycle. An example of this is the integers with function (arg)+1. This produces a single unbranched approach tree that extends over the entire set. With function (arg)+2, one gets two unbranched approach trees: all even numbers and all odd numbers. These examples show that approach trees for infinite sets can have no beginning as well as no end.

    Subalgebras are simple. Limit cycles with optionally parts of the approach trees such that if a tree member is in it, all downstream tree members are also in it.

    Homomorphisms are interesting. One can map a subalgebra onto a single element with the others all remaining separate. Or with all the approach trees' members separate, one can do an alternating homomorphism in the limit cycle. For length 6, there are two nontrivial alternating ones, corresponding to divisors 2 and 3:

    1 2 3 4 5 6 -> 1
    1 3 5 -> 1, 2 4 6 -> 2
    1 4 -> 1, 2 5 -> 2, 3 6 -> 3
    1 -> 1, 2 -> 2, 3 -> 3, 4 -> 4, 5 -> 5, 6 -> 6

  10. Top | #70
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    16,221
    Archived
    16,829
    Total Posts
    33,050
    Rep Power
    97
    Now to binary algebras or groupoids.

    It is easy to show by construction that a groupoid can contain arbitrarily many subgroupoids with arbitrary sizes. However, decomposition into subgroupoids is *not* unique, and a groupoid may contain elements that are outside of some decomposition, though those elements may be inside some other one. Consider

    1 2 3
    2 1 1
    3 1 1

    This groupoid has three subgroupoids: (1), (1, 2) and (1,3). But (2), (3), and (2, 3) are not subgroupoids.

    If a subgroupoid contains an identity, then that identity need not be the identity of the whole groupoid, if it has one at all. Likewise for zeros and ideals, and likewise for left and right ones.

    But if a groupoid has an identity and a subgroupoid has that element in it, then that element is also an identity for the subgroupoid. Likewise for zeros and ideals, for left and right.

    Turning to homomorphisms, it's hard to make general statements. But if the groupoid has an ideal J, one can construct the homomorphism f(J) = some new element j and f(G - J element) = itself. Then j becomes a zero for the result groupoid.

    -

    An interesting question is how many groupoids are there without subgroupoids or else without nontrivial homomorphisms onto other groupoids. Nontrivial meaning something other than the two trivial ones: f(G element) = same element with the same operation, and f(G) = one element for all as the order-1 groupoid.

    For subgroupoids, order-2 groupoids have order 1, and every idempotent element (x*x = x) has its own subgroupoid: {x}. Out of the 16 total groupoids, only 4 have no subgroupoids, groupoids like
    2 2
    1 1

    For homomorphisms, order-2 groupoids may have a homomorphism that reverses the two elements. This is an automorphism, an isomorphism of an algebra onto itself, and in turn, and an isomorphism is a homomorphism where the result algebra has the same size as the source algebra -- every source element goes onto a distinct result element.

    Of the order-2 groupoids, 12 do not have this homomorphism, the only possible nontrivial one. One of those with it is the above one,
    2 2
    1 1

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •