# Random sequential adsorption of aligned rectangles with two discrete
orientations: Finite-size scaling effects

Luca Petrone  via B. Cesana 6, 20132 Milano, Italy  Nikolai Lebovka
Laboratory of Physical Chemistry of Disperse Minerals, F. D. Ovcharenko
Institute of Biocolloidal Chemistry, NAS of Ukraine, Kyiv 03142, Ukraine
Michał Cieśla  Institute of Theoretical Physics, Jagiellonian University,
30-348 Kraków, Łojasiewicza 11, Poland

###### Abstract

We study saturated packings produced according to random sequential adsorption
(RSA) protocol built of identical rectangles deposited on a flat, continuous
plane. An aspect ratio of rectangles is defined as the length-to-width ratio,
$f=l/w$. The rectangles have a fixed unit area (i.e., $l\times w=1$), and
therefore, their shape is defined by the value of $f$ ($l=\sqrt{f}$ and
$w=1/\sqrt{f}$). The rectangles are allowed to align either vertically or
horizontally with equal probability. The particles are deposited on a flat
square substrate of side length $L$ (measured in units of particle length,
$L\in[20,1000]$) and periodic boundary conditions are applied along both
directions. The finite-size scaling effects are characterized by a scaled
anisotropy defined as $\alpha=l/L=\sqrt{f}/L$. We showed that the properties
of such packings strongly depend on the value of aspect ratio $f$ and the most
significant scaling effects are observed for relatively long rectangles when
$l\geq L/2$ (i.e. $\alpha\geq 0.5$). It is especially visible for the mean
packing fraction as a function of the scaled anisotropy $\alpha$. The kinetics
of packing growth for low to moderate rectangle anisotropy is to be governed
by $\ln t/t$ law, where $t$ is proportional to the number of RSA iterations,
which is the same as in the case of RSA of parallel squares. We also analyzed
global orientational ordering in such packings and properties of domains
consisting of a set of neighboring rectangles of the same orientation, and the
probability that such domain forms a percolation.

Keywords: random sequential adsorption; packing of aligned rectangles;
kinetics of packing growth; percolations

##  1 Introduction

Random sequential adsorption (RSA) is one of the protocols used for generating
random packings. The next particle with a random position and orientation is
added to the packing only if it does not intersect with any of the previously
deposited objects. Otherwise, it is removed and abandoned. The added particles
do not change positions and orientations. The packing generation finishes when
there is no place large enough to add the next object, and such packing is
called saturated. Although the first application of the RSA protocol dates
from 1939 when Flory studied the attachment of blocking groups on a linear
polymer chain [1], RSA owes its name and popularity to Feder, who noticed that
such packings resemble monolayers formed in irreversible adsorption processes
[2]. Since then RSA become an important tool in the modeling of adsorption
monolayers [3, 4], but, because of its simplicity, it attracted a lot of
attention from theoretical studies devoted to properties of random media [5,
6]. Besides the protocol seeming to be very simple, there are not many
analytical results, especially for continuous packings. For example, a mean
saturated packing fraction, which is the most important property of packing,
was determined analytically only in the case of RSA of segments on a one-
dimensional line [7] and equals $0.7475979202...$. The same parameter for two-
dimensional RSA packing built of parallel squares was determined numerically
only and equals $0.562009(4)$ [8]. The situation changes when rectangles’
orientations are arbitrary. For unoriented squares, the packing fraction
equals $0.527640(18)$ [9, 10], and for unoriented rectangles, it reaches the
maximum at $0.549632(17)$ for a side length ratio of $1.492(22)$ and then
decreases monotonically with the growth of side length ratio [11, 9]. It is
worth noting, that the highest RSA packing fraction for this kind of system
was recently reported for horizontally or vertically aligned rectangles with
random side length ratio but constant surface area [12, 13]. There the packing
fractions were up to $0.7$, depending on the probability distribution used for
choosing rectangles’ anisotropy.

Another property is the kinetics of packing growth. Generally, it is described
by the power law

$\theta-\theta(t)\sim t^{-\frac{1}{d}},$ (1)

where $\theta(t)$ is the packing fraction after $t$ trials of adding a new
particle to the packing. Here, $\theta\equiv\theta(t\to\infty)$ is the
saturated packing fraction [2, 14, 15]. The parameter $d$ is related to the
number of particle degrees of freedom [16, 17]. Among others, such behavior
was also reported for RSA of freely oriented rectangles of fixed aspect ratio
[11] and for horizontally or vertically aligned ones with random aspect ratio
but fixed area [12, 13]. On the other hand, for RSA of parallel squares, the
kinetics of packing fraction takes the form [8]

$\theta-\theta(t)\sim\frac{\ln(t)}{t},$ (2)

It is worth noting, that for lattice RSA the packing growth kinetics follows
another, exponential law

$\theta-\theta(t)\sim\exp\left(-\frac{t}{\sigma}\right),$ (3)

where $\sigma$ depends on lattice details [18].

The third aspect of random arrangements of anisotropic shapes like rectangles
is their tendency to form orientationally oriented clusters. Typically in RSA
packings, the range of orientational ordering is very short [9, 19, 20, 21],
however, for very elongated molecules it can be significant [17], and
orientationally oriented domains can appear [22]. It appears that especially
in lattice packings, where orientations are discrete, one can observe long-
range connectivity, which could lead to percolation transition, typically
observed and studied for RSA on lattices [23, 24, 25, 26, 27, 28, 29].

To address all these phenomenons, we focus on the numerical study of RSA of
rectangles placed on a continuous and flat plane that have two possible
orientations: horizontal and vertical ones, but, in contrast to recent studies
[12, 13], fixed aspect ratio. Thus, the studied packings could allow us to
effectively address all the abovementioned properties at the border between
lattice and continuous packings built of oriented and unoriented elongated
particles. Additionally, we also studied all these properties in the limit of
very long elongations that makes the length of the longer rectangle side
comparable with packing size.

##  2 Algorithm

The algorithm for generating strictly saturated packing built of horizontally
and vertically oriented rectangles bases on the concept introduced by Wang
[30] of tracing regions large enough to hold a next shape. In order to
implement it, we divide the whole packing area into squares, and identified,
which of them are available for further deposition. Each deposited rectangle
excludes the areas shown in Fig. 1

Figure 1: Area blocked by the deposited black rectangle. The red region is
blocked for placing the center of a horizontally aligned rectangle and the
blue one is for the center of a vertically aligned rectangle. The whole
packing is divided into smaller squares. A square is available for further
deposition of a rectangle of a given orientation if it is not fully covered by
the corresponding blocked area. The available squares are outside the bold
black line.

Because there are two possible orientations we have two separate lists for
these squares. One for the possible placing of horizontally aligned rectangles
and the other for vertically aligned ones. If an area is completely covered by
a union of the exclusion zones of deposited rectangles, it is not available
for further depositions and is removed from the corresponding list. Thus, the
available squares approximate regions where centers of subsequent rectangles
can be placed. After a certain number of trials of adding a new particle to
the packing the available squares are divided - each one into four smaller
squares of a two times smaller side length, and the new squares are reexamined
if they are still available. It allows for improving the approximation of
available regions.

In detail, the crucial part of the algorithm that determines if the square is
available or not consists of a sequential evaluation of the points described
below.

Figure 2: Various relative positions of analyzed square (with black sides) and
excluded regions of neighboring rectangles. In cases a), c), and e), the
square is fully covered and can be removed from the list of available squares.
In cases b) and d), it contains the area where it is possible to place the
center of the next rectangle.

  1. 1.

Find neighboring rectangles to the current square. A rectangle is neighboring
if its excluded region overlaps with the square.

  2. 2.

If all of the four vertices of the square are inside an excluded region of a
single rectangle, then the square is fully covered (Fig. 2a), and is removed
from the corresponding list.

  3. 3.

Otherwise, if any one of the square vertices is not covered by any neighboring
rectangle excluded region, the square is not fully covered (Fig. 2b), and it
stays on the list of available squares.

  4. 4.

