Goto Chapter: Top 1 2 3 Ind
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 

1 The category of finite sets
 1.1 GAP Categories
 1.2 Attributes
 1.3 Constructors
 1.4 Tools
 1.5 Examples

1 The category of finite sets

1.1 GAP Categories

1.1-1 IsCategoryOfFiniteSets
‣ IsCategoryOfFiniteSets( object )( filter )

Returns: true or false

The GAP category of categories of finite sets.

1.1-2 IsObjectInCategoryOfFiniteSets
‣ IsObjectInCategoryOfFiniteSets( object )( filter )

Returns: true or false

The GAP category of objects in the category of finite sets.

1.1-3 IsMorphismInCategoryOfFiniteSets
‣ IsMorphismInCategoryOfFiniteSets( object )( filter )

Returns: true or false

The GAP category of morphisms in the category of finite sets.

1.2 Attributes

1.2-1 AsList
‣ AsList( M )( attribute )

Returns: a GAP set

The GAP set of the list used to construct a finite set S, i.e., AsList( FinSet( L ) ) = Set( L ).

1.2-2 Length
‣ Length( M )( attribute )

Returns: an integer

The length of the GAP set of the list used to construct a finite set S, i.e., Length( FinSet( L ) ) = Length( Set( L ) ).

1.2-3 AsList
‣ AsList( f )( attribute )

Returns: a list

The relation underlying a map between finite sets, i.e., AsList( MapOfFinSets( S, G, T ) ) = G.

1.3 Constructors

1.3-1 CategoryOfFiniteSets
‣ CategoryOfFiniteSets( )( operation )

Returns: a CAP category

Construct a category of finite sets.

1.3-2 FinSets
‣ FinSets( global variable )

The default instance of the category of finite sets. It is automatically created while loading this package.

1.3-3 FinSet
‣ FinSet( cat_of_fin_sets, L )( operation )

Returns: a CAP object

Construct a finite set out of the dense list L, i.e., an object in the CAP category cat_of_fin_sets. The GAP operation Set must be applicable to L without throwing an error. Equality is determined as follows: FinSet( L1 ) = FinSet( L2 ) iff IsEqualForElementsOfFinSets( Immutable( Set( L1 ) ), Immutable( Set( L2 ) ) ). Warning: all internal operations use FinSetNC (see below) instead of FinSet. Thus, this notion of equality is only valid for objects created by calling FinSet explicitly. Internally, FinSet( cat_of_fin_sets, L ) is an alias for FinSetNC( cat_of_fin_sets, Set( L ) ) and equality is determined as for FinSetNC. Thus, FinSet( cat_of_fin_sets, L1 ) = FinSetNC( cat_of_fin_sets, L2 ) iff IsEqualForElementsOfFinSets( Immutable( Set( L1 ) ), Immutable( L2 ) ) and FinSetNC( cat_of_fin_sets, L1 ) = FinSet( cat_of_fin_sets, L2 ) iff IsEqualForElementsOfFinSets( Immutable( L1 ), Immutable( Set( L2 ) ) ).

1.3-4 FinSet
‣ FinSet( L )( operation )

Returns: a CAP object

Return FinSet( FinSets, L ).

gap> LoadPackage( "FinSetsForCAP", false );
true
gap> S := FinSet( [ 1, 3, 2, 2, 1 ] );
<An object in FinSets>
gap> Display( S );
[ 1, 2, 3 ]
gap> L := AsList( S );;
gap> Display( L );
[ 1, 2, 3 ]
gap> Q := FinSet( L );
<An object in FinSets>
gap> S = Q;
true
gap> FinSet( [ 1, 2 ] ) = FinSet( [ 2, 1 ] );
true
gap> M := FinSetNC( [ 1, 2, 3, 3 ] );
<An object in FinSets>
gap> IsWellDefined( M );
false

1.3-5 FinSetNC
‣ FinSetNC( cat_of_fin_sets, L )( operation )

Returns: a CAP object

Construct a finite set out of the duplicate-free (w.r.t. IsEqualForElementsOfFinSets) and dense list L, i.e., an object in the CAP category cat_of_fin_sets,. Equality is determined as follows: FinSetNC( cat_of_fin_sets, L1 ) = FinSetNC( cat_of_fin_sets, L2 ) iff IsEqualForElementsOfFinSets( Immutable( L1 ), Immutable( L2 ) ).

1.3-6 FinSetNC
‣ FinSetNC( L )( operation )

Returns: a CAP object

Return FinSetNC( FinSets, L ).

gap> LoadPackage( "FinSetsForCAP", false );
true
gap> S := FinSetNC( [ 1, 3, 2 ] );
<An object in FinSets>
gap> Display( S );
[ 1, 3, 2 ]
gap> L := AsList( S );;
gap> Display( L );
[ 1, 3, 2 ]
gap> Q := FinSetNC( L );
<An object in FinSets>
gap> S = Q;
true
gap> S := ObjectConstructor( FinSets, [ 1, 3, 2 ] );
<An object in FinSets>
gap> Display( S );
[ 1, 3, 2 ]
gap> L := ObjectDatum( S );;
gap> Display( L );
[ 1, 3, 2 ]
gap> Q := ObjectConstructor( FinSets, L );
<An object in FinSets>
gap> S = Q;
true
gap> FinSetNC( [ 1, 2 ] ) = FinSetNC( [ 2, 1 ] );
false

1.3-7 MapOfFinSets
‣ MapOfFinSets( S, G, T )( operation )

Returns: a CAP morphism

Construct a map \phi:S\toT of the finite sets S and T, i.e., a morphism in the CAP category FinSets, where G is a dense list of pairs in S\timesT describing the graph of \phi.

