Partitioning of Any Infinite Set with the Aid of Non-Surjective Injective Maps and the Study of a Remarkable Semigroup

Charif  Harrafa

doi:10.4236/ojdm.2020.103008

Charif Harrafa

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.

Keywords: Partitioning, Non-Surjective, Injective, Infinite Set, Fixed Points, Lattice Structure

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 \circ g})$ forms a partition of F.

· $(B, g (A), I_{g \circ f})$ forms a partition of E.

where,

$A = {y \in F | \forall x \in E, f (x) \neq y}$ and $B = {x \in E | \forall y \in F, g (y) \neq 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 \in F | \forall x \in E, f (x) \neq y}$ and $B = {x \in E | \forall y \in F, g (y) \neq x}$ are non-empty.

Also, obviously $E = B \cup I_{g}$ such as $B \cap I_{g} = \emptyset$ as follows from the deﬁnition of $I_{g}$ .

For any such map ƒ from E to F:

$I_{f} = f (E) = f (B \cup I_{g}) = f (B) \cup f (I_{g}) = f (B) \cup I_{f \circ g}$

So $F = A \cup f (B) \cup I_{f \circ g}$

Since ƒ is an injective map then:

$f (B \cap I_{g}) = f (B) \cap I_{f \circ g} = f (\emptyset) = \emptyset$

Therefore, $(A, f (B), I_{f \circ g})$ forms a partition of F.

In analogy to the map g from F to E, $(B, g (A), I_{g \circ f})$ forms a partition of E.

Note 1

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

· $E = B \cup g (A) \cup (g \circ f) (B) \cup I_{g \circ f \circ g}$

· $F = A \cup f (B) \cup (f \circ g) (A) \cup I_{f \circ g \circ f}$

In case that ƒ and g are (two) (2) diﬀerent non-surjective injective maps from an inﬁnite set E to itself, we can compose either by ƒ or by g, or by both indeﬁnitely. Thus several partition classes of E can obtained, for example after a second (2^nd) iteration

· $E = A_{f} \cup f (A_{f}) \cup f^{2} (A_{f}) \cup I_{f^{3}}$

· $E = A_{g} \cup g (A_{g}) \cup g^{2} (A_{g}) \cup I_{g^{3}}$

· $E = A_{f} \cup f (A_{g}) \cup (f \circ g) (A_{f}) \cup I_{f \circ g \circ f}$

· $E = A_{g} \cup g (A_{f}) \cup (g \circ f) (A_{g}) \cup I_{g \circ f \circ g}$

· $E = A_{f} \cup f (A_{g}) \cup (f \circ g) (A_{g}) \cup I_{f \circ g^{2}}$

· $E = A_{g} \cup g (A_{f}) \cup (g \circ f) (A_{f}) \cup I_{g \circ f^{2}}$

where,

$A_{f} = {y \in F | \forall x \in E, f (x) \neq y}$ and $A_{g} = {x \in E | \forall y \in F, g (y) \neq 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 deﬁned by:

· $\forall n \in ℕ, f (n) = 2 n$

· $\forall n \in ℕ, 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 \circ g) (A_{f}) = 8 ℕ + 6$

· $(g \circ f) (A_{g}) = 8 ℕ + 1$

· $(f \circ g \circ f) (ℕ) = 8 ℕ + 2$

· $(g \circ f \circ g) (ℕ) = 8 ℕ + 5$

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

$ℕ = (2 ℕ + 1) \cup (4 ℕ) \cup (8 ℕ + 6) \cup (8 ℕ + 2)$

$ℕ = (2 ℕ) \cup (4 ℕ + 3) \cup (8 ℕ + 1) \cup (8 ℕ + 5)$

2.1. Remarkable Partition

Proposition 2

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

$A_{f} = {y \in E | \forall x \in E, f (x) \neq y}$

Then,

$\forall n \in ℕ, E = [\cup_{i = 0}^{i = n} f^{i} (A_{f})] \cup I_{f^{n + 1}}$

where, $f^{i} (A_{f}) = \underset{i times}{\underset{︸}{f \circ f \circ \dots \circ f (A_{f})}}$

Proof

By induction:

For $n = 0$ , we have, by deﬁnition $E = A_{f} \cup I_{f}$ , and for $n = 1$ the proposition 1 states that, if $E = F$ and $f = g$ then, $E = A_{f} \cup f (A_{f}) \cup I_{f^{2}}$ Suppose that the said property is true for n. Then, by composing by ƒ, we get:

$I_{f} = f (E) = [\cup_{i = 0}^{i = n} f^{i + 1} (A_{f})] \cup I_{f^{n + 2}} = [\cup_{i = 1}^{i = n + 1} f^{i} (A_{f})] \cup I_{f^{n + 2}}$

Then,

$E = A_{f} \cup [\cup_{i = 1}^{i = n + 1} f^{i} (A_{f})] \cup I_{f^{n + 2}} = [\cup_{i = 0}^{i = n + 1} f^{i} (A_{f})] \cup I_{f^{n + 2}}$

