Back
 OJDM  Vol.10 No.3 , July 2020
Partitioning of Any Infinite Set with the Aid of Non-Surjective Injective Maps and the Study of a Remarkable Semigroup
Abstract: In this article, we will present a particularly remarkable partitioning method of any infinite set with the aid of non-surjective injective maps. The non-surjective injective maps from an infinite set to itself constitute a semigroup for the law of composition bundled with certain properties allowing us to prove the existence of remarkable elements. Not to mention a compatible equivalence relation that allows transferring the said law to the quotient set, which can be provided with a lattice structure. Finally, we will present the concept of Co-injectivity and some of its properties.

1. Introduction

The concept of map in mathematics has a primordial role in understanding the links that exist between the different mathematical fields and structures. A map is binary relation over two sets that associates to every element of the first set exactly one element of the second set, sometimes with a specific property. For instance, a “map” is a “linear transformation” in linear algebra, a “continuous function” in topology, operators in analysis and representations in group theory, etc. In this article we will show how non-surjective injective maps allow to partitioning an infinite set in several ways.

2. Part I

Proposition 1

Let E, and F be non-empty sets. If f , g are two non-surjective injective maps from E to F and from F to E respectively, then:

· ( A , f ( B ) , I f g ) forms a partition of F.

· ( B , g ( A ) , I g f ) forms a partition of E.

where,

A = { y F | x E , f ( x ) y } and B = { x E | y F , g ( y ) x }

and I f , I g representing the image sets under f , g respectively.

Proof

Let E and F be two non-empty sets, and let ƒ and g be two non-surjective injective maps from E to F, and from F to E respectively. Since ƒ and g are non-surjective, then the following sets:

A = { y F | x E , f ( x ) y } and B = { x E | y F , g ( y ) x } are non-empty.

Also, obviously E = B I g such as B I g = as follows from the definition of I g .

For any such map ƒ from E to F:

I f = f ( E ) = f ( B I g ) = f ( B ) f ( I g ) = f ( B ) I f g

So F = A f ( B ) I f g

Since ƒ is an injective map then:

f ( B I g ) = f ( B ) I f g = f ( ) =

Therefore, ( A , f ( B ) , I f g ) forms a partition of F.

In analogy to the map g from F to E, ( B , g ( A ) , I g f ) forms a partition of E.

Note 1

This process could be applied repeatedly, and for each iteration, finer partitions of the sets E and F respectively will be obtained, e.g. after 2nd iteration we have:

· E = B g ( A ) ( g f ) ( B ) I g f g

· F = A f ( B ) ( f g ) ( A ) I f g f

In case that ƒ and g are (two) (2) different non-surjective injective maps from an infinite set E to itself, we can compose either by ƒ or by g, or by both indefinitely. Thus several partition classes of E can obtained, for example after a second (2nd) iteration

· E = A f f ( A f ) f 2 ( A f ) I f 3

· E = A g g ( A g ) g 2 ( A g ) I g 3

· E = A f f ( A g ) ( f g ) ( A f ) I f g f

· E = A g g ( A f ) ( g f ) ( A g ) I g f g

· E = A f f ( A g ) ( f g ) ( A g ) I f g 2

· E = A g g ( A f ) ( g f ) ( A f ) I g f 2

where,

A f = { y F | x E , f ( x ) y } and A g = { x E | y F , g ( y ) x }

Example 1

If E = F = i.e. the set of natural numbers, ƒ and g are two maps from to itself (i.e. ƒ and g are non-surjective injective) and defined by: ˆ

· n , f ( n ) = 2 n

· n , g ( n ) = 2 n + 1

Knowing that A f = 2 + 1 and A g = 2 then:

· f ( A g ) = 4

· g ( A f ) = 4 + 3

· ( f g ) ( A f ) = 8 + 6

· ( g f ) ( A g ) = 8 + 1

· ( f g f ) ( ) = 8 + 2

· ( g f g ) ( ) = 8 + 5

Therefore, we can partition the set to the second (2nd) order by ƒ and g such as:

= ( 2 + 1 ) ( 4 ) ( 8 + 6 ) ( 8 + 2 )

