Counting Specific Classes of Relations Regarding Fixed Points and Reflexive Points
Rudolf Berghammer Institut für Informatik Christian-Albrechts-Universität zu Kiel 24098 Kiel, Germany [email protected], Jules Desharnais Départment d’informatique et de génie logiciel Université Laval Québec, QC, Canada, G1V 0A6 [email protected], Michael Winter Department of · 2025
Read Counting Specific Classes of Relations Regarding Fixed Points and Reflexive Points by Rudolf Berghammer Institut für Informatik Christian-Albrechts-Universität zu Kiel 24098 Kiel, Germany [email protected], Jules Desharnais Départment d’informatique et de génie logiciel Université Laval Québec, QC, Canada, G1V 0A6 [email protected], Michael Winter Department of (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-00140.txt.
Introduction
Rudolf Berghammer, Jules Desharnais, and Michael Winter count functions and relations with special points in a 2025 mathematics paper. A fixed point is an element mapped to itself; a reflexive point is one related to itself. Given a finite set, the authors ask how often random functions and relations have such points.
They work across a ladder of classes: functions, partial functions, all relations, and permutations, and then involutions and their proper subclass. For each they count the relations, compute chances, and find limits as the set grows without bound. Idempotent functions, which stabilize after one application, get the same treatment. The work was motivated and checked by many experiments in the RelView relation tool.
Catalog record
| CREATOR | Rudolf Berghammer Institut für Informatik Christian-Albrechts-Universität zu Kiel 24098 Kiel, Germany [email protected], Jules Desharnais Départment d’informatique et de génie logiciel Université Laval Québec, QC, Canada, G1V 0A6 [email protected], Michael Winter Department of |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 99 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-00140
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Counting Specific Classes of Relations Regarding Fixed Points and Reflexive Points Rudolf Berghammer Institut für Informatik Christian-Albrechts-Universität zu Kiel 24098 Kiel, Germany [email protected], Jules Desharnais Départment d’informatique et de génie logiciel Université Laval Québec, QC, Canada, G1V 0A6 [email protected], Michael Winter Department of Computer Science Brock University St. Catharines, Ontario, Canada, L2S 3A1 [email protected] Abstract Given a finite and non-empty set X X and randomly selected specific functions and relations on X X , we investigate the existence and non-existence of fixed points and reflexive points, respectively. First, we consider the class of functions, weaken it to the classes of partial functions, total relations and general relations and also strengthen it to the class of permutations. Then we investigate the class of involutions and the subclass of proper involutions. Finally, we treat idempotent functions, partial idempotent functions and related concepts. We count relations, calculate corresponding probabilities and also calculate the limiting values of the latter in case that the cardinality of X X tends to infinity. All these results have been motivated and also supported by numerous experiments performed with the RelView tool. Counting Specific Classes of Relations 1 Introduction Fixed points of functions play a central role in mathematics and computer science. Thus, a series of fixed point theorems have been developed that ensure their existence under certain conditions. Well-known examples are the Knaster-Tarski fixed point theorem on complete lattices, the Kleene and Bourbaki-Witt fixed point theorems on chain-complete posets, the Banach fixed point theorem on metric spaces, the Brouwer fixed point theorem on unit balls of Euclidean spaces and its generalization to topological Hausdorff vector spaces, called Schauder fixed point theorem. A question that naturally arises in this context concerns the portion of functions that have fixed points if no specific condition on the carrier set is assumed. Or, in other words: Given a finite set X with n elements (or an n -set for short), where n\in{\mathbb{N}}_{\geq 1}:={\mathbb{N}}\setminus\{0\} , what is the probability that a randomly selected function on X has a fixed point and what happens if n tends to infinity? To answer this question, we have considered functions f:X\to X as univalent and total relations f\subseteq X\times X . Then f has a fixed point iff f is not irreflexive, i.e., there exists an element x\in X such that (x,x)\in f . Following [ 6 ] , we call an element with this property also a reflexive point of a relation. Using the relational specifications \mathfrak{unival}(X,Y) , \mathfrak{total}(X,Y) and \mathfrak{irrefl}(X) of [ 4 ] for the sets of univalent and total relations between sets X and Y and the set of irreflexive relations on a set X , respectively, and their implementations as programs of the RelView tool (cf. [ 2 , 19 , 20 ] ), we have performed many experiments. In RelView relations are implemented via binary decision diagrams. See [ 1 , 2 ] for more details. This very efficient implementation is particularly suitable for the enumeration of huge sets of relations as, for example, demonstrated in [ 1 , 2 , 3 , 4 , 5 ] . In particular, we have been able to compute on n elements all functions having a fixed point up to n=250 . The results are shown in Figure 1 . \begin{array}[]{r|r|r|r}n&\lx@intercol\hfil\#\mbox{ functions}\hfil\lx@intercol\vrule\lx@intercol&\lx@intercol\hfil\#\mbox{ with fixed point}\hfil\lx@intercol\vrule\lx@intercol&\lx@intercol\hfil\mbox{ratio}\hfil\lx@intercol\\ \hline\cr 1&1.000000\cdot 10^{0}&1.000000\cdot 10^{0}&100.000\%\\ 5&3.125000\cdot 10^{3}&2.101000\cdot 10^{3}&67.232\%\\ 10&1.000000\cdot 10^{10}&6.513216\cdot 10^{09}&65.132\%\\ 25&8.881784\cdot 10^{34}&5.680818\cdot 10^{34}&63.960\%\\ 50&8.881784\cdot 10^{84}&5.647308\cdot 10^{84}&63.583\%\\ 100&1.000000\cdot 10^{200}&6.339677\cdot 10^{199}&63.397\%\\ 150&2.592321\cdot 10^{326}&1.641847\cdot 10^{326}&63.385\%\\ 200&1.606938\cdot 10^{460}&1.017260\cdot 10^{460}&63.304\%\\ 250&3.054936\cdot 10^{599}&1.933340\cdot 10^{599}&63.286\%\\ \end{array} Figure 1: Number of functions and functions with fixed points Looking at the table of Figure 1 , it seems that the probability that a randomly selected function on an n -set converges to a number near to 0.6328. In fact, it converges to 1-\frac{1}{\rm e}\approx 0.6321205 , as we will show in Section 3 . Inspired by this result, we have investigated reflexive points (fixed points in the case of functions) in the case of a randomly selected relation from a certain class of relations on an n -set in more detail. In Section 3 we concentrate on the existence of fixed points. Besides functions, i.e., univalent and total relations as mentioned above, we also consider relations where only one or even none of these properties holds. That is, we also calculate the probability that a randomly selected partial function, total relation or arbitrary relation, respectively, on a set X with n elements has a fixed point respectively a reflexive point, and its limiting value if n tends to infinity. In addition, we strengthen the assumption and answer the analog question for the set of permutations on X . In each case the decisive part for obtaining the probability consists in counting those relations of the class under consideration which have at least one reflexive point (fixed point for functions). In Section 3 we generalize these counting problems in two ways. With the exception of permutations, first, we allow relations between possibly different sets, i.e., heterogeneous relations. The only restriction is that the source is a subset of the target. This allows to define fixed points and reflexive points also for such relations in an obvious way. Second, we introduce an additional parameter k and compute for each of the five classes mentioned above the number of relations with k fixed points respectively k reflexive points. So, for each class we obtain a list of numbers indicating the number of relations of the class which have 0,1,2, … fixed points respectively reflexive points. For each of the five lists we then show how its members are related to each other with respect to their sizes. To simplify presentation, for these comparisons we assume that source and target are equal, i.e., the relations are homogeneous. There are some classes of relations which are defined by means of the absence of reflexive points (fixed points for functions). For instance, the irreflexive relations constitute such a class. Also derangements are defined this way, viz. as permutations without a fixed point. In Section 3 we will use derangements to determine the number of permutations on an n -set with k fixed points. A further such class is that of proper involutions. These are involutions (i.e., self-inverse permutations) without a fixed point. In Section 4 we compute the number of involutions on an n -set X that have k fixed points. This not only yields the number of proper involutions on X but also allows to compute the probability that a randomly selected involution on X is proper and its limiting value if n tends to infinity. A class of functions that always have fixed points is given by the idempotent functions on a set X , since for such a function f:X\to X each image element f(x) is a fixed point of f . If totality of f is not demanded, then f becomes an idempotent partial function on X . In such a case it may happen that f has no fixed point. Due to this fact, in Section 5 we investigate idempotent functions, idempotent partial functions and their weakening to transitive partial functions on n -sets and present solutions of problems similar to those we have treated in Sections 3 and