Therefore,

$\forall n \in ℕ, E = [\cup_{i = 0}^{i = n} f^{i} (A_{f})] \cup I_{f^{n + 1}}$

Note 2

For all non-surjective injective maps ƒ from an inﬁnite set E to itself,

$\forall n \in ℕ, A_{f^{n + 1}} = \cup_{i = 0}^{i = n} f^{i} ( A f )$

Deﬁnition 1

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

· $x \in E$ is a ﬁxed point of ƒ if, $f (x) = x$ .

· $A \subset E$ is a ﬁxed point set of ƒ if, $f (A) = A$ .

Proposition 3

For all non-surjective injective maps f from an inﬁnite set E to itself, $\forall n \in ℕ$ , $f^{n} (A_{f})$ contains no ﬁxed points of ƒ.

Proof

By induction:

For $n = 0$ , let $x \in A_{f}$ , and by deﬁnition $\forall y \in E$ , $f (y) \neq x$ , particularly for $y = x$ so $f (x) \neq x$ then $A_{f}$ contains no ﬁxed points of f. Suppose that the aforementioned property is true for n, let $x \in f^{n + 1} (A_{f}) = f (f^{n} (A_{f}))$ , then $\exists y \in f^{n} (A_{f})$ such that $x = f (y)$ , we have $f (y) \neq y$ (by inductive hypothesis), since ƒ is injective then $f (f (y)) \neq f (y)$ so $f (x) \neq x$ , then $\forall x \in f^{n + 1} (A_{f})$ , $f (x) \neq x$ . Therefore, $\forall n \in ℕ$ , $f^{n} (A_{f})$ contains no ﬁxed points of ƒ.

Note 3

Let E be an inﬁnite set, and ƒ be a non-surjective injective map from E to itself, we deﬁne the following:

$F i x_{f} = {x \in E | f (x) = x}$ and $S t_{f} (E) = {A \subset E | f (A) = A}$

· $\forall n \in ℕ, F i x_{f} \cap f^{n} (A_{f}) = \emptyset$

· $\forall n \in ℕ^{*}, F i x_{f} \subseteq F i x_{f^{n}}$

· $\forall n \in ℕ^{*}, F i x_{f^{n}} \subseteq F i x_{f^{2 n}}$

· $\forall p \in ℕ, \forall n \in ℕ^{*}, f^{p} (F i x_{f^{n}}) = F i x_{f^{n}}$

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

$F i x_{f} \in S t_{f} ( E )$

Proposition 4

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

$\forall A \in S t_{f} (E), \forall n \in ℕ, f^{n} (A_{f}) \cap A = \emptyset$

Proof

Let $A \in S t_{f} (E)$ , by induction, For $n = 0$ , we have, by deﬁnition $A_{f} \cap I_{f} = \emptyset$ then $A_{f} \cap A = A_{f} \cap f (A) = \emptyset$ Suppose that the said property is true for $n \in ℕ$ , let $x \in f^{n + 1} (A_{f}) \cap A$ , then, $\exists y \in f^{n} (A_{f}), x = f (y)$ and $\exists y_{0} \in A, x = f (y_{0})$ . Since ƒ is injective so $y = y_{0} \in f^{n} (A_{f}) \cap A$ , which contradicts the inductive hypothesis. Then,

$f^{n + 1} (A_{f}) \cap A = \emptyset$ .

Therefore, $\forall A \in S t_{f} (E), \forall n \in ℕ, f^{n} (A_{f}) \cap A = \emptyset$

Lemma 1 (Generalization)

$\forall p \in ℕ^{*}, \forall A \in S t_{f^{p}} (E), \forall n \in ℕ, f^{n} (A_{f}) \cap A = \emptyset$

Proof

By complete (strong) induction,

Let $p \in ℕ^{*}$ , and $A \in S t_{f^{p}} (E) = {A \subset E | f^{p} (A) = A}$ : For $n = 0$ , we have, by deﬁnition $A_{f} \cap I_{f} = \emptyset$ , since $\exists p \in ℕ^{*}, I_{f^{p}} \subseteq I_{f}$ , then: $A_{f} \cap A = A_{f} \cap f^{p} (A) = \emptyset$

Suppose that the said property is true for all $i \in {1, \dots, n}$ , let $x \in f^{n + 1} (A_{f}) \cap A$ , then, $\exists y \in A_{f}, x = f^{n + 1} (y)$ and $\exists y_{0} \in 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 \in {1, \dots, n}$

· $y = f^{p - n - 1} (y_{0})$ , if $p > n + 1$ , which contradicts $A_{f} \cap I_{f^{p - n - 1}} = \emptyset$

· $y = y_{0}$ , if $n + 1 = p$ , which contradicts $A_{f} \cap A = \emptyset$

Then,

$f^{n + 1} (A_{f}) \cap A = \emptyset$ ,

Therefore,

$\forall p \in ℕ^{*}, \forall A \in S t_{f^{p}} (E), \forall n \in ℕ, f^{n} (A_{f}) \cap A = \emptyset$