= ( 2 ) ( 4 + 3 ) ( 8 + 1 ) ( 8 + 5 )

2.1. Remarkable Partition

Proposition 2

Let E be an infinite set, be the set of natural numbers, and ƒ be a non-surjective injective map from E to itself, such that:

A f = { y E | x E , f ( x ) y }

Then,

n , E = [ i = 0 i = n f i ( A f ) ] I f n + 1

where, f i ( A f ) = f f f ( A f ) i times

Proof

By induction:

For n = 0 , we have, by definition E = A f I f , and for n = 1 the proposition 1 states that, if E = F and f = g then, E = A f f ( A f ) I f 2 Suppose that the said property is true for n. Then, by composing by ƒ, we get:

I f = f ( E ) = [ i = 0 i = n f i + 1 ( A f ) ] I f n + 2 = [ i = 1 i = n + 1 f i ( A f ) ] I f n + 2

Then,

E = A f [ i = 1 i = n + 1 f i ( A f ) ] I f n + 2 = [ i = 0 i = n + 1 f i ( A f ) ] I f n + 2

Therefore,

n , E = [ i = 0 i = n f i ( A f ) ] I f n + 1

Note 2

For all non-surjective injective maps ƒ from an infinite set E to itself,

n , A f n + 1 = i = 0 i = n f i ( A f )

Definition 1

Let ƒ be a map from no-empty set E to itself,

· x E is a fixed point of ƒ if, f ( x ) = x .

· A E is a fixed point set of ƒ if, f ( A ) = A .

Proposition 3

For all non-surjective injective maps f from an infinite set E to itself, n , f n ( A f ) contains no fixed points of ƒ.

Proof

By induction:

For n = 0 , let x A f , and by definition y E , f ( y ) x , particularly for y = x so f ( x ) x then A f contains no fixed points of f. Suppose that the aforementioned property is true for n, let x f n + 1 ( A f ) = f ( f n ( A f ) ) , then y f n ( A f ) such that x = f ( y ) , we have f ( y ) y (by inductive hypothesis), since ƒ is injective then f ( f ( y ) ) f ( y ) so f ( x ) x , then x f n + 1 ( A f ) , f ( x ) x . Therefore, n , f n ( A f ) contains no fixed points of ƒ.

Note 3

Let E be an infinite set, and ƒ be a non-surjective injective map from E to itself, we define the following:

F i x f = { x E | f ( x ) = x } and S t f ( E ) = { A E | f ( A ) = A }

· n , F i x f f n ( A f ) =

· n * , F i x f F i x f n

· n * , F i x f n F i x f 2 n

· p , n * , f p ( F i x f n ) = F i x f n

· For all ƒ non-surjective injective maps from an infinite set E to itself,

F i x f S t f ( E )

Proposition 4

For all ƒ non-surjective injective maps from E to itself,

A S t f ( E ) , n , f n ( A f ) A =

Proof

Let A S t f ( E ) , by induction, For n = 0 , we have, by definition A f I f = then A f A = A f f ( A ) = ˆ Suppose that the said property is true for n , let x f n + 1 ( A f ) A , then, y f n ( A f ) , x = f ( y ) and y 0 A , x = f ( y 0 ) . Since ƒ is injective so y = y 0 f n ( A f ) A , which contradicts the inductive hypothesis. Then,

f n + 1 ( A f ) A = .

Therefore, A S t f ( E ) , n , f n ( A f ) A =

Lemma 1 (Generalization)

p * , A S t f p ( E ) , n , f n ( A f ) A =

Proof

By complete (strong) induction,

Let p * , and A S t f p ( E ) = { A E | f p ( A ) = A } : For n = 0 , we have, by definition A f I f = , since p * , I f p I f , then: A f A = A f f p ( A ) =

Suppose that the said property is true for all i { 1 , , n } , let x f n + 1 ( A f ) A , then, y A f , x = f n + 1 ( y ) and y 0 A , x = f p ( y 0 ) . Since ƒ is injective then,

· f n p + 1 ( y ) = y 0 , if n + 1 > p , which contradicts the inductive hypothesis, because i = n p + 1 { 1 , , n }

