On a First-Order Theory of Building Blocks and its
Relation to Arithmetic and Set Theory
Juvenal Murwanashyaka
Department of Mathematics, University of Oslo, Norway

July 28, 2023

Juvenal Murwanashyaka (Department of Mathematics,On a First-OrderUniversity
Theoryof Oslo,of BuildingNorway)Blocks and its Relation to Arithmetic
July 28, 2023
and Set 1Theory/ 10

On a First-Order Theory of Building Blocks

Motivation

Question
If we are given some primitive objects, just let us regard these objects asbuilding blocks, which essential properties must they satisfy in order toencode basic finitary mathematics?

Juvenal Murwanashyaka (Department of Mathematics,
On a First-Order
University
Theoryof Oslo,of BuildingNorway)Blocks and its Relation to Arithmetic
July 28, 2023
and Set 2Theory/ 10

On a First-Order Theory of Building Blocks

Atoms
There is an unlimited supply of atoms, in the sense that for any one thing
we can always find an atom that is not a part of that thing.
Composition
Any two things x and y can be combined to form a thing z whose parts
are exactly z, the parts of x and the parts of y .

Juvenal Murwanashyaka (Department of Mathematics,On a First-OrderUniversityTheoryof Oslo,of BuildingNorway)Blocks and its Relation to Arithmetic
July 28, 2023
and Set 3Theory/ 10

On a First-Order Theory of Building Blocks

First-Order Theory BBLanguage is {}.
Let BB− be defined by the non-logical axioms
BB1 ∀x ∃y [ y 6 x ∧ ∀z [ z  y ↔ z = y ] ]BB2 ∀xy ∃z ∀w [ w  z ↔ ( w = z ∨ w  x ∨ w  y ) ]BB is BB− extended with three axioms stating that  is a partial
order (reflexive, symmetric, transitive).
BB and BB− are mutually interpretable.
When reasoning in an arbitrary model, if x 6 y and y 6 x, wevisualize the composition of x and y as the unordered binary treexyIf x  y , then we can take y as the composition of x and y .
Juvenal Murwanashyaka (Department of Mathematics,
On a First-Order
University
Theoryof Oslo,of BuildingNorway)Blocks and its Relation to Arithmetic
July 28, 2023
and Set 4Theory/ 10

On a First-Order Theory of Building Blocks

Ordered Pairs

We show how to define ordered pairs in BB.
We want a relation (x, y ) ' z such that∀xy ∃z [ (x, y ) ' z ]and(x, y ) ' z ∧ (u, v ) ' z → x = u ∧ y = v
BB− does not have pairing (for all elements of the universe).

Juvenal Murwanashyaka (Department of Mathematics,
On a First-Order
UniversityTheoryof Oslo,of BuildingNorway)Blocks and its Relation to Arithmetic
July 28, 2023
and Set 5Theory/ 10

On a First-Order Theory of Building Blocks

Let x and y be given.
Choose five distinct atoms
α0 , α1 , β0 , β1 , γthat are parts of neither x nor y , and thenrsγs0β0tt0s1xβ1α0t1yα1yx

Juvenal Murwanashyaka (Department of Mathematics,
On a First-OrderUniversityTheoryof Oslo,of BuildingNorway)Blocks and its Relation to Arithmetic
July 28, 2023
and Set 6Theory/ 10

On a First-Order Theory of Building Blocks

Encoding Finite Sets
Encoding the finite set {x, y }: we choose an atom α that is a part ofneither x nor y , and thenαxαy

Encoding the finite set {x, y , z}: we choose an atom α that is a partof neither x nor y nor z, and thenααxαzy

Juvenal Murwanashyaka (Department of Mathematics,On a First-OrderUniversity
Theoryof Oslo,of Building
Norway)Blocks and its Relation to Arithmetic
July 28, 2023
and Set 7Theory/ 10

Results

Interpretability Results
TheoremBB− , BB, Adjunctive Set Theory and Robinson arithmetic are mutuallyinterpretable.
An interpretation K : S → T is a uniform internal model construction
K∗ : Mod(T ) → Mod(S). The universe of K∗ (M) is X / ∼ where
X ⊆ M.
K is direct if the universe of K∗ (M) is M (no relativization andequality is not redefined).
TheoremBB and Adjunctive Set Theory are mutually directly interpretable.

Juvenal Murwanashyaka (Department of Mathematics,
On a First-Order
University
Theoryof Oslo,of BuildingNorway)Blocks and its Relation to Arithmetic
July 28, 2023
and Set 8Theory/ 10Open Questions

Open Questions

Problem
Are BB and Adjunctive Set Theory synonymous or bi-interpretable?
ProblemWhat is a natural extension of Adjunctive Set Theory that isbi-interpretable with BB?

Juvenal Murwanashyaka (Department of Mathematics,
On a First-Order
University
Theoryof Oslo,of Building
Norway)Blocks and its Relation to Arithmetic
July 28, 2023
and Set 9Theory/ 10Open Questions

Thank You!

Juvenal Murwanashyaka (Department of Mathematics,
On a First-OrderUniversity
Theoryof Oslo,of Building
Norway)Blocks and its Relation to July
Arithmetic28, 2023
and Set10Theory/ 10