gap> LoadPackage( "FinSetsForCAP", false );
true
gap> S := FinSet( [ 1, 3, 2, 2, 1 ] );
<An object in FinSets>
gap> T := FinSet( [ "a", "b", "c" ] );
<An object in FinSets>
gap> G := [ [ 1, "b" ], [ 3, "b" ], [ 2, "a" ] ];;
gap> phi := MapOfFinSets( S, G, T );
<A morphism in FinSets>
gap> IsWellDefined( phi );
true
gap> Display( AsList( phi ) );
[ [ 1, "b" ], [ 2, "a" ], [ 3, "b" ] ]
gap> phi2 := MorphismConstructor( S, G, T );
<A morphism in FinSets>
gap> Display( MorphismDatum( phi2 ) );
[ [ 1, "b" ], [ 2, "a" ], [ 3, "b" ] ]
gap> phi = phi2;
true
gap> phi( 1 );
"b"
gap> phi( 2 );
"a"
gap> phi( 3 );
"b"
gap> Display( List( S, phi ) );
[ "b", "a", "b" ]
gap> psi := [ [ 1, "b" ], [ 2, "a" ], [ 3, "b" ] ];;
gap> psi := MapOfFinSets( S, psi, T );
<A morphism in FinSets>
gap> IsWellDefined( psi );
true
gap> phi = psi;
true
gap> psi := MapOfFinSets( S, [ [ 1, "d" ], [ 3, "b" ] ], T );
<A morphism in FinSets>
gap> IsWellDefined( psi );
false
gap> psi := MapOfFinSets( S, [ 1, 2, 3 ], T );
<A morphism in FinSets>
gap> IsWellDefined( psi );
false
gap> psi := MapOfFinSets( S, [ [ 1, "b" ], [ 3, "b" ], [ 2, "a", "b" ] ], T );
<A morphism in FinSets>
gap> IsWellDefined( psi );
false
gap> psi := MapOfFinSets( S, [ [ 5, "b" ], [ 3, "b" ], [ 2, "a" ] ], T );
<A morphism in FinSets>
gap> IsWellDefined( psi );
false
gap> psi := MapOfFinSets( S, [ [ 1, "d" ], [ 3, "b" ], [ 2, "a" ] ], T );
<A morphism in FinSets>
gap> IsWellDefined( psi );
false
gap> psi := MapOfFinSets( S, [ [ 1, "b" ], [ 2, "b" ], [ 2, "a" ] ], T );
<A morphism in FinSets>
gap> IsWellDefined( psi );
false

1.3-8 MapOfFinSetsNC
‣ MapOfFinSetsNC( S, G, T )( operation )

Returns: a CAP morphism

Construct a map \phi:S\toT of the finite sets S and T, i.e., a morphism in the CAP category FinSets, where G is a duplicate-free and dense list of pairs in S\timesT describing the graph of \phi.

gap> LoadPackage( "FinSetsForCAP", false );
true
gap> S := FinSetNC( [ 1, 3, 2 ] );
<An object in FinSets>
gap> T := FinSetNC( [ "a", "b", "c" ] );
<An object in FinSets>
gap> G := [ [ 1, "b" ], [ 3, "b" ], [ 2, "a" ] ];;
gap> phi := MapOfFinSetsNC( S, G, T );
<A morphism in FinSets>
gap> IsWellDefined( phi );
true
gap> phi( 1 );
"b"
gap> phi( 2 );
"a"
gap> phi( 3 );
"b"
gap> Display( List( S, phi ) );
[ "b", "b", "a" ]
gap> psi := [ [ 1, "b" ], [ 2, "a" ], [ 3, "b" ] ];;
gap> psi := MapOfFinSetsNC( S, psi, T );
<A morphism in FinSets>
gap> IsWellDefined( psi );
true
gap> phi = psi;
true

1.4 Tools

1.4-1 IsEqualForElementsOfFinSets
‣ IsEqualForElementsOfFinSets( a, b )( operation )

Returns: a boolean

Compares two arbitrary objects using the following rules:

Note: if CAP category objects or CAP category morphisms are compared using IsEqualForObjects or IsEqualForMorphismsOnMor, respectively, the result must not be fail.

gap> LoadPackage( "FinSetsForCAP", false );
true
gap> IsEqualForElementsOfFinSets( 2, 2 );
true
gap> IsEqualForElementsOfFinSets( 2, "2" );
false
gap> IsEqualForElementsOfFinSets( 'a', 'a' );
true
gap> IsEqualForElementsOfFinSets( 'a', 'b' );
false
gap> IsEqualForElementsOfFinSets( [ 2 ], [ 2 ] );
true
gap> IsEqualForElementsOfFinSets( [ 2 ], [ 2, 3 ] );
false
gap> IsEqualForElementsOfFinSets( rec( a := "a", b := "b" ),
>                              rec( b := "b", a := "a" )
>                            );
true
gap> IsEqualForElementsOfFinSets( rec( a := "a", b := "b" ),
>                              rec( a := "a" )
>                            );
false
gap> IsEqualForElementsOfFinSets( rec( a := "a", b := "b" ),
>                              rec( a := "a", b := "notb" )
>                            );
false
gap> M := FinSet( [ ] );;
gap> N := FinSet( [ ] );;
gap> m := FinSet( 0 );;
gap> id_M := IdentityMorphism( M );;
gap> id_N := IdentityMorphism( N );;
gap> id_m := IdentityMorphism( m );;
gap> IsEqualForElementsOfFinSets( M, N );
true
gap> IsEqualForElementsOfFinSets( M, m );
false
gap> IsEqualForElementsOfFinSets( id_M, id_N );
true
gap> IsEqualForElementsOfFinSets( id_M, id_m );
false
gap> IsEqualForElementsOfFinSets( FinSets, SkeletalFinSets );
false

1.4-2 \in
‣ \in( obj, M )( operation )

Returns: a boolean

Returns true if there exists an element in AsList( M ) which is equal to obj w.r.t. IsEqualForElementsOfFinSets and false if not.

1.4-3 []
‣ []( M, i )( operation )

Returns: an object

Returns the i-th entry of the GAP set of the list used to construct a finite set S, i.e., FinSet( L )[ i ] = Set( L )[ i ].

1.4-4 Iterator
‣ Iterator( M )( operation )

Returns: an iterator

An iterator of the GAP set of the list used to construct a finite set S, i.e., Iterator( FinSet( L ) ) = Iterator( Set( L ) ).

1.4-5 UnionOfFinSets
‣ UnionOfFinSets( cat_of_fin_sets, L )( operation )

Returns: a CAP object

Compute the set-theoretic union of the elements of L, where L is a dense list of finite sets in the category cat_of_fin_sets.

1.4-6 ListOp
‣ ListOp( M, f )( operation )

Returns: a list

Returns List( AsList( M ), f ).

1.4-7 FilteredOp
‣ FilteredOp( M, f )( operation )

Returns: a list

Returns FinSetNC( Filtered( AsList( M ), f ) ).

