# Local Diversity of Condorcet Domains

Alexander Karpov111Authors are listed in alphabetical order HSE University,
Moscow, Russia  Institute of Control Sciences, Russian Academy of Sciences,
Moscow, Russia  Klas Markström  Umeå University  Søren Riis  Queen Mary
University of London  Bei Zhou  Queen Mary University of London

###### Abstract

Several of the classical results in social choice theory demonstrate that in
order for many voting systems to be well-behaved the set domain of individual
preferences must satisfy some kind of restriction, such as being single-peaked
on a political axis. As a consequence it becomes interesting to measure how
diverse the preferences in a well-behaved domain can be.

In this paper we introduce an egalitarian approach to measuring preference
diversity, focusing on the abundance of distinct suborders one subsets of the
alternative. We provide a common generalisation of the frequently used
concepts of ampleness and copiousness.

We give a detailed investigation of the abundance for Condorcet domains. Our
theorems imply a ceiling for the local diversity in domains on large sets of
alternatives, which show that in this measure Black’s single-peaked domain is
in fact optimal. We also demonstrate that for some numbers of alternatives,
there are Condorcet domains which have largest local diversity without having
maximum order.

##  1 Introduction

In many situations studied in social choice a group of agents, which may be
voters in a political system or artificial agents in a computer environment,
need to reach a common decision based on their individual preferences. In
situations where the individual preferences are completely unrestricted the
now classical theorem of Arrow (1950) shows that all decision procedures fail
to satisfy several desirable properties. Similarly the Gibbard-Satterwhaite
theorem Gibbard (1973); Satterthwaite (1975) demonstrates the only social
choice procedure which is proof against strategic manipulation is dictatorial.
On the other hand Black (1948) showed that when preferences are based on
preferences which are single-peaked on a common political axis, majority
voting will be both decisive and strategyproof. These contrasting results lead
to the question of how diverse a collection of individual preferences can be
while also having a well-behaved social choice procedure. One of the most
studied classes of well-behaved preferences is the Condorcet domain. A
Condorcet domain is a set of linear orders such that the majority voting
decision is transitive when each voter chooses their preferences from this
domain. Condorcet domains secure strategyproofness in both deterministic
(Campbell and Kelly, 2003) and randomized environments (Brandt et al., 2023).

One of the most obvious measures for the diversity of opinions in a Condorcet
domain is the size of the domain. This is a well-studied problem in social
choice theory Kim et al. (1992); Puppe and Slinko (2023). Recent studies
(Karpov and Slinko, 2023; Karpov et al., 2023) improved the asymptotic lower
bound for the size of the largest Condorcet domains. Up to seven alternatives,
all maximal Condorcet domains are investigated in Akello-Egwell et al. (2023),
and in Leedham-Green et al. (2023) the largest domains on eight alternatives
were determined. For higher numbers of alternatives the maximum possible size
of a Condorcet domain remains an open problem.

However, the size is only the simplest measure of diversity and domains of the
same size may have very different structures. With this in mind, other types
of diversity measures have been studied. Puppe (2018) justified the single-
peaked domain of preferences by requiring maximal diversity of the top
elements. A more general measure of diversity is the support-based preference
diversity index Hashemi and Endriss (2014) that evaluates diversity by the
total number of distinct suborders of a given size. It reflects the idea of
utilitarianism. It has substitutability, i.e. low diversity of preferences
within one subset of alternatives can be compensated by high diversity within
another subset of alternatives. By measuring the lowest number of distinct
suborders over all subsets of a given size, we implement an egalitarian
(Rawlsian) approach to preference diversity measurement. Note that this is
egalitarian with respect to alternatives (subsets of alternatives), not
voters/agents.

Recent literature has introduced two local diversity conditions for domains:
_ampleness_ and _copiousness_ , see Slinko (2019); Puppe and Slinko (2023).
The first means that the restriction of the domain to any pair of alternatives
contains both of the possible orders, and the latter means that the
restriction to any triple contains four orders. In this paper we generalize
these notions by introducing a new diversity measure called abundance. Here we
say that a Condorcet domain that contains at least $s$ suborders for each
$k$-elements subset of alternatives is more diverse than a Condorcet domain
that contains at least $s^{\prime}$ suborders for each $k$-elements subset of
alternatives if we have $s>s^{\prime}$.

Some Condorcet domains have very low local diversity, e.g. non-ample Condorcet
domains Akello-Egwell et al. (2023). On the other hand, there are Condorcet
domains with at least $2^{k-1}$ distinct suborders for each $k$-elements
subset. Single-peaked, single-dipped, and group-separable domains are examples
of such domains. Utilizing Ramsey’s theorem, we show that for sufficiently big
numbers of alternatives $n$ and a fixed $k$, $2^{k-1}$ distinct suborders is
the highest possible local diversity. This fact is an additional justification
for the classical domains such as the single-peaked, and group-separable
domains. It is possible to find significantly larger Condorcet domains than
the single-peaked domain (see e.g. set-alternating scheme Karpov et al.
(2023)), but their local diversity properties cannot be strictly better.

For a small number of alternatives, the Condorcet domain with the highest
number of orders also has the best local diversity properties. Starting with
$n=7$, there are maximal Condorcet domains that do not have the highest number
of orders but have better local diversity parameters than the Condorcet
domains of the maximal size. The study of local diversity properties thus
opens a new line of research on large Condorcet domains.

In this paper we focus our discussion on Condorcet domains, however the
concept of abundance applies to general domains and we will in our
experimental analysis also include less restricted domains.

The structure of the paper is organised as follows: Section 2 introduces the
notation and definitions employed throughout the paper. Section 3 defines the
abundance of a domain and presents a series of theorems about abundance.
Section 4 discusses the maximality of Condorcet domains, used in some of the
later computational work. Section 5 establishes asymptotic upper bounds for
abundance via a Ramsey-type property for Condorcet domains. Section 6
discusses abundance in terms of diversity indices and diversity orders for
profiles. It follows this by an experimental study that compares the abundance
of profiles randomly sampled from various domain types, including domains
arising from empirical data. Finally, section 7 gives some conclusions.

##  2 Background and Notation

Let a finite set $X=[n]=\\{1,\dots,n\\}$ be the set of alternatives. Let
$L(X)$ be the set of all linear orders over $X$. Each agent $i\in N$ has a
preference order $P_{i}$ over $X$ (each preference order is a linear order).
For brevity, we will write preference orders as strings, e.g. $12\dots n$
means that $1$ is the best alternative, $n$ is the worst.

A subset of preference orders $D\subseteq L(X)$ is called a _domain_ of
preference orders. A domain $D$ is a _Condorcet domain_ if whenever the
preferences of all agents belong to the domain, the majority relation of any
preference profile with an odd number of agents is transitive. A Condorcet
domain $D$ is _maximal_ if every Condorcet domain $D^{\prime}\supset D$ (on
the same set of alternatives) coincides with $D$. A Condorcet domain $D$ is
_unitary_ if it contains order $12\ldots n$. Each Condorcet domain can be
rearranged to a unitary form by renaming alternatives. We will consider mainly
unitary Condorcet domains.

Two Condorcet domains are isomorphic if they differ only by a relabeling of
the alternatives.

The _restriction_ of a domain $D$ to a subset $A\subset X$ is the set of
linear orders from $L(A)$ obtained by restricting each linear order from $D$
to $A$.

Sen (1966) proved that a domain is a Condorcet domain if the restriction of
the domain to any triple of alternatives $(a,b,c)$ satisfies a never
condition. A never condition can be of three forms $xNb$, $xNm$ $xNt$,
referred to as a never bottom, a never middle, and a never top condition
respectively. Here $x$ is an alternative from the triple and $xnb$, $xNm$, and
$xNt$ means that $x$ is not ranked last, second, or first respectively in the
restricted domain. Fishburn noted that for domains with a societal axis never
conditions can instead be described as $iNj$, $i,j\in[3]$. $iNj$ means that
$i^{th}$ alternative from the triple according to societal axis does not fall
in $j^{th}$ place within this triple in any order from the domain. Unitary
domains have at most six types of never conditions in Fishburn’s format.

A _profile_ is a vector $\mathbf{R}=(R_{1},R_{2},\ldots,R_{N})$ such that
$R_{i}$ is the preferences of voter/agent $i$. The _support_
$Supp(\mathbf{R})$ of a profile is the set of distinct preference orders
occurring in $\mathbf{R}$. A profile is unanimous if the support has size 1.
The _census_ of $\mathbf{R}$ is the vector
$C(\mathbf{R})=((f_{1},R_{1}),(f_{2},R_{2}),\ldots)$ with one pair
$(f_{i},R_{i})$ for each $R_{i}\in Supp(\mathbf{R})$ where $f_{i}$ is the
number of agents with preference $R_{i}$.

