OKlibrary  0.2.1.6
BasicNotions.mac
Go to the documentation of this file.
```00001 /* Oliver Kullmann, 10.7.2008 (Swansea) */
00002 /* Copyright 2008, 2009 Oliver Kullmann
00003 This file is part of the OKlibrary. OKlibrary is free software; you can redistribute
00004 it and/or modify it under the terms of the GNU General Public License as published by
00005 the Free Software Foundation and included in this library; either version 3 of the
00006 License, or any later version. */
00007
00022 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/Lists.mac")\$
00023
00024
00025 /* *****************
00026    * Basic notions *
00027    *****************
00028 */
00029
00030 /*
00031  A "left-action" of a set A on a set X is a map *: A x X -> X,
00032  and a "right-action" accordingly is a map *: X x A -> X.
00033  Left-actions are the default ("act"), and right-actions
00034  are abbreviated by "ract".
00035
00036  An action on a groupoid preserves the operation, i.e., all maps X -> X
00037  (for given a in A) are homomorphisms.
00038 */
00039
00040 /* Checking whether compo is a binary left-external law of composition on
00041    sets A, X: */
00042 ecompo_p(compo,A,X) := block(
00043  [e : errcatch(
00044    subsetp(map(lambda([P],apply(compo,P)),cartesian_product(A,X)),X))],
00045  not emptyp(e) and e[1])\$
00046 /* Checking whether compo is a binary right-external law of composition on
00047    sets X, A: */
00048 recompo_p(compo,X,A) := block(
00049  [e : errcatch(
00050    subsetp(map(lambda([P],apply(compo,P)),cartesian_product(X,A)),X))],
00051  not emptyp(e) and e[1])\$
00052
00053 /* Checking whether act is an action of set A on set X resp. (unital)
00054    groupoid V:
00055 */
00056 act_set_p(act_,A,X) := setp(A) and setp(X) and ecompo_p(act_,A,X)\$
00057 ract_set_p(act_,X,A) := setp(A) and setp(X) and recompo_p(act_,X,A)\$
00058
00059 act_grd_p(act_,A,V) := act_set_p(act_,A,V[1]) and
00060 block([counterexample : false],
00061  for a in A unless counterexample do
00062   for x in V[1] unless counterexample do
00063    for y in V[1] unless counterexample do
00064      if act_(a,V[2](x,y)) # V[2](act_(a,x),act_(a,y)) then counterexample : true,
00065  return(not counterexample))\$
00066 ract_grd_p(act_,V,A) := ract_set_p(act_,V[1],A) and
00067 block([counterexample : false],
00068  for a in A unless counterexample do
00069   for x in V[1] unless counterexample do
00070    for y in V[1] unless counterexample do
00071      if act_(V[2](x,y),a) # V[2](act_(x,a),act_(y,a)) then counterexample : true,
00072  return(not counterexample))\$
00073
00074 act_ugrd_p(act_,A,V) :=
00075   act_grd_p(act_,A,V) and every_s(lambda([a], is(act_(a,V[3]) = V[3])), A)\$
00076 ract_ugrd_p(act_,V,A) :=
00077   ract_grd_p(act_,V,A) and every_s(lambda([a], is(act_(V[3],a) = V[3])), A)\$
00078
00079
00080 /* ***************
00081    * Conversions *
00082    ***************
00083 */
00084
00085 act2ract(compo) := lambda([x,a],compo(a,x))\$
00086 ract2act(compo) := lambda([a,x],compo(x,a))\$
00087
00088 /* An action as a map into the transformation set,
00089    yielding maps: */
00090 act2mp_trs_mp(compo) := buildq([compo],
00091   lambda([a], buildq([a], lambda([x], compo(a,x)))))\$
00092 ract2mp_trs_mp(compo) := buildq([compo],
00093   lambda([a], buildq([a], lambda([x], compo(x,a)))))\$
00094 /* Yielding set-maps: */
00095 act2mp_trs_sm(compo,X) := buildq([compo,X],
00096   lambda([a], map(lambda([x],[x,compo(a,x)]), X)))\$
00097 ract2mp_trs_sm(compo,X) := buildq([compo,X],
00098   lambda([a], map(lambda([x],[x,compo(x,a)]), X)))\$
00099 /* Now assuming that X = {1, ..., n}, and representing transformations
00100    as lists: */
00101 act2mp_trs_l(compo,n) := buildq([compo,n],
00102   lambda([a], create_list(compo(a,i), i,1,n)))\$
00103 ract2mp_trs_l(compo,n) := buildq([compo,n],
00104   lambda([a], create_list(compo(i,a), i,1,n)))\$
00105
00106
00107 /* ********************
00108    * Basic operations *
00109    ********************
00110 */
00111
00112 orbit_act(act,A,x) := map(lambda([a],act(a,x)), A)\$
00113 orbit_ract(act,x,A) := map(lambda([a],act(x,a)), A)\$
00114
00115 stabiliser_act(act,A,x) := subset(A,lambda([a],is(act(a,x)=x)))\$
00116 stabiliser_ract(act,x,A) := subset(A,lambda([a],is(act(x,a)=x)))\$
00117
00118
```