1.4-8 First
‣ First( M, f )( operation )

Returns: a list

Returns First( AsList( M ), f ).

1.4-9 EmbeddingOfFinSets
‣ EmbeddingOfFinSets( S, T )( operation )

Returns: a CAP morphism

Construct the embedding \iota:S\toT of the finite sets S and T, where S must be subset of T.

1.4-10 ProjectionOfFinSets
‣ ProjectionOfFinSets( S, T )( operation )

Returns: a CAP morphism

Construct the projection \pi:S\toT of the finite sets S and T, where T is a partition of S.

1.4-11 Preimage
‣ Preimage( f, T_ )( operation )

Returns: a CAP object

Compute the preimage of T_ under the morphism f.

1.4-12 ImageObject
‣ ImageObject( f, S_ )( operation )

Returns: a CAP object

Compute the image of S_ under the morphism f.

1.4-13 CallFuncList
‣ CallFuncList( phi, L )( operation )

Returns: a list

Returns the image of L[1] under the map phi assuming L[1] is an element of AsList( Source( phi ) ).

1.4-14 ListOp
‣ ListOp( F, phi )( operation )

Returns: a list

Returns List( AsList( F ), phi ).

1.5 Examples

1.5-1 IsHomSetInhabited
gap> LoadPackage( "FinSetsForCAP", false );
true
gap> L := FinSet( [ ] );
<An object in FinSets>
gap> M := FinSet( [ 2 ] );
<An object in FinSets>
gap> N := FinSet( [ 3 ] );
<An object in FinSets>
gap> IsHomSetInhabited( L, L );
true
gap> IsHomSetInhabited( M, L );
false
gap> IsHomSetInhabited( L, M );
true
gap> IsHomSetInhabited( M, N );
true

1.5-2 Morphisms of external Hom
gap> LoadPackage( "FinSetsForCAP", false );
true
gap> L := FinSet( 0 );
|0|
gap> M := FinSet( 2 );
|2|
gap> N := FinSet( 3 );
|3|
gap> Display( MorphismsOfExternalHom( L, L ) );
[ ∅ ⱶ[  ]→ ∅ ]
gap> Display( MorphismsOfExternalHom( M, L ) );
[  ]
gap> Display( MorphismsOfExternalHom( L, M ) );
[ ∅ ⱶ[  ]→ { 0, 1 } ]
gap> Display( MorphismsOfExternalHom( M, N ) );
[ { 0, 1 } ⱶ[ 0, 0 ]→ { 0, 1, 2 }, { 0, 1 } ⱶ[ 1, 0 ]→ { 0, 1, 2 },\
 { 0, 1 } ⱶ[ 2, 0 ]→ { 0, 1, 2 }, { 0, 1 } ⱶ[ 0, 1 ]→ { 0, 1, 2 },\
 { 0, 1 } ⱶ[ 1, 1 ]→ { 0, 1, 2 }, { 0, 1 } ⱶ[ 2, 1 ]→ { 0, 1, 2 },\
 { 0, 1 } ⱶ[ 0, 2 ]→ { 0, 1, 2 }, { 0, 1 } ⱶ[ 1, 2 ]→ { 0, 1, 2 },\
 { 0, 1 } ⱶ[ 2, 2 ]→ { 0, 1, 2 } ]

1.5-3 Exact cover with global elements
gap> LoadPackage( "FinSetsForCAP", false );
true
gap> L := FinSet( 0 );
|0|
gap> M := FinSet( 2 );
|2|
gap> Display( ExactCoverWithGlobalElements( L ) );
[  ]
gap> g := ExactCoverWithGlobalElements( M );;
gap> Display( g );
[ { 0 } ⱶ[ 0 ]→ { 0, 1 }, { 0 } ⱶ[ 1 ]→ { 0, 1 } ]
gap> IsOne( UniversalMorphismFromCoproduct( g ) );
true

1.5-4 PreCompose
gap> LoadPackage( "FinSetsForCAP", false );
true
gap> S := FinSet( [ 1, 2, 3 ] );
<An object in FinSets>
gap> T := FinSet( [ "a", "b" ] );
<An object in FinSets>
gap> phi := [ [ 1, "b" ], [ 2, "a" ], [ 3, "b" ] ];;
gap> phi := MapOfFinSets( S, phi, T );
<A morphism in FinSets>
gap> psi := [ [ "a", 3 ], [ "b", 1 ] ];;
gap> psi := MapOfFinSets( T, psi, S );
<A morphism in FinSets>
gap> alpha := PreCompose( phi, psi );
<A morphism in FinSets>
gap> Display( List( S, alpha ) );
[ 1, 3, 1 ]
gap> IsOne( alpha );
false

1.5-5 IsEpimorphism and IsMonomorhism
gap> LoadPackage( "FinSetsForCAP", false );
true
gap> S := FinSet( [ 1, 2, 3 ] );
<An object in FinSets>
gap> T := S;
<An object in FinSets>
gap> phi := [ [ 1, 2 ], [ 2, 3 ], [ 3, 1 ] ];;
gap> phi := MapOfFinSets( S, phi, T );
<A morphism in FinSets>
gap> I := ImageObject( phi );
<An object in FinSets>
gap> Length( I );
3
gap> IsMonomorphism( phi );
true
gap> IsSplitMonomorphism( phi );
true
gap> IsEpimorphism( phi );
true
gap> IsSplitEpimorphism( phi );
true
gap> iota := ImageEmbedding( phi );
<A monomorphism in FinSets>
gap> pi := CoastrictionToImage( phi );
<An epimorphism in FinSets>
gap> PreCompose( pi, iota ) = phi;
true

1.5-6 Initial and Terminal Objects
gap> LoadPackage( "FinSetsForCAP", false );
true
gap> M := FinSet( [ 1, 2, 3 ] );
<An object in FinSets>
gap> IsInitial( M );
false
gap> IsTerminal( M );
false
gap> I := InitialObject( FinSets );
<An object in FinSets>
gap> IsInitial( I );
true
gap> IsTerminal( I );
false
gap> iota := UniversalMorphismFromInitialObject( M );
<A morphism in FinSets>
gap> Display( I );
[  ]
gap> T := TerminalObject( FinSets );
<An object in FinSets>
gap> Display( T );
[ [  ] ]
gap> IsInitial( T );
false
gap> IsTerminal( T );
true
gap> pi := UniversalMorphismIntoTerminalObject( M );
<A morphism in FinSets>
gap> IsIdenticalObj( Range( pi ), T );
true
gap> t := FinSet( [ "Julia" ] );
<An object in FinSets>
gap> pi_t := UniversalMorphismIntoTerminalObjectWithGivenTerminalObject( M, t );
<A morphism in FinSets>
gap> Display( List( M, pi_t ) );
[ "Julia", "Julia", "Julia" ]

