# Boolean logic as an alternate, minimalist foundation for arithmetic

Arithmetic, and math in general, is typically formalized in first-order ZFC set theory. Since there are no urelements, the closest thing we have to an "atom" is the empty set. Sets are built up gradually from sets containing sets containing... the empty set. We can construct the natural numbers via the Von Neumann construction, where $0=\{\}$, $1={0}=\{\{\}\}$, $2=\{0,1\}=\{\{\},\{\{\}\}\}$, and so on. From here we can develop arithmetic (and more) by defining tuples, relations, functions and so on. The empty set and the containment relation is all we need.

Meanwhile, in the practical world, we appear to have a completely different "de facto" foundation for much of math: Boolean logic. Rather than building everything up from the empty set, we build everything up from bits, which are our new "atoms." We can build up the natural numbers from bits via the base 2 representation. From here we can develop arithmetic (and more) by creating Boolean circuits for addition, multiplication, and so on. Bits and NAND gates are all we need.

Despite the obvious connections, I have never seen an attempt to formalize arithmetic in a parsimonious, reductionist way using only bits and logic gates as primitives. This is obviously possible since basically every computer is doing it.

In theory, it might even be possible to build set theory on a foundation of bits and logic gates, as Boolean algebra and set theory are intimately connected on a few different levels. Stone's representation theorem is an isomorphism between Boolean algebras and fields of sets, so there should be a proper class-sized Boolean algebra that is a model of ZFC (or close enough to get somewhere). Boolean logic is basically equivalent to classical propositional logic due to the completeness theorem, so "bits" are equivalent to classical propositions. I suppose one could think of sets themselves as related to Boolean-valued models of propositional logic.

Does anyone know of such an approach? If not, how could one accomplish this?

• But there are versions of $\mathsf {ZF}$ with atoms. – Mauro ALLEGRANZA Sep 20 '17 at 6:10
• Sure, and while we're at it, there are also set theories other than ZFC. – Mike Battaglia Sep 20 '17 at 6:11
• You might be interested in "set theoretic mereology"; see mathoverflow.net/questions/58495/…. Its models are "atomic relatively complemented distributive lattices", which sounds to me like a close relative of "complemented distributive lattices" i.e. Boolean algebras. – Dap Sep 20 '17 at 7:01