From Hashemi and Endriss (2014) we have the following definitions. A
_preference diversity order_ is a partial order $\preceq$ on the set of
profiles such that $\mathbf{R}_{1}\preceq\mathbf{R}_{2}$ if $\mathbf{R}_{1}$
is unanimous. A _preference diversity index_ is a function $\Delta$ from the
set of profiles to the non-negative real numbers such that
$\Delta(\mathbf{R})=0$ if $\mathbf{R}$ is unanimous.

A diversity index $\Delta$ also defines a natural diversity order
$\preceq_{\Delta}$ by saying that
$\mathbf{R}_{1}\preceq_{\Delta}\mathbf{R}_{2}$ if
$\Delta(\mathbf{R}_{1})\leq\Delta(\mathbf{R}_{2})$.

A Condorcet domain is said to be _ample_ if restriction of the domain to any
pair of alternatives contains both of the possible orders, and _copious_ if
the restriction to any triple contains four orders.

A domain which satisfies a never condition of the form $xN3$ for every triple
is called an _Arrow’s single-peaked domain_ Arrow (1963). _Black’s single-
peaked domain_ is the maximal Arrow’s single-peaked domain isomorphic to the
domain defined by using the never condition $2N3$ on all triples Black (1948).
A domain is a _single-crossing domain_ if there is an ordering for the set of
preference orders in the domain such that for any pair of alternatives $(i,j)$
there exists a unique $k$ so that their relative order is $(i,j)$ for the top
$k$ preference orders and $(j,i)$ for the rest Slinko et al. (2021).
Fishburn’s alternating domains are defined by assigning a triple $(i,j,k)$ the
never condition $2N1$ if $j$ is odd and $2N3$ if $j$ is even Fishburn (1997).
Karpov et al. (2023) introduced the _set-alternating_ domains. Given a subset
$A$ of the alternatives the corresponding set-alternating domain has the never
condition $1N3$ on each triple $(i,j,k)$ where $j\in A$, and $3N1$ on the
other triples.

Ramsey’s theorem Ramsey (1930) asserts that given positive integers $k,r,n$
there is a positive integer $R(k,r,n)$ such that if $N\geq R(k,r,n)$, and each
subset of size $r$ from $[N]$ is assigned a label from $[k]$, then all
$r$-subsets from some subset of $[N]$ of size $n$ has the same label.

###  2.1 Code and data

For our computational results we have used the CDL library Zhou et al. (2023),
which provides functions for the study of Condorcet domains and other types of
restricted preference orders. This library includes a function which computes
the restriction of a domain to a subset of the alternatives.

The programs and data used to derive the results in this paper are publicly
available222GitHub.
https://github.com/sagebei/Local_Diversity_of_Condorcet_Domains.git.

Whenever possible we have also verified our results by using independently
coded functions in Mathematica.

##  3 Local diversity conditions for Condorcet domains

There are two kinds of local conditions on domains that have been much used in
recent literature, _ampleness_ and _copiousness_. The first means that the
restriction of the domain to any pair of alternatives will contain both of the
possible orders, and the latter that the restriction to any triple will see
the maximum possible four orders.

One way of looking at these conditions is that they require a minimum
diversity of orders on sets of size 2 and 3 respectively. This point of view
can be naturally generalised as follows.

######  Definition 1.

A domain $D$ is $(k,s)$-abundant if the restriction of $D$ to any subset of
$k$ alternatives has size at least $s$.

A domain is _exactly_ $(k,s)$-abundant if it is $(k,s)$-abundant but not
$(k,s+1)$-abundant.

Being $(3,4)$-abundant is equivalent to being copious and $(2,2)$-abundant is
equivalent to being ample. Here we also note that being $(k,s)$-abundant is a
monotone-increasing property under the addition of new orders to the domain;
that is, for a given $k$ the domain $C\cup\\{\sigma\\}$ always has at least as
large abundance as the domain $C$. This in turn implies that the largest
possible abundance can always be found among the maximal Condorcet domains,
but it can also occur already in non-maximal Condorcet domains.

Let us look at the abundance properties of some classes of Condorcet domains.

######  Theorem 1.

  1. 1.

The maximal Black’s and Arrow’s single-peaked domains on $n$ alternatives are
exactly $(k,2^{k-1})$-abundant for every $k\leq n$.

  2. 2.

Set-alternating domains Karpov et al. (2023) are $(k,2^{k-1})$-abundant for
every $k\leq n$. If $k<n/2$ then they are exactly $(k,2^{k-1})$-abundant.

  3. 3.

Fishburn’s alternating domains are exactly $(k,2^{k-1})$-abundant if
$k\leq\lceil n/2\rceil+1$.

For $n=4,5$ they are $(4,s)$-abundant for $s=9,8$.

For $n=5,6,7$ they are $(5,s)$-abundant for $s=20,19,16$.

For $n=6,7,8,9$ they are $(6,s)$-abundant for $s=45,42,39,32$.

For $n=7,8,9,10,11$ they are $(7,s)$-abundant for $s=100,96$, $86,79,64$.

  4. 4.

The maximum Condorcet domain for $n=8$ is $(4,8),(5,18),(6,40),$ and
$(7,96)$-abundant.

###### Proof.

Point 1 follows since the restriction of an Arrow’s single-peaked domain to a
subset of the alternatives is also an Arrow’s single-peaked domain, and by
Slinko (2019) any maximal Arrow’s single-peaked domain on $k$ alternatives has
size $2^{k-1}$.

Point 2 follows using the construction in Karpov et al. (2023) of set-
alternating domains. It is shown that every such domain on $t$ alternatives
has size at least $2^{t-1}$, and the restriction of a set-alternating domain
to a subset of the alternatives is also a set-alternating domain.

The first part of point 3 follows by taking the restriction of the domain to
the set of even integers together with 1 $n$, if the latter is odd. This set
has size $\lceil n/2\rceil+1$ and the restricted domain uses only the never
condition $2N1$. If $k$ is smaller than $\lceil n/2\rceil+1$ we further
restrict to an arbitrary subset $A$ of size $k$. By Raynaud (1981) the
restricted domain has size $2^{k-1}$, since it uses a single never condition.

The remainder of point 3 follows from a computational test of these domains,
done independently in Mathematica and CDL.

Point 4 follows by a computational test of the maximum domain from Leedham-
Green et al. (2023). ∎

######  Theorem 2.

For $n\leq 6$ and $k=2,3,4,5,6$, Fishburn’s alternating domains have the
maximum possible abundance among all maximal Condorcet domains with a given
number of alternatives. For $n=7$, they do not reach the maximum possible for
$k=6$.

###### Proof.

The abundances for all maximal Condorcet domains in this range were computed
using the data from Akello-Egwell et al. (2023). ∎

For $n=7$, $n=8$, with $k=6$, there are maximal Condorcet domains with higher
abundance than the Condorcet domains of maximum size.

Given two domains with large abundances, we have a natural construction for
larger domains which inherit some abundances from the first domains.

######  Definition 2.

Given two domains $D_{1}$ and $D_{2}$ on the sets $A$ and $B$ respectively we
define a domain $S(D_{1},D2)$ on the set $A\cup B$ as follows: Given any order
$u$ from $D_{1}$ and any order $v$ from $D_{2}$ the domain contains both the
concatenation $uv$ and the concatenation $vu$.

The domain $S(D_{1},D2)$ has size $2|D_{1}||D_{2}|$ and cannot have low
abundance when $D_{1}$ and $D_{2}$ do not.

######  Proposition 1.

If $D_{1}$ and $D_{2}$ are $(k,2^{k-1})$-abundant for each $k\leq t$ then so
$S(D_{1},D_{2})$.

###### Proof.

This obviously holds for $k$-tuples which only contain alternatives from one
of $A$ and $B$. Let us assume that the tuple has elements $T_{1}$ from $A$ and
$T_{2}$ from $B$. Then $S(D_{1},D_{2})$ contains both every concatenation of
the, at least, $2^{|T_{1}|-1}$ elements in the restriction of $D_{1}$ to
$T_{1}$ with the, at least, $2^{|T_{2}|-1}$ elements in the restriction of
$D_{2}$ to $T_{2}$, and the same number of concatenations om the opposite
order.

This gives a total of at least $2\times 2^{|T_{1}|-1}\times
2^{|T_{2}|-1}=2^{k-1}$ linear orders in the restriction to this $k$-tuple. ∎