1.5-7 Projective and Injective Objects
gap> LoadPackage( "FinSetsForCAP", false );
true
gap> I := FinSet( [ ] );
<An object in FinSets>
gap> T := FinSet( [ 1 ] );
<An object in FinSets>
gap> M := FinSet( [ 2 ] );
<An object in FinSets>
gap> IsProjective( I );
true
gap> IsProjective( T );
true
gap> IsProjective( M );
true
gap> IsOne( EpimorphismFromSomeProjectiveObject( I ) );
true
gap> IsOne( EpimorphismFromSomeProjectiveObject( M ) );
true
gap> LoadPackage( "FinSetsForCAP", false );
true
gap> I := FinSet( [ ] );
<An object in FinSets>
gap> T := FinSet( [ 1 ] );
<An object in FinSets>
gap> M := FinSet( [ 2 ] );
<An object in FinSets>
gap> IsInjective( I );
false
gap> IsInjective( T );
true
gap> IsInjective( M );
true
gap> IsIsomorphism( MonomorphismIntoSomeInjectiveObject( I ) );
false
gap> IsMonomorphism( MonomorphismIntoSomeInjectiveObject( I ) );
true
gap> IsOne( MonomorphismIntoSomeInjectiveObject( M ) );
true

1.5-8 Product
gap> LoadPackage( "FinSetsForCAP", false );
true
gap> S := FinSet( [ 1, 2, 3 ] );
<An object in FinSets>
gap> Length( S );
3
gap> T := FinSet( [ "a", "b" ] );
<An object in FinSets>
gap> Length( T );
2
gap> P := DirectProduct( S, T );
<An object in FinSets>
gap> Length( P );
6
gap> Display( P );
[ [ 1, "a" ], [ 2, "a" ], [ 3, "a" ], [ 1, "b" ], [ 2, "b" ], [ 3, "b" ] ]

1.5-9 Coproduct
gap> LoadPackage( "FinSetsForCAP", false );
true
gap> S := FinSet( [ 1, 2, 3 ] );
<An object in FinSets>
gap> Length( S );
3
gap> T := FinSet( [ "a", "b" ] );
<An object in FinSets>
gap> Length( T );
2
gap> C := Coproduct( T, S );
<An object in FinSets>
gap> Length( C );
5
gap> Display( C );
[ [ 1, "a" ], [ 1, "b" ], [ 2, 1 ], [ 2, 2 ], [ 2, 3 ] ]
gap> M := FinSet( [ 1, 2, 3, 4, 5, 6, 7 ] );
<An object in FinSets>
gap> N := FinSet( [ 1, 2, 3 ] );
<An object in FinSets>
gap> P := FinSet( [ 1, 2, 3, 4 ] );
<An object in FinSets>
gap> C := Coproduct( M, N, P );
<An object in FinSets>
gap> Display( AsList( C ) );
[ [ 1, 1 ], [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 5 ], [ 1, 6 ],\
 [ 1, 7 ], [ 2, 1 ], [ 2, 2 ], [ 2, 3 ], [ 3, 1 ], [ 3, 2 ],\
 [ 3, 3 ], [ 3, 4 ] ]
gap> iota1 := InjectionOfCofactorOfCoproduct( [ M, N, P ], 1 );
<A morphism in FinSets>
gap> IsWellDefined( iota1 );
true
gap> Display( AsList( iota1 ) );
[ [ 1, [ 1, 1 ] ], [ 2, [ 1, 2 ] ], [ 3, [ 1, 3 ] ], [ 4, [ 1, 4 ] ],\
 [ 5, [ 1, 5 ] ], [ 6, [ 1, 6 ] ], [ 7, [ 1, 7 ] ] ]
gap> iota2 := InjectionOfCofactorOfCoproduct( [ M, N, P ], 2 );
<A morphism in FinSets>
gap> IsWellDefined( iota2 );
true
gap> Display( AsList( iota2 ) );
[ [ 1, [ 2, 1 ] ], [ 2, [ 2, 2 ] ], [ 3, [ 2, 3 ] ] ]
gap> iota3 := InjectionOfCofactorOfCoproduct( [ M, N, P ], 3 );
<A morphism in FinSets>
gap> IsWellDefined( iota3 );
true
gap> Display( AsList( iota3 ) );
[ [ 1, [ 3, 1 ] ], [ 2, [ 3, 2 ] ], [ 3, [ 3, 3 ] ], [ 4, [ 3, 4 ] ] ]
gap> psi := UniversalMorphismFromCoproduct( [ M, N, P ],
>                                        [ iota1, iota2, iota3 ]
>                                      );
<A morphism in FinSets>
gap> psi = IdentityMorphism( Coproduct( [ M, N, P ] ) );
true

1.5-10 Image
gap> LoadPackage( "FinSetsForCAP", false );
true
gap> S := FinSet( [ 1, 2, 3 ] );
<An object in FinSets>
gap> T := FinSet( [ "a", "b", "c" ] );
<An object in FinSets>
gap> phi := [ [ 1, "b" ], [ 2, "a" ], [ 3, "b" ] ];;
gap> phi := MapOfFinSets( S, phi, T );
<A morphism in FinSets>
gap> I := ImageObject( phi );
<An object in FinSets>
gap> Length( I );
2
gap> IsMonomorphism( phi );
false
gap> IsSplitMonomorphism( phi );
false
gap> IsEpimorphism( phi );
false
gap> IsSplitEpimorphism( phi );
false
gap> iota := ImageEmbedding( phi );
<A monomorphism in FinSets>
gap> pi := CoastrictionToImage( phi );
<An epimorphism in FinSets>
gap> PreCompose( pi, iota ) = phi;
true