· y = f p n 1 ( y 0 ) , if p > n + 1 , which contradicts A f I f p n 1 =

· y = y 0 , if n + 1 = p , which contradicts A f A =

Then,

f n + 1 ( A f ) A = ,

Therefore,

p * , A S t f p ( E ) , n , f n ( A f ) A =

QED

For all n , and for all ƒ non-surjective injective maps from an infinite set E to itself, we define the following:

· S f n ( E ) = { A E | p { 1 , , n + 1 } , f p ( A ) = A }

· S f ( E ) = { A E | p * , f p ( A ) = A }

· S f n = { x A | A S f n ( E ) }

· S f = { x A | A S f ( E ) }

Theorem 1

Let E be an infinite set, and ƒ be a non-surjective injective map from E to itself, then:

E = [ n f n ( A f ) ] S f

Proof

Note that for n = 0 , S f 0 ( E ) = S t f ( E ) , The sequence of subsets of E, ( S f n ) n is increasing by inclusion, so it is convergent, the limit is: n S f n = S f

We have already established that,

n , E = [ i = 0 i = n f i ( A f ) ] I f n + 1

Otherly, according to the Lemma 1, n , E = [ i = 0 i = n f i ( A f ) ] S f n =

Let’s define the following, n , I f n + 1 ^ = I f n + 1 \ S f n the sequence of subsets of ( I f n + 1 ^ ) n is decreasing by inclusion then, it is convergent [1], the limit is:

n I f n + 1 ^ =

Because, let x n I f n + 1 ^ , then:

x n I f n + 1 \ S f n n , x I f n + 1 \ S f n n , x I f n + 1 and x S f n ¯

n , x I f n + 1 and n , x S f n ¯ x n I f n + 1 and x n S f n ¯

x n I f n + 1 and x n S f n ¯ x n I f n + 1 and x S f ¯

x [ n I f n + 1 ] \ S f

On the other hand, the sequence of subsets of E, ( I f n + 1 ) n is strictly decreasing by inclusion, then it is convergent and the limit is H = n I f n + 1 , and since ƒ is injective, so f ( H ) = H then ƒ is bijective from H to itself, and H S t f ( E ) S f ( E ) .

n , E = [ i = 0 i = n f i ( A f ) ] I f n + 1 ^ S f n

Therefore,

E = [ n f n ( A f ) ] S f

N.B. If S f = , then we get:

E = n f n ( A f )

QED

Example 2

is the set of real numbers, and P ( ) is the set of subsets of .

Let ƒ be a map from to itself, defined by:

f ( x ) = { x + 1 , if x 0 x , if x < 0

Therefore, ƒ is injective non-surjective from to itself, because ƒ is injective and A f = [ 0 , 1 [ .

where,

n * , f n ( x ) = { x + n , if x 0 x , if x < 0

We have, f ( A f ) = [ f ( 0 ) , f ( 1 ) [ = [ 1 , 2 [ + since ƒ is increasing Therefore,

n * , f n ( A f ) = [ n , n + 1 [

· n , S f n = S f = *

· n , S f n ( E ) = S f ( E ) = P ( * )

According to the theorem 1, we can write:

= * [ n [ n , n + 1 [ ]

Example 3

Remark

If h is an affine map from to , so that h ( x ) = a x + b / a , b and a 0 , then:

n * , x , h n ( x ) = a n x + b ( 1 + a + + a n 1 )

If a 1 , then:

n * , x , h n ( x ) = a n x + b ( 1 a n 1 a )

Let ƒ be a map defined from E = [ 0 , 4 ] to itself by:

x [ 0 , 4 ] , f ( x ) = { x + 1 , if x [ 0 , 1 ] x + 1 , if x ] 1 , 2 ] 1 2 x + 2 , if x [ 2 , 4 ]

ƒ is non-surjective injective map from E to itself, so that:

· A f = ] 1 , 2 ]

· F i x f = { 4 }

· The set A = [ 0 , 1 ] E , fulfills the condition f ( A ) = A

· We have A f = ] 1 , 2 ] , f ( A f ) = f ( ] 1 , 2 ] ) = ] 2 , 3 ] [ 2 , 4 ] , f ( ] 2 , 3 ] ) = ] 3 , 7 2 ] ,