Given that abundance is a monotone-increasing property it is natural to ask
how many linear orders we must have in order to achieve a specified abundance.
This is equivalent to asking, given a fixed $k$ how small can a _minimal_
$(k,s)$-abundant domain $D$ be? Here minimal means that every subset of $D$ is
a domain which is not $(k,s)$-abundant.

######  Theorem 3.

We have the following existence results for small domains with given
abundance:

  1. 1.

For every $k\geq 2$ there are $(k,2)$-abundant domains of size 2 for every
$n\geq 2$.

  2. 2.

There exists $(3,3)$-abundant and $(3,4)$-abundant domains of size 3 and 4
respectively if and only if $3\leq n\leq 8$.

  3. 3.

There exists single-crossing maximal Condorcet domains with size ${n\choose
2}+1$ which are $(3,4)$-abundant

###### Proof.

  1. 1.

Take the domain which consists of the natural order and its reverse.

  2. 2.

One such domain for $n=8$ is displayed in Figure 1 (rows represent linear
orders). The first three orders form a $(3,3)$-abundant domain, and by
deleting alternatives we reach domains for smaller $n$ with the same
abundance. A computer search shows that no $(3,3)$-abundant domains exist for
$n=9$.

  3. 3.

See Slinko et al. (2021) for an example of a maximal single-crossing domain
that is copious and has size ${n\choose 2}+1$.

∎

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8
---|---|---|---|---|---|---|---
4 | 3 | 2 | 1 | 8 | 7 | 6 | 5
6 | 5 | 8 | 7 | 2 | 1 | 4 | 3
7 | 8 | 5 | 6 | 3 | 4 | 1 | 2
Figure 1: A $(3,4)$-abundant domain of size 4 for $n=8$

As the example in Figure 1 (each row is an order) shows it is possible to have
a large abundance with a, perhaps, surprisingly small number of voters.
However, examples of the type given here are rare, for $n=8$ there is up to
isomorphism just 7 such Condorcet domains. As a comparison, for a set of $t$
randomly chosen orders from the unrestricted domain with $n=8$ reaches
expected abundance $(3,4)$ at $t=14$. It would be interesting to investigate
how large the abundance in empirical domains typically is.

###  3.1 Diversity inheritance

Being abundant for one set of parameters often implies that a domain is
abundant for additional parameters. Using data from Akello-Egwell et al.
(2023) one can establish the inheritance properties presented in Table 1. Here
$(k_{1},s_{1})\rightarrow{}(k_{2},s_{2})$ means that every domain which is
$(k_{1},s_{1})$-abundant is also $(k_{2},s_{2})$-abundant.

Table 1: Implications for induced abundance $(3,4)\rightarrow{}(2,2)$ | $(4,9)\rightarrow{}(2,2)$ |
---|---|---
$(5,19)\rightarrow{}(2,2)$ | $(6,43)\rightarrow{}(2,2)$ |
$(4,4)\rightarrow{}(3,1)$ | $(4,5-6)\rightarrow{}(3,2)$ | $(4,7-8)\rightarrow{}(3,3)$
$(4,9)\rightarrow{}(3,4)$ |  |
$(5,12)\rightarrow{}(3,1)$ | $(5,13-16)\rightarrow{}(3,2)$ | $(5,17-18)\rightarrow{}(3,3)$
$(5,19-20)\rightarrow{}(3,4)$ |  |
$(6,40)\rightarrow{}(3,2)$ | $(6,41-42)\rightarrow{}(3,3)$ | $(6,43)\rightarrow{}(3,4)$
$(5,5)\rightarrow{}(4,1)$ | $(5,6-8)\rightarrow{}(4,2)$ | $(5,9-11)\rightarrow{}(4,3)$
$(5,12-13)\rightarrow{}(4,4)$ | $(5,14-15)\rightarrow{}(4,5)$ | $(5,16-17)\rightarrow{}(4,6)$
$(5,18)\rightarrow{}(4,7)$ | $(5,19-20)\rightarrow{}(4,8)$ |
$(6,40-41)\rightarrow{}(4,6)$ | $(6,42-43)\rightarrow{}(4,7)$ | $(6,44-45)\rightarrow{}(4,8)$
$(6,37)\rightarrow{}(5,13)$ | $(6,38)\rightarrow{}(5,13)$ | $(6,39)\rightarrow{}(5,14)$
$(6,40)\rightarrow{}(5,15)$ | $(6,41)\rightarrow{}(5,16)$ | $(6,42)\rightarrow{}(5,16)$
$(6,43)\rightarrow{}(5,17)$ | $(6,44)\rightarrow{}(5,18)$ | $(6,45)\rightarrow{}(5,19)$

Here we point out that it is only for $k=3$ that we see an implication of the
form $(k,2^{k-1})\rightarrow{}(k-1,2^{k-2})$, corresponding to the known fact
that being copious implies that the domain is also ample. This demonstrates
that for $k\geq 4$ the abundance properties are genuinely distinct. As the
table shows, the inherited abundance drops quickly when $k$ is increased.

##  4 A note on maximality

In this section we will consider the restrictions of a maximal Condorcet
domain to all subsets of alternatives of size $n-1$. This is done for two
reasons. First, this will give us information about how compatible the
rankings of alternatives from different subsets are, and as we will see there
are domains where this is so context dependent that none of these restrictions
are maximal domains. Second, domains which can be restricted to maximal
subdomains are sometimes easier to treat computationally and some of the
results in the next section will depend on this.

When considering the collection of restrictions to $n-1$ alternatives there
are in principle three cases. Either all restrictions to $n-1$ alternatives
are maximal Condorcet domains, or there are both maximal and non-maximal
restrictions, or all such restrictions are non-maximal Condorcet domains. In
the last case we have mutually incompatible preferences coming from all
subsets of the alternatives.

Let us say that a Condorcet domain $D$ on $n$ alternatives is _discordant_ if
$D$ is maximal but does not have a subdomain $D^{\prime}$ on $n-1$
alternatives which is also a maximal Condorcet domain. By eliminating an
alternative from a discordant domain we resolve conflicting never conditions,
and we can find some orders that do not belong to the restriction, but satisfy
all never conditions.

Note that the copiousness property of Slinko (2019) is equivalent to saying
that every subdomain on $3$ alternatives is maximal. Slinko gave examples of
domains which are not copious, and many such examples were given in Akello-
Egwell et al. (2023). However, all the non-copious examples for small $n$ also
have subdomains on 3 alternatives which are maximal, i.e. they have triples of
both kinds. In fact, using the data from Akello-Egwell et al. (2023)
exhaustive testing shows that for $4\leq n\leq 5$ there are no discordant
domains. However, by extending this exhaustive search to the domains for
$n=6,7$ are found.

We find that for $n=6$ there are in total five discordant domains. One of
these has size 4 and the other four have size 25. We display the example of
size 4 domain in Figure 2. The restriction of this domain to each five-
alternatives subset contains four orders, but the corresponding maximal
Condorcet domain on five alternatives has eight orders.

1 | 2 | 3 | 4 | 5 | 6
---|---|---|---|---|---
3 | 6 | 2 | 5 | 1 | 4
4 | 1 | 5 | 2 | 6 | 3
6 | 5 | 4 | 3 | 2 | 1
Figure 2: The smallest discordant Condorcet domain

For $n=7$ we have a much wider range of domain sizes for which discordant
domains exist. In Table 2 we show the number of non-isomorphic discordant
Condorcet domains of each size for $n=7$. These domains can be downloaded from
”” (2199).

Table 2: The number of discordant domains and their sizes for $n=7$ Size | 12 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22
---|---|---|---|---|---|---|---|---|---|---
Count | 2 | 4 | 2 | 20 | 14 | 8 | 66 | 48 | 48 | 24
Size | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32
Count | 8 | 28 | 32 | 38 | 26 | 38 | 32 | 69 | 36 | 89
Size | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42
Count | 64 | 30 | 90 | 102 | 78 | 70 | 70 | 304 | 34 | 49
Size | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52
Count | 44 | 95 | 92 | 74 | 64 | 94 | 56 | 110 | 42 | 100
Size | 53 | 54 | 55 | 56 | 57 | 58 | 60 |  |  |
Count | 38 | 78 | 10 | 74 | 4 | 48 | 15 |  |  |

As we can see, discordant domains exist for most small sizes for $n=7$ but do
not exist for any size above 60. For domains close to the maximum possible
size it seems likely that restrictions will also remain large and we pose the
following problem:

######  Problem 1.

Let $f(n)$ denote the maximum possible size for a Condorcet domain on $n$
alternatives.