Otherwise, if all square edges are completely covered by two or three
neighboring rectangles excluded regions, the square is fully covered (Fig.
2c), and it is removed from the corresponding list. To check if the edge is
covered we used Klee’s algorithm [31].

  5. 5.

Otherwise, we know that the square may be covered by at least four excluded
regions. Even if all its edges are covered, the square can still contain
uncovered area (Fig. 2d). To check it, the coordinates of the intersection
points of the excluded regions are calculated. If each intersection point of
any pair of the excluded regions is covered by any other region, the square is
fully covered (Fig. 2e, and is removed from the corresponding list. Otherwise,
it is not fully covered and it stays on the list.

###  2.1 Numerical details

Rectangles with length $l$, width $w$, and unit area (i.e. $l\times w=1$) are
deposited on a flat square substrate of side length $L\in[30,1000]$. Periodic
boundary conditions are used to decrease finite size effects [32]. For a given
packing size, typically $100$ independent packings were generated. The
position of the deposited figure is drawn according to the uniform probability
distribution. The shape of a rectangle is determined by the aspect ratio
defined as the length-to-width ratio, $f=l/w$. Therefore, we have $l=\sqrt{f}$
and $w=1/\sqrt{f}$. Horizontal and vertical orientations are equally probable.
For a given $f$ and $L$, the scaled anisotropy was defined as

$\alpha=\frac{l}{L}=\frac{\sqrt{f}}{L}.$ (4)

To speed up the overlap detection of rectangles we implemented a neighbor grid
that covers the whole packing. The grid is built of square cells. Each cell
contains a list of already deposited rectangles with the center inside it. The
cell size is $2l\times 2l$, thus, the rectangle can only intersect with
another shape from the same cell or from one of its eight nearest neighbors.
The newly deposited rectangle finds all the cells it covers and then checks
overlap with all the rectangles stored in these cells’ lists.

After the initial filling of packing with rectangles, when the number of
consecutive unsuccessful trials of placing a new figure reaches a threshold
value (we used $10^{3}$), we initiate the square lists described in the
previous section, and further attempts are restricted only to available
squares.

It should be noted that the aspect ratio $f$ should not exceed $L^{2}$ (i.e.
$\alpha\leq 1$), to avoid self-overlapping due to periodic boundary
conditions.

##  3 Results

Fragments of example packings are shown in Fig. 3.

Figure 3: Example saturated packings of $L=20$ build of rectangles of aspect
ratio $f=1.6,3.0$, and $10.0$ for left, middle and right panel, respectively.
Different colors of rectangles are to better distinguish them visually.

The properties of obtained packing are presented and discussed in the
following sections.

###  3.1 Mean saturated packing fraction

The mean saturated packing fraction $\theta$ for small and moderate aspect
ratio $f$ and sufficiently large $L$ ($=1000$) is shown in Fig. 4.

Figure 4: The mean saturated packing fraction as a function of the aspect
ratio $f$ for several values of packing size $L$. Points correspond to
measured values with error bars denoting their standard deviation. Lines are
to guide the eye. The inset shows the magnification near the maximum. The
solid line is the least squares fit to the data for $L=1000$:
$\theta=0.60254-[0.23(f-1.57)]^{2}$.

First, the mean saturated packing fraction of squares aligned in parallel is
$0.562019\pm 0.000021$ and it agrees with the earlier report [8, 33]. The
packing fraction grows with the rectangle anisotropy up to the value of
$\theta_{max}=0.60252694\pm 0.000019$ reached for $f=1.56$. These values were
calculated by averaging saturated packing fractions of $100$ independently
generated packings of size $L=1000$. The position of the maximum and its value
does not depend on the size of the packing, which means that finite-size
effects do not affect presented results. It is quite reasonable for the
selected value of $f$ ($f\leq 100$ and $L\geq 200$), i.e. very small values of
scaled anisotropy $\alpha$ ($\leq 0.05$). The presence of this maximum at low
to moderate sides-ratio is the effect of competition between two factors. The
first is the tendency to place figures in parallel at the late stages of
packing generation which promotes parallel alignment and favors denser
configuration. On the other hand, anisotropy spoils the packing density at the
beginning of packing generation because the mean area blocked by a single
shape grows with its sides-ratio. Therefore there is an optimal value of
anisotropy for which packing fraction is maximized [11]. This effect was
observed for a number of packings built of anisotropies objects [34, 21, 35,
36]. Interestingly, for RSA of unoriented rectangles, the maximum packing
fraction was observed for sides-ratio of $1.492\pm 0.022$ [9], which is a
close, but slightly smaller value than the one observed here. It is probably
due to only two possible orientations of a rectangle in the packing, thus, the
larger anisotropy does not harm the denser configuration as much as for
unoriented shapes.

For larger rectangle side-ratio, the packing fraction decreases, similarly as
for RSA of unoriented anisotropic shapes [11, 9, 35, 34]. However, for larger
values of the scaled anisotropy $\alpha$ (Eq. (4)), when the particle length
$l$ is comparable with the system size $L$, the orientation of the first-
placed rectangle determines orientations of all the rest rectangles as there
is no possibility of placing perpendicular figures without intersection with
the first one. Thus, the process is effectively reduced to one-dimensional
RSA, mentioned in the introduction section, for which the packing fraction is
$0.7475979202...$ [7]. Therefore for finite packings, as in this study, we
expect that the saturated packing fraction should begin to grow for some large
value of $f$. To study this phenomenon we used relatively small packings
because the computational complexity of the simulation algorithm described in
Sec. 2 grows rapidly with rectangle anisotropy. The obtained results are shown
in Fig. 5.

Figure 5: The mean saturated packing fraction as a function of the aspect
ratio $f$ for smaller packings and the whole possible range of anisotropies.
Dots are data measured from simulations and lines are to guide the eye. Inset
shows the same data but rescaled - the control parameter on the horizontal
axis is the ratio of the longer rectangle side length and packing side length.
The dotted line corresponds to the saturated packing fraction in one dimension
$\theta=0.7476...$

Although the packing size is small, the dependence of packing fraction on
rectangle anisotropy for small and moderate $f$ is the same as for larger
packings. However here, the packing fraction starts to grow when the longer
rectangle side length exceeds one-third of the packing side length. The local
minimum packing fraction there is around $\theta=0.5$ and depends on the
packing size - for smaller packings, this minimum is shallower. The growth is
due to better filling the space of two rectangles laying one after the other
or one above the other, and it continues up to the scaled anisotropy
$\alpha=0.5$ and $\theta\approx 0.55$. When this limiting value is exceeded,
the sudden drop is observed to $\theta\approx 0.45$ because now two rectangles
cannot be placed one after the other or one above the other, because they will
overlap due to periodic boundary conditions. If there was only one possible
orientation, the packing fraction would drop to half of the saturated packing
fraction for one-dimensional RSA, but the possibility of placing figures
perpendicular raises the packing density. It is worth noting, that the
observed densities around $\alpha\approx 0.5$ are weakly or not dependent on
packing side length $L$. For larger anisotropies, we observe monotonic growth
of packing fraction, and for scaled anisotropy $\alpha\to 1$, as expected, we
restore the saturated density of one-dimensional RSA packings.

###  3.2 Kinetics of packing growth

Kinetics of packing growth was studied in order to determine whether it obeys
the power (1), extended logarithmic (2), or exponential (3) law. The first one
is known to be valid for most cases of RSA [37] while the second was confirmed
for RSA of parallel squares [8]. The third one, as mentioned in the
Introduction, is observed for RSA on lattices, where positions of packed
objects are restricted to a finite (or countable in the limit of infinite
packing size) number of places. The comparison of these theoretical laws for
the exemplary data taken from $100$ independent packings at the limit of large
$t$ for $L=100$ and $f\in[1,10000]$, which corresponds to $\alpha\in[0.01-1]$
is shown in Fig. 6.

Figure 6: The kinetics of packing growth for $L=100$ and various scaled
anisotropy $\alpha$. All plots show the same data, but presented in a
different way to show differences between theoretical laws (1) in (a), (2) in
(b), and (3) in (c). If the law is fulfilled the data should form a straight
line for large enough $t$ (small $1/t$). Data for packings built of rectangles
of the highest anisotropies were drawn using dashed lines for convenience.
Panel (d) shows the dependence of linear fit accuracy for the data shown in
panel (b). The dashed line corresponds to ideal linear dependence. The data
was taken for $L=100$ and $100$ independently generated saturated packings.

The exponential law (3) does not fit well for any anisotropy, as the
dependence of $\theta-\theta(t)$ does not form a straight line – see Fig. 6
(c). This is expected since such kinetic dependence has been observed so far
only in lattice packings. On the other hand, for large enough $t$ all the data
fit well to the power law (1) – see Fig. 6 (a). The fit correlation
coefficient exceeds $0.99$. This is because, for large but finite $t$, which
is the case in computer simulations, the $1/t^{d}$ function is hard to
distinguish from the $\ln t/t$ if the exponent $d$ is slightly larger than
$1$. On the other hand, in Fig. 6 (b), we can see that there are straight
lines for all but the three most extreme elongations of rectangles, for which
we expected a power law kinetics, as due to finite size effects, they
correspond to one-dimensional RSA [15, 14]. To further support this
observation we studied the dependence on the square of Pearson’s coefficient
of the linear fit for data from panel (b) $r$ on the scaled anisotropy of
rectangle $\alpha$. The fitting was done for $ln(t)/t<0.1$. For almost all
anisotropies the dependence is nearly linear as $(1-r^{2})\approx 0$. The more
significant deviations are observed, as expected, for the largest
anisotropies, and interestingly, for scaled anisotropy $\alpha$ corresponding
to $f=2$. The latter case could be the result of a quite large range of
fitting because the linear dependence of $\theta-\theta(t)$ on $\ln(t)/t$ for
parallel squares is reported for $\ln(t)/t<0.002$ only [8]. In summary, we
conclude that in the general case ($\alpha\ll 1$), the RSA kinetics for
packings built of rectangles placed on a two-dimensional plane and aligned
horizontally and vertically only is governed by the logarithmic law (2).

###  3.3 Orientational order

Orientations in RSA packings are random, thus typically there is no global
orientational order. On the other hand, locally anisotropic figures tend to
align in parallel due to the smaller excluded surface of such configuration
[21, 17, 20]. However, for relatively large values of the scaled anisotropy
$\alpha$ (Eq. (4)), when the values $l$ and $L$ are comparable, all the
rectangles have to be aligned in the same direction because perpendicular
alignment is impossible due to crossing. For slightly smaller anisotropies if
the first few rectangles happen to be in the same orientation then they cause
hindrance to the deposition of rectangles in the orthogonal direction, all the
following deposited rectangles are forced to be in the same direction. To
study this phenomenon, we define an order parameter, as:

$S=\left|\frac{n_{h}-n_{v}}{n_{h}+n_{v}}\right|,$ (5)

where $n_{h}$ and $n_{v}$ are, respectively, the number of rectangles in the
horizontal and vertical direction. So, $S$ is equal to $0$ for a packing where
the number of the two orientations of the rectangles is the same and $1$ if
only one of them is present (fully ordered packing). It appears that $S$
depends mostly on the value of scaled anisotropy $\alpha$ (Eq. (4)) and does
not depend on particular values of the packing sizes $L$ and rectangles sides-
ratio $f$ – see Fig. 7.

Figure 7: Orientational order parameter $S$ as a function of scaled anisotropy
$\alpha$ (Eq. (4)) for different values of $L$. Different colors and shapes of
points correspond to different values of $L$. The value of $S$ for each set of
parameters $(\alpha,L)$ was averaged over $100$ independent packings. The
solid line is to guide the eye.

As expected, for small $\alpha$, there is no significant preference of one
alignment to the other, but with the growth of the relative anisotropy,
packings become more orientationally ordered. For $\alpha\to 1$ almost all
rectangles in a packing share the same orientation.

###  3.4 Percolating clusters

We defined a cluster or a domain as a set of identically oriented rectangles
that are so close that no other figures can be placed between them, which
means that the edge-to-edge distance measured along the horizontal or vertical
axis is not larger than the shorter side of a rectangle. This definition is in
analogy with one for $k$-mers in a square lattice [25, 29], and can be
extended to the case of non-saturated packings on a continuous plane. Then the
edge-to-edge distance between neighboring shapes has to be smaller than a
given arbitrary value. Thus, the domain sizes depend on it [38]. The example
saturated packings divided into such clusters are shown in Fig. 8.

Figure 8: Saturated packing divided into domains. Rectangles in a cluster have
the same color. On the left, there is no percolating domain while on the
right, the percolating cluster is the blue one. These example packings were
generated for $L=100$ and $f=10$ ($\alpha\approx 0.013$).

Here, we are focused on the probability of percolation, i.e., the existence of
a cluster that splits the packing into two separated parts – see Fig. 8. The
results are shown in Fig. 9.

Figure 9: Percolation probability dependence on the scaled anisotropy $\alpha$
(Eq. (4)) for various packing sizes. Inset shows the same dependence but only
on anisotropy $f$ and using a different horizontal scale. Solid lines are to
guide the eye. For each set of parameters $f$ and $L$ the probability was
estimated by studying $100$ independently generated saturated packings, thus
the relative statistical error is of the order of $10\%$.

Interestingly, percolations are highly probable for both: very small and very
large rectangles’ anisotropy. For squares, because packing is saturated, all
the particles are in one domain, thus the percolation always is observed. It
does not change for small anisotropy ($f$ only slightly higher than $1$), but
then a majority of the figures belong to one of two large domains consisting
of horizontally or vertically aligned shapes. At relatively small values of
rectangle aspect ratio $f$ ($<10$) the percolation probability drops down with
the growth of $f$. The minimums in $P(f)$ dependencies are observed for all
values of $L$ at approximately the same value of $f$ ($\approx 10$). The depth
of this minimum increases with $L$, which reflects the manifestation of the
finite size effects in percolation. Particularly, for large enough values of
$L$ ($L=200$) the minimum probability drops down practically to $0$ (Fig. 9).
It is worth noting, that the orientational order propagation in RSA packings
built of anisotropic, unoriented figures is typically limited to very short
distances – see e.g. [9]. Thus, in general, the sizes or orientationally
oriented domains are small and will not form a percolating cluster, which
explains the minimum of the percolation probability observed for small
$\alpha$. On the other hand, in the limit of $\alpha\to 1$, when the length of
the rectangle $l$ becomes comparable to the system size $L$, the packing
becomes ordered (see Fig. 7), so the majority of shapes are parallel and the
probability that they will form one big cluster raises and therefore
percolating probability $P\to 1$.

##  4 Conclusions

Finite-size scaling behavior of the density $\theta$ of saturated RSA packings
built of horizontally or vertically aligned rectangles is mainly determined by
the value scaled anisotropy $\alpha$ defined by Eq. (4). In the limit of
$\alpha\to 0$ (at a relatively small value of aspect ratio $f$ of rectangles
and very large size of packings $L$) the finite size scaling is practically
absent. The maximum value of $\theta=0.60252694\pm 0.000019$ at $f\approx
1.56$. The more complicated behavior of $\theta(\alpha)$ is observed at the
finite values of $\alpha$ (Fig. 5). It evidently reflects the manifestation of
finite-size scaling effects. Particularly, in the limit $\alpha\to 1$ (i.e. at
$l\to L$) the problem reduces to RSA in one dimension and the packing fraction
rises up to 0.7476… [7]. The kinetics of packing growth fits well with the
extended logarithmic law (Eq. (2)) predicted [15] and observed [8] in the case
of parallelly aligned squares. Because of only two possible orientations of
rectangles, the packing can exhibit global orientational order that grows with
scaled anisotropy $\alpha$. The analysis of rectangles connectivity in
saturated packing is performed via the calculation of percolation probability
$P$ at different values of $\alpha$. The data reveals the large values of
$P\approx 1$ in the limits of $\alpha\to 0$ and $\alpha\to 1$. The minimum of
$P$ at some intermediate length-to-width ratio ($f\approx 10$) is detected.

In general, it is worth noticing that in some aspects the behavior of the
system is fully determined by $f$, e.g., the position of the first maximum of
packing fraction or the minimum of percolation probability, while other
characteristics are governed by $\alpha=\sqrt{f}/L$, like for example the
transition saturation packing fraction or the global orientational order. This
reflects the manifestation of percolation finite-size scaling effects.

## Acknowledgments

Part of the numerical simulations was carried out with the support of the
Interdisciplinary Center for Mathematical and Computational Modeling (ICM) at
the University of Warsaw under grant no. GB76-1. N.L. acknowledges partial
funding from the NAS of Ukraine, Project No. 0123U101080.

## References

## References

  * [1] Flory P J 1939 Journal of the American Chemical Society 61 1518–1521
  * [2] Feder J 1980 Journal of Theoretical Biology 87 237–254
  * [3] Kubala P, Batys P, Barbasz J, Weroński P and Cieśla M 2022 Advances in Colloid and Interface Science 306 102692 ISSN 0001-8686 URL https://www.sciencedirect.com/science/article/pii/S000186862200094X
  * [4] Talbot J, Tarjus G, Van Tassel P and Viot P 2000 Colloids and Surfaces A: Physicochemical and Engineering Aspects 165 287–324
  * [5] Evans J W 1993 Reviews of Modern Physics 65 1281
  * [6] Torquato S and Stillinger F H 2010 Reviews of Modern Physics 82 2633
  * [7] Renyi A 1958 Publications of the Mathematical Institute of the Hungarian Academy of Sciences 3 109–127
  * [8] Brosilow B J, Ziff R M and Vigil R D 1991 Physical Review A 43 631
  * [9] Kasperek W, Kubala P and Cieśla M 2018 Physical Review E 98 063310
  * [10] Zhang G 2018 Physical Review E 97 043311
  * [11] Vigil R D and Ziff R M 1989 The Journal of Chemical Physics 91 2599–2602
  * [12] Petrone L and Cieśla M 2021 Physical Review E 104 034903
  * [13] Petrone L 2022 Acta Physica Polonica B 53 5–A1
  * [14] Pomeau Y 1980 Journal of Physics A: Mathematical and General 13 L193
  * [15] Swendsen R H 1981 Physical Review A 24 504
  * [16] Hinrichsen E L, Feder J and Jøssang T 1986 Journal of Statistical Physics 44 793–827
  * [17] Cieśla M 2013 Physical Review E 87 052401
  * [18] Privman V, Wang J S and Nielaba P 1991 Physical Review B 43 3366
  * [19] Ricci S, Talbot J, Tarjus G and Viot P 1992 The Journal of Chemical Physics 97 5219–5228
  * [20] Abritta P and Hoy R S 2022 Physical Review E 106 054604
  * [21] Sherwood J 1997 Journal of Physics A: Mathematical and General 30 L839
  * [22] Barbasz J and Cieśla M 2013 Acta Physica Polonica B 44 937 ISSN 0587-4254 URL http://www.actaphys.uj.edu.pl/vol44/abs/v44p0937
  * [23] Kondrat G and Pȩkalski A 2001 Physical Review E 63 051108
  * [24] Cadilhe A, Araújo N and Privman V 2007 Journal of Physics: Condensed Matter 19 065124
  * [25] Lebovka N I, Karmazina N N, Tarasevich Y Y and Laptev V V 2011 Physical Review E 84(6) 061603 URL https://link.aps.org/doi/10.1103/PhysRevE.84.061603
  * [26] Tarasevich Y Y, Laptev V V, Vygornitskii N V and Lebovka N I 2015 Physical Review E 91 012109
  * [27] Centres P M and Ramirez-Pastor A J 2015 Journal of Statistical Mechanics: Theory and Experiment 2015 P10011
  * [28] Budinski-Petković L, Lončarević I, Jakšić Z and Vrhovac S 2016 Journal of Statistical Mechanics: Theory and Experiment 2016 053101
  * [29] Slutskii M G, Barash L Y and Tarasevich Y Y 2018 Physical Review E 98(6) 062130 URL https://link.aps.org/doi/10.1103/PhysRevE.98.062130
  * [30] Wang J S 1994 International Journal of Modern Physics C 5 707–715
  * [31] Klee V 1977 The American Mathematical Monthly 84 284–285
  * [32] Cieśla M and Ziff R M 2018 Journal of Statistical Mechanics: Theory and Experiment 2018 043302
  * [33] Wang J S 2000 Progress of Theoretical Physics Supplement 138 433–441 URL https://doi.org/10.1143%2Fptps.138.433
  * [34] Viot P, Tarjus G, Ricci S and Talbot J 1992 The Journal of Chemical Physics 97 5212–5218
  * [35] Haiduk K, Kubala P and Cieśla M 2018 Physical Review E 98 063309
  * [36] Cieśla M, Paja̧k G and Ziff R M 2016 The Journal of Chemical Physics 145 044708 URL https://doi.org/10.1063%2F1.4959584
  * [37] Shelke P B, Khandkar M D, Banpurkar A G, Ogale S B and Limaye A V 2007 Phys. Rev. E 75(6) 060601(R) URL https://link.aps.org/doi/10.1103/PhysRevE.75.060601
  * [38] Lebovka N I, Tatochenko M O, Vygornitskii N V, Eserkepov A V, Akhunzhanov R K and Tarasevich Y Y 2021 Phys. Rev. E 103(4) 042113 URL https://link.aps.org/doi/10.1103/PhysRevE.103.042113


# Some Infinitary Paradoxes and Undecidable Sentences in Peano Arithmetic

Cheng Ka Yue
<EMAIL_ADDRESS>
##  1 Introduction

In Chaitin, [1995] there is a conversation between Gregory Chaitin and Kurt
Gödel:

> [Chaitin] said, “Professor Gödel, I’m fascinated by your incompleteness
> theorem. I have a new proof based on Berry paradox that I’d like to tell you
> about.” Gödel said, “It doesn’t matter which paradox you use.”

To support this claim, we need to investigate what will happen if we formalize
different paradoxes in Peano arithmetic (PA). Most notably, Chaitin proved a
version of the First Incompleteness Theorem with a proof resembling the Berry
paradox in his Chaitin, [1971], so did George Boolos gave his proof using the
same paradox (independently) in Boolos, [1998].

In this paper111This paper was presented in Logic Colloquium 2015, and the
results are from my mater’s thesis Cheng, [2015]., I will present a few
infinitary paradoxes and corresponding undecidable sentences. The first three
paradoxes are developed, in my master thesis, from a version of the Preface
paradox, and the last one is an infinite version of the Surprise Examination
paradox from Sorensen, [1993].

We will work in the usual first order Peano arithmetic, though in fact the
results hold in any theory that extends PA. The non-logical symbols in the
language are the only constant symbol $0$, a unary function symbol $S$ and two
binary function symbols $+$ and $\times$.

The technique being used to produce undecidable sentences in this paper,
involving a general version of the Diagonal Lemma, is mainly from Cies̀liǹski
and Urbaniak, [2013].

##  2 Preliminaries

In this section, I will state a few facts and definitions that are useful in
this paper, proofs of those facts and details of the arithmetization of syntax
will be skipped. These details can be found in books about Gödel’s
Incompleteness Theorems, for examples, Smullyan, [1992] and Smith, [2007].

There are formulas in PA that are said to be _provable_. If a formula
$\varphi$ is provable in Peano arithmetic, we will denote this fact by
$\vdash\varphi$. Then we have some definitions:

  1. 1.

A formula $\varphi$ is said to be _refutable_ if the negation of it,
$\neg\varphi$, is provable.

  2. 2.

A formula is decidable if it is provable or refutable, otherwise it is
undecidable. Hence a formula $\varphi$ is undecidable if neither $\varphi$ nor
$\neg\varphi$ is provable.

  3. 3.

Two formulae $\varphi$ and $\psi$ are _provable equivalent_ if the formula
$\varphi\longleftrightarrow\psi$ is provable.

  4. 4.

A quantifier is _bounded_ in a formula if it is of the form $\exists
x(x<t\land\varphi)$ or $\forall x(x<t\rightarrow\varphi)$, where $t$ is a
term, and we will write $(\exists x<t)\varphi$ and $(\forall x<t)\varphi$
respectively.

  5. 5.

A formula is a _$\Delta_{0}$ formula_ if it is provably equivalent to a
formula containing only bounded quantifiers.

  6. 6.

A formula is a _$\Sigma_{1}$ formula_ if it is provably equivalent to a
formula of the form $\exists x\varphi$, where $\varphi$ is a $\Delta_{0}$
formula.

We say that a theory is _consistent_ if there is no formula $\varphi$ such
that both $\varphi$ and $\neg\varphi$ are provable. And we say that a theory
is $\omega$-consistent if there is no open formula $\varphi(x)$ such that
$\exists x\varphi(x)$ is provable, but for every natural number $n$,
$\varphi(n)$ is not provable. In this paper we assume PA is both consistent
and $\omega$-consistent.222The latter actually implies the former and can be
replaced by weaker a weaker condition called 1-consistency (or $\Sigma_{1}$
soundness), which also implies consistency.

The following corollary of the assumption of $\omega$-consistency is useful:

######  Lemma 1.

Let $\varphi(x)$ be a $\Sigma_{1}$ formula with a free variable $x$. If
$\exists x\varphi(x)$ is provable, then there is a number $n$ such that
$\varphi(n)$ is provable.

This result simply follows from the definition of $\omega$-consistency and the
fact that all $\Delta_{0}$ formulae are decidable.

Another lemma about $\Sigma_{1}$ formulae is also useful:

######  Lemma 2.

If $\varphi$ is a $\Sigma_{1}$ formula, then for any variable $x$, $\exists
x\varphi$ is also a $\Sigma_{1}$ formula.

A proof of this lemma can be found in Smullyan, [1992].

We can encode each finite sequence of natural numbers into a natural number,
call the _code_ of the sequence, in a way that we can also decode that number
and obtain the original sequence. A number which is the code of a finite
sequence is called a _code number_.

Then we assign different numbers to the symbols in our object language, hence
every expression corresponds to a finite sequence, which can be encoded into a
natural number. Such a number is called the _Gödel number_ of that expression.
Let $\varphi$ be a formula, the Gödel number of $\varphi$ will be denoted by
$\ulcorner\varphi\urcorner$.

After that, (syntactical) properties and relations of expressions correspond
to properties and relations of the Gödel numbers of expressions. Then we can
construct the following predicates and functions333Since we usually do not
include function symbols other than $S$, $+$ and $\times$, “$f(x)=y$” should
be understood as a relation of $x$ and $y$ and “$f(x)$” should be understood
as pterms (p for pseudo) in [Boolos, 1993].:

  1. 1.

$Code(x)$ is provable if $x$ is a code number.

  2. 2.

$l(x)=n$ is provable if $x$ is a code number of a sequence with length $n$.

  3. 3.

$Dec(x,k)=y$ is provable if $x$ is a code number and the $k^{th}$ term of the
sequence encoded by $x$ is $y$.

  4. 4.

$Neg(x)$ is a function such that
$Neg(\ulcorner\varphi\urcorner)=\ulcorner\neg\varphi\urcorner$ is provable for
any formula $varphi$.444In fact for any expressions, not restricted to
formulas, but here we only concern formulas.

  5. 5.

$Subs(x,v,y)$ is a function such that if for any formula $\varphi$, term $t$,
variable $v_{i}$ free in $\varphi$, then
$Sub(\ulcorner\varphi\urcorner,\ulcorner v_{i}\urcorner,\ulcorner
t\urcorner)=\ulcorner\varphi(t/v_{i})\urcorner$, where $\varphi(t/v_{i})$ is
the formula obtained from substituting all free occurrence of $v_{i}$ in
$\varphi$ by $t$, is provable.

The above relations are $\Delta_{0}$. We also have an open $\Sigma_{1}$
formula $Prov(x)$ with one free variable satisfying the following two lemmas:

######  Lemma 3 ($Prov$-introduction).

If $\varphi$ is a provable formula, then $Prov(\ulcorner\varphi\urcorner)$ is
provable.

######  Lemma 4 ($Prov$-elimination).

If Peano arithmetic is $\omega$-consistent, and $\varphi$ is a formula such
that $Prov(\ulcorner\varphi\urcorner)$ is provable, then $\varphi$ is
provable.

Since we assume the consistency and $\omega$-consistency of PA,
$Prov(\ulcorner\varphi\urcorner)$ is provable if and only if $\varphi$ is
provable for any formula $\varphi$.

Finally we need two more lemmas. The first one is a generalized version of the
usual Diagonal Lemma, the proof of it can be found in Boolos, [1993]:

######  Lemma 5 (Generalized Diagonal Lemma).

Let $\varphi(x,y)$ be an open formula with two free variables $x,y$, then
there is an open formula $\psi(x)$ with one free variable $x$ such that
$\psi(x)\longleftrightarrow\varphi(x,\ulcorner\psi(x)\urcorner)$ is provable.

The second one is a consequence of Gödel’s Second Incompleteness Theorem:

######  Lemma 6.

Let $\varphi$ be a sentence, then $\neg Prov(\ulcorner\varphi\urcorner)$ is
not provable.

##  3 The Paradoxes

In this section I will present four infinitary paradoxes, the first three of
them are from my master thesis, though there are some similar finite version
in the literature, I cannot find any name for the infinitary ones. The last
one is called the Earliest Class Inspection paradox from Sorensen, [1993], as
noted in the introduction.

Imagine there are infinitely many people in a room, each of them say one and
only one sentence. The following three situations correspond to the first
three paradoxes.

### Paradox 1: Someone is wrong.

If everyone in the room says “Someone is wrong” 555To be more precise, it
should be “At least one sentence uttered in this room is false”. But for
convenience, we simply talk about people being right and wrong instead of the
sentences they uttered is true or false., then it is impossible for everyone
to be right, otherwise none of them is wrong, contradicting their claims.
Hence someone must be wrong, but that person also says “Someone is wrong”, so
“No one is wrong” is true, contradicting him or her being wrong.

### Paradox 2: Someone else is wrong.

If everyone in the room says “Someone else is wrong”, then this situation is
slightly more complicated. It is consistent that there is exactly one person
being wrong, while the rest of them are right. Furthermore, since everyone
says the same thing and it is a symmetric situation, it does not matter that
which one is wrong. So the truth value assignments of their sentence is
arbitrary in this sense, which is similar to the Truth-teller paradox, i.e.
“This sentence is true”.

### Paradox 3: Some people are wrong.

Suppose all people in the room queue up, and the $k^{th}$ person says “There
are at least $k$ people wrong”. Notice that if the $k^{th}$ person is right,
then everyone before this person is also right.666Since the $k^{th}$ person is
right, there are at least $k$ people wrong. Hence for any $j<k$, it is true
that there are at least $j$ people wrong, which means the $j^{th}$ person is
right. Similarly, if the $k^{th}$ person is wrong, then everyone after this
person is also wrong.

Using logic we know that either everyone is right or someone is wrong, in both
cases the first person is right.777If everyone is right, then of course the
first person is right; if someone is wrong, then at least one person is wrong,
which is what the first person asserts. Since the first person is right,
someone must be wrong, and there must be someone who is the first person (in
the queue) being wrong. Let this person be the $k^{th}$ person. By our
observation everyone after her or him is wrong, so there are more than $k$
people wrong, but that means the $k^{th}$ person is right, and we have a
contradiction.

### Paradox 4: The Earliest Class Inspection Paradox

Suppose you are a new teacher, and you are told that there will be a class
inspection. There are two conditions on the date of the inspection: first, the
sooner the better; second, you do not know and cannot guess the day so that
you cannot prepare for it. Therefore, the inspection will be on the first day
which you do not believe there will be a class inspection.

Now, the next school day is the first available day for class inspection, but
then the inspection cannot be on that day since you can reason it. Similarly
you can rule out the possibilities of the inspection being on the second day,
the third day, the fourth day, and so on. Hence the earliest unexpected class
inspection is impossible.

### Notes on the paradoxes

Here are some notes on the paradoxes.

The finite version of the first paradox, which is still a paradox, is related
to the Liar cycles.888That is, the people are in a circle, and everyone says
the next person is wrong, with an exception that if the number of people is
even, then one of them says the next one is right. However an existential
quantifier is informally used in this paradox, and it can be extended to the
infinite case easily, unlike the Liar cycles.

The finite version of the second paradox is again similar to the infinite
case, that is, we have different consistent truth-value assignments. It is
related to a paradox by Jean Buridan, which is “Socrates says that Plato tells
a lie, Plato says that Socrates tells a lie” (and they say nothing more), it
is also called the No-No paradox in Sorensen, [2004]. In Sorensen’s book,
there is a finite version of the second paradox.999In almost the same form,
except that he uses a list of 100 sentences, each of them is the sentence
“Some other sentence on this list is false”.

The finite version of the third paradox is not necessarily a paradox: if the
number of people is even, then the first half people are right and the second
half wrong; if the number of people is odd, then the one who is in the exact
middle of the queue is in a Liar paradox situation. And the infinite version
resembles the Yablo’s paradox101010Yablo’s paradox is about an infinite list
of sentences where every sentence is “All sentences below are false”. If the
first sentence is true, then the second one is false, hence some sentence
below it is true, contradicting the first one. On the other hand, if the first
sentence is false, then some sentence below it is true, and we will get a
similar contradiction.

The Earliest Class Inspection Paradox can be regarded as an infinite version
of the Surprise Examination Paradox.

##  4 The Undecidable Sentences

In Cies̀liǹski and Urbaniak, [2013], the authors apply Lemma 5 to an open
formula to obtain undecidable sentences resembling Yablo’s paradox. In the
following, we will do the same for the paradoxes in the last section.

### Formalizing Paradox 1

Consider the open formula111111The subformula $0\leq x$ is to make sure the
formula contains $x$ as a free variable. It is not difficult to prove that
$0\leq x$ is provable.:

$\exists z\Big{(}Prov\big{(}Neg(Subs(y,\ulcorner x\urcorner,\ulcorner
z\urcorner))\big{)}\Big{)}\land(0\leq x)$

By Lemma 5 there is an open formula $\mathbf{P}(x)$ with one free variable $x$
such that:

$\displaystyle\vdash\mathbf{P}(x)\longleftrightarrow\exists
z\Big{(}Prov\big{(}Neg(Subs(\ulcorner\mathbf{P}(x)\urcorner,\ulcorner
x\urcorner,\ulcorner z\urcorner))\big{)}\Big{)}\land(0\leq x)$
$\displaystyle\Rightarrow\,$
$\displaystyle\vdash\mathbf{P}(x)\longleftrightarrow\exists
z\big{(}Prov(\ulcorner\neg\mathbf{P}(z)\urcorner)\big{)}\land(0\leq y)$
$\displaystyle\Rightarrow\,$
$\displaystyle\vdash\mathbf{P}(x)\longleftrightarrow\exists
z\big{(}Prov(\ulcorner\neg\mathbf{P}(z)\urcorner)\big{)}$

Here $\mathbf{P}(k)$ can be read as the sentence that the $k^{th}$ person
says, which is, intuitively, “There is someone whose sentence is refutable”.
Like the undecidable sentence in Gödel original proof, which is a
formalization of the Liar paradox, we replace “truth” by “provability”, since
the latter can be formulated in the object language.

We have the following result:

######  Theorem 7.

For any natural number $k$, $\mathbf{P}(k)$ is undecidable.

###### Proof.

Let $k$ be a natural number. Suppose $\mathbf{P}(k)$ is provable. Then by the
choice of $\mathbf{P}(x)$, $\exists
z\big{(}Prov(\ulcorner\neg\mathbf{P}(z)\urcorner)\big{)}$ is also provable. By
$\omega$-consistency of PA, Lemma 1 and Lemma 2, there is a natural number $n$
such that $\neg Prov(\ulcorner\mathbf{P}(n)\urcorner)$ is provable. But by
Lemma 6 this is impossible.

On the other hand, suppose $\mathbf{P}(k)$ is refutable. Then:

$\displaystyle\vdash\neg\mathbf{P}(k)\Rightarrow\,$
$\displaystyle\vdash\neg\exists
z\big{(}Prov(\ulcorner\neg\mathbf{P}(z)\urcorner)\big{)}$ (By the choice of
$\mathbf{P}(x)$) $\displaystyle\Rightarrow\,$ $\displaystyle\vdash\forall
z\neg Prov(\ulcorner\neg\mathbf{P}(z)\urcorner)$ $\displaystyle\Rightarrow\,$
$\displaystyle\vdash\neg Prov(\ulcorner\neg\mathbf{P}(k)\urcorner)$ (By
universal instantiation)

While by Lemma 3, we have $Prov(\ulcorner\neg\mathbf{P}(k)\urcorner)$
provable. Since we assume that PA is consistent, this is impossible.

Therefore for any natural number $k$, $\mathbf{P}(k)$ is neither provable nor
refutable, hence undecidable. ∎

### Formalizing Paradox 2

Consider the following open formula:

$\exists z\Big{(}z\neq x\land Prov\big{(}Neg(Subs(y,\ulcorner
x\urcorner,\ulcorner z\urcorner))\big{)}\Big{)}$

By Lemma 5, there is an open formula $\mathbf{Q}(x)$ with one free variable
$x$ such that

$\vdash\mathbf{Q}(x)\longleftrightarrow\exists z\big{(}z\neq x\land
Prov(\ulcorner\neg\mathbf{Q}(z)\urcorner)\big{)}$

Similar to the previous formalization, $\mathbf{Q}(k)$ can be read as the
sentence that the $k^{th}$ person says, which is, intuitively, “There is
someone else whose sentence is refutable”.

We have the following result:

######  Theorem 8.

For any natural number $k$, $\mathbf{Q}(k)$ is undecidable.

###### Proof.

Let $k$ be a natural number. Suppose $\mathbf{Q}(k)$ is refutable. Then:

$\displaystyle\vdash\neg\mathbf{Q}(k)\Rightarrow\,$
$\displaystyle\vdash\neg\exists z\big{(}z\neq k\land
Prov(\ulcorner\neg\mathbf{Q}(z)\urcorner)\big{)}$ (By the choice of
$\mathbf{Q}(x)$) $\displaystyle\Rightarrow\,$ $\displaystyle\vdash\forall
z\big{(}Prov(\ulcorner\neg\mathbf{Q}(z)\urcorner)\rightarrow z=k\big{)}$
$\displaystyle\Rightarrow\,$ $\displaystyle\vdash\forall z\big{(}z\neq
k\rightarrow\neg Prov(\ulcorner\neg\mathbf{Q}(z)\urcorner)\big{)}$
$\displaystyle\Rightarrow\,$ $\displaystyle\vdash\big{(}k+1\neq
k\rightarrow\neg Prov(\ulcorner\neg\mathbf{Q}(k+1)\urcorner)\big{)}$ (By
Universal Instantiation) $\displaystyle\Rightarrow\,$ $\displaystyle\vdash\neg
Prov(\ulcorner\neg\mathbf{Q}(k+1)\urcorner)$ ($\vdash k+1\neq k$)

But by Lemma 6, $\neg Prov(\ulcorner\neg\mathbf{Q}(k+1)\urcorner)$ is not
provable. Hence $\mathbf{Q}(k)$ cannot be refutable.

On the other hand, suppose $\mathbf{Q}(k)$ is provable, then by the choice of
$\mathbf{Q}(x)$, $\exists z\big{(}z\neq k\land
Prov(\ulcorner\neg\mathbf{Q}(z)\urcorner)\big{)}$ is also provable. By
$\omega$-consistency of PA, Lemma 2 and Lemma 1, there is a natural number $n$
such that $Prov(\ulcorner\neg\mathbf{Q}(n)\urcorner)$ is provable.

By Lemma 4, $\neg\mathbf{Q}(n)$ is also provable. But this contradicts the
first half of this proof, hence $\mathbf{Q}(k)$ cannot be provable.

Therefore for any natural number $k$, $\mathbf{Q}(k)$ is undecidable. ∎

We have noted the similarity between paradox 2 and the Truth-teller paradox.
Nevertheless, the Henkin sentence, the formalized Truth-teller, is provable by
Löb’s celebrated theorem, while the formalized version of paradox 2 above is
undecidable.

### Formalizing Paradox 3

To formalize the third paradox, it is more complicated since we need to refer
to a set of numbers (of size $k$) in the object language. So we need a two
more definitions:

  * •

$HetSeq(x)\longleftrightarrow Code(x)\land\big{(}\forall y\leq
l(x)\big{)}\big{(}\forall z\leq l(x)\big{)}\big{(}y\neq z\rightarrow
Dec(y,x)\neq Dec(z,x)\big{)}$
If $HetSeq(x)$ is provable, then $x$ is a code number of a sequence where no
two terms are the same.

  * •

$Ele(x,y)\longleftrightarrow Code(y)\land\big{(}\exists u\leq
l(y)\big{)}\big{(}Dec(u,y)=x\big{)}$
If $Ele(x,y)$ is provable, then $x$ represents a number which is a term of the
sequence represented by $y$.

The idea is to define a kind of sequence, called heterosequence, in which no
two terms are the same. Instead of saying there is a set of $k$ natural
numbers, we can say there is a heterosequence of length $k$. Note that both
$HetSeq(x)$ and $Ele(x,y)$ are $\Delta_{0}$.

Then consider the open formula:

$\exists z\Big{[}HetSeq(z)\land l(z)=Sx\land(\forall t\leq
z)\big{[}Ele(t,z)\rightarrow Prov\big{(}Neg(Subs(y,\ulcorner
x\urcorner,\ulcorner t\urcorner))\big{)}\big{]}\Big{]}$

Again by Lemma 5 there is an open formula $\mathbf{R}(x)$ such that:

$\vdash\mathbf{R}(x)\longleftrightarrow\exists
z\Big{(}HetSeq(z)\land\big{(}l(z)=Sx\big{)}\land(\forall t\leq
z)\big{(}Ele(t,z)\rightarrow
Prov(\ulcorner\neg\mathbf{R}(t)\urcorner)\big{)}\Big{)}$

Intuitively, $\mathbf{R}(k)$ is provable if and only if there is a
heterosequence of length $k+1$ such that for each element $t$ of that
sequence, $\mathbf{R}(t)$ is refutable.121212The length of the heterosequence
is $k+1$, since we count the natural numbers from $0$.

We have the following two lemmas:

######  Lemma 9.

If $m,n$ are natural numbers and $m<n$, then
$\vdash\mathbf{R}(n)\rightarrow\mathbf{R}(m)$.

###### Proof.

Let $m,n$ be natural numbers and $m<n$. Suppose $\vdash\mathbf{R}(n)$. Then by
the choice of $\mathbf{R}(x)$:

$\vdash\exists z\Big{(}HetSeq(z)\land\big{(}l(z)=Sn\big{)}\land(\forall t\leq
z)\big{(}Ele(t,z)\rightarrow
Prov(\ulcorner\neg\mathbf{R}(t)\urcorner)\big{)}\Big{)}$

By $\omega$-consistency, there is a natural number $N$ such that

$\vdash\Big{(}HetSeq(N)\land\big{(}l(N)=Sn\big{)}\land(\forall t\leq
N)\big{(}Ele(t,N)\rightarrow
Prov(\ulcorner\neg\mathbf{R}(t)\urcorner)\big{)}\Big{)}$

$N$ is the code number of a heterosequence of length $n+1$, then we can take
the first $m+1$ terms of the sequence to form a new heterosequence, and let
its code number be $M$. By definition, both $l(b)=Sm$ and $Ele(t,M)\rightarrow
Ele(t,N)$ are provable, hence

$\vdash\Big{(}HetSeq(M)\land\big{(}l(b)=Sm\big{)}\land(\forall t\leq
M)\big{(}Ele(t,M)\rightarrow
Prov(\ulcorner\neg\mathbf{R}(t)\urcorner)\big{)}\Big{)}$

Therefore $\vdash\mathbf{R}(m)$. By the deduction theorem we get
$\vdash\mathbf{R}(n)\rightarrow\mathbf{R}(m)$. ∎

######  Lemma 10.

If $m,n$ are natural numbers and $m>n$, then
$\vdash\neg\mathbf{R}(n)\rightarrow\neg\mathbf{R}(m)$.

###### Proof.

By Lemma 9 we have $\vdash\mathbf{R}(m)\rightarrow\mathbf{R}(n)$, which
implies the contrapositive of the formula, therefore
$\vdash\neg\mathbf{R}(n)\rightarrow\neg\mathbf{R}(m)$. ∎

These two lemmas formalize our previous observations in the situation of
paradox 3: “if the $k^{th}$ person is right then everyone before him or her is
right” and “if the $k^{th}$ person is wrong then everyone after her or him is
wrong”.

Then we have the following result:

######  Theorem 11.

For any natural number $n$, $\mathbf{R}(n)$ is undecidable.

###### Proof.

Let $n$ be a natural number. Suppose $\mathbf{R}(n)$ is refutable, then
$\vdash\neg\mathbf{R}(n)$.

By Lemma 10, for every $m>n$, $\mathbf{R}(m)$ is refutable. Therefore the
sentences $\neg\mathbf{R}(n),\neg\mathbf{R}(n+1),\ldots,\neg\mathbf{R}(n+n)$
are all provable, by Lemma 3 the sentences
$Prov(\ulcorner\neg\mathbf{R}(n)\urcorner),Prov(\ulcorner\neg\mathbf{R}(n+1)\urcorner),\ldots,Prov(\ulcorner\neg\mathbf{R}(n+n)\urcorner)$
are also provable.

Let $c$ be the code number of the sequence $(n,n+1,\ldots,n+n)$. Then the
sentences $HetSeq(c)$, $l(c)=Sn$, and $(\forall t\leq
c)\big{(}Ele(t,c)\rightarrow Prov(\ulcorner\neg\mathbf{R}(t)\urcorner)\big{)}$
are all provable. This implies that $\mathbf{R}(n)$ is provable and we get
another contradiction.

On the other hand, suppose $\mathbf{R}(n)$ is provable. Then

$\exists z\Big{(}HetSeq(z)\land\big{(}l(z)=Sn\big{)}\land(\forall t\leq
z)\big{(}Ele(t,z)\rightarrow
Prov(\ulcorner\neg\mathbf{R}(t)\urcorner)\big{)}\Big{)}$

is also provable. By $\omega$-consistency, there is an number $c$ such that

$\displaystyle\vdash\Big{(}HetSeq(c)\land l(c)=Sn\land(\forall t\leq
c)\big{(}Ele(t,c)\rightarrow
Prov(\ulcorner\neg\mathbf{R}(t)\urcorner)\big{)}\Big{)}$
$\displaystyle\Rightarrow\,$ $\displaystyle\vdash(\forall t\leq
c)\big{(}Ele(t,c)\rightarrow
Prov(\ulcorner\neg\mathbf{R}(t)\urcorner))\big{)}\Big{)}\quad\qquad\text{(By
conjunction elimination)}$ $\displaystyle\Rightarrow\,$ $\displaystyle\vdash
Prov(\ulcorner\neg\mathbf{R}(Dec(1,c)\urcorner)\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\,\text{(By
fact 3)}$

But it is impossible by the first half of this proof, so $\mathbf{R}(n)$ is
not provable. Therefore $\mathbf{R}(n)$ is neither provable nor refutable. ∎

### Formalizing Paradox 4

Consider the open formula:

$(\forall z<x)Prov\big{(}Neg(Subs(y,\ulcorner x\urcorner,\ulcorner
z\urcorner))\big{)}\rightarrow Prov\big{(}Neg(y)\big{)}$

Apply Lemma 5, we will get an open formula $\mathbf{F}(x)$ with one variable
$x$ such that:

$\vdash\mathbf{F}(x)\longleftrightarrow\big{[}(\forall
z<x)Prov\big{(}\ulcorner\neg\mathbf{F}(z)\urcorner\big{)}\rightarrow
Prov\big{(}\ulcorner\neg\mathbf{F}(x)\urcorner)\big{)}\big{]}$