QED

For all $n \in ℕ$ , and for all ƒ non-surjective injective maps from an inﬁnite set E to itself, we define the following:

· $S_{f^{n}} (E) = {A \subset E | \exists p \in {1, \dots, n + 1}, f^{p} (A) = A}$

· $S_{f^{\infty}} (E) = {A \subset E | \exists p \in ℕ^{*}, f^{p} (A) = A}$

· $S_{f^{n}} = {x \in A | A \in S_{f^{n}} (E)}$

· $S_{f^{\infty}} = {x \in A | A \in S_{f^{\infty}} (E)}$

Theorem 1

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

$E = [\underset{n \in ℕ}{\cup} f^{n} (A_{f})] \cup S_{f^{\infty}}$

Proof

Note that for $n = 0$ , $S_{f^{0}} (E) = S t_{f} (E)$ , The sequence of subsets of E, ${(S_{f^{n}})}_{n \in ℕ}$ is increasing by inclusion, so it is convergent, the limit is: $\cup_{n \in ℕ} S_{f^{n}} = S_{f^{\infty}}$

We have already established that,

$\forall n \in ℕ, E = [\cup_{i = 0}^{i = n} f^{i} (A_{f})] \cup I_{f^{n + 1}}$

Otherly, according to the Lemma 1, $\forall n \in ℕ, E = [\cup_{i = 0}^{i = n} f^{i} (A_{f})] \cap S_{f^{n}} = \emptyset$

Let’s define the following, $\forall n \in ℕ, \hat{I_{f^{n + 1}}} = I_{f^{n + 1}} \ S_{f^{n}}$ the sequence of subsets of ${(\hat{I_{f^{n + 1}}})}_{n \in ℕ}$ is decreasing by inclusion then, it is convergent [1], the limit is:

$\underset{n \in ℕ}{\cap} \hat{I_{f^{n + 1}}} = \emptyset$

Because, let $x \in \cap_{n \in ℕ} \hat{I_{f^{n + 1}}}$ , then:

$x \in \underset{n \in ℕ}{\cap} I_{f^{n + 1}} \ S_{f^{n}} \Leftrightarrow \forall n \in ℕ, x \in I_{f^{n + 1}} \ S_{f^{n}} \Leftrightarrow \forall n \in ℕ, x \in I_{f^{n + 1}} and x \in \bar{S_{f^{n}}}$

$\Leftrightarrow \forall n \in ℕ, x \in I_{f^{n + 1}} and \forall n \in ℕ, x \in \bar{S_{f^{n}}} \Leftrightarrow x \in \underset{n \in ℕ}{\cap} I_{f^{n + 1}} and x \in \underset{n \in ℕ}{\cap} \bar{S_{f^{n}}}$

$\Leftrightarrow x \in \underset{n \in ℕ}{\cap} I_{f^{n + 1}} and x \in \bar{\underset{n \in ℕ}{\cup} S_{f^{n}}} \Leftrightarrow x \in \underset{n \in ℕ}{\cap} I_{f^{n + 1}} and x \in \bar{S_{f^{\infty}}}$

$\Leftrightarrow x \in [\underset{n \in ℕ}{\cap} I_{f^{n + 1}}] \ S_{f^{\infty}}$

On the other hand, the sequence of subsets of E, ${(I_{f^{n + 1}})}_{n \in ℕ}$ is strictly decreasing by inclusion, then it is convergent and the limit is $H = \cap_{n \in ℕ} I_{f^{n + 1}}$ , and since ƒ is injective, so $f (H) = H$ then ƒ is bijective from H to itself, and $H \in S t_{f} (E) \subset S_{f^{\infty}} (E)$ .

$\forall n \in ℕ, E = [\cup_{i = 0}^{i = n} f^{i} (A_{f})] \cup \hat{I_{f^{n + 1}}} \cup S_{f^{n}}$

Therefore,

$E = [\underset{n \in ℕ}{\cup} f^{n} (A_{f})] \cup S_{f^{\infty}}$

N.B. If $S_{f^{\infty}} = \emptyset$ , then we get:

$E = \underset{n \in ℕ}{\cup} 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, deﬁned by:

$f (x) = {\begin{cases} x + 1, if x \geq 0 \\ x, if x < 0 \end{cases}$

Therefore, ƒ is injective non-surjective from $ℝ$ to itself, because ƒ is injective and $A_{f} = [0, 1 [$ .

where,

$\forall n \in ℕ^{*}, f^{n} (x) = {\begin{cases} x + n, if x \geq 0 \\ x, if x < 0 \end{cases}$

We have, $f (A_{f}) = [f (0), f (1) [= [1, 2 [\subset ℝ_{+}$ since ƒ is increasing Therefore,

$\forall n \in ℕ^{*}, f^{n} (A_{f}) = [n, n + 1 [$

· $\forall n \in ℕ, S_{f^{n}} = S_{f^{\infty}} = ℝ_{-}^{*}$

· $\forall n \in ℕ, S_{f^{n}} (E) = S_{f^{\infty}} (E) = P (ℝ_{-}^{*})$

According to the theorem 1, we can write:

$ℝ = ℝ_{-}^{*} \cup [\underset{n \in ℕ}{\cup} [n, n + 1 []$

Example 3

Remark

If h is an aﬃne map from $ℝ$ to $ℝ$ , so that $h (x) = a x + b / a, b \in ℝ$ and $a \neq 0$ , then:

$\forall n \in ℕ^{*}, \forall x \in ℝ, h^{n} (x) = a^{n} x + b (1 + a + \dots + a^{n - 1})$

If $a \neq 1$ , then:

$\forall n \in ℕ^{*}, \forall x \in ℝ, h^{n} (x) = a^{n} x + b (\frac{1 - a^{n}}{1 - a})$

Let ƒ be a map deﬁned from $E = [0, 4]$ to itself by:

$\forall x \in [0, 4], f (x) = {\begin{cases} - x + 1, if x \in [0, 1] \\ x + 1, if x \in] 1, 2] \\ \frac{1}{2} x + 2, if x \in [2, 4] \end{cases}$

ƒ 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] \subset E$ , fulﬁlls the condition $f (A) = A$

· We have $A_{f} =] 1, 2]$ , $f (A_{f}) = f (] 1, 2]) =] 2, 3] \subset [2, 4]$ , $f (] 2, 3]) =] 3, \frac{7}{2}]$ , $\dots$

· $S_{f^{\infty}} = {4} \cup [0, 1]$

The restriction of ƒ to $[2, 4]$ is an aﬃne function such as $a = \frac{1}{2}$ , and $b = 2$ , then:

$\forall n \in ℕ^{*}, f^{n} (x) = \frac{1}{2^{n}} x + 2 (1 + \frac{1}{2} + \dots + \frac{1}{2^{n - 1}})$

We have: $f^{n} (2) = 4 - \frac{1}{2^{n - 1}}$ , and $f^{n} (3) = 4 - \frac{1}{2^{n}}$ ,

According to Theorem 1:

$[0, 4] = {] 1, 2] \cup_{n \in ℕ}] 4 - \frac{1}{2^{n - 1}}, 4 - \frac{1}{2^{n}}]} \cup {4} \cup [0, 1]$

Example 4

Let ƒ be a map deﬁned from $E = [0, 3]$ to itself by:

$\forall x \in [0, 3], f (x) = {\begin{cases} x + 2, if x \in [0, 1] \\ \frac{1}{2} x + 1, if x \in] 1, 2 [ \\ x - 2, if x \in [2, 3] \end{cases}$

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

· $A_{f} =] 1, \frac{3}{2}]$

· $F i x_{f} = \emptyset$

· The set $A = [0, 1] \subset E$ , fulﬁlls the condition $f (A) \neq A$ , and $f^{2} (A) = A$

· The set $B = [2, 3] \subset E$ , fulﬁlls the condition $f (B) \neq B$ , and $f^{2} (B) = B$

· $S_{f^{\infty}} = [0, 1] \cup [2, 3]$

We have,

· $\forall x \in] 1, 2 [, \forall n \in ℕ^{*}, f^{n} (x) = \frac{1}{2^{n}} x + 2 (1 - \frac{1}{2^{n}})$

· $\lim_{x \to 1^{-}} f^{n} (x) = 2 - \frac{1}{2^{n}}$ and $f^{n} (\frac{3}{2}) = 2 - \frac{1}{2^{n + 1}}$

Therefore, according to Theorem 1:

$[0, 3] = {\cup_{n \in ℕ}] 2 - \frac{1}{2^{n}}, 2 - \frac{1}{2^{n + 1}}]} \cup [0, 1] \cup [2, 3]$

Corollary 1

Let $f, g$ be non-surjective injective maps from an inﬁnite set E to itself such as $S_{f^{\infty}} = \bar{S_{g^{\infty}}}$ , then:

$E = \underset{n \in ℕ}{\cup} B_{n}$

where, $\forall n \in ℕ, B_{n} = f^{n} (A_{f}) \cup g^{n} ( A g )$

Therefore, ${(B_{n})}_{n \in ℕ}$ forms a partition of E.

Deﬁnition 2

· Let E be an inﬁnite 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 | \leq | F |$ ( $| E |$ is the cardinal of E).

Properties

1) $(I n j n s (E), \circ)$ is a semigroup, because the composite of 2 (two) injective maps ƒ and g is injective and $I_{f \circ g} \subset I_{f}$ , so $\forall f, g \in I n j n s (E)$ , $f \circ g \in I n j n s (E)$ .

2) $\forall f, g \in I n j n s (E)$ , $A_{f \circ g} = A_{f} \cup f (A_{g})$ , $(A_{f}, f (A_{g}), I_{f \circ g})$ is, indeed, a partition of E and $E = A_{f \circ g} \cup I_{f \circ g}$ , because $f \circ g \in 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 \in I n j n s (E)$ .