Is it true that every discordant Condorcet domain has size at most $0.8f(n)$?

The constant 0.8 in the problem is not intended to be sharp, but rather is a
description of the intuitive picture that very large domains should be so
diverse that this is true for their restrictions as well. From our data, we
see that for $n\leq 7$ the problem would have a positive answer for a constant
much smaller than 0.8.

##  5 Ramsey properties of diversity

From e.g. Black’s single-peaked domain we know that $(k,2^{k-1})$ domains
exist for all $n\geq k$. However, for a fixed $k\geq 4$ there are values of
$s$ such that $(k,s)$-abundant domains exist only for a finite set of values
of $n$. This connects to the observation in Zhou and Riis (2023) that large
enough domains should have subdomains of size six using only a single never
condition. We here provide a proof using the hypergraph version of Ramsey’s
theorem and also note that this implies the existence of a more specifically
order-theoretic Ramsey property.

######  Theorem 4.

Given an integer $k$ there exists two numbers $R_{s}(k)\leq R_{u}(k)$ such
that

  * •

For $n\geq R_{s}(k)$, no domain on $n$ alternatives is $(k,s)$-abundant for
$s>2^{k-1}$.

  * •

For $n\geq R_{u}(k)$, every domain on $n$ alternatives has a subset
$A^{\prime}$ of $k$ alternatives such that every triple in $A^{\prime}$
satisfies the same never condition.

###### Proof.

Given a unitary Condorcet domain $C$ on $n$ alternatives we define an edge
colouring of the complete 3-uniform hypergraph $K_{n}^{(3)}$ by using the name
of the never condition on a triple as the colour of the corresponding edge of
the hypergraph. This colouring uses at most 6 colours.

By Ramsey’s theorem for hypergraphs Ramsey (1930) there exists an integer $N$
such that if $n\geq N$ then there must exist a subset $A^{\prime}$ of the
vertices such that every triple has the same colour. This proves the existence
of $R_{u}(k)$.

By Theorems 3 and 4 of Raynaud (1981) a domain on $k$ alternatives in which
every triple satisfies the same never condition has size $2^{k-1}$. This
proves that $R_{s}(k)$ exists and is at most $R_{u}(k)$. ∎

The general theorem shows that $R_{s}(k)\leq R_{u}(k)$ but for small values of
$k$ we find that $R_{s}(k)$ is typically much smaller than $R_{u}(k)$, which
is equal to the corresponding Ramsey number. The latter is known to grow
super-exponentially in $k$ Conlon et al. (2010) and the only known exact value
is that with two colours an $k=4$ we get $R=13$ McKay and Radziszowski (1991).

We have computed the exact value of $R_{s}(k)$ for several small values of
$k$.

######  Theorem 5.

The following bounds on the number of alternatives in a $(k,s)$-abundant
domain hold:

  1. 1.

$(4,9)$-abundant domains exist only for $n=4$.

  2. 2.

$(5,20)$ and $(5,19)$-abundant domains exist if and only $5\leq n\leq 6$.

  3. 3.

$(5,18)$ and $(5,17)$-abundant domains exist if and only if $5\leq n\leq 8$.

  4. 4.

$(6,43)$, $(6,44)$, and $(6,45)$-abundant domains exist only for $n=6$.

  5. 5.

$(6,42)$-abundant domains exist for $n=6,7$. If problem 1 has an affirmative
answer, they do not exist for $n\geq 8$.

  6. 6.

$(6,41)$-abundant domains exist for $n=6,7,8$. If problem 1 has an affirmative
answer, they do not exist for $n\geq 9$.

###### Proof.

Points 1 to 4 follow by exhaustively checking the abundance for the maximal
CDs generated in Akello-Egwell et al. (2023) and the maximum CD from Leedham-
Green et al. (2023), followed by a search for $n=9$ using CDL.

For point 5, the existence of $(6,42)$-abundant domains again follows by
analysing the data set from Akello-Egwell et al. (2023). From that data we
found all maximal $(6,42)$-abundant domains for $n=7$, all these domains had
size 92 or more. Using CDL we found all extensions of these domains to $n=8$
and checked that none were $(6,42)$-abundant.

For point 6, the existence of $(6,41)$-abundant domains for $n=6,7$ again
follows by analysing the data set from Akello-Egwell et al. (2023). From that
data, we found all maximal $(6,41)$-abundant domains for $n=7$, all these
domains had size 91 or more. Using CDL we found all extensions of these
domains to $n=8$, where examples of such domains were found. These were in
turn extended to $n=9$ checked that none were $(6,41)$-abundant. ∎

Abundance $(5,18)$ is achieved for $n=8$ by the maximum domain from Akello-
Egwell et al. (2023), and for $n=7$ an example of size 96 can be constructed
as a subdomain of the $n=8$ domain.

Abundance $(6,42)$ for $n=7$ is achieved by Fishburn’s alternating domain.

Abundance $(6,41)$ is achieved for $n=8$ by two maximal domains of size 219.
The first of these can be viewed as a variation of Fishburn’s alternating
domain where the never conditions on four triples have been changed as
follows: ((1, 2, 4),1N3),((1, 2, 6),1N3), ((3, 7, 8),3N1),((5, 7, 8),3N1).

##  6 Abundance based diversity indices

Our next aim is to connect the local diversity in the form of abundance to the
study of diversity indices, as outlined by Hashemi and Endriss Hashemi and
Endriss (2014).

We define the _abundance vector_ $\mathcal{A}(D)$ of a domain $D$ to the
vector in which entry number $k$ is the $s$ such that $D$ is exactly
$(k,s)$-abundant. Here position $k=1$ will be $1$ for every non-empty domain.

We say that $D_{1}$ is ranked higher than $D_{2}$ if $\mathcal{A}(D_{1})$ is
lexicographically larger than $\mathcal{A}(D_{2})$

This diversity order emphasises diversity according to set size, so that the
smallest sets are the most significant. This is often the prioritisation since
two domains can easily have the same, large, size without having the same
abundance even for $k=2$.

Hashemi and Endriss Hashemi and Endriss (2014) considered, among others, two
basic diversity indices. The _simple support-based index_
$\Delta_{supp}(D)=|D|-1$ and the _support-based index_
$\Delta_{supp}^{k}=|\cup_{A\subset X,|A|=k}Supp(D(A))|-{n\choose k}$. Given a
fixed integer $k$ we can similarly define a simple diversity index by taking
the largest $s$ such that $Supp(\mathbf{R})=D$ is $(k,s)$-abundant. This index
will rank profiles, and domains, specifically according to their diversity on
the restriction to $k$-sets. Here $\Delta_{k}(D)=s$ if $D$ is exactly
$(k,s)$-abundant.

Recall that the binary entropy function is given by

$H(x)=-x\ln(x)-(1-x)\ln(1-x)$

If two profiles have the same abundance index
$\Delta_{k}(\mathbf{R}_{1})=\Delta_{k}(\mathbf{R}_{2})$ we can instead use the
entropy version of the abundance index $\Delta_{k}(D)^{e}=\min_{A\subset
X,|A|=k}H(D(A))$, where $H(D(A))$ is the entropy of the census counts
$f_{i}/N$. Note that $H(D(A))$ is maximized if the profile is uniform over the
preferences in $A$ and minimized if as many agents as possible use a single
order from $D(A)$. This index can either be seen as measuring how uniform the
agent’s preferences are on $A$ or as a proxy for how robustly $(k,s)$-abundant
the profile is. Here the robustness refers to how many preference orders would
one have to change in order to reduce the abundance for $k$-subsets.

The highest entropy is seen for maximal group-separable domains. For each pair
of alternatives each group-separable domain is partitioned on two equal-sized
parts with different preferences over the pair of alternatives. For each
subset of alternatives of size $k$, each group-separable domain is partitioned
on $2^{k-1}$ equal-sized parts with different preferences over the subset
alternatives.

A less egalitarian alternative for comparing domains with equal abundance
vector is to use the sum of the abundances for all $k$-subsets:
$\sum_{|A|=k}|D(A)|$ or, for a profile, the sum of the entropies
$\sum_{|A|=k}|H(D(A))|$.

###  6.1 Experimental analysis

In order to demonstrate the concepts developed in this paper we applied them
to both profiles based on empirical data and profiles based on sampling from
different types of known domains, both Condorcet and not.

Our empirical data comes from the AGH data set333PrefLib.
https://www.preflib.org/dataset/00009 from Mattei and Walsh (2013). This is a
data set based on the choices of courses for a group of students during two
consecutive years. There were 9 available courses in 2003 and 7 in 2004. The
first year had 123 students and the second 70. Neither year leads to a CD.
This data set was also used for simulations in Hashemi and Endriss (2014).