Roughly speaking, $\mathbf{F}(n)$ is related to the proposition “there will be
a class inspection at the $(n+1)^{st}$ day”131313Note that we count from $0$..
And it satisfies the condition that if it is deducible that there is no class
inspection at the first $n$ day, then it is deducible that there is no class
inspection at the $(n+1)^{st}$ day.

Then we have the following result:

######  Theorem 12.

$\exists x\mathbf{F}(x)$ is undecidable.

To prove this theorem, we need the following fact:

######  Proposition 13 (The Least Number Principle).

For any open formula $P(x)$ with exactly one free variable $x$, it is provable
that $\exists xP(x)\rightarrow\exists x\big{(}P(x)\land(\forall y<x)\neg
P(y)\big{)}$.

The proof of this principle, which can be found in Boolos, [1993], is skipped
here. Now we can prove Theorem 12.

###### Proof.

Suppose $\exists x\mathbf{F}(x)$ is provable, then by the Least Number
Principle, $\exists x\big{(}\mathbf{F}(x)\land(\forall
z<x)\neg\mathbf{F}(z)\big{)}$ is also provable.

By the $\omega$-consistency, there is a natural number $n$ such that the
formula $(\forall z<n)\neg\mathbf{F}(z)\land\mathbf{F}(n)$ is provable. Then
$(\forall z<n)\neg\mathbf{F}(z)$ is provable, by substitution and modus ponens
we have $\neg\mathbf{F}(0),\neg\mathbf{F}(1),\ldots,\neg\mathbf{F}(n-1)$ are
all provable. Hence by Lemma 3,
$Prov(\ulcorner\neg\mathbf{F}(0)\urcorner),Prov(\ulcorner\neg\mathbf{F}(1)\urcorner),\ldots,Prov(\ulcorner\neg\mathbf{F}(n-1)\urcorner)$
are all provable, so is $(\forall
z<n)Prov(\ulcorner\neg\mathbf{F}(z)\urcorner)$.