4)Let $f \in I n j n s (E)$ , and assuming that ƒ is a map from E to itself such as: $\tilde{f} (x) = {\begin{cases} x, if x \in A_{f} \\ f (x), if x \in I_{f} \end{cases}$

5) We have, $\forall f \in I n j n s (E), \tilde{f} \in I n j n s (E)$ knowing that $I_{\tilde{f}} = A_{f} \cup I_{f^{2}}$ and $A_{\tilde{f}} = f ( A f )$

6) Let $f \in I n j n s (E)$ , we have, $\tilde{f} (A_{\tilde{f}}) = \tilde{f} (f (A_{f})) = f^{2} (A_{f})$ , and

$I_{{\tilde{f}}^{2}} = \tilde{f} (I_{\tilde{f}}) = \tilde{f} (A_{f} \cup I_{f^{2}}) = \tilde{f} (A_{f}) \cup \tilde{f} (I_{f^{2}}) = A_{f} \cup I_{f^{3}}$

Then,

$E = A_{\tilde{f}} \cup \tilde{f} (A_{\tilde{f}}) \cup I_{{\tilde{f}}^{2}} = A_{f} \cup f (A_{f}) \cup f^{2} (A_{f}) \cup I_{f^{3}}$

Therefore, $\tilde{f}$ allow us to reduce order of iteration.

7) $\forall f \in I n j n s (E)$ ,

· $A_{\tilde{f} \circ f} = A_{\tilde{f}} \cup \tilde{f} (A_{f}) = A_{f} \cup f (A_{f}) = A_{f^{2}}$ , then $I_{\tilde{f} \circ f} = I_{f^{2}}$

· $A_{f \circ \tilde{f}} = A_{f} \cup f (A_{\tilde{f}}) = A_{f} \cup f^{2} (A_{f})$ ,then, $I_{f \circ \tilde{f}} = f (A_{f}) \cup I_{f^{3}}$

· $A_{\tilde{\tilde{f}}} = \tilde{f} (A_{\tilde{f}}) = f^{2} (A_{f})$ , then $I_{\tilde{\tilde{f}}} = A_{f} \cup f (A_{f}) \cup I_{f^{3}}$

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

$f \circ g \in I n j n s (F)$ and $g \circ f \in I n j n s ( E )$

2.2. Equivalence Relations

Example 5

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

$f R g \Leftrightarrow A_{f} = A_{f} \Leftrightarrow I_{f} = I_{g}$

R is, indeed, an equivalence relation, because:

· R is reﬂexive, $f R f, \forall f \in I n j n s ( E )$

· R is symmetric, $f R g \Leftrightarrow A_{f} = A_{g} \Leftrightarrow g R f, \forall f, g \in I n j n s ( E )$

· R is transitive, $\forall f, g$ and $h \in I n j n s (E)$ , $f R g$ and $g R h \Leftrightarrow A_{f} = A_{g}$ and $A_{g} = A_{h} \Leftrightarrow A_{f} = A_{h} \Leftrightarrow f R h$

Example 6

Let $f, g \in I n j n s (E)$ , we deﬁne the binary relation R on $I n j n s (E)$ , by:

$\forall f, g \in I n j n s (E) : f R g \Leftrightarrow \forall n \in ℕ^{*}, I_{f^{n}} = I_{g^{n}}$

R is, indeed, an equivalence relation, because:

· R is reﬂexive, $f R f, \forall f \in I n j n s ( E )$

· R is symmetric, $f R g \Leftrightarrow \forall n \in ℕ^{*}, I_{f^{n}} = I_{g^{n}} \Leftrightarrow g R f, \forall f, g \in I n j n s ( E )$

· R is transitive, $f, g$ and $h \in I n j n s (E)$ , $f R g$ and $g R h \Leftrightarrow \forall n \in ℕ^{*}, I_{f^{n}} = I_{g^{n}}$ and $\forall n \in ℕ^{*}, I_{g^{n}} = I_{h^{n}} \Leftrightarrow \forall n \in ℕ^{*}, I_{f^{n}} = I_{h^{n}} \Leftrightarrow f R h$

Example 7

$\forall f, g \in I n j n s (E), f R g \Leftrightarrow f (A_{f}) = g ( A g )$

Example 8

$\forall f, g \in I n j n s (E), f R g \Leftrightarrow S_{f^{\infty}} = S_{g^{\infty}} \Leftrightarrow \underset{n \in ℕ}{\cup} f^{n} (A_{f}) = \underset{n \in ℕ}{\cup} g^{n} ( A g )$

$\underset{n \in ℕ}{\cup} f^{n} (A_{f})$ : as being the ƒ-semicoverage of a set E.

3. Part II

Let E be an infinite set, $f \in I n j n s (E)$ , and $\bar{f} = {g \in I n j n s (E) | I_{g} \cap I_{f} \neq \emptyset}$

We get the following:

· $\forall f \in I n j n s (E), \forall n \in ℕ^{*}, f^{n} \in \bar{f}$