· S f = { 4 } [ 0 , 1 ]

The restriction of ƒ to [ 2 , 4 ] is an affine function such as a = 1 2 , and b = 2 , then:

n * , f n ( x ) = 1 2 n x + 2 ( 1 + 1 2 + + 1 2 n 1 )

We have: f n ( 2 ) = 4 1 2 n 1 , and f n ( 3 ) = 4 1 2 n ,

According to Theorem 1:

[ 0 , 4 ] = { ] 1 , 2 ] n ] 4 1 2 n 1 , 4 1 2 n ] } { 4 } [ 0 , 1 ]

Example 4

Let ƒ be a map defined from E = [ 0 , 3 ] to itself by:

x [ 0 , 3 ] , f ( x ) = { x + 2 , if x [ 0 , 1 ] 1 2 x + 1 , if x ] 1 , 2 [ x 2 , if x [ 2 , 3 ]

ƒ is non-surjective injective from E to itself, so that:

· A f = ] 1 , 3 2 ]

· F i x f =

· The set A = [ 0 , 1 ] E , fulfills the condition f ( A ) A , and f 2 ( A ) = A

· The set B = [ 2 , 3 ] E , fulfills the condition f ( B ) B , and f 2 ( B ) = B

· S f = [ 0 , 1 ] [ 2 , 3 ]

We have,

· x ] 1 , 2 [ , n * , f n ( x ) = 1 2 n x + 2 ( 1 1 2 n )

· lim x 1 f n ( x ) = 2 1 2 n and f n ( 3 2 ) = 2 1 2 n + 1

Therefore, according to Theorem 1:

[ 0 , 3 ] = { n ] 2 1 2 n , 2 1 2 n + 1 ] } [ 0 , 1 ] [ 2 , 3 ]

Corollary 1

Let f , g be non-surjective injective maps from an infinite set E to itself such as S f = S g ¯ , then:

E = n B n

where, n , B n = f n ( A f ) g n ( A g )

Therefore, ( B n ) n forms a partition of E.

Definition 2

· Let E be an infinite set, we write: I n j n s ( E ) as being the set of non-surjective injective maps from E to itself.

· I n j n s ( E , F ) as the set of non-surjective injective maps from a set E to a set F, that being said, E and F are supposed to be non-empty and | E | | F | ( | E | is the cardinal of E).

Properties

1) ( I n j n s ( E ) , ) is a semigroup, because the composite of 2 (two) injective maps ƒ and g is injective and I f g I f , so f , g I n j n s ( E ) , f g I n j n s ( E ) .

2) f , g I n j n s ( E ) , A f g = A f f ( A g ) , ( A f , f ( A g ) , I f g ) is, indeed, a partition of E and E = A f g I f g , because f g I n j n s ( E ) .

3) There is no idempotent element for the law of composition in I n j n s ( E ) and if such an element exists, then f 2 = f and since ƒ is injective, then f = I d which is contradictory, because, f I n j n s ( E ) .

4)Let f I n j n s ( E ) , and assuming that ƒ is a map from E to itself such as: f ˜ ( x ) = { x , if x A f f ( x ) , if x I f

5) We have, f I n j n s ( E ) , f ˜ I n j n s ( E ) knowing that I f ˜ = A f I f 2 and A f ˜ = f ( A f )

6) Let f I n j n s ( E ) , we have, f ˜ ( A f ˜ ) = f ˜ ( f ( A f ) ) = f 2 ( A f ) , and

I f ˜ 2 = f ˜ ( I f ˜ ) = f ˜ ( A f I f 2 ) = f ˜ ( A f ) f ˜ ( I f 2 ) = A f I f 3

Then,

E = A f ˜ f ˜ ( A f ˜ ) I f ˜ 2 = A f f ( A f ) f 2 ( A f ) I f 3

Therefore, f ˜ allow us to reduce order of iteration.

7) f I n j n s ( E ) ,

· A f ˜ f = A f ˜ f ˜ ( A f ) = A f f ( A f ) = A f 2 , then I f ˜ f = I f 2

