Composition

Suppose we have

A \xrightarrow {f} B \xrightarrow {g} C

two functions, so that the codomain of f coincides with the domain of g. It is then possible to define a composite function g \circ f such that for all a \in A (g \circ f)(a)=g(f(a)).That is, as a set of pairs g \circ f \subseteq A \times C is:

g \circ f = {(a,c) \in A \times C \; | \; \exist _{b \in B} ((a,b) \in f \land (b,c) \in g)}

An elementary, and important ,property of composition is the associative property. If we have:

A \xrightarrow {f} B \xrightarrow {g} C \xrightarrow {g} D

Then, for all a \in A we have:

(h \circ g) \circ f)(a) = (h \circ g)(f(a))= h(g(f(a))= h \circ (g \circ f)(a)

and therefore (h \circ g) \circ f = h \circ (g \circ f)

In every set A there is a special function ld_{A} that we call the identify in A. This function is the epitome of the non-action, it leaves everything as it was found.for every element a \in A we have ld_{A}. Two fundamental properties of the identify are:

  • f \circ ld_A=f for any function f with domain A
  • ld_A \circ f = f for any function f with domain A

Inverse function

With f : A \to B we can conclude that:

  • An inverse of f from the right is a function g such that f \circ g = ld_{B}

  • An inverse of f from the left is a function h such that h \circ f = ld_{A}

the only inverse function, on either side, of a bijective function f is called the inverse of f and is denoted by f^{-1}

when we have partial functions

f: A \dashrightarrow B, \;\;\; g: B \dashrightarrow C

then it is also possible to perform the composition, but note that the domain g \circ f may be smaller than the domain f. In general, we have :

dom(g \circ f) = \{ x \in dom(f) \; | \; f(x)\in dom(g) \} =f^{*}(dom(g))

Sometimes, if the range of f and the domain of g are disjoint, the composition has by domain \varnothing and is the empty function Recall that an injective function f: A \to B can always be seen as a bijective function if we reduce its codimension to ran(f). Por tanto cualquier funcion inyectiva f: A \to B admits a partial inverse

f^{-1}:ran(f)\to A

in such a way that:

f^{-1} \circ f = \text{ld}_{A},\;\;\;\; f \circ f^{-1}= \text{ld}_{ran(f)}

Laws of internal composition, semigrouping, groups

let M be a set. An operation or law of internal composition on M is a function:

\star : M \times M \to M

it is usual to represent symbolically the law of internal composition using a connective. That is, instead of writing \star (m,n) we can write m \star n

An example is when M is a finite set, then an operation can be expressed by a table. by means of a table, For example, suppose M= \{ a,b,c\}. The following table:

⋆abc
aabc
bbcb
ccab

It encodes the value of x\star y,which we find if we look in the row corresponding to element x and the row corresponding to element y. x and the row corresponding to element y.

We already know a whole series of operations on different sets, for example, addition, multiplication of integers, rational or real numbers. Multiplication of integers, rational or real numbers. Logic connectives can also be understood as operations on the set of well-formed formulas

We should know that

  • We say that the operation \star on the set M is associative if for any elements a, b and c of M are satisfied:
(a \star b) \star c = a \star (b \star c)
  • An semigroup is a set M endowed with an associative operation \star. Formally, the semigroup is usually referred to as M, and to over-understand the operation \star
  • Let (M , \star) be a semigroup. We say that e \in M is a neutral element if verifies that for all x \in M :
x \star e = e \star x = x

  • We say that two elements m and n of a monoid M are inverses of each other if m \star n = e, the neutral element.

  • We say that two elements m and n of a moinoid M are inverses of each other if m \star n = n \star m= e, the neutral element of M. In such a case we say that m and n are invertible.

  • We say that a semigroup (M, \star) is commutative if for any pair m, n of elements of M one has, for any pair m, n of elements of M one has,

m \star n\star =n \star m

given the above definitions, we can conclude several interesting facts

If a semigroup has a neutral element, it is unique.

Proof. Suppose that e and u are two neutral elements of the semigroup M. Then e \star u = e, since e is a neutral element. Moreover e \star u = u, because u is a neutral element. That is,

e=e\star u= e

and therefore all the neutral elements that could be in M are equal to each other

if m is invertible, its inverse is unique Proof. Let n_{1} and n_{2} be two inverses of m. We have then,

m \star n_{1} = e= m \star n_{2}

Operating on the elements of this identity with n1 from the left, we obtain:

(n_{1} \star m) \star n_{1} = (n_{1} \star m) \star n_{2}

and from there,

n_{1}=n_{2}

Given any monoid (M , \star), we can always find a group within it as follows. The set of its invertible elements is nonempty, since it always has at least one identity element.The subset (M, \star), endowed with the operation \star restricted to M\star, is a group. Which we call the unit group of M

Another thing is that given any monoid (M,\star), we can always find a group within it as follows. as follows. The set of its invertible elements is noneempty, since it always has at leat the identify element.iThe subset M\star, endowed with the operation \star restricted to M\star is a group, wich we call the unit group of M.

The concept of invertible element in a monoid is precisely a generalization of the concept of invertible function. A function f: X\to X is an invertible element of the monoid $F(X,x) if and only if it is an invertible function, if only if is a bijective function. The inverse element of f is nothing else than the inverse function.

the set Biy(X) of all invertible functions of X on X is then the unit group of F(X,X). units of F(X,X). If X has at least 3 elements, Biy(X) is a noncommutative group

Morphism

A morphism between (M,\star) and (N,\cdot) is a function,

\varphi : M \to N

wich has the property that for any m and m' elements of M, one has:

\varphi (m\star n)= \varphi (m) \cdot \varphi (n)

if in addition \varphi is bijective we say that M is an isomorphism

Depending on wheter the structures in question are semigroups, monoids or groups, we can speak of semigroup, monoid or group morphisms. Morphisms of semigroupsm, monoids or groups

Carley theorem

Let G be a group. Then G is isomorphic to a semigroup of Biy (G).

Proof Let's define a morphism:

L:G \to \text{Biy}(G)

as follows: for any g and h of G,L(g)(h)= g \star h isuffices now to prove that this morphism is injective

Since the elements of Biy(X) are functions of X in X, the subgroups of Biy(X) are called groups of transformations. of X in X, the subgroups of Biy(X) are called groups of transformations. In a sense, we can say that the groups of transformations are concrete manifestations of the notation of group abstactness.Cayley's theorem tells us that every group is isomorphic to a group of transformations. It also tells us that every finite group with n different elements, is isomorphic to a subgroup of the symmetric group of n letters.

Set equipotence

We say that A and B are equipotent if there exists a bijective function between A and B. A and B. We write in that case |A| = |B|.

It is clear that if A and B are finite, then they are equipotent if and only if they have the same number of elements. In general, another way to express that A and B are equipotent is by the phrase A and B have the same cardinal.

Similarly, we know that A is minuspotent to B if there exists an injective function of A on B, in which case we write |A| ≤ |B|. If in addition A and B are not equipotent, we write |A| < |B|.

Another way of expressing that A is minuspotent to B are equipotent is by the phrase A has cardinal less than or equal to B. Again, this phrase will make sense later, until we have accepted the principle of good order we will not be able to show that all sets are comparable to each other, that is, that given two sets A and B then one of them must have cardinality less than or equal to B.

if A is not empty and there is an injective function f: f: A \to B then there is an overjective funcion g:A \to A and we can prove this as follows:

If A is not empty then we can choose an element a \in A. We define then:

f(x)= \left\{ \begin{array}{lcc} f^{-1}(x) & si & x \in ran(f) \\ \\ a & si & x \notin ran(f) \end{array} \right.

thus g is overjective and with that we can see the Cantor-Schr theorem ̈oder-Bernstein:

Theorem. Suppose that there are injective functions f:A\to B and g: B\to A. Then there is a bijective function: F: A\to B

Proof . We consider the inverse functions f^{-1} : f(A) \xrightarrow{\sim} B y g^{-1} : g(B) \xrightarrow{\sim} A For each element a \in A we define a finite or infinite sequence a_{0},a_{1},a_{2},a_{3},... of elements alternating A and B as follows

  • Elements to wich corresponds a sequence that never ends

  • Elements that generate a finite sequence with an odd number of terms that terminates in an element A that does not belong to g(B)

  • Elements that generate a finite sequence with an even number of terms that terminates in an element of B that does not belong to g(B)

It is clear that these three possibilities are mutually exclusive. We call A' the subset of the elements of a that verify condition (c) above. Let us first note that A' \sube g(B) since if the sequence starting with a terminates in an element of B then it is because it was at least possible to take the first step. This allow us to define by a function F: A \to B by means of the formula

F(x)= \left\{ \begin{array}{lcc} g^{-1}(x) & si & x \in A' \\ \\ f(x) & si & x \notin A' \end{array} \right.

Let us see that F is overjective. Consider any element b \in B. There are two possibles cases, b \notin f(A) or b \in f(A). Let us consider the first case. If b \notin f(A) the sequence corresponding to the elemnt g(b)\in A has only two termins:

g(b),b

since it is no longer possible to apply f^{-1} to b.This implies that g(b) \in A' and in that case F(g(b))=g^{-1}(g(b))=b. Let us consider the second case b \in f(A). examine now the element g(b) \in A, the sequence that corresponds to it has three terms, and may eventually be infinite

g(b),b,f^{-1}(b), ...

Again there are two possibilities, g(b)\in A' (which corresponds to a finite sequence ending in B) and g(b) \notin A'. in the first case, we have f(g(b))=b. In the second case, g(b) \notin A' let us note that the sequence corresponding to f^{-1} (b) is the same as that of g(b), but without the first two terms. Therefore, in that case we also have f^{-1}(b) \notin A' and F(f^{-1}(b))=b. In either case we have found an element of a whose image by F is b and we can ensure that F is overjective

Let us see that F is injective. Let a and a' two elements of A having the same image b= F(a)=F(a). There are three mutually exclusive possibilities.

  1. a and a are both in the set A'. in that case g^{-1}(a)=g^{-1}(a') and since g^{-1} is a bijection between g(B) and A we have that a=a'

  2. a and a' are both outside A'. in that case f(a)=f(a') and since f is injective we get a = a

  3. One of them is in A' and the other is outside A. Let us see that this case is not possible, and assuming it leads to contradiction. Without loss of generality let us consider a \notin A' and a' \in A'. That means f(a) = g^{-1}(a')=b. let us consider the sequence corresponding to the element a. This is,

a',b,a,...

That is the sequence of a is the sequence of a' eliminating the first two terms. Since the element a' corresponds to a finite sequence that ends in an element of B, the element a, must have the same ocurrence, and therefore a \in A', in contradiction with our hypotesis a \notin A'. We have seen then that in the first two cases a = a' and that the third case cannot occur. Therefore F is injective.

Thanks to the Cantor-Schroder-Bernstein theorem, we can compare the size of the conjunctions. c conjuncts.

Equipotent

We say that A and B are equipotent if there exists a bijective function between A and B. A and B. We write in that case |A| = |B|. It is clear that if A and B are finite, then they are equipotent if and only if they have the same number of elements. In general, another way to express that A and B are equipotent is by the phrase A and B have the same cardinal.

Similarly, we know that A is minuspotent to B if there exists an injective function of A on B, in which case we write |A| ≤ |B|. If in addition A and B are not equipotent, we write |A| < |B|. Another way of expressing that A is minuspotent to B are equipotent is by the phrase A has cardinal less than or equal to B. Again, this phrase will make sense later, until we have accepted the principle of good order we will not be able to show that all sets are comparable to each other, that is, that given two sets A and B then one of them must have cardinality less than or equal to B.

if A is not empty and there is an injective function f: f: A \to B then there is an overjective funcion g:A \to A
and we can prove this as follows: If A is not empty then we can choose an element a \in A. We define then:

f(x)= \left\{ \begin{array}{lcc} f^{-1}(x) & si & x \in ran(f) \\ \\ a & si & x \notin ran(f) \end{array} \right.

thus g is overjective and with that we can see the Cantor-Schr theorem ̈oder-Bernstein: Theorem. Suppose that there are injective functions f:A\to B and g: B\to A. Then there is a bijective function: F: A\to B Proof We consider the inverse functions f^{-1} : f(A) \xrightarrow{\sim} B y g^{-1} : g(B) \xrightarrow{\sim} A For each element a \in A we define a finite or infinite sequence a_{0},a_{1},a_{2},a_{3},... of elements alternating A and B as follows

  • Elements to wich corresponds a sequence that never ends
  • Elements that generate a finite sequence with an odd number of terms that terminates in an element A that does not belong to g(B)
  • Elements that generate a finite sequence with an even number of terms that terminates in an element of B that does not belong to g(B)

It is clear that these three possibilities are mutually exclusive. We call A' the subset of the elements of a that verify condition (c) above. Let us first note that A' \sube g(B) since if the sequence starting with a terminates in an element of B then it is because it was at least possible to take the first step. This allow us to define by a function F: A \to B by means of the formula

F(x)= \left\{ \begin{array}{lcc} g^{-1}(x) & si & x \in A' \\ \\ f(x) & si & x \notin A' \end{array} \right.
g(b),b

since it is no longer possible to apply f^{-1} to b.This implies that g(b) \in A' and in that case F(g(b))=g^{-1}(g(b))=b. Let us consider the second case b \in f(A). examine now the element g(b) \in A, the sequence that corresponds to it has three terms, and may eventually be infinite

g(b),b,f^{-1}(b), ...

Again there are two possibilities, g(b)\in A' (which corresponds to a finite sequence ending in B) and g(b) \notin A'. in the first case, we have f(g(b))=b. In the second case, g(b) \notin A' let us note that the sequence corresponding to f^{-1} (b) is the same as that of g(b), but without the first two terms. Therefore, in that case we also have f^{-1}(b) \notin A' and F(f^{-1}(b))=b. In either case we have found an element of a whose image by F is b and we can ensure that F is overjective Let us see that F is injective. Let a and a' two elements of A having the same image b= F(a)=F(a). There are three mutually exclusive possibilities.

1) a and a are both in the set A'. in that case g^{-1}(a)=g^{-1}(a') and since g^{-1} is a bijection between g(B) and A we have that a=a'

2) a and a' are both outside A'. in that case f(a)=f(a') and since f is injective we get a = a

3) One of them is in A' and the other is outside A. Let us see that this case is not possible, and assuming it leads to contradiction. Without loss of generality let us consider a \notin A' and a' \in A'. That means f(a) = g^{-1}(a')=b. let us consider the sequence corresponding to the element a. This is,

a',b,a,...

That is the sequence of a is the sequence of a' eliminating the first two terms. Since the element a' corresponds to a finite sequence that ends in an element of B, the element a, must have the same ocurrence, and therefore a \in A', in contradiction with our hypotesis a \notin A' We have seen then that in the first two cases a = a' and that the third case cannot occur. Therefore F is injective. Thanks to the Cantor-Schroder-Bernstein theorem, we can compare the size of the conjunctions. c conjuncts.