OKlibrary  0.2.1.6
Homomorphisms.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 9.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/HashMaps.mac")$
00023 
00024 /* ***********************
00025    * Fundamental notions *
00026    ***********************
00027 */
00028 
00029 /* Test whether f is a groupoid homomorphism with domain V, where
00030    the target-composition is compo. */
00031 /* Prerequisite: For all x, y in V it is compo(f(x),f(y)) defined.
00032 */
00033 homomorphism_bydef_grd(f,V,compo) := block([counterexample : false],
00034  for x in V[1] unless counterexample do
00035   for y in V[1] unless counterexample do
00036     if f(V[2](x,y)) # compo(f(x),f(y)) then counterexample : true,
00037  return(not counterexample))$
00038 homomorphism_bydef2_grd(f,V1,V2) := homomorphism_bydef_grd(f,V1,V2[2])$
00039 /* Testing whether we have a unital groupoid homomorphism. */
00040 /* Again compo(f(x),f(y)) must be always defined. */
00041 homomorphism_bydef_ugrd(f,V,compo,e) := is(f(V[3]) = e) and 
00042   homomorphism_bydef_grd(f,V,compo)$
00043 homomorphism_bydef2_ugrd(f,V1,V2) := homomorphism_bydef_ugrd(f,V1,V2[2],V2[3])$
00044 
00045 
00046 /* The canonical congruence relation on a groupoid V given by a
00047    homomorphism f: */
00048 induced_congruence_grd(V,f) := buildq([f], lambda([x,y], is(f(x) = f(y))))$
00049 
00050 
00051 /* ***********************
00052    * Isomorphism testing *
00053    ***********************
00054 */
00055 
00056 /* Testing whether two groupoids are isomorphic by running through all
00057    bijections:
00058 */
00059 is_isomorphic_bydef_grd(V1,V2) := if length(V1[1]) # length(V2[1]) then false
00060  else block(
00061  [L1 : listify(V1[1]), L2 : listify(V2[1]), found : false],
00062   for p in permutations(L2) unless found do
00063     found : homomorphism_bydef_grd(lambda_hm(osm2hm(map("[", L1,p))),V1,V2[2]),
00064   return(found))$
00065 
00066 /* Given a groupoid V and an injective map f, transport the structure V
00067    via f (obtaining a groupoid V' such that f is an isomorphism from
00068    V to V'):
00069 */
00070 transport_grd(V,f) := block(
00071  [h : osm2hm(map(lambda([P], [map(f,P), f(apply(V[2],P))]), 
00072         cartesian_product(V[1],V[1])))],
00073   [map(f,V[1]), buildq([h], lambda([x,y], ev_hm(h,[x,y])))])$
00074 /* Now transporting via an "isotopy"; the three maps f,g,h must all be
00075    bijections from V to the same set.
00076 */
00077 transport3_grd(V,f,g,h) := block(
00078  [h : osm2hm(map(lambda([P], [[f(P[1]),g(P[2])], h(apply(V[2],P))]), 
00079         cartesian_product(V[1],V[1])))],
00080   [map(f,V[1]), buildq([h], lambda([x,y], ev_hm(h,[x,y])))])$
00081 
00082