A naïve encoding of Russell’s paradox in type theory
Qu Zhuoyuan · 2026
Read A naïve encoding of Russell’s paradox in type theory by Qu Zhuoyuan (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-00811.txt.
Introduction
Zhuoyuan Qu presents a short note encoding Russell's paradox directly inside type theory. Russell's paradox, the famous argument about the set of all sets that do not contain themselves, is the standard illustration of how naive set theory contradicts itself. Qu asks what it takes to reproduce that contradiction in a typed framework instead.
The encoding uses a type-in-type universe, where a universe contains itself, together with sigma types, which package a value with data depending on it. It goes through under either of two treatments of identity: extensional identity, or intensional identity supplemented by the uniqueness of identity proofs. The note is a compact exercise showing exactly which assumptions make a type theory inconsistent.
Catalog record
| CREATOR | Qu Zhuoyuan |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 5 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-00811
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A naïve encoding of Russell’s paradox in type theory
Qu Zhuoyuan
Abstract
. Russell’s paradox is the most easily understandable way to illustrate the inconsistency of naïve set theory. This note proposes a direct encoding of Russell’s paradox with type-in-type universe, sigma types, and either extensional identity or intensional identity with the uniqueness of identity proofs (UIP).
1 Background
It is well-known that a ”type in type” system can construct Girard’s paradox
[
3
]
, breaking consistency. The paradox is the type-theoretic analogue of Burali-Forti paradox. But there are not many attempts on Russell’s paradox. Coquand
[
2
]
used W-types (general inductive types) to make a tree that corresponds to Russell’s paradoxical set. It is a quite old paper, 1Lab project has a nice formalization in Agda
[
1
]
. In this note, we will show a way to formalize Russell’s paradox in a type-in-type system with sigma-types and identity types with UIP.
2 Russell’s paradox in set theory
In a naïve set theory, Russell constructed a set where all of its elements are not members of the element itself, written as
R:=\{x\in V|x\not\in x\}
, where
V
is the set of all sets including
V
itself (
V\in V
). Then one may ask whether
R\not\in R
. It is true, since if
R\in R
we should have
R\not\in R
by the definition of
R
. However,
R\in R
is also true, since we already have
R\not\in R
, which means that
R
follows the property of
R
, so it should be in
R
. And that leads to a contradiction.
Some people have some misunderstanding that the key reason of Russell’s paradox is that all the objects in set theory are sets. For example, in set theory
0:=\{\}
,
1:=\{\{\}\}
, so we have a fact that
0\in 1
, this is meaningless in mathematics. Such theorems are called junk theorems. While in Russell’s paradoxical set, the property
x\not\in x
is a meaningless proposition. In type theory (including Russell’s type theory), objects are separated into types, so that one cannot construct Russell’s paradoxical set.
3 Constructing Russell’s paradox in type theory
We assume that we are in a type theory with a single universe
\mathcal{U}
such that
\mathcal{U}:\mathcal{U}
. We define a type representing subsets of all types..
\begin{split}&V:\mathcal{U}\\
&V:=\sum_{A:\mathcal{U}}(A\to\mathcal{U})\end{split}
We will use the following notation,
\{x:A\ |\ P(x)\}:=(A,P):V
where
P:A\to\mathcal{U}
.
As examples, we have such definitions,
\begin{split}&\mathbb{N}:=\{n:\text{Nat}\ |\ \top\}\\
&\mathbb{Z}^{+}:=\{n:\text{Int}\ |\ n>0\}\end{split}
Before we construct the paradoxical set, we need the ”element of” operation. Let us try,
\begin{split}&(\in_{A}):A\to V\to\mathcal{U}\\
&a\in_{A}\{x:B\ |\ P(x)\}:=P(a)\end{split}
Here
a:A
but
P:B\to\mathcal{U}
, so we require an operation to transport
x:A
to
x:B
.
Thus we define,
\begin{split}&\text{coe}_{AB}:\text{Id}_{\mathcal{U}}(A,B)\to A\to B\\
&\text{coe}_{AB}\ (\text{refl},\ a):=a\\
&\\
&\text{coe-eq}_{A}:\prod_{(x:A)}\prod_{h:\text{Id}(A,A)}\text{Id}_{A}(a,\text{coe}(h,a))\\
&\text{coe-eq}_{A}\ (x,\text{refl}):=\text{refl}\\
&\\
&(\in_{A}):A\to V\to\mathcal{U}\\
&a\in_{A}\{x:B\ |\ P(x)\}:=\sum_{h:\text{Id}(A,B)}P(\text{coe}(h,a))\end{split}
Note that the definition of
coe
and
coe-eq
used dependent pattern matching,
coe
can be easily defined with J-rule, but
coe-eq
require not only J-rule but also K-rule, equivalently, UIP.
And also, we do not even need to define
coe
, if we are using extensional type theory
[
4
]
, the
a:A
can be directly transport to
a:B
under the assumption
h:\text{Id}(A,B)
.
We also write
(\in):=(\in_{V})
for short. This means that sets can appear in both sides of
(\in)
. This is exactly what we need in the paradoxical set.
After that we can construct the paradoxical set,
R:=\{x:V\ |\ x\not\in x\}
where
x\not\in x:=x\in x\to\bot
.
Thus we have,
\begin{split}&\text{lemma1}:R\not\in R\\
&\text{lemma1}\ (h,p):=p(\text{subst}_{\lambda x.x\in x}(\text{coe}(\text{coe-eq}(R,h)),(h,p))\end{split}
Where for
P:A\to\mathcal{U}
,
\text{subst}_{P}:\text{Id}_{A}(x,y)\to P(x)\to P(y)
is defined by,
\begin{split}&\text{subst}_{P}\ (\text{refl},p):=p\end{split}
We can illustrate the proof in English. Assuming we have
H:R\in R
, to show
\bot
, we first split
H
(since
R\in R
is a sigma-type) into
h:\text{Id}(V,V)
and
p:\text{coe}(h,R)\not\in\text{coe}(h,R)
. Since we have
\text{coe-eq}(R,h):\text{Id}(R,\text{coe}(h,R))
, we can use it to rewrite the type of
p
and get
R\not\in R
, which is contradict to
H:R\in R
.
With
lemma1
, construct
R\in R
is easy,
\begin{split}&\text{lemma2}:R\in R\\
&\text{lemma2}:=(\text{refl},\text{lemma1})\end{split}
4 Conclusion
This note illustrates that it is possible to naïvely encode Russell’s paradox in type theory. However, the construction strongly depends on UIP, hence it will not be able to formalize in homotopy type theory
[
6
]
where UIP cannot be assumed. One may try to change the definition of
V
to
V:=\sum_{A:\mathcal{U}}\text{isSet}(A)\times(A\to P)
. This will fail because
V
itself is not a set, making it impossible to construct
R
. The whole construction has been formalized in Agda prover and Rocq prover with universe checking off
[
5
]