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 are two non-surjective injective maps from E to F and from F to E respectively, then:
· forms a partition of F.
· forms a partition of E.
where,
and
and representing the image sets under 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:
and are non-empty.
Also, obviously such as as follows from the definition of .
For any such map ƒ from E to F:
So
Since ƒ is an injective map then:
Therefore, forms a partition of F.
In analogy to the map g from F to E, 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:
·
·
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
·
·
·
·
·
·
where,
and
Example 1
If 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:
·
·
Knowing that and then:
·
·
·
·
·
·
Therefore, we can partition the set to the second (2nd) order by ƒ and g such as:
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:
Then,
where,
Proof
By induction:
For , we have, by definition , and for the proposition 1 states that, if and then, Suppose that the said property is true for n. Then, by composing by ƒ, we get:
Then,
Therefore,
Note 2
For all non-surjective injective maps ƒ from an infinite set E to itself,
Definition 1
Let ƒ be a map from no-empty set E to itself,
· is a fixed point of ƒ if, .
· is a fixed point set of ƒ if, .
Proposition 3
For all non-surjective injective maps f from an infinite set E to itself, , contains no fixed points of ƒ.
Proof
By induction:
For , let , and by definition , , particularly for so then contains no fixed points of f. Suppose that the aforementioned property is true for n, let , then such that , we have (by inductive hypothesis), since ƒ is injective then so , then , . Therefore, , 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:
and
·
·
·
·
· For all ƒ non-surjective injective maps from an infinite set E to itself,
Proposition 4
For all ƒ non-surjective injective maps from E to itself,
Proof
Let , by induction, For , we have, by definition then Suppose that the said property is true for , let , then, and . Since ƒ is injective so , which contradicts the inductive hypothesis. Then,
.
Therefore,
Lemma 1 (Generalization)
Proof
By complete (strong) induction,
Let , and : For , we have, by definition , since , then:
Suppose that the said property is true for all , let , then, and . Since ƒ is injective then,
· , if , which contradicts the inductive hypothesis, because
· , if , which contradicts
· , if , which contradicts
Then,
,
Therefore,
QED
For all , and for all ƒ non-surjective injective maps from an infinite set E to itself, we define the following:
·
·
·
·
Theorem 1
Let E be an infinite set, and ƒ be a non-surjective injective map from E to itself, then:
Proof
Note that for , , The sequence of subsets of E, is increasing by inclusion, so it is convergent, the limit is:
We have already established that,
Otherly, according to the Lemma 1,
Let’s define the following, the sequence of subsets of is decreasing by inclusion then, it is convergent [1], the limit is:
Because, let , then:
On the other hand, the sequence of subsets of E, is strictly decreasing by inclusion, then it is convergent and the limit is , and since ƒ is injective, so then ƒ is bijective from H to itself, and .
Therefore,
N.B. If , then we get:
QED
Example 2
is the set of real numbers, and is the set of subsets of .
Let ƒ be a map from to itself, defined by:
Therefore, ƒ is injective non-surjective from to itself, because ƒ is injective and .
where,
We have, since ƒ is increasing Therefore,
·
·
According to the theorem 1, we can write:
Example 3
Remark
If h is an affine map from to , so that and , then:
If , then:
Let ƒ be a map defined from to itself by:
ƒ is non-surjective injective map from E to itself, so that:
·
·
· The set , fulfills the condition
· We have , , ,
·
The restriction of ƒ to is an affine function such as , and , then:
We have: , and ,
According to Theorem 1:
Example 4
Let ƒ be a map defined from to itself by:
ƒ is non-surjective injective from E to itself, so that:
·
·
· The set , fulfills the condition , and
· The set , fulfills the condition , and
·
We have,
·
· and
Therefore, according to Theorem 1:
Corollary 1
Let be non-surjective injective maps from an infinite set E to itself such as , then:
where,
Therefore, forms a partition of E.
Definition 2
· Let E be an infinite set, we write: as being the set of non-surjective injective maps from E to itself.
· 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 ( is the cardinal of E).
Properties
1) is a semigroup, because the composite of 2 (two) injective maps ƒ and g is injective and , so , .
2) , , is, indeed, a partition of E and , because .
3) There is no idempotent element for the law of composition in and if such an element exists, then and since ƒ is injective, then which is contradictory, because, .
4)Let , and assuming that ƒ is a map from E to itself such as:
5) We have, knowing that and
6) Let , we have, , and
Then,
Therefore, allow us to reduce order of iteration.
7) ,
· , then
· ,then,
· , then
8) Let and , so:
and
2.2. Equivalence Relations
Example 5
Let , we define the binary relation R on , by:
R is, indeed, an equivalence relation, because:
· R is reflexive,
· R is symmetric,
· R is transitive, and , and and
Example 6
Let , we define the binary relation R on , by:
R is, indeed, an equivalence relation, because:
· R is reflexive,
· R is symmetric,
· R is transitive, and , and and
Example 7
Example 8
: as being the ƒ-semicoverage of a set E.
3. Part II
Let E be an infinite set, , and
We get the following:
·
·
Let i.e. let , so and , so and , so so , then therefore
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:
Proof
By contradiction, let’s suppose that for all non-surjective injective maps from E to itself, there exists a map such as so that . Additionally E is an infinite set, so E is equipotential [2] to . Considering this bijection ƒ as a map from E to itself, then , and , according to all of the above, there exists a map such as , which contradicts the fact that injective.
QED
Note 4
· , so that: ,
· If applies to the former theorem then: .
Proposition 5
, , so that
Proof
By contradiction, assuming that exists a map , so that , , then , .
Let , so because which is contradictory.
Proposition 6
, , such as
Proof
By contradiction, assuming that exists a map , so that, , then . On the other hand, if , additionally so which is contradictory.
Note 5
We can define another composition law T for so that,
· then every element is idempotent under the law T.
· , if , then .
· , if , then .
· , and .
· Generally, , .
4. Part III
4.1. Study of the Quotient Set
Let E be an infinite set, and . We define the binary relation R on , by:
and have the same cardinal
The binary relation R is reflexive, symmetric and transitive, so R is an equivalence relation on .
We define the equivalence class of a map ƒ.
Note 6
· Let , as so and have the same cardinal, because ƒ is injective then , therefore,
· Let , assuming that the cardinals of and are finite, and thus, , and since , then: .Since the composition of two (2) maps ƒ and g on yields a disjoint union, i.e. , with ,then we can extend the sum of the cardinals even for infinite sets, such as:
· For all maps and so that and i.e. and . Since:
, therefore,
· The map’s composition law is compatible under the equivalence relation R, then we can provide the quotient set with a structure of a semigroup.
· and :
4.2. Partial Order
Let , define a binary relation on by:
·
So is reflexive.
· , and and so
So is asymmetric.
· and : and and
So is transitive.
Therefore, the relation is a partial order on .
Note 7
· Since , or then is a total partial order on .
· The partial order on the semigroup is, indeed, compatible [3] with the equivalence class’s composition law of composition *, then:
and ,
If then and
· is well-ordered, because any non-empty subset has a smallest element.
· is a lattice, because it is ordered and every pair of elements has both upper bound and lower bound [4].
· provided with the order relation has a minimal element , so that , and also maximal element , so that has the same cardinality as E.
· If E is an infinite countable set, the map defined by:
,
where, represents the cardinal of .
Considering the convention: , , is a morphism of semigroups of on .
Complement
Let so that , with the assumption that and are considered finite, and are equipotential because, the map defined from to by:
, is bijective, where is defined from to E, and for all , we associated its inputs by ƒ, we have:
· , (because both g and are injectives). Therefore is injective.
· On the other hand so is surjective.
Let so that the map is defined by:
Belong to and .
Note 8
· If so so if then we have, , and if so
· We considered, previously, that, and are finite. That said, we can build the map even in case that and are infinite and that .
5. Part IV
E Permutations Group Action
Let be the permutations group of E, and , , because, since ƒ and are injective then is injective and , then is non-surjective.
where then .
We have,
· and :
· ,
Let
so that , ,
Therefore, the E permutations group operates on the rightmost on .
Note 9
The relation R defined on by: such as is an equivalence relation, that is called Intransitivity relation [5].
Proposition 7
Let be, : so that .
Proof
) If there exists so that .
) If , then the map , so that is bijective, because:
· so is surjective.
· : so is injective.
· ,
Note 10
· The equivalence class (Intransitivity relation) of the element ƒ is called the orbit of ƒ, .
· The stabilizer of ƒ is: , i.e. the morphism associated with the said action is injective.
6. Part V
Let .
Definition 3
ƒ and g are said to be Co-injectives, if,
and
Let
We have because , and , so ƒ is Co-injective with itself.
Therefore , , then, :
Proposition 8
Let , :
are Co-injectives and are Co-injectives.
Proof:
Let , and such as ƒ and g are Co-injective. , additionally (h is injective).
Let , (because h is injective and are Co-injectives).
Therefore and are Co-injectives.
Note 11
For all , so that are Co-injectives, so:
· and are Co-injectives
· , , so that,
·
· If, , then
· Let , if , then and are Co-injectives.
Proposition 9
, if , then are not Co-injective.
Proof
, suppose that , then we have . If are Co-injectives, then , which is contradictory because:
, and , so .
Proposition 10
Let , so that ƒ and g are Co-injectives, , if g and h are Co-injectives and then ƒ and h are Co-injectives.
Proof
, let , so that . We have , then (because are Co-injectives), and since g and h are Co-injectives then . So , . Therefore 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.
[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.