Since $\mathbf{F}(n)$ is also provable, we have:

$\displaystyle\vdash\mathbf{F}(n)\Rightarrow\,$
$\displaystyle\vdash\big{[}(\forall
z<n)Prov\big{(}\ulcorner\neg\mathbf{F}(z)\urcorner\big{)}\rightarrow
Prov\big{(}\ulcorner\neg\mathbf{F}(n)\urcorner)\big{)}\big{]}$ (By the choie
of $\mathbf{F}(x)$) $\displaystyle\Rightarrow\,$ $\displaystyle\vdash
Prov\big{(}\ulcorner\neg\mathbf{F}(n)\big{)}$ (By modus ponens)
$\displaystyle\Rightarrow\,$ $\displaystyle\vdash\neg\mathbf{F}(n)$ (By Lemma
4)

So we get a contradiction, and $\exists x\mathbf{F}(x)$ is not provable.

On the other hand, suppose $\exists x\mathbf{F}(x)$ is refutable. Then
$\neg\exists x\mathbf{F}(x)$, and equivalently, $\forall x\neg\mathbf{F}(x)$
are provable. For any natural number $n$, we have:

$\displaystyle\vdash\neg\mathbf{F}(n)$ (By universal instantiation)
$\displaystyle\Rightarrow\,$ $\displaystyle\vdash(\forall
z<n)Prov\big{(}\ulcorner\neg\mathbf{F}(z)\urcorner\big{)}\land\neg
Prov(\ulcorner\neg\mathbf{F}(n)\urcorner)$ (By the choice of $\mathbf{F}(x)$)
$\displaystyle\Rightarrow\,$ $\displaystyle\vdash\neg
Prov(\ulcorner\neg\mathbf{F}(n)\urcorner)$ (By conjunction elimination)