1.5-11 Coimage
gap> LoadPackage( "FinSetsForCAP", false );
true
gap> S := FinSet( [ 1, 2, 3 ] );
<An object in FinSets>
gap> T := FinSet( [ "a", "b", "c" ] );
<An object in FinSets>
gap> phi := [ [ 1, "b" ], [ 2, "a" ], [ 3, "b" ] ];;
gap> phi := MapOfFinSets( S, phi, T );
<A morphism in FinSets>
gap> I := CoimageObject( phi );
<An object in FinSets>
gap> Length( I );
2
gap> IsMonomorphism( phi );
false
gap> IsSplitMonomorphism( phi );
false
gap> IsEpimorphism( phi );
false
gap> IsSplitEpimorphism( phi );
false
gap> pi := CoimageProjection( phi );
<An epimorphism in FinSets>
gap> iota := AstrictionToCoimage( phi );
<A morphism in FinSets>
gap> PreCompose( pi, iota ) = phi;
true

1.5-12 Equalizer
gap> LoadPackage( "FinSetsForCAP", false );
true
gap> S := FinSet( [ 1 .. 5 ] );
<An object in FinSets>
gap> T := FinSet( [ 1 .. 3 ] );
<An object in FinSets>
gap> f1 := MapOfFinSets( S, [ [1,3],[2,3],[3,1],[4,2],[5,2] ], T );
<A morphism in FinSets>
gap> f2 := MapOfFinSets( S, [ [1,3],[2,2],[3,3],[4,1],[5,2] ], T );
<A morphism in FinSets>
gap> f3 := MapOfFinSets( S, [ [1,3],[2,1],[3,2],[4,1],[5,2] ], T );
<A morphism in FinSets>
gap> D := [ f1, f2, f3 ];;
gap> Eq := Equalizer( D );
<An object in FinSets>
gap> Display( Eq );
[ 1, 5 ]
gap> iota := EmbeddingOfEqualizer( D );;
gap> IsWellDefined( iota );
true
gap> Im := ImageObject( iota );
<An object in FinSets>
gap> Display( Im );
[ 1, 5 ]
gap> mu := MorphismFromEqualizerToSink( D );;
gap> PreCompose( iota, f1 ) = mu;
true
gap> M := FinSet( [ "a" ] );;
gap> phi := MapOfFinSets( M, [ [ "a", 5 ] ], S );;
gap> IsWellDefined( phi );
true
gap> psi := UniversalMorphismIntoEqualizer( D, phi );
<A morphism in FinSets>
gap> IsWellDefined( psi );
true
gap> Display( psi );
[ [ "a" ], [ [ "a", 5 ] ], [ 1, 5 ] ]
gap> PreCompose( psi, iota ) = phi;
true

1.5-13 Pullback
gap> LoadPackage( "FinSetsForCAP", false );
true
gap> M := FinSet( [ 1 .. 5 ] );
<An object in FinSets>
gap> N1 := FinSet( [ 1 .. 3 ] );
<An object in FinSets>
gap> iota1 := EmbeddingOfFinSets( N1, M );
<A monomorphism in FinSets>
gap> N2 := FinSet( [ 2 .. 5 ] );
<An object in FinSets>
gap> iota2 := EmbeddingOfFinSets( N2, M );
<A monomorphism in FinSets>
gap> D := [ iota1, iota2 ];;
gap> int := FiberProduct( D );
<An object in FinSets>
gap> Display( int );
[ [ 2, 2 ], [ 3, 3 ] ]
gap> pi1 := ProjectionInFactorOfFiberProduct( D, 1 );
<A monomorphism in FinSets>
gap> int1 := ImageObject( pi1 );
<An object in FinSets>
gap> Display( int1 );
[ 2, 3 ]
gap> pi2 := ProjectionInFactorOfFiberProduct( D, 2 );
<A monomorphism in FinSets>
gap> int2 := ImageObject( pi2 );
<An object in FinSets>
gap> Display( int2 );
[ 2, 3 ]

