OKlibrary  0.2.1.6
BasicNotions.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 6.7.2008 (Swansea) */
00002 /* Copyright 2008, 2009, 2012 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/Algebra/Lisp/Groupoids/Associativity.mac")$
00023 oklib_include("OKlib/ComputerAlgebra/Algebra/Lisp/Groupoids/NeutralElements.mac")$
00024 oklib_include("OKlib/ComputerAlgebra/Algebra/Lisp/Groupoids/InvertibleElements.mac")$
00025 oklib_include("OKlib/ComputerAlgebra/Algebra/Lisp/Groupoids/UniquelySolvableElements.mac")$
00026 oklib_include("OKlib/ComputerAlgebra/Algebra/Lisp/Groupoids/Commutativity.mac")$
00027 oklib_include("OKlib/ComputerAlgebra/CombinatorialMatrices/Lisp/Basics.mac")$
00028 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/HashMaps.mac")$
00029 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/SetSystems.mac")$
00030 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/Lists.mac")$
00031 
00032 
00033 /* ***********************
00034    * Fundamental notions *
00035    ***********************
00036 */
00037 
00038 /* ************************************
00039    * Checking the defining properties *
00040    ************************************
00041 */
00042 
00043 /* Checking whether compo is a binary law of composition on set X: */
00044 compo_p(compo,X) := block(
00045  [e : errcatch(
00046    subsetp(map(lambda([P],apply(compo,P)),cartesian_product(X,X)),X))],
00047  not emptyp(e) and e[1])$
00048 
00049 /* Groupoids: */
00050 grd_p(V) := listp(V) and is(length(V)=2) and setp(V[1]) and compo_p(V[2],V[1])$
00051 ugrd_p(V) := listp(V) and is(length(V)=3) and grd_p([V[1],V[2]]) and 
00052   elementp(V[3],V[1]) and neutral_el_grd(V,V[3])$
00053 cgrd_p(V) := grd_p(V) and commutative_bydef_grd(V)$
00054 cugrd_p(V) := ugrd_p(V) and commutative_bydef_grd(V)$
00055 
00056 ogrd_p(V) := listp(V) and is(length(V)=2) and listnorep_p(first(V)) and
00057   grd_p(ogrd2grd(V))$
00058 ougrd_p(V) := listp(V) and is(length(V)=3) and listnorep_p(first(V)) and
00059   not emptyp(first(V)) and is(first(first(V)) = third(V)) and
00060   ugrd_p(ougrd2ugrd(V))$
00061 
00062 /* Semigroups and monoids: */
00063 sgr_p(S) := grd_p(S) and associative_bydef_grd(S)$
00064 csgr_p(S) := sgr_p(S) and commutative_bydef_grd(S)$
00065 mon_p(M) := listp(M) and is(length(M)=3) and sgr_p([M[1],M[2]]) and 
00066   elementp(M[3],M[1]) and neutral_el_grd(M,M[3])$
00067 cmon_p(M) := mon_p(M) and commutative_bydef_grd(M)$
00068 
00069 /* Quasigroups: */
00070 qgrp_p(Q) := grd_p(Q) and uniquelysolvable_bydef_grd(Q)$
00071 /* Remark: qgrp_p(Q) = ls_p(Q). */
00072 /* Commutative quasigroups: */
00073 cqgrp_p(Q) := qgrp_p(Q) and commutative_bydef_grd(Q)$
00074 /* Unital quasigroups (also known as "loops"): */
00075 uqgrp_p(L) := ugrd_p(L) and uniquelysolvable_bydef_grd(ugrd2grd(L))$
00076 /* Commutative unital quasigroups: */
00077 cuqgrp_p(L) := uqgrp_p(L) and commutative_bydef_grd(ugrd2grd(L))$
00078 
00079 oqgrp_p(Q) := listp(Q) and is(length(Q)=2) and listnorep_p(first(Q)) and
00080   qgrp_p(ogrd2grd(Q))$
00081 ouqgrp_p(L) := listp(L) and is(length(L)=3) and listnorep_p(first(L)) and
00082   not emptyp(first(L)) and is(first(first(L)) = third(L)) and
00083   uqgrp_p(ougrd2ugrd(L))$
00084 
00085 /* Groups: */
00086 grp_p(G) := qgrp_p(G) and associative_bydef_grd(G) and not emptyp(G[1])$
00087 cgrp_p(G) := grp_p(G) and commutative_bydef_grd(G)$
00088 ugrp_p(G) := uqgrp_p(G) and associative_bydef_grd(G)$
00089 cugrp_p(G) := ugrp_p(G) and commutative_bydef_grd(G)$
00090 ugrpi_p(G) := ugrp_p(rest(G,-1)) and inversion_ugrd(G,G[4])$
00091 cugrpi_p(G) := ugrpi_p(G) and commutative_bydef_grd(G)$
00092 
00093 ogrp_p(G) := listp(G) and is(length(G)=2) and listnorep_p(first(G)) and
00094   grp_p(ogrd2grd(G))$
00095 ougrp_p(G) := listp(G) and is(length(G)=3) and listnorep_p(first(G)) and
00096   not emptyp(first(G)) and is(first(first(G)) = third(G)) and
00097   ugrp_p(ougrd2ugrd(G))$
00098 ougrpi_p(G) := listp(G) and is(length(G)=4) and listnorep_p(first(G)) and
00099   not emptyp(first(G)) and is(first(first(G)) = third(G)) and
00100   ugrpi_p(ougrpi2ugrpi(G))$
00101 
00102 
00103 /* *********************
00104    * Checking equality *
00105    *********************
00106 */
00107 
00108 grd_equalp(V1,V2) := scom_equalp(V1,V2)$
00109 ugrd_equalp(V1,V2) := grd_equalp(rest(V1,-1),rest(V2,-1)) and is(V1[3]=V2[3])$
00110 
00111 
00112 /* *************
00113    * Downcasts *
00114    *************
00115 */
00116 
00117 ugrd2grd(V) := rest(V,-1)$
00118 
00119 ogrd2grd(V) := [setify(first(V)), second(V)]$
00120 ougrd2ugrd(V) := [setify(first(V)), second(V), third(V)]$
00121 
00122 ugrpi2ugrp(G) := rest(G,-1)$
00123 ugrpi2grp(G) := rest(G,-2)$
00124 ugrp2grp(G) := rest(G,-1)$
00125 
00126 ougrp2ugrp(G) := [setify(first(G)), second(G), third(G)]$
00127 ougrpi2ugrpi(G) := [setify(first(G)), second(G), third(G), fourth(G)]$
00128 
00129 
00130 /* **************
00131    * Promotions *
00132    **************
00133 */
00134 
00135 /* grp2ugrp(G), grp2ugrpi(G), ugrp2ugrpi(G) : 
00136    here we have the typical three possibilities ... 
00137 */
00138 
00139 grd2ogrd(V) := [listify(first(V)), second(V)]$
00140 ugrd2ougrd(V) := [cons(third(V), listify(disjoin(third(V),first(V)))),
00141  second(V), third(V)]$
00142 
00143 ugrp2ougrp(G) := ugrd2ougrd(G)$
00144 ugrpi2ougrpi(G) := [cons(third(G), listify(disjoin(third(G),first(G)))),
00145  second(G), third(G), fourth(G)]$
00146 
00147 
00148 /* ***************
00149    * Conversions *
00150    ***************
00151 */
00152 
00153 /* Between combinatorial square matrices and groupoids: */
00154 scom2grd(M) := M$
00155 grd2scom(V) := V$
00156 
00157 /* Transforming a Maxima matrix into a groupoid. */
00158 /* Prerequisite: all values of M must be indices. */
00159 m2grd(M) := scom2grd(m2scom(M))$
00160 /* Transforming a groupoid into a Maxima matrix.
00161    Note that this keeps the values of the composition intact and
00162    does not rename them.
00163 */
00164 grd2m(V) := scom2m(grd2scom(V))$
00165 
00166 /* Standardising a groupoid: */
00167 grd2stdgrd(V) := block([L : listify(V[1]), S, a, compo : V[2], h],
00168   S : setn(length(L)),
00169   a : l2array(L),
00170   h : osm2hm(map("[", L, create_list(i,i,1,length(L)))), 
00171   ev(buildq([L,S,a,compo,h], [S, lambda([x,y], ev_hm(h,compo(a[x],a[y])))])))$
00172 /* We have for W := grd2stdgrd(V) :
00173  - W[1] = {1, ..., length(V[1])}
00174  - W is isomorphic to V via i -> V[1][i].
00175 */
00176 
00177 /* Now transforming a groupoid into a Maxima matrix with corresponding 
00178    renaming of the values:
00179 */
00180 grd2m_std(V) := grd2m(grd2stdgrd(V))$
00181 /* Note that m2grd(grd2m_std(V)) is isomorphic to V. */
00182 
00183 
00184 /* ******************
00185    * Basic examples *
00186    ******************
00187 */
00188 
00189 /* A smallest non-associativ groupoid: */
00190 non_assoc_2_grd : m2grd(matrix([2,2],[1,2]))$
00191 
00192