· $\forall f, g \in I n j n s (E) : I_{f} \subset I_{g} \Rightarrow \bar{f} \subset \bar{g}$

Let $h \in \bar{f}$ i.e. $I_{f} \cap I_{h} \neq \emptyset$ let $x \in I_{h} \cap I_{f}$ , so $x \in I_{h}$ and $x \in I_{f} \subset I_{g}$ , so $x \in I_{h}$ and $x \in I_{g}$ , so $x \in I_{h} \cap I_{g}$ so $I_{h} \cap I_{g} \neq \emptyset$ , then $h \in \bar{g}$ therefore $\bar{f} \subset \bar{g}$

Theorem 2

Let E be an inﬁnite 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_{ψ} \cap I_{ϕ} \neq \emptyset$

Proof

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

QED

Note 4

· $\exists ψ \in I n j n s (E)$ , so that: $\forall φ \in I n j n s (E)$ , $ψ^{- 1} (I_{φ}) \neq \emptyset$

· If $ψ$ applies to the former theorem then: $\bar{ψ} = I n j n s (E)$ .

Proposition 5

$\forall f \in I n j n s (E)$ , $\exists g \in I n j n s (E) \ {f}$ , so that $A_{f} \cap A_{g} \neq \emptyset$

Proof

By contradiction, assuming that exists a map $f \in I n j n s (E)$ , so that $\forall g \in I n j n s (E) \ {f}$ , $A_{f} \cap A_{g} = \emptyset$ , then $\forall g \in I n j n s (E) \ {f}$ , $I_{f} \cup I_{g} = E$ .

Let $g = f^{2}$ , so $I_{f} \cup I_{g} = I_{f} ⊊ E$ because $f \in I n j n s (E)$ which is contradictory.

Proposition 6

$\forall f \in I n j n s (E)$ , $\exists g \in I n j n s (E) \ {f}$ , such as $A_{f} \cap I_{g} \neq \emptyset$

Proof

By contradiction, assuming that exists a map $f \in I n j n s (E)$ , so that, $\forall g \in I n j n s (E) \ {f}$ , $A_{f} \cap I_{g} = \emptyset$ then $\forall g \in I n j n s (E) \ {f}, I_{f} \cup A_{g} = E$ . On the other hand, if $g = \tilde{f}, I_{f} \cup A_{g} = E$ , additionally $A_{g} = f (A_{f}) \subset I_{f}$ so $I_{f} \cup A_{g} = I_{f} = E$ which is contradictory.

Note 5

We can deﬁne another composition law T for $I n j n s (E)$ so that,

$\forall f, g \in I n j n s (E), (f T g) (x) = {\begin{cases} g (x), if x \in f^{- 1} (I_{g}) \\ f (x), if x \in f^{- 1} ( A g ) \end{cases}$

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

· $\forall f, g \in I n j n s (E)$ , if $I_{f} \cap I_{g} = \emptyset$ , then $f T g = f$ .

· $\forall f, g \in I n j n s (E)$ , if $I_{f} \subseteq I_{g}$ , then $f T g = g$ .

· $\forall f \in I n j n s (E)$ , $f T \tilde{f} = f$ and $\tilde{f} T f = \tilde{f}$ .

· Generally, $\forall f, g \in I n j n s (E)$ , $f T g \neq g T f$ .

4. Part III

4.1. Study of the Quotient Set

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

$f R g \Leftrightarrow A_{f}$ and $A_{g}$ have the same cardinal

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

We deﬁne $C l (f) = {g \in I n j n s (E) | | A_{g} | = | A_{f} |}$ the equivalence class of a map ƒ.

Note 6

· Let $f \in I n j n s (E)$ , as $A_{\tilde{f}} = f (A_{f})$ so $A_{f}$ and $A_{\tilde{f}}$ have the same cardinal, because ƒ is injective then $\tilde{f} \in C l (f)$ , therefore,

$\forall f \in I n j n s (E), \tilde{f} \in C l ( f )$

· Let $f, g \in I n j n s (E)$ , assuming that the cardinals of $A_{f}$ and $A_{f}$ are ﬁnite, and thus, $| A_{f \circ g} | = | A_{f} \cup f (A_{g}) | = | A_{f} | + | A_{g} | - | A_{f} \cap f (A_{g}) |$ , and since $A_{f} \cap f (A_{g}) = \emptyset$ , then: $| A_{f \circ g} | = | A_{f} \cup 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 \circ g} = A_{f} \cup f (A_{g})$ , with $A_{f} \cap f (A_{g}) = \emptyset$ ,then we can extend the sum of the cardinals even for infinite sets, such as:

$| A_{f \circ g} | = | A_{f} \cup f (A_{g}) | = | A_{f} | + | A_{g} | = \sup {| A_{f} |, | A_{g} |}$

· For all maps $f, g, h$ and $t \in 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 \circ h} | = \sup {| A_{f} |, | A_{g} |} = \sup {| A_{g} |, | A_{t} |} = | A_{g \circ t} |$ , therefore,

