1
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ But there are versions of $\mathsf {ZF}$ with atoms. $\endgroup$ – Mauro ALLEGRANZA Sep 20 '17 at 6:10
  • $\begingroup$ Sure, and while we're at it, there are also set theories other than ZFC. $\endgroup$ – Mike Battaglia Sep 20 '17 at 6:11
  • 1
    $\begingroup$ 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. $\endgroup$ – Dap Sep 20 '17 at 7:01
2
$\begingroup$

I'm not that familiar with Stone's representation, but to me it seem that the existence of multiplicative unity corresponds to the existence of an universe which is non-existant in ZF set theory. A question is if Stone's representation works if we drop the requirement of the unity?

Furthermore it look's like the Stone's representation does not automatically guarantees the existence of power set and infinite set. Those axioms or equivalent are needed in order to build real arithmetics (we need both infinite sets and even larger sets).

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Stone's theorem is just a starting point. You can drop the unity, although you then technically don't satisfy the definition of a Boolean algebra which requires one. Or you could use a strongly inaccessible cardinal. Still, though, one would think there exists a way to build up at least arithmetic from bits and Boolean functions, since this is what computers do. $\endgroup$ – Mike Battaglia Sep 21 '17 at 18:30
  • $\begingroup$ @MikeBattaglia While a boolean algebra would work as a model for some universe it's not the case that every boolean algebra would work as a model for every universe and certainly not for that of ZFC. My point is that you would need to add axioms to guarantee that it would work as a model for the required universe - this is much of what the axioms of ZFC does. $\endgroup$ – skyking Sep 22 '17 at 6:18
  • $\begingroup$ @MikeBattaglia As for what computers do: they're working in a finite, bounded and discrete arithmetic space. If that capability is enough then you might not need an infinite universe and not the axiom of infinity. However without axioms that extends the universe reasonably enough you would probably not have anything meaningful (say you know that you have numbers, but not how many - then what?). $\endgroup$ – skyking Sep 22 '17 at 6:25
  • $\begingroup$ I'm more interested in arithmetic than set theory so I'll move off of that... my idea was just that you can use Stone's theorem to give you a starting point, and then you can add axioms from there. $\endgroup$ – Mike Battaglia Sep 22 '17 at 15:35
  • $\begingroup$ For arithmetic: of course the least interesting part of this analogy is that computers are finite, and of course I don't want a finite version of arithmetic!! The point is to ask: given bits and NAND gates as primitive objects, how can we formalize arithmetic? Obviously you will need an infinite number of them. But how can you axiomatize this formally so as to build everything up from first principles? $\endgroup$ – Mike Battaglia Sep 22 '17 at 15:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.