· A f f ˜ = A f f ( A f ˜ ) = A f f 2 ( A f ) ,then, I f f ˜ = f ( A f ) I f 3

· A f ˜ ˜ = f ˜ ( A f ˜ ) = f 2 ( A f ) , then I f ˜ ˜ = A f f ( A f ) I f 3

8) Let f I n j n s ( E , F ) and g I n j n s ( F , E ) , so:

f g I n j n s ( F ) and g f I n j n s ( E )

2.2. Equivalence Relations

Example 5

Let f , g I n j n s ( E ) , we define the binary relation R on I n j n s ( E ) , by:

f R g A f = A f I f = I g

R is, indeed, an equivalence relation, because:

· R is reflexive, f R f , f I n j n s ( E )

· R is symmetric, f R g A f = A g g R f , f , g I n j n s ( E )

· R is transitive, f , g and h I n j n s ( E ) , f R g and g R h A f = A g and A g = A h A f = A h f R h

Example 6

Let f , g I n j n s ( E ) , we define the binary relation R on I n j n s ( E ) , by:

f , g I n j n s ( E ) : f R g n * , I f n = I g n

R is, indeed, an equivalence relation, because:

· R is reflexive, f R f , f I n j n s ( E )

· R is symmetric, f R g n * , I f n = I g n g R f , f , g I n j n s ( E )

· R is transitive, f , g and h I n j n s ( E ) , f R g and g R h n * , I f n = I g n and n * , I g n = I h n n * , I f n = I h n f R h

Example 7

f , g I n j n s ( E ) , f R g f ( A f ) = g ( A g )

Example 8

f , g I n j n s ( E ) , f R g S f = S g n f n ( A f ) = n g n ( A g )

n f n ( A f ) : as being the ƒ-semicoverage of a set E.

3. Part II

Let E be an infinite set, f I n j n s ( E ) , and f ¯ = { g I n j n s ( E ) | I g I f }

We get the following:

· f I n j n s ( E ) , n * , f n f ¯

· f , g I n j n s ( E ) : I f I g f ¯ g ¯

Let h f ¯ i.e. I f I h let x I h I f , so x I h and x I f I g , so x I h and x I g , so x I h I g so I h I g , then h g ¯ therefore f ¯ g ¯

Theorem 2

Let E be an infinite set, then there exists a non-surjective injective map ψ from E to itself, so that for any such non-surjective injective map ϕ from E to itself, we have:

I ψ I ϕ

Proof

By contradiction, let’s suppose that for all ψ non-surjective injective maps from E to itself, there exists a map ϕ ψ I n j n s ( E ) such as I ψ I ϕ ψ = so that I ϕ ψ A ψ . Additionally E is an infinite set, so E is equipotential [2] to E \ { a } , a E . Considering this bijection ƒ as a map from E to itself, then f I n j n s ( E ) , and A f = { a } , according to all of the above, there exists a map f ϕ I n j n s ( E ) such as I f ϕ A f = { a } , which contradicts the fact that f ϕ injective.

QED

Note 4

· ψ I n j n s ( E ) , so that: φ I n j n s ( E ) , ψ 1 ( I φ )

· If ψ applies to the former theorem then: ψ ¯ = I n j n s ( E ) .

Proposition 5

f I n j n s ( E ) , g I n j n s ( E ) \ { f } , so that A f A g

Proof

By contradiction, assuming that exists a map f I n j n s ( E ) , so that g I n j n s ( E ) \ { f } , A f A g = , then g I n j n s ( E ) \ { f } , I f I g = E .

Let g = f 2 , so I f I g = I f E because f I n j n s ( E ) which is contradictory.

Proposition 6

f I n j n s ( E ) , g I n j n s ( E ) \ { f } , such as A f I g

Proof

By contradiction, assuming that exists a map f I n j n s ( E ) , so that, g I n j n s ( E ) \ { f } , A f I g = then g I n j n s ( E ) \ { f } , I f A g = E . On the other hand, if g = f ˜ , I f A g = E , additionally A g = f ( A f ) I f so I f A g = I f = E which is contradictory.