1.5-14 Coequalizer
gap> LoadPackage( "FinSetsForCAP", false );
true
gap> N := FinSet( [1,3] );
<An object in FinSets>
gap> M := FinSet( [1,2,4] );
<An object in FinSets>
gap> f := MapOfFinSets( N, [ [1,1], [3,2] ], M );
<A morphism in FinSets>
gap> g := MapOfFinSets( N, [ [1,2], [3,4] ], M );
<A morphism in FinSets>
gap> C := Coequalizer( f, g );
<An object in FinSets>
gap> Display( AsList( C ) );
[ [ 1, 2, 4 ] ]
gap> A := FinSet( [ 1, 2, 3, 4 ] );
<An object in FinSets>
gap> B := FinSet( [ 1, 2, 3, 4, 5, 6, 7, 8 ] );
<An object in FinSets>
gap> f1 := MapOfFinSets( A, [ [ 1, 1 ], [ 2, 2 ], [ 3, 3 ], [ 4, 8 ] ], B );
<A morphism in FinSets>
gap> f2 := MapOfFinSets( A, [ [ 1, 2 ], [ 2, 3 ], [ 3, 8 ], [ 4, 5 ] ], B );
<A morphism in FinSets>
gap> f3 := MapOfFinSets( A, [ [ 1, 4 ], [ 2, 2 ], [ 3, 3 ], [ 4, 8 ] ], B );
<A morphism in FinSets>
gap> C1 := Coequalizer( [ f1, f3 ] );
<An object in FinSets>
gap> Display( AsList( C1 ) );
[ [ 1, 4 ], [ 2 ], [ 3 ], [ 5 ], [ 6 ], [ 7 ], [ 8 ] ]
gap> C2 := Coequalizer( [ f1, f2, f3 ] );
<An object in FinSets>
gap> Display( AsList( C2 ) );
[ [ 1, 2, 3, 8, 5, 4 ], [ 6 ], [ 7 ] ]
gap> S := FinSet( [ 1 .. 5 ] );
<An object in FinSets>
gap> T := FinSet( [ 1 .. 4 ] );
<An object in FinSets>
gap> f := MapOfFinSets( S, [ [1,2], [2,4], [3,4], [4,3], [5,4] ], T );
<A morphism in FinSets>
gap> g := MapOfFinSets( S, [ [1,2], [2,3], [3,4], [4,3], [5,4] ], T );
<A morphism in FinSets>
gap> C := Coequalizer( f, g );
<An object in FinSets>
gap> Display( C );
[ [ 1 ], [ 2 ], [ 4, 3 ] ]
gap> S := FinSet( [ 1, 2, 3, 4, 5 ] );
<An object in FinSets>
gap> T := FinSet( [ 1, 2, 3, 4 ] );
<An object in FinSets>
gap> G_f := [ [ 1, 3 ], [ 2, 4 ], [ 3, 4 ], [ 4, 2 ], [ 5, 4 ] ];;
gap> f := MapOfFinSets( S, G_f, T );
<A morphism in FinSets>
gap> G_g := [ [ 1, 3 ], [ 2, 3 ], [ 3, 4 ], [ 4, 2 ], [ 5, 4 ] ];;
gap> g := MapOfFinSets( S, G_g, T );
<A morphism in FinSets>
gap> D := [ f, g ];;
gap> C := Coequalizer( D );
<An object in FinSets>
gap> Display( AsList( C ) );
[ [ 1 ], [ 2 ], [ 3, 4 ] ]
gap> pi := ProjectionOntoCoequalizer( D );
<An epimorphism in FinSets>
gap> Display( AsList( pi ) );
[ [ 1, [ 1 ] ], [ 2, [ 2 ] ], [ 3, [ 3, 4 ] ], [ 4, [ 3, 4 ] ] ]
gap> mu := MorphismFromSourceToCoequalizer( D );;
gap> PreCompose( f, pi ) = mu;
true
gap> G_tau := [ [ 1, 2 ], [ 2, 1 ], [ 3, 2 ], [ 4, 2 ] ];;
gap> tau := MapOfFinSets( T, G_tau, FinSet( [ 1, 2 ] ) );
<A morphism in FinSets>
gap> phi := UniversalMorphismFromCoequalizer( D, tau );
<A morphism in FinSets>
gap> Display( AsList( phi ) );
[ [ [ 1 ], 2 ], [ [ 2 ], 1 ], [ [ 3, 4 ], 2 ] ]
gap> PreCompose( pi, phi ) = tau;
true
gap> S := FinSet( [ 1, 2, 3, 4, 5 ] );
<An object in FinSets>
gap> T := FinSet( [ 1, 2, 3, 4 ] );
<An object in FinSets>
gap> G_f := [ [ 1, 2 ], [ 2, 3 ], [ 3, 3 ], [ 4, 2 ], [ 5, 4 ] ];;
gap> f := MapOfFinSets( S, G_f, T );
<A morphism in FinSets>
gap> G_g := [ [ 1, 2 ], [ 2, 3 ], [ 3, 2 ], [ 4, 2 ], [ 5, 4 ] ];;
gap> g := MapOfFinSets( S, G_g, T );
<A morphism in FinSets>
gap> D := [ f, g ];;
gap> C := Coequalizer( D );
<An object in FinSets>
gap> Display( AsList( C ) );
[ [ 1 ], [ 2, 3 ], [ 4 ] ]
gap> pi := ProjectionOntoCoequalizer( D );
<An epimorphism in FinSets>
gap> Display( AsList( pi ) );
[ [ 1, [ 1 ] ], [ 2, [ 2, 3 ] ], [ 3, [ 2, 3 ] ], [ 4, [ 4 ] ] ]
gap> PreCompose( f, pi ) = PreCompose( g, pi );
true
gap> mu := MorphismFromSourceToCoequalizer( D );;
gap> PreCompose( f, pi ) = mu;
true
gap> G_tau := [ [ 1, 1 ], [ 2, 2 ], [ 3, 2 ], [ 4, 1 ] ];;
gap> tau := MapOfFinSets( T, G_tau, FinSet( [ 1, 2 ] ) );
<A morphism in FinSets>
gap> phi := UniversalMorphismFromCoequalizer( D, tau );
<A morphism in FinSets>
gap> Display( AsList( phi ) );
[ [ [ 1 ], 1 ], [ [ 2, 3 ], 2 ], [ [ 4 ], 1 ] ]
gap> PreCompose( pi, phi ) = tau;
true
gap> A := FinSet( [ "A" ] );
<An object in FinSets>
gap> B := FinSet( [ "B" ] );
<An object in FinSets>
gap> M := FinSetNC( [ A, B ] );
<An object in FinSets>
gap> f := MapOfFinSetsNC( M, [ [ A, A ], [ B, A ] ], M );
<A morphism in FinSets>
gap> g := IdentityMorphism( M );
<An identity morphism in FinSets>
gap> C := Coequalizer( [ f, g ] );
<An object in FinSets>
gap> Length( C );
1
gap> Length( AsList( C )[ 1 ] );
2
gap> Display( AsList( C )[ 1 ][ 1 ] );
[ "A" ]
gap> Display( AsList( C )[ 1 ][ 2 ] );
[ "B" ]

1.5-15 Pushout
gap> LoadPackage( "FinSetsForCAP", false );
true
gap> M := FinSet( [ 1 .. 5 ] );
<An object in FinSets>
gap> N1 := FinSet( [ 1, 2, 4 ] );
<An object in FinSets>
gap> iota1 := EmbeddingOfFinSets( N1, M );
<A monomorphism in FinSets>
gap> N2 := FinSet( [ 2, 3 ] );
<An object in FinSets>
gap> iota2 := EmbeddingOfFinSets( N2, M );
<A monomorphism in FinSets>
gap> D := [ iota1, iota2 ];;
gap> int := FiberProduct( D );
<An object in FinSets>
gap> Display( int );
[ [ 2, 2 ] ]
gap> pi1 := ProjectionInFactorOfFiberProduct( D, 1 );
<A monomorphism in FinSets>
gap> pi2 := ProjectionInFactorOfFiberProduct( D, 2 );
<A monomorphism in FinSets>
gap> UU := Pushout( pi1, pi2 );
<An object in FinSets>
gap> Display( UU );
[ [ [ 1, 1 ] ], [ [ 1, 2 ], [ 2, 2 ] ], [ [ 1, 4 ] ], [ [ 2, 3 ] ] ]
gap> iota := UniversalMorphismFromPushout( [ pi1, pi2 ], [ iota1, iota2 ] );
<A morphism in FinSets>
gap> U := ImageObject( iota );
<An object in FinSets>
gap> Display( U );
[ 1, 2, 4, 3 ]
gap> UnionOfFinSets( FinSets, [ N1, N2 ] ) = U;
true