But by Lemma 3, $\neg\mathbf{F}(n)$ is provable implies that
$Prov(\ulcorner\neg\mathbf{F}(n)\urcorner)$ is also provable. Again we get a
contradiction.

Therefore, $\exists x\mathbf{F}(x)$ is undecidable. ∎

With some modifications on the definition of $\mathbf{F}(x)$, we can obtain a
formalization of the Surprise Examination paradox which is essentially
different from the one in Fitch, [1964], since the former is undecidable but
the latter is refutable.

##  5 Summary

We have seen four infinitary paradoxes, and four related open formulas,
$\mathbf{P}(x)$, $\mathbf{Q}(x)$, $\mathbf{R}(x)$, and $\mathbf{F}(x)$. The
first three open formulas lead to infinitely many undecidable sentences, and
for the last one we have an undecidable sentence $\exists x\mathbf{F}(x)$.

These results partly confirm Gödel’s claim quoted in the first section, and
refute a possible counterexample from Fitch, [1964]. Also, it is interesting
to investigate whether there is any other paradox like the paradox 2, and to
understand the difference between paradox 2 and the Truth-teller.

## References

  * Boolos, [1993] Boolos, G. (1993).  The Logic of Provability.  Cambridge University Press.
  * Boolos, [1998] Boolos, G. (1998).  A New Proof of the Gödel Incompleteness Theorem.  In Logic, Logic, and Logic, pages 383–388. Harvard University Press.
  * Chaitin, [1971] Chaitin, G. J. (1971).  Computational Complexity and Gödel’s Incompleteness Theorem.  ACM SIGACT News.
  * Chaitin, [1995] Chaitin, G. J. (1995).  The Berry Paradox.  Complexity, 1(1):26–30.
  * Cheng, [2015] Cheng, K. Y. (2015).  Logical Paradoxes and Undecidable Sentences.  Master’s thesis, Eötvös Loránd University.
  * Cies̀liǹski and Urbaniak, [2013] Cies̀liǹski, C. and Urbaniak, R. (2013).  Gödelizing the Yablo Sequence.  Journal of Philosophical Logic, 42(5):679–695.
  * Fitch, [1964] Fitch, F. B. (1964).  A Goedelized Formulation of the Prediction Paradox.  American Philosophical Quarterly, 1(2):161–164.
  * Smith, [2007] Smith, P. (2007).  An Introduction to Gödel’s Theorems.  Cambridge Introductions to Philosophy. Cambridge University Press.
  * Smullyan, [1992] Smullyan, R. M. (1992).  Gödel’s Incompleteness Theorems.  Oxford University Press.
  * Sorensen, [1993] Sorensen, R. A. (1993).  The Earliest Unexpected Class Inspection.  Analysis, 53(4):252 –.
  * Sorensen, [2004] Sorensen, R. A. (2004).  Vagueness and Contradiction.  Oxford University Press.