Note 5

We can define another composition law T for I n j n s ( E ) so that,

f , g I n j n s ( E ) , ( f T g ) ( x ) = { g ( x ) , if x f 1 ( I g ) f ( x ) , if x f 1 ( A g )

· f T f = f , f I n j n s ( E ) then every element is idempotent under the law T.

· f , g I n j n s ( E ) , if I f I g = , then f T g = f .

· f , g I n j n s ( E ) , if I f I g , then f T g = g .

· f I n j n s ( E ) , f T f ˜ = f and f ˜ T f = f ˜ .

· Generally, f , g I n j n s ( E ) , f T g g T f .

4. Part III

4.1. Study of the Quotient Set

Let E be an infinite set, and f , g I n j n s ( E ) . We define the binary relation R on I n j n s ( E ) , by:

f R g A f and A g have the same cardinal

The binary relation R is reflexive, symmetric and transitive, so R is an equivalence relation on I n j n s ( E ) .

We define C l ( f ) = { g I n j n s ( E ) | | A g | = | A f | } the equivalence class of a map ƒ.

Note 6

· Let f I n j n s ( E ) , as A f ˜ = f ( A f ) so A f and A f ˜ have the same cardinal, because ƒ is injective then f ˜ C l ( f ) , therefore,

f I n j n s ( E ) , f ˜ C l ( f )

· Let f , g I n j n s ( E ) , assuming that the cardinals of A f and A f are finite, and thus, | A f g | = | A f f ( A g ) | = | A f | + | A g | | A f f ( A g ) | , and since A f f ( A g ) = , then: | A f g | = | A f f ( A g ) | = | A f | + | A g | .Since the composition of two (2) maps ƒ and g on I n j n s ( E ) yields a disjoint union, i.e. A f g = A f f ( A g ) , with A f f ( A g ) = ,then we can extend the sum of the cardinals even for infinite sets, such as:

| A f g | = | A f f ( A g ) | = | A f | + | A g | = sup { | A f | , | A g | }

· For all maps f , g , h and t I n j n s ( E ) so that f R g and h R t i.e. | A f | = | A g | and | A h | = | A t | . Since:

| A f h | = sup { | A f | , | A g | } = sup { | A g | , | A t | } = | A g t | , therefore,

f g R h t

· The map’s composition law is compatible under the equivalence relation R, then we can provide the quotient set ( I n j n s ( E ) / R , ) with a structure of a semigroup.

· C l ( f ) and C l ( g ) I n j n s ( E ) / R : C l ( f ) C l ( g ) = C l ( f g )

4.2. Partial Order

Let C l ( f ) , C l ( g ) I n j n s ( E ) / R , define a binary relation on I n j n s ( E ) / R by:

C l ( f ) C l ( g ) | A f | | A g |

· C l ( f ) I n j n s ( E ) / R , C l ( f ) C l ( f )

So is reflexive.

· C l ( f ) , C l ( g ) I n j n s ( E ) \ R , C l ( f ) C l ( g ) and C l ( g ) C l ( f ) | A f | | A g | and | A g | | A f | | A f | = | A g | so C l ( f ) = C l ( g )

So is asymmetric.

· C l ( f ) , C l ( g ) and C l ( h ) I n j n s ( E ) / R : C l ( f ) C l ( g ) and C l ( g ) C l ( h ) | A f | | A g | and | A g | | A h | | A f | | A h | C l ( f ) C l ( h )

So is transitive.

Therefore, the relation is a partial order on I n j n s ( E ) / R .

Note 7

· Since C l ( f ) , C l ( g ) I n j n s ( E ) / R , C l ( f ) C l ( g ) or C l ( g ) C l ( f ) then is a total partial order on I n j n s ( E ) / R .

· The partial order on the semigroup ( I n j n s ( E ) / R , ) is, indeed, compatible [3] with the equivalence class’s composition law of composition *, then:

C l ( f ) , C l ( g ) and C l ( h ) I n j n s ( E ) / R ,

If C l ( f ) C l ( g ) then C l ( f ) C l ( h ) = C l ( f h ) C l ( g h ) = C l ( g ) C l ( h ) and C l ( h ) C l ( f ) = C l ( h f ) C l ( h g ) = C l ( h ) C l ( g )

· I n j n s ( E ) / R is well-ordered, because any non-empty subset has a smallest element.

· I n j n s ( E ) / R is a lattice, because it is ordered and every pair of elements has both upper bound and lower bound [4].

· I n j n s ( E ) / R provided with the order relation has a minimal element C l ( f ) , so that | A f | = 1 , and also maximal element C l ( g ) , so that A g has the same cardinality as E.

· If E is an infinite countable set, the map φ defined by:

φ : I n j n s ( E ) * { 0 } = M , f I n j n s ( E ) , φ ( f ) = | A f | ,

where, 0 represents the cardinal of .

Considering the convention: n * , n + 0 = 0 , φ is a morphism of semigroups of ( I n j n s ( E ) , ) on ( M , + ) .

f , g I n j n s ( E ) , φ ( f g ) = | A f g | = | A f | + | A g | = φ ( f ) + φ ( g )

Complement

Let f , g I n j n s ( E ) so that | A f | < | A g | , with the assumption that A f and A g are considered finite, I f and I g are equipotential because, the map ψ defined from I f to I g by:

x I f , ψ ( x ) = ( g f 1 ) ( x ) is bijective, where f 1 is defined from I f to E, and for all x I f , we associated its inputs by ƒ, we have:

· x , y I f , ψ ( x ) = ψ ( y ) ( g f 1 ) ( x ) = ( g f 1 ) ( y ) g ( f 1 ( x ) ) = g ( f 1 ( y ) ) f 1 ( x ) = f 1 ( y ) x = y (because both g and f 1 are injectives). Therefore ψ is injective.

· On the other hand ψ ( I f ) = ( g f 1 ) ( I f ) = g ( f 1 ( I f ) ) = g ( E ) = I g so ψ is surjective.

Let φ I n j n s ( A f , A g ) so that the map θ is defined by:

θ ( x ) = { φ ( x ) , if x A f ψ ( x ) , if x I f

Belong to I n j n s ( E ) and A θ = A φ .

Note 8

· If g = f 2 so x I f , ψ ( x ) = f ( x ) so if φ = f / A f then we have, θ = f , and if φ = I d / A f so θ = f ˜

· We considered, previously, that, A f and A g are finite. That said, we can build the φ map even in case that A f and A g are infinite and that | A f | = | A g | .

5. Part IV

E Permutations Group Action

Let σ ( E ) be the permutations group of E, f I n j n s ( E ) and σ σ ( E ) , f σ I n j n s ( E ) , because, since ƒ and σ are injective then f σ is injective and σ σ ( E ) , ( f σ ) ( E ) = f ( σ ( E ) ) = f ( E ) = I f E then f σ is non-surjective.

where σ σ ( E ) , I f σ = I f then A f σ = A f .

We have,

· ˆ σ 1 , σ 2 σ ( E ) and f I n j n s ( E ) : ( f σ 1 ) σ 2 = f ( σ 1 σ 2 )

· f I n j n s ( E ) , f I d = f

Let θ : σ ( E ) × I n j n s ( E ) I n j n s ( E )

so that σ σ ( E ) , f I n j n s ( E ) , θ ( σ , f ) = f σ

Therefore, the E permutations group operates on the rightmost on I n j n s ( E ) .

Note 9

The relation R defined on I n j n s ( E ) by: f R g σ σ ( E ) such as g = f σ is an equivalence relation, that is called Intransitivity relation [5].

Proposition 7

Let be, g I n j n s ( E ) : σ σ ( E ) so that g = f σ I f = I g .

Proof

) If there exists σ σ ( E ) so that g = f σ I g = I f σ = I f .

) If I f = I g , then the map σ : E E , so that x σ ( x ) = f 1 ( g ( x ) ) is bijective, because:

· σ ( E ) = f 1 ( g ( E ) ) = E so σ is surjective.

· x , y E : σ ( x ) = σ ( y ) f 1 ( g ( x ) ) = f 1 ( g ( y ) ) g ( x ) = g ( y ) x = y so σ is injective.

· x E , f σ ( x ) = f ( σ ( x ) ) = g ( x )

Note 10

· The equivalence class (Intransitivity relation) of the element ƒ is called the orbit of ƒ, C l ( f ) = { f σ | σ σ ( E ) } = { g I n j n s ( E ) | I g = I f } .

· The stabilizer of ƒ is: Δ f = { σ σ ( E ) | f σ = f } = { I d } , i.e. the morphism associated with the said action is injective.

6. Part V

Let f , g I n j n s ( E ) .

Definition 3

ƒ and g are said to be Co-injectives, if,

I f I g and x , y E , f ( x ) = g ( y ) x = y

Let f ^ = { g I n j n s ( E ) | g is Co-injective with f }

We have f ^ because f I n j n s ( E ) , I f I f and x , y E , f ( x ) = f ( y ) x = y so ƒ is Co-injective with itself.

Therefore f I n j n s ( E ) , f f ^ , then, f I n j n s ( E ) : f ^ ϕ

Proposition 8

Let h I n j n s ( E ) , f , g I n j n s ( E ) :