We first investigate the empirical data as it is. The support is not a
Condorcet domain for either of the two years. Using the full data set and all
alternatives the two years give abundance vectors

$(1,1,2,6,16,39,75,101),$ $(1,1,2,6,16,39).$

The domains are non-ample due to a single course which every student takes. If
we delete that course both years lead to an ample domain. If we delete the
mandatory course and restrict to the 5 most popular courses we get the vectors

$(1,2,5,15,31),$ $(1,2,6,16,32).$

Here we see that despite the first profile having more students, 123 vs 70, it
is the second one which has higher abundance.

We have also made a study for different kinds of randomly sampled profiles,
similar to that in Hashemi and Endriss (2014). We generate random samples from
six different models, and in each case we generate domains with $n=7$
alternatives and $N=50$ agents. In the first model we pick preferences
uniformly at random from Black’s single-peaked domain for $n=5$. In the second
model we pick orders from the 2004 AGH data restricted by removing
alternatives 8 and 9. In the third model we pick orders from the unrestricted
domain for $n=7$, a probabilistic model known at the Impartial culture. In the
next models we pick preferences from Fishburn’s alternating domain, a group-
separable/symmetric domain, and a (5,18)-abundant domain of size 96.

In Figure 3 we show the empirical distribution for the abundance when 2000
domains are sampled uniformly from each model. For both $k=3$ and $k=4$ we see
that the unrestricted domain leads to the largest expected abundance, and the
single-peaked domain with given axis to the lowest. Among Condorcet domains
the group-separable domains (caterpillar group-separable, see Faliszewski et
al. (2022)) give the highest expected abundance, except for $k=6$. In this
domain different suborders emerge with equal probabilities, and we have high
abundance with a higher probability, than in domains in which diversity is
based on several rare orders. For $k=6$, (5,18)-abundant domain surpasses the
group-separable domain. It confirms the superiority of the investigated
domain.

The data-based model has higher diversity than Condorcet domains, and since
the support is not a Condorcet domain one might expect more varied preferences
there.

Most of the abundance distributions are unimodal or bell-type for the chosen
parameters. However, for each size $k$ we will see the abundance concentrating
on the maximum possible value for the underlying domain when the number of
agents is large enough. In particular the classical Coupon collector problem
shows that if the support is $(k,s)$-abundant then a uniformly sampled profile
will typically also be that if the number of agents substantially exceeds
$s\log{s}$. However, for a well-structured support one might see such
concentration already for smaller numbers of agents.

The abundance (diversity) axis is an additional dimension which can be used to
distinguish statistical cultures (see the survey Szufa et al. (2023) about
statistical cultures). Other such distinguishing indices have been studied but
unlike e.g. the distance-based indices utilized in Faliszewski et al. (2023)
abundance calculation is quite simple, as long as $k$ is moderate in size.

(a) $k=3$

(b) $k=4$

(c) $k=5$

(d) $k=6$

Figure 3: Frequencies for given abundances. Dotted is Black’s single-peaked
domain, solid is 2004 AGH, dot-dashed is single-crossing, the thick solid line
is Fishburn, the orange line is the symmetric/group-separable domain, red is
the (5,18)-abundant domain, and dashed is the unrestricted domain/Impartial
culture.

##  7 Conclusion

This paper links the study of local diversity to Condorcet domains. For a
given number of alternatives $n$, we determine the Condorcet domains that
exhibit the highest possible diversity for their least diverse restriction.
The results are valid for an unlimited number $N$ of agents. For $n\geq 7$,
several of these domains are novel and have not been previously explored,
while for smaller values of $n$, Fishburn’s alternating domains serve as
examples of maximum diversity. Notably, in several instances, the domains with
the highest local diversity are not the ones with the greatest number of
preference orders, underlining that maximizing the number of preference orders
and maximizing diversity are two separate challenges for Condorcet domains.

We have shown that for restrictions to subsets of a fixed size $k$, the
abundance cannot be higher than $(k,2^{k-1})$ if $n$ is large enough. This
demonstrates that even though Condorcet domains can be much larger than
Black’s single-peaked domain, their abundance for small subsets cannot be
higher than that of Black’s single-peaked domain, when the number of
alternatives is large.

## Acknowledgement

Bei Zhou was funded by the China Scholarship Council (CSC). The Basic Research
Program of the National Research University Higher School of Economics
partially supported Alexander Karpov. This research utilised Queen Mary’s
Apocrita HPC facility, supported by QMUL Research-IT.

## Compliance with Ethical Standards

Conflict of interest The authors have no relevant financial or non-financial
interests that could potentially compromise the integrity, impartiality, or
credibility of the research presented in this paper.

## References

  * (1)
  * ”” (2199) ””, “Maximal Condorcet Domains,” http://abel.math.umu.se/~ klasm/Data/CONDORCET/.
  * Akello-Egwell et al. (2023) Akello-Egwell, Dolica, Charles Leedham-Green, Alastair Litterick, Klas Markström, and Søren Riis (2023) “Condorcet Domains of Degree at most Seven,” arXiv preprint arXiv:2306.15993.
  * Arrow (1950) Arrow, Kenneth J (1950) “A difficulty in the concept of social welfare,” Journal of political economy, 58 (4), 328–346.
  * Arrow (1963) (1963) Social choice and individual values, 12: Yale university press, 2nd edition.
  * Black (1948) Black, Duncan (1948) “On the Rationale of Group Decision-making,” Journal of Political Economy, 56 (1), 23–34, http://www.jstor.org/stable/1825026.
  * Brandt et al. (2023) Brandt, F., P. Lederer, and S. Tausch (2023) “Strategyproof social decision schemes on super Condorcet domains,” in Proc. of the 22nd International Conference on Autonomous Agents and Multiagent Systems, 1734–1742.
  * Campbell and Kelly (2003) Campbell, D.E. and J.S. Kelly (2003) “A strategy-proofness characterization of majority rule,” Economic Theory, 22 (3), 557–568.
  * Conlon et al. (2010) Conlon, David, Jacob Fox, and Benny Sudakov (2010) “Hypergraph Ramsey numbers,” J. Amer. Math. Soc., 23 (1), 247–266,  10.1090/S0894-0347-09-00645-6.
  * Faliszewski et al. (2023) Faliszewski, P., A. Kaczmarczyk, K. Sornat, S. Szufa, and T. Was (2023) “Diversity, Agreement, and Polarization in Elections,” Arxiv preprint arXiv:2305.09780.
  * Faliszewski et al. (2022) Faliszewski, P., A. Karpov, and S Obraztsova (2022) “The complexity of election problems with group-separable preferences,” Autonomous Agents and Multi-Agent Systems volume, 36, 18.
  * Fishburn (1997) Fishburn, Peter (1997) “Acyclic sets of linear orders,” Social choice and Welfare, 113–124.
  * Gibbard (1973) Gibbard, A. (1973) “Manipulation of Voting Schemes: A General Result,” Econometrica, 41 (4), 587–601, http://www.jstor.org/stable/1914083.
  * Hashemi and Endriss (2014) Hashemi, V. and U. Endriss (2014) “Measuring Diversity of Preferences in a Group,” in Proc. of the 21st European Conference on Artificial Intelligence, 423–428.
  * Karpov et al. (2023) Karpov, A., K. Markström, S. Riis, and B. Zhou (2023) “Bipartite peak-pit domains,” Arxiv preprint arXiv:2308.02817.
  * Karpov and Slinko (2023) Karpov, A. and A. Slinko (2023) “Constructing large peak-pit Condorcet domains,” Theory and Decision, 94 (1), 97–120.
  * Kim et al. (1992) Kim, K.H, F.W Roush, and M.D Intriligator (1992) “Overview of mathematical social sciences,” The American Mathematical Monthly, 99 (9), 838–844.
  * Leedham-Green et al. (2023) Leedham-Green, Charles, , Klas Markström, and Søren Riis (2023) “The Largest Condorcet Domain on 8 Alternatives,” arXiv preprint arXiv:2303.15002.
  * Mattei and Walsh (2013) Mattei, Nicholas and Toby Walsh (2013) “PrefLib: A Library of Preference Data http://preflib.org,” in Proceedings of the 3rd International Conference on Algorithmic Decision Theory (ADT 2013), Lecture Notes in Artificial Intelligence: Springer.
  * McKay and Radziszowski (1991) McKay, Brendan D. and Stanisław P. Radziszowski (1991) “The first classical Ramsey number for hypergraphs is computed,” in Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, CA, 1991), 304–308: ACM, New York.
  * Puppe (2018) Puppe, C. (2018) “The single-peaked domain revisited: A simple global characterization,” Journal of Economic Theory, 176, 55–80.
  * Puppe and Slinko (2023) Puppe, Clemens and Arkadii Slinko (2023) “Maximal Condorcet domains. A further progress report,” A Further Progress Report.
  * Ramsey (1930) Ramsey, F. P. (1930) “On a Problem of Formal Logic,” Proceedings of the London Mathematical Society, s2-30 (1), 264–286,  https://doi.org/10.1112/plms/s2-30.1.264.
  * Raynaud (1981) Raynaud, H. (1981) Paradoxical results from Inada’s conditions for majority rule: Institute for Mathematical Studies in the Social Sciences, Stanford University.
  * Satterthwaite (1975) Satterthwaite, Mark Allen (1975) “Strategy-proofness and Arrow’s conditions: Existence and correspondence theorems for voting procedures and social welfare functions,” Journal of Economic Theory, 10 (2), 187–217,  https://doi.org/10.1016/0022-0531(75)90050-2.
  * Sen (1966) Sen, A. K. (1966) “A Possibility theorem on majority decisions,” Econometrica, 34 (2), 491–499.
  * Slinko (2019) Slinko, A. (2019) ”Condorcet domains satisfying Arrow’s single-peakedness,” Journal of Mathematical Economics, 84, 166–175.
  * Slinko et al. (2021) Slinko, A., Q. Wu, and X Wu (2021) “A characterization of preference domains that are single-crossing and maximal Condorcet,” Economics Letters, 204, 109918.
  * Szufa et al. (2023) Szufa, S., P. Faliszewski, P. Skowron, A. Slinko, and N. Talmon (2023) “Drawing a Map of Elections in the Space of Statistical Cultures,” in Proc. of the 19th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2020), 1341-1349.
  * Zhou et al. (2023) Zhou, Bei, Klas Markstrōm, and Søren Riis (2023) “CDL: A fast and flexible library for the study of permutation sets with structural restrictions,” arXiv preprint arXiv:2309.06306.
  * Zhou and Riis (2023) Zhou, Bei and Søren Riis (2023) “New Record-Breaking Condorcet Domains on 10 and 11 Alternatives,” arXiv preprint arXiv:2303.06524.