$f \circ g R h \circ 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.

· $\forall C l (f)$ and $C l (g) \in I n j n s (E) / R$ : $C l (f) * C l (g) = C l (f \circ g)$

4.2. Partial Order

Let $C l (f), C l (g) \in I n j n s (E) / R$ , deﬁne a binary relation on $I n j n s (E) / R$ by:

$C l (f) \leq C l (g) \Leftrightarrow | A_{f} | \leq | A_{g} |$

· $\forall C l (f) \in I n j n s (E) / R, C l (f) \leq C l ( f )$

So $\leq$ is reﬂexive.

· $\forall C l (f), C l (g) \in I n j n s (E) \ R$ , $C l (f) \leq C l (g)$ and $C l (g) \leq C l (f)$ $\Leftrightarrow$ $| A_{f} | \leq | A_{g} |$ and $| A_{g} | \leq | A_{f} |$ $\Leftrightarrow$ $| A_{f} | = | A_{g} |$ so $C l (f) = C l ( g )$

So $\leq$ is asymmetric.

· $\forall C l (f), C l (g)$ and $C l (h) \in I n j n s (E) / R$ : $C l (f) \leq C l (g)$ and $C l (g) \leq C l (h)$ $\Leftrightarrow$ $| A_{f} | \leq | A_{g} |$ and $| A_{g} | \leq | A_{h} |$ $\Rightarrow$ $| A_{f} | \leq | A_{h} |$ $\Rightarrow$ $C l (f) \leq C l ( h )$

So $\leq$ is transitive.

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

Note 7

· Since $\forall C l (f), C l (g) \in I n j n s (E) / R$ , $C l (f) \leq C l (g)$ or $C l (g) \leq C l (f)$ then $\leq$ 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:

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