f , g are Co-injectives h f and h g are Co-injectives.

Proof:

Let h I n j n s ( E ) , and f , g I n j n s ( E ) such as ƒ and g are Co-injective. I f I g , additionally h ( I f I g ) = I h f I h g (h is injective).

Let x , y E , h f ( x ) = h g ( y ) f ( x ) = g ( y ) x = y (because h is injective and f , g are Co-injectives).

Therefore h f and h g are Co-injectives.

Note 11

For all f , g I n j n s ( E ) , so that f , g are Co-injectives, so: ˆ

· f 2 and f g are Co-injectives

· z I f I g , ! x E , so that, z = f ( x ) = g ( x )

· f 1 ( I g ) = g 1 ( I f )

· If, I f = I g , then f = g ˆ

· Let h I n j n s ( E ) , if f ( I h ) g ( I h ) , then f h and g h are Co-injectives.

Proposition 9

f , g I n j n s ( E ) , if I f I g , then f , g are not Co-injective.

Proof

f , g I n j n s ( E ) , suppose that I f I g , then we have I g = I f ( I g \ I f ) . If f , g are Co-injectives, then f 1 ( I g ) = g 1 ( I f ) = E , which is contradictory because:

E = g 1 ( I f ) g 1 ( I g \ I f ) , and g 1 ( I g \ I f ) , so g 1 ( I f ) E .

Proposition 10

Let f , g I n j n s ( E ) , so that ƒ and g are Co-injectives, h I n j n s ( E ) , if g and h are Co-injectives and I f I h = I f I g then ƒ and h are Co-injectives.

Proof

I f I h , let x , y E , so that f ( x ) = h ( y ) . We have f ( x ) = h ( y ) I f I h = I f I g , then f ( x ) = g ( x ) = h ( y ) (because f , g are Co-injectives), and since g and h are Co-injectives then x = y . So x , y E , f ( x ) = h ( y ) x = y . Therefore f , h are Co-injectives.

Acknowledgements

I would like to thank my dear friends, especially Chafik Bouazzaoui for us discussing the Cantor-Bernstein theorem and Mai Mohammed mainly who for his help with translating this document.

Cite this paper: Harrafa, C. (2020) Partitioning of Any Infinite Set with the Aid of Non-Surjective Injective Maps and the Study of a Remarkable Semigroup. Open Journal of Discrete Mathematics, 10, 74-88. doi: 10.4236/ojdm.2020.103008.
References

[1]   Berhuy, G. (2002) Algébre: le grand combat. Clavage et Mounet, Montrouge.

[2]   Dehornoy, P. (2017) La théorie des ensembles. Clavage et Mounet, Montrouge.

[3]   Gourdon, X. (1994) Les maths en tête Algèbre. Ellipses, Paris.

[4]   Jacobson, N. (2009) Basic Algebra I. Dover Publication Inc., New York.

[5]   Guégand, T.D.J. (1999) Algèbre en classe préparatoires MP*. Ellipses, Paris.

 
 
Top