1.5-16 Cartesian Lambda Introduction
gap> LoadPackage( "FinSetsForCAP", false );
true
gap> S := FinSet( [ 1 .. 3 ] );
<An object in FinSets>
gap> R := FinSet( [ 1 .. 2 ] );
<An object in FinSets>
gap> f := MapOfFinSets( S, [ [1,2],[2,2],[3,1] ], R );
<A morphism in FinSets>
gap> IsWellDefined( f );
true
gap> T := TerminalObject( FinSets );
<An object in FinSets>
gap> IsTerminal( T );
true
gap> lf := CartesianLambdaIntroduction( f );
<A split monomorphism in FinSets>
gap> Source( lf ) = T;
true
gap> Length( Range( lf ) );
8
gap> lf( T[1] ) = f;
true
gap> elf := CartesianLambdaElimination( S, R, lf );
<A morphism in FinSets>
gap> elf = f;
true

1.5-17 Lift
gap> LoadPackage( "FinSetsForCAP", false );
true
gap> m := FinSet( [ 1 .. 3 ] );
<An object in FinSets>
gap> n := FinSet( [ 1 .. 4 ] );
<An object in FinSets>
gap> f := MapOfFinSets( m, [ [ 1, 2 ], [ 2, 2 ], [ 3, 1 ] ], m );
<A morphism in FinSets>
gap> g := MapOfFinSets( n, [ [ 1, 3 ], [ 2, 2 ], [ 3, 1 ], [ 4, 2 ] ], m );
<A morphism in FinSets>
gap> IsLiftable( f, g );
true
gap> chi := Lift( f, g );
<A morphism in FinSets>
gap> Display( chi );
[ [ 1 .. 3 ], [ [ 1, 2 ], [ 2, 2 ], [ 3, 3 ] ], [ 1 .. 4 ] ]
gap> PreCompose( Lift( f, g ), g ) = f;
true
gap> IsLiftable( g, f );
false
gap> k := FinSet( [ 1 .. 100 ] );
<An object in FinSets>
gap> h := ListWithIdenticalEntries( Length( k ) - 3, 3 );;
gap> h := Concatenation( h, [ 2, 1, 2 ] );;
gap> h := MapOfFinSets( k, List( k, i -> [ i, h[i] ] ), m );
<A morphism in FinSets>
gap> IsLiftable( f, h );
true
gap> IsLiftable( h, f );
false

1.5-18 Singleton morphism
gap> LoadPackage( "FinSetsForCAP" );
true
gap> a := FinSet( [ 1, 2, 3 ] );
<An object in FinSets>
gap> sa := SingletonMorphism( a );
<A monomorphism in FinSets>
gap> sa = LowerSegmentOfRelation( a, a, CartesianDiagonal( a, 2 ) );
true
gap> sa = UpperSegmentOfRelation( a, a, CartesianDiagonal( a, 2 ) );
true

1.5-19 Topos properties
gap> LoadPackage( "FinSetsForCAP", false );
true
gap> M := FinSet( [ 1 .. 5 ] );;
gap> N := FinSet( [ 1, 2, 4 ] );;
gap> P := FinSet( [ 1, 4, 8, 9 ] );;
gap> G_f := [ [ 1, 1 ], [ 2, 2 ], [ 3, 1 ], [ 4, 2 ], [ 5, 4 ] ];;
gap> f := MapOfFinSets( M, G_f, N );;
gap> IsWellDefined( f );
true
gap> G_g := [ [ 1, 4 ], [ 2, 4 ], [ 3, 2 ], [ 4, 2 ], [ 5, 1 ] ];;
gap> g := MapOfFinSets( M, G_g, N );;
gap> IsWellDefined( g );
true
gap> DirectProduct( M, N );;
gap> DirectProductOnMorphisms( f, g );;
gap> CartesianAssociatorLeftToRight( M, N, P );;
gap> CartesianAssociatorRightToLeft( M, N, P );;
gap> TerminalObject( FinSets );;
gap> CartesianLeftUnitor( M );;
gap> CartesianLeftUnitorInverse( M );;
gap> CartesianRightUnitor( M );;
gap> CartesianRightUnitorInverse( M );;
gap> CartesianBraiding( M, N );;
gap> CartesianBraidingInverse( M, N );;
gap> exp := ExponentialOnObjects( M, N );;
gap> ExponentialOnObjects( FinSet( [ 1 ] ), exp );;
gap> ExponentialOnMorphisms( f, g );;
gap> CartesianRightEvaluationMorphism( M, N );;
gap> CartesianRightCoevaluationMorphism( N, M );;
gap> DirectProductToExponentialRightAdjunctMorphism( M, N,
>     UniversalMorphismIntoTerminalObject( DirectProduct( M, N ) )
> );;
gap> ExponentialToDirectProductRightAdjunctMorphism( M, N,
>     UniversalMorphismFromInitialObject( ExponentialOnObjects( M, N ) )
> );;
gap> CartesianLeftEvaluationMorphism( M, N );;
gap> CartesianLeftCoevaluationMorphism( N, M );;
gap> DirectProductToExponentialLeftAdjunctMorphism( M, N,
>     UniversalMorphismIntoTerminalObject( DirectProduct( M, N ) )
> );;
gap> ExponentialToDirectProductLeftAdjunctMorphism( M, N,
>     UniversalMorphismFromInitialObject( ExponentialOnObjects( M, N ) )
> );;
gap> M := FinSet( [ 1, 2 ] );;
gap> N := FinSet( [ "a", "b" ] );;
gap> P := FinSet( [ "*" ] );;
gap> Q := FinSet( [ "§", "&" ] );;
gap> CartesianPreComposeMorphism( M, N, P );;
gap> CartesianPostComposeMorphism( M, N, P );;
gap> DirectProductExponentialCompatibilityMorphism( [ M, N, P, Q ] );;

1.5-20 Subobject Classifier
gap> LoadPackage( "FinSetsForCAP", false );
true
gap> Display( SubobjectClassifier( FinSets ) );
[ "true", "false" ]
gap> Display( TruthMorphismOfTrue( FinSets ) );
[ [ [  ] ], [ [ [  ], "true" ] ], [ "true", "false" ] ]
gap> Display( TruthMorphismOfFalse( FinSets ) );
[ [ [  ] ], [ [ [  ], "false" ] ], [ "true", "false" ] ]
gap> Display( TruthMorphismOfNot( FinSets ) );
[ [ "true", "false" ],\
 [ [ "false", "true" ], [ "true", "false" ] ],\
 [ "true", "false" ] ]