# Infinitesimals via Cauchy sequences: Refining the classical equivalence

Emanuele Bottazzi  E. Bottazzi, Department of Mathematics F. Casorati,
University of Pavia, Via Ferrata, 5, 27100 Pavia, Italy
<EMAIL_ADDRESS><EMAIL_ADDRESS>and  Mikhail G.
Katz  M. Katz, Department of Mathematics, Bar Ilan University, Ramat Gan
5290002 Israel<EMAIL_ADDRESS>
###### Abstract.

A refinement of the classic equivalence relation among Cauchy sequences yields
a useful infinitesimal-enriched number system. Such an approach can be seen as
formalizing Cauchy’s sentiment that a null sequence “becomes” an
infinitesimal. We signal a little-noticed construction of a system with
infinitesimals in a 1910 publication by Giuseppe Peano, reversing his earlier
endorsement of Cantor’s belittling of infinitesimals.

###### Key words and phrases:

Cauchy sequence; hyperreal; infinitesimal

##  1\. Historical background

Robinson developed his framework for analysis with infinitesimals in his 1966
book [1]. There have been various attempts either

  1. (1)

to obtain clarity and uniformity in developing analysis with infinitesimals by
working in a version of set theory with a concept of infinitesimal built in
syntactically (see e.g., [2], [3]), or

  2. (2)

to define nonstandard universes in a simplified way by providing mathematical
structures that would not have all the features of a Hewitt–Luxemburg-style
ultrapower [4], [5], but nevertheless would suffice for basic application and
possibly could be helpful in teaching.

The second approach has been carried out, for example, by James Henle in his
non-nonstandard Analysis [6] (based on Schmieden–Laugwitz [7]; see also [8]),
as well as by Terry Tao in his “cheap nonstandard analysis” [9]. These
frameworks are based upon the identification of real sequences whenever they
are eventually equal.111I.e., modulo the Fréchet filter. A precursor of this
approach is found in the work of Giuseppe Peano. In his 1910 paper [10] (see
also [11]) he introduced the notion of the end (_fine_ ; pl.  _fini_) of a
function (i.e., sequence) based upon its eventual behavior. Equality and order
between such _fini_ are defined as follows:

  * •

$\text{fine}(f)=\text{fine}(g)$ if and only if $f(n)=g(n)$ eventually;

  * •

$\text{fine}(f)<\text{fine}(g)$ if and only if $f(n)<g(n)$ eventually.

The collection

$Pe=\big{\\{}\text{fine}(f)\colon{\mathbb{N}}\stackrel{{\scriptstyle
f}}{{\rightarrow}}{\mathbb{R}}\big{\\}}$ (1.1)

extends the set of real numbers (included as constant sequences), is partially
ordered, and includes infinite and infinitesimal elements. For instance, if
$f(n)=n$, then $\text{fine}(f)>r$ for every $r\in{\mathbb{R}}$, since
eventually $f(n)>r$. Similarly, if $g(n)=n^{-1}$, then $0<\text{fine}(g)<r$
for every positive $r\in{\mathbb{R}}$, since eventually $0<g(n)<r$. Moreover,
Peano defines operations on the _fini_. For instance,
$\text{fine}(f)+\text{fine}(g)$ can be defined as $\text{fine}(f+g)$, and
$\text{fine}(f)\cdot\text{fine}(g)$, as $\text{fine}(fg)$. The construction
results in Peano’s partially ordered non-Archimedean ring $Pe$ of (1.1) with
zero divisors that extends ${\mathbb{R}}$. Commenting on Peano’s 1910
construction, Fisher notes that here

> Peano contradicts his contention of 1892, following Cantor, that constant
> infinitesimals are impossible. (Fisher [12], 1981, p. 154)

Peano’s 1910 article seems to have been overlooked by Freguglia who claims “to
put Peano’s opinion about the unacceptability of the actual infinitesimal
notion into evidence” [13, p. 145].

##  2\. Refining the equivalence relation on Cauchy sequences

The present text belongs to neither of the categories summarized in Section 1.
Rather, we propose to exploit a concept that is a household word for most of
the mathematical audience to a greater extent than either Fréchet filters or
ends of functions, namely Cauchy sequences. More precisely, we propose to
factor the classical homomorphism

$C\to{\mathbb{R}},$

from the ring $C$ of Cauchy sequences to its quotient space ${\mathbb{R}}$,
through an intermediate integral domain $D$, by refining the traditional
equivalence relation on $C$. The composition

$C\to D\to{\mathbb{R}}$

(“undoing” the refinement) is the classical homomorphism.

The classical construction of the real line ${\mathbb{R}}$ involves declaring
Cauchy sequences $u=(u_{i})$ and $v=(v_{i})$ to be equivalent if the sequence
$(u_{i}-v_{i})$ tends to zero. Instead, we define an equivalence relation
$\sim$ on $C$ by setting $u\sim v$ if and only if they actually coincide on a
_dominant_ set of indices $i$ (this would be true in particular if
$\text{fine}(u)=\text{fine}(v)$). The notion of dominance is relative to a
nonprincipal ultrafilter $\mathcal{U}$ on the set of natural numbers.222An
ultrafilter on ${\mathbb{N}}$ is a maximal collection of subsets of
${\mathbb{N}}$ which is closed under finite intersection and passage to a
superset. An ultrafilter is nonprincipal if and only if it includes no finite
subsets of ${\mathbb{N}}$. The complement of a dominant set is called
negligible. Namely, we have

$u\sim v\text{ if and only if }\\{i\in{\mathbb{N}}\colon
u_{i}=v_{i}\\}\in\mathcal{U}.$ (2.1)

We set $D=C/\\!\\!\sim$. Then a null sequence generates an infinitesimal of
$D$. By further identifying all null sequences with the constant sequence
$(0)$, we obtain an epimorphism

$\mathbf{sh}\colon D\to{\mathbb{R}},$ (2.2)

assigning to each Cauchy sequence, the value of its limit in ${\mathbb{R}}$.
It turns out that such a framework is sufficient to develop infinitesimal
analysis in the sense specified in Section 3.

##  3\. Null sequences, infinitesimals, and P-points

For the purposes of the definition below, it is convenient to distinguish
notationally between ${\mathbb{N}}$ used as the index set of sequences, and
$\omega$ used as the collection on which our filters are defined.

######  Definition 3.1.