If $C l (f) \leq C l (g)$ then $C l (f) * C l (h) = C l (f \circ h) \leq C l (g \circ h) = C l (g) * C l (h)$ and $C l (h) * C l (f) = C l (h \circ f) \leq C l (h \circ 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 inﬁnite countable set, the map $φ$ deﬁned by:

$φ : I n j n s (E) \to ℕ^{*} \cup {ℵ 0} = M, \forall f \in I n j n s (E), φ (f) = | A_{f} |$ ,

where, $ℵ 0$ represents the cardinal of $ℕ$ .

Considering the convention: $\forall n \in ℕ^{*}$ , $n + ℵ 0 = ℵ 0$ , $φ$ is a morphism of semigroups of $(I n j n s (E), \circ)$ on $(M, +)$ .

$\forall f, g \in I n j n s (E), φ (f \circ g) = | A_{f \circ g} | = | A_{f} | + | A_{g} | = φ (f) + φ ( g )$

Complement

Let $f, g \in I n j n s (E)$ so that $| A_{f} | < | A_{g} |$ , with the assumption that $A_{f}$ and $A_{g}$ are considered ﬁnite, $I_{f}$ and $I_{g}$ are equipotential because, the map $ψ$ defined from $I_{f}$ to $I_{g}$ by:

$\forall x \in I_{f}$ , $ψ (x) = (g \circ f^{- 1}) (x)$ is bijective, where $f^{- 1}$ is deﬁned from $I_{f}$ to E, and for all $x \in I_{f}$ , we associated its inputs by ƒ, we have:

· $\forall x, y \in I_{f}$ , $ψ (x) = ψ (y)$ $\Rightarrow$ $(g \circ f^{- 1}) (x) = (g \circ f^{- 1}) (y)$ $\Rightarrow$ $g (f^{- 1} (x)) = g (f^{- 1} (y))$ $\Rightarrow$ $f^{- 1} (x) = f^{- 1} (y) \Rightarrow x = y$ (because both g and $f^{- 1}$ are injectives). Therefore $ψ$ is injective.

· On the other hand $ψ (I_{f}) = (g \circ f^{- 1}) (I_{f}) = g (f^{- 1} (I_{f})) = g (E) = I_{g}$ so $ψ$ is surjective.

Let $φ \in I n j n s (A_{f}, A_{g})$ so that the map $θ$ is defined by:

$θ (x) = {\begin{cases} φ (x), if x \in A_{f} \\ ψ (x), if x \in I_{f} \end{cases}$

Belong to $I n j n s (E)$ and $A_{θ} = A_{φ}$ .

Note 8

· If $g = f^{2}$ so $\forall x \in I_{f}, ψ (x) = f (x)$ so if $φ = f / A_{f}$ then we have, $θ = f$ , and if $φ = I_{d} / A_{f}$ so $θ = \tilde{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 \in I n j n s (E)$ and $σ \in σ (E)$ , $f \circ σ \in I n j n s (E)$ , because, since ƒ and $σ$ are injective then $f \circ σ$ is injective and $\forall σ \in σ (E)$ , $(f \circ σ) (E) = f (σ (E)) = f (E) = I_{f} ⊊ E$ then $f \circ σ$ is non-surjective.

where $\forall σ \in σ (E), I_{f \circ σ} = I_{f}$ then $A_{f \circ σ} = A_{f}$ .

We have,

· $\forall σ_{1}, σ_{2} \in σ (E)$ and $f \in I n j n s (E)$ : $(f \circ σ_{1}) \circ σ_{2} = f \circ (σ_{1} \circ σ_{2})$

· $\forall f \in I n j n s (E)$ , $f \circ I_{d} = f$

Let $θ : σ (E) \times I n j n s (E) \to I n j n s ( E )$

so that $\forall σ \in σ (E)$ , $\forall f \in I n j n s (E)$ , $θ (σ, f) = f \circ σ$

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

Note 9

The relation R deﬁned on $I n j n s (E)$ by: $f R g \Leftrightarrow \exists σ \in σ (E)$ such as $g = f \circ σ$ is an equivalence relation, that is called Intransitivity relation [5].

Proposition 7

Let be, $g \in I n j n s (E)$ : $\exists σ \in σ (E)$ so that $g = f \circ σ \Leftrightarrow I_{f} = I_{g}$ .

Proof

$\Rightarrow$ ) If there exists $σ \in σ (E)$ so that $g = f \circ σ \Rightarrow I_{g} = I_{f \circ σ} = I_{f}$ .

$\Leftarrow$ ) If $I_{f} = I_{g}$ , then the map $σ : E \to E$ , so that $x \mapsto σ (x) = f^{- 1} (g (x))$ is bijective, because:

· $σ (E) = f^{- 1} (g (E)) = E$ so $σ$ is surjective.

· $\forall x, y \in E$ : $σ (x) = σ (y)$ $\Rightarrow$ $f^{- 1} (g (x)) = f^{- 1} (g (y))$ $\Rightarrow$ $g (x) = g (y)$ $\Rightarrow$ $x = y$ so $σ$ is injective.

· $\forall x \in E$ , $f \circ σ (x) = f (σ (x)) = g ( x )$

Note 10

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

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

6. Part V

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

Deﬁnition 3

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

$I_{f} \cap I_{g} \neq \emptyset$ and $\forall x, y \in E, f (x) = g (y) \Rightarrow x = y$

Let $\hat{f} = {g \in I n j n s (E) | g is Co-injective with f}$

We have $\hat{f} \neq \emptyset$ because $\forall f \in I n j n s (E)$ , $I_{f} \cap I_{f} \neq \emptyset$ and $\forall x, y \in E$ , $f (x) = f (y) \Rightarrow x = y$ so ƒ is Co-injective with itself.

Therefore $\forall f \in I n j n s (E)$ , $f \in \hat{f}$ , then, $\forall f \in I n j n s (E)$ : $\hat{f} \neq ϕ$

Proposition 8

Let $h \in I n j n s (E)$ , $\forall f, g \in I n j n s (E)$ :

$f, g$ are Co-injectives $\Rightarrow$ $h \circ f$ and $h \circ g$ are Co-injectives.

Proof:

Let $h \in I n j n s (E)$ , and $f, g \in I n j n s (E)$ such as ƒ and g are Co-injective. $I_{f} \cap I_{g} \neq \emptyset$ , additionally $h (I_{f} \cap I_{g}) = I_{h \circ f} \cap I_{h \circ g} \neq \emptyset$ (h is injective).

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

Therefore $h \circ f$ and $h \circ g$ are Co-injectives.

Note 11

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

· $f^{2}$ and $f \circ g$ are Co-injectives

· $\forall z \in I_{f} \cap I_{g}$ , $\exists! x \in 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 \in I n j n s (E)$ , if $f (I_{h}) \cap g (I_{h}) \neq \emptyset$ , then $f \circ h$ and $g \circ h$ are Co-injectives.

Proposition 9

$\forall f, g \in I n j n s (E)$ , if $I_{f} ⊊ I_{g}$ , then $f, g$ are not Co-injective.

Proof

$\forall f, g \in I n j n s (E)$ , suppose that $I_{f} ⊊ I_{g}$ , then we have $I_{g} = I_{f} \cup (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}) \cup g^{- 1} (I_{g} \ I_{f})$ , and $g^{- 1} (I_{g} \ I_{f}) \neq \emptyset$ , so $g^{- 1} (I_{f}) ⊊ E$ .

Proposition 10

Let $f, g \in I n j n s (E)$ , so that ƒ and g are Co-injectives, $\forall h \in I n j n s (E)$ , if g and h are Co-injectives and $I_{f} \cap I_{h} = I_{f} \cap I_{g}$ then ƒ and h are Co-injectives.

Proof

$I_{f} \cap I_{h} \neq \emptyset$ , let $x, y \in E$ , so that $f (x) = h (y)$ . We have $f (x) = h (y) \in I_{f} \cap I_{h} = I_{f} \cap 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 $\forall x, y \in E$ , $f (x) = h (y) \Rightarrow x = y$ . Therefore $f, h$ are Co-injectives.

Acknowledgements

I would like to thank my dear friends, especially Chaﬁk 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.