gap> Display( CartesianSquareOfSubobjectClassifier( FinSets ) );
[ [ "true", "true" ], [ "false", "true" ],\
 [ "true", "false" ], [ "false", "false" ] ]
gap> Display( TruthMorphismOfAnd( FinSets ) );
[ [ [ "true", "true" ], [ "false", "true" ],\
 [ "true", "false" ], [ "false", "false" ] ],\
 [ [ [ "false", "false" ], "false" ], [ [ "false", "true" ], "false" ],\
 [ [ "true", "false" ], "false" ], [ [ "true", "true" ], "true" ] ],\
 [ "true", "false" ] ]
gap> Display( TruthMorphismOfOr( FinSets ) );
[ [ [ "true", "true" ], [ "false", "true" ],\
 [ "true", "false" ], [ "false", "false" ] ],\
 [ [ [ "false", "false" ], "false" ], [ [ "false", "true" ], "true" ],\
 [ [ "true", "false" ], "true" ], [ [ "true", "true" ], "true" ] ],\
 [ "true", "false" ] ]
gap> Display( TruthMorphismOfImplies( FinSets ) );
[ [ [ "true", "true" ], [ "false", "true" ],\
 [ "true", "false" ], [ "false", "false" ] ],\
 [ [ [ "false", "false" ], "true" ], [ [ "false", "true" ], "true" ],\
 [ [ "true", "false" ], "false" ], [ [ "true", "true" ], "true" ] ],\
 [ "true", "false" ] ]
gap> S := FinSet( [ 1, 2, 3, 4, 5 ] );
<An object in FinSets>
gap> A := FinSet( [ 1, 5 ] );
<An object in FinSets>
gap> m := EmbeddingOfFinSets( A, S );
<A monomorphism in FinSets>
gap> Display( ClassifyingMorphismOfSubobject( m ) );
[ [ 1, 2, 3, 4, 5 ], [ [ 1, "true" ], [ 2, "false" ], [ 3, "false" ],\
 [ 4, "false" ], [ 5, "true" ] ], [ "true", "false" ] ]
gap> LoadPackage( "FinSetsForCAP", false );
true
gap> M := FinSet( [ 1 .. 7 ] );
<An object in FinSets>
gap> N := FinSet( [ 2, 3, 5 ] );
<An object in FinSets>
gap> iotaN := EmbeddingOfFinSets( N, M );
<A monomorphism in FinSets>
gap> NC := PseudoComplementSubobject( iotaN );
<An object in FinSets>
gap> Display( NC );
[ [ 1, [  ] ], [ 4, [  ] ], [ 6, [  ] ], [ 7, [  ] ] ]
gap> tauN := EmbeddingOfPseudoComplementSubobject( iotaN );
<A monomorphism in FinSets>
gap> Nc := ImageObject( tauN );
<An object in FinSets>
gap> Display( Nc );
[ 1, 4, 6, 7 ]
gap> L := FinSet( [ 2, 4, 5, 7 ] );
<An object in FinSets>
gap> iotaL := EmbeddingOfFinSets( L, M );
<A monomorphism in FinSets>
gap> NIL := IntersectionSubobject( iotaN, iotaL );
<An object in FinSets>
gap> Display( NIL );
[ [ 2, 2 ], [ 5, 5 ] ]
gap> iotaNiL := EmbeddingOfIntersectionSubobject( iotaN, iotaL );
<A monomorphism in FinSets>
gap> NiL := ImageObject( iotaNiL );
<An object in FinSets>
gap> Display( NiL );
[ 2, 5 ]
gap> NUL := UnionSubobject( iotaN, iotaL );
<An object in FinSets>
gap> Display( NUL );
[ 2, 3, 5, 4, 7 ]
gap> iotaNuL := EmbeddingOfUnionSubobject( iotaN, iotaL );
<A monomorphism in FinSets>
gap> NuL := ImageObject( iotaNuL );
<An object in FinSets>
gap> Display( NuL );
[ 2, 3, 5, 4, 7 ]
gap> NPL := RelativePseudoComplementSubobject( iotaN, iotaL );
<An object in FinSets>
gap> Display( NPL );
[ [ 1, [  ] ], [ 2, [  ] ], [ 4, [  ] ], [ 5, [  ] ], [ 6, [  ] ], [ 7, [  ] ]\
 ]
gap> iotaNpL := EmbeddingOfRelativePseudoComplementSubobject( iotaN, iotaL );
<A monomorphism in FinSets>
gap> NpL := ImageObject( iotaNpL );
<An object in FinSets>
gap> Display( NpL );
[ 1, 2, 4, 5, 6, 7 ]

1.5-21 Pushout Complement

Define two composable monos K \stackrel{l}{\hookrightarrow} L \stackrel{m}{\hookrightarrow} G in FinSets:

gap> LoadPackage( "FinSetsForCAP", false );
true
gap> K := FinSet( [ 2, 3, 5 ] );;
gap> Display( K );
[ 2, 3, 5 ]
gap> L := FinSet( [ 0, 1, 2, 3, 5, 6 ] );;
gap> Display( L );
[ 0, 1, 2, 3, 5, 6 ]
gap> l := EmbeddingOfFinSets( K, L );
<A monomorphism in FinSets>
gap> G := FinSet( [ 0, 1, 2, 3, 4, 5, 6, 10 ] );;
gap> Display( G );
[ 0, 1, 2, 3, 4, 5, 6, 10 ]
gap> m := EmbeddingOfFinSets( L, G );
<A monomorphism in FinSets>

Now we compute the pushout complement D \stackrel{c}{\hookrightarrow} G of K \stackrel{l}{\hookrightarrow} L \stackrel{m}{\hookrightarrow} G:

gap> LoadPackage( "FinSetsForCAP", false );
true
gap> HasPushoutComplement( l, m );
true
gap> c := PushoutComplement( l, m );
<A monomorphism in FinSets>
gap> D := Source( c );;
gap> Display( D );
[ 2, 3, 4, 5, 10 ]
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 
Goto Chapter: Top 1 2 3 Ind

generated by GAPDoc2HTML