A non-principal ultrafilter $\mathcal{U}$ on $\omega$ is called a _P-point_ if
for every partition $\\{C_{n}\colon n\in{\mathbb{N}}\\}$ of $\omega$ such that

$(\forall n\in{\mathbb{N}})\,C_{n}\not\in\mathcal{U},$

there exists some $A\in\mathcal{U}$ such that $A\cap C_{n}$ is a finite set
for each $n$.

Informally, $\mathcal{U}$ being a P-point means that every partition of
$\omega$ into negligible sets is actually a partition into _finite_ sets, up
to a $\mathcal{U}$-negligible subset of $\omega$. The existence of P-point
ultrafilters is consistent with the Zermelo–Fraenkel set theory with the Axiom
of Choice (ZFC) as is their nonexistence, as shown by Shelah; see [14]. Their
existence is guaranteed by the Continuum Hypothesis by Rudin [15].

Theorem 3.2 below originates with Choquet [16]; see Benci and Di Nasso [17,
Proposition 6.6], and the end of this section for additional historical
remarks.

Denote by $C\subseteq{\mathbb{R}}^{\mathbb{N}}$ the ring of Cauchy sequences
(i.e., convergent sequences) of real numbers, and by $D$ its quotient by the
relation (2.1).

######  Theorem 3.2.

$\mathcal{U}$ is a P-point ultrafilter if and only if $D$ is isomorphic to the
ring of finite hyperreals in ${\mathbb{R}}^{\mathbb{N}}\\!/\mathcal{U}$ where
the epimorphism sh of (2.2) corresponds to the shadow/standard part.

###### Proof.

Suppose every bounded sequence becomes Cauchy when restricted to a suitable
$\mathcal{U}$-dominant set $Y\subseteq{\mathbb{N}}$. Let
$X_{1}={\mathbb{N}},X_{2},X_{3},\ldots$ be an inclusion-decreasing sequence of
sets in $\mathcal{U}$. Define a sequence $f$ by setting $f(i)=\frac{1}{n}$ for
$i\in X_{n}\setminus X_{n+1}$. By hypothesis there is a $Y\\!\in\mathcal{U}$
such that $f$ is Cauchy on $Y$. Suppose the intersection $Y\cap(X_{n}\setminus
X_{n+1})$ is infinite for some $n$. Then there are infinitely many $i$ where
$f(i)=\frac{1}{n}$ and also infinitely many $i$ where $f(i)<\frac{1}{n+1}$
(this happens for all $i\in Y\cap X_{n+2}\in\mathcal{U}$). Such a sequence is
not Cauchy on $Y$. The contradiction shows that every intersection with $Y$
must be finite, proving that $\mathcal{U}$ is a P-point.

Conversely, suppose $\mathcal{U}$ is a P-point. Let $f$ be a bounded sequence.
By binary divide-and-conquer, we construct inductively a sequence of nested
compact segments $S_{i}\subseteq{\mathbb{R}}$ of length tending to zero such
that for each $i$, the sequence $f$ takes values in $S_{i}$ for a dominant set
$X_{i}\subseteq{\mathbb{N}}$ of indices. By hypothesis, there exists
$Y\\!\in\mathcal{U}$ such that each complement $S_{i}\setminus Y$ is finite.
Then the restriction of $f$ to the dominant set $Y$ necessarily tends to the
intersection point $\bigcap_{i\in{\mathbb{N}}}S_{i}\in{\mathbb{R}}$.

Benci and Di Nasso give a similar argument relating _monotone_ sequences and
selective ultrafilters in [17, p. 376]. ∎

If $\mathcal{U}$ is not a P-point, the natural monomorphism
$D\to{\mathbb{R}}^{\mathbb{N}}\\!/\mathcal{U}$ will not be onto the finite
part of the ultrapower ${\mathbb{R}}^{\mathbb{N}}\\!/\mathcal{U}$.

Let $I\subseteq D$ be the ideal of infinitesimals, and denote by $I^{-1}$ the
set of inverses of nonzero infinitesimals.

######  Corollary 3.3.

If $\mathcal{U}$ is a P-point ultrafilter, then the hyperreal field
${\mathbb{R}}^{\mathbb{N}}\\!/\mathcal{U}$ decomposes as a disjoint union
$D\sqcup I^{-1}$.

Here every element of $I^{-1}$ can be represented by a sequence tending to
infinity. In this sense, Cauchy sequences of reals (together with a refined
equivalence relation) suffice to construct the hyperreal field
${\mathbb{R}}^{\ast}={\mathbb{R}}^{\mathbb{N}}\\!/\mathcal{U}$ and enable
analysis with infinitesimals. Thus, if $f$ is a continuous real function on
$[0,1]$, its extension $f^{\ast}$ to the hyperreal interval
$[0,1]^{\ast}\subseteq{\mathbb{R}}^{\ast}$ maps the equivalence class of a
Cauchy sequence $(u_{n})$ to the equivalence class of the Cauchy sequence
$(f(u_{n}))$. The derivative of $f$ at a real point $x\in[0,1]$ is the shadow

$\mathbf{sh}\left(\frac{f^{\ast}(x+\epsilon)-f^{\ast}(x)}{\epsilon}\right)$

for infinitesimal $\epsilon\not=0$, while the integral $\int_{0}^{1}f(x)dx$ is
the shadow of the sum $\sum_{i=1}^{\mu}f^{\ast}(x_{i})\epsilon$ where the
$x_{i}$ are the partition points of $[0,1]^{\ast}$ into (an infinite integer)
$\mu$ subintervals, and $\epsilon=\frac{1}{\mu}$. For the definition of
infinite Riemann sums see Keisler [18].

We elaborate on the history of the problem. According to Cleave’s hypothesis
[19], every infinitesimal $\varepsilon\in{\mathbb{R}}^{\ast}$ is determined by
a sequence of real numbers tending to zero. Cutland et al. [20] showed that
the Cleave hypothesis requires $\mathcal{U}$ to be a P-point ultrafilter.
Benci and Di Nasso [17, p. 376] developed the problem further by relating the
Cleave hypothesis to the so-called selective ultrafilters and monotone
sequences.

##  4\. Concluding remarks

1. Our approach can be seen as a formalisation of Cauchy’s sentiment that a null sequence “becomes” an infinitesimal, while a sequence tending to infinity becomes an infinite number; see e.g., Bair et al. ([21], 2020).

2. A perspective on hyperreal numbers via Cauchy sequences has value as an educational tool according to the post [22]. Formally, one could start with the full ring of sequences (Cauchy or not), and form the traditional quotient modulo a nonprincipal ultrafilter, to obtain the standard construction of the hyperreal field where every null sequence generates an infinitesimal (see e.g., [18, p. 913], [23]; but there may be additional infinitesimals). However, pedagogical experience shows that the full ring of sequences sometimes appears as a nebulous object to students who are not yet familiar with the ultrafilter construction (see e.g., the discussion at [22]); starting with more familiar objects such as Cauchy sequences builds upon the students’ previous experience, and may be more successful in facilitating intuitions about infinitesimals.

3. The refinement of the equivalence relation on Cauchy sequences (modulo the existence of P-points) enables one to obtain the (finite) hyperreals as the set of equivalence classes of Cauchy sequences, and both equivalence classes and Cauchy sequences are household concepts for any mathematics sophomore. We still use ultrafilters; however, in this setting, they are conceptually similar to maximal ideals, routinely used in undergraduate algebra.

4. The distinction between procedures and ontology is a key related issue. Historical mathematical pioneers from Fermat to Cauchy applied certain procedures in their mathematics, and while modern set-theoretic _ontology_ appears to be beyond their conceptual world, many of the _procedures_ of modern mathematics are not (see [24] for a more detailed discussion). Arguably the procedures in modern infinitesimal analysis are closer to theirs than procedures in modern Weierstrassian analysis. Note that the mathematical pioneers would have been just as puzzled by Cantorian set theory as by ultrafilters. For example, Leibniz would have likely rejected Cantorian set theory as incoherent because contrary to the part-whole axiom; see [25].

5. Bertrand Russell accepted, as a matter of ontological certainty, Cantor’s position concerning the non-existence of infinitesimals. For an analysis of a dissenting opinion by contemporary neo-Kantians see [26].

6. Robinson’s framework for analysis with infinitesimals is the first (and currently the only) framework meeting the Klein–Fraenkel criteria for a successful theory of infinitesimals in terms of an infinitesimal treatment of the mean-value theorem and an approach to the definite integral via partitions into infinitesimal segments; see [27].

7. Arguably, Robinson’s framework is the most successful theory of infinitesimals in applications to natural science, probability, and related fields; see [28] as well as [29], [30].

8. Robinson explained his choice of the name for his theory as follows: “The resulting subject was called by me Non-standard Analysis since it involves and was, in part, inspired by the so-called Non-standard models of Arithmetic whose existence was first pointed out by T. Skolem” [1, p. vii].

9. Currently there are two popular approaches to Robinson’s mathematics: model-theoretic and axiomatic/syntactic. Since Skolem’s construction [31] did not use either the Axiom of Choice or ultrafilters, it is natural to ask whether one can develop an approach to analysis with infinitesimals, meeting the Klein–Fraenkel criteria, that does not refer to the notion of an ultrafilter at all. The answer is affirmative and was provided in [3] via an internal axiomatic approach. Hrbacek and Katz [32] present a construction of Loeb measures and nonstandard hulls in internal set theories. The effectiveness of infinitesimal methods in analysis has recently been explored in reverse mathematics; see e.g., Sanders [33].

## References

  * [1] Abraham Robinson, _Non-standard analysis_ , North-Holland Publishing, Amsterdam, 1966.
  * [2] Vladimir Kanovei and Michael Reeken, _Nonstandard analysis, axiomatically_. Springer Monographs in Mathematics. Springer-Verlag, Berlin, 2004.
  * [3] Karel Hrbacek and Mikhail Katz, _Infinitesimal analysis without the Axiom of Choice_ , Ann. Pure Appl. Logic 172 (2021), no. 6, 102959. https://doi.org/10.1016/j.apal.2021.102959, https://arxiv.org/abs/2009.04980
  * [4] Edwin Hewitt, _Rings of real-valued continuous functions. I_ , Trans. Amer. Math. Soc. 64 (1948), 45–99.
  * [5] Wilhelmus Luxemburg, _Nonstandard analysis. Lectures on A. Robinson’s Theory of infinitesimals and infinitely large numbers_ , Pasadena: Mathematics Department, California Institute of Technology, second corrected ed., 1964.
  * [6] James Henle, _Non-nonstandard analysis: real infinitesimals_ , The Mathematical Intelligencer 21 (1999), no. 1, 67–73.
  * [7] Curt Schmieden and Detlef Laugwitz, Eine Erweiterung der Infinitesimalrechnung. _Math. Z_. 69 (1958), 1–39.
  * [8] Detlef Laugwitz, _Curt Schmieden’s approach to infinitesimals. An eye-opener to the historiography of analysis_ , Reuniting the antipodes—constructive and nonstandard views of the continuum (Venice, 1999), 127–142, Synthese Lib., 306, Kluwer Acad. Publ., Dordrecht, 2001.
  * [9] Terence Tao, _A cheap version of nonstandard analysis_ (2012). https://terrytao.wordpress.com/2012/04/02/a-cheap-version-of-nonstandard-analysis
  * [10] Giuseppe Peano, _Sugli ordini degli infiniti_ , Atti della Reale Accademia dei Lincei: Rendiconti, 1910, s. 5, v. 19, pp. 778–781. Repinted in [11], pp. 359–362.
  * [11] Giuseppe Peano, _Opere Scelte_ , Volume 1, Edizioni Cremonese, Roma, 1957.
  * [12] Gordon Fisher, _The infinite and infinitesimal quantities of du Bois-Reymond and their reception_ , Arch. Hist. Exact Sci. 24 (1981), no. 2, 101–163.
  * [13] Paolo Freguglia, _Peano and the debate on infinitesimals_ , Philosophia Scientiæ25 (2021), no. 1, 145–156.
  * [14] Edward Wimmers, _The Shelah P-point independence theorem_ , Israel J. Math. 43 (1982), no. 1, 28–48.
  * [15] Walter Rudin, _Homogeneity problems in the theory of Čech compactifications_ , Duke Math. J. 23 (1956), 409–419.
  * [16] Gustave Choquet, _Deux classes remarquables d’ultrafiltres sur ${\mathbb{N}}$_, Bull. Sc. Math. 92 (1968), 143–153.
  * [17] Vieri Benci and Mauro Di Nasso, _Alpha-theory: an elementary axiomatics for nonstandard analysis_ , Expo. Math. 21 (2003), no. 4, 355–386.
  * [18] H. Jerome Keisler, _Elementary Calculus: An Infinitesimal Approach, Second Edition_ , Prindle, Weber and Schmidt, Boston, 1986. See http://www.math.wisc.edu/~keisler/calc.html
  * [19] John Cleave, _Cauchy, convergence and continuity_ , British J. Philos. Sci. 22 (1971), 27–37.
  * [20] Nigel Cutland, C. Kessler, Ekkehard Kopp, and David Ross, _On Cauchy’s notion of infinitesimal_ , British J. Philos. Sci. 39 (1988), no. 3, 375–378.
  * [21] Jacques Bair, Piotr Błaszczyk, Elías Fuentes Guillén, Peter Heinig, Vladimir Kanovei, and Mikhail Katz, _Continuity between Cauchy and Bolzano: Issues of antecedents and priority_ , British Journal for the History of Mathematics 35 (2020), no. 3, 207–224. https://doi.org/10.1080/26375451.2020.1770015, https://arxiv.org/abs/2005.13259
  * [22] Rivers McForge, _Ultraproduct construction: are finite hyperreals just a thinly disguised version of Cauchy sequences?_ , https://math.stackexchange.com/q/3897109 (2020).
  * [23] Piotr Błaszczyk and Joanna Major, _Calculus without the concept of limits_. _Annales Universitatis Paedagogicae Cracoviensis. Studia ad Didacticam Mathematicae Pertinentia_ VI (2014), 19–38. https://didacticammath.up.krakow.pl/article/view/3654
  * [24] Piotr Błaszczyk, Vladimir Kanovei, Karin Katz, Mikhail Katz, Semen Kutateladze, and David Sherry, _Toward a history of mathematics focused on procedures_ , Foundations of Science 22 (2017), no. 4, 763–783. http://doi.org/10.1007/s10699-016-9498-3, https://arxiv.org/abs/1609.04531
  * [25] Jacques Bair, Piotr Błaszczyk, Robert Ely, Mikhail Katz, and Karl Kuhlemann, _Procedures of Leibnizian infinitesimal calculus: An account in three modern frameworks_ , British Journal for the History of Mathematics 36 (2021), no. 2. https://doi.org/10.1080/26375451.2020.1851120, https://arxiv.org/abs/2011.12628
  * [26] Thomas Mormann and Mikhail Katz, _Infinitesimals as an issue of neo-Kantian philosophy of science_ , HOPOS: The Journal of the International Society for the History of Philosophy of Science 3 (2013), no. 2, 236-280. http://doi.org/10.1086/671348, https://arxiv.org/abs/1304.1027
  * [27] Vladimir Kanovei, Karin Katz, Mikhail Katz, Thomas Mormann, _What makes a theory of infinitesimals useful? A view by Klein and Fraenkel_ , Journal of Humanistic Mathematics 8 (2018), no. 1, 108–119. http://scholarship.claremont.edu/jhm/vol8/iss1/7, https://arxiv.org/abs/1802.01972
  * [28] Emanuele Bottazzi, Vladimir Kanovei, Mikhail Katz, Thomas Mormann, and David Sherry, _On mathematical realism and the applicability of hyperreals_ , Mat. Stud. 51 (2019), no. 2, 200–224. http://doi.org/10.15330/ms.51.2.200-224, https://arxiv.org/abs/1907.07040
  * [29] Emanuele Bottazzi and Mikhail Katz, _Infinite lotteries, spinners, and the applicability of hyperreals_ , Philosophia Mathematica 29 (2021), no. 1, 88–109. https://doi.org/10.1093/philmat/nkaa032, https://arxiv.org/abs/2008.11509
  * [30] Emanuele Bottazzi and Mikhail Katz, _Internality, transfer, and infinitesimal modeling of infinite processes_ , Philosophia Mathematica 29 (2021), no. 2. https://doi.org/10.1093/philmat/nkaa033, https://arxiv.org/abs/2008.11513
  * [31] Thoralf Skolem, _Über die Unmöglichkeit einer vollständigen Charakterisierung der Zahlenreihe mittels eines endlichen Axiomensystems_ , Norsk Mat. Forenings Skr., II. Ser., no. 1/12 (1933), 73–82.
  * [32] Karel Hrbacek and Mikhail Katz, _Constructing nonstandard hulls and Loeb measures in internal set theories_ (in preparation).
  * [33] Sam Sanders, _The unreasonable effectiveness of nonstandard analysis_ , J. Logic Comput. 30 (2020), no. 1, 459–524.