Skip to main content
4 of 4
edited tags; edited title
Jim
  • 548
  • 2
  • 8

Relation between semiring structure of natural numbers and their hereditarily finite sets structure under bitwise operations

Some background

The natural numbers $\mathsf{Nat}=\{0,1,2,\dots\}$ has the structure of a semiring under addition and multiplication.

Write $\mathsf{HFS}$ for the set of all hereditarily finite sets (the inductively defined collection of all sets that are finite and all of whose elements are hereditarily finite).

$\mathsf{Nat}$ bijects with $\mathsf{HFS}$ under the Ackermann coding $ack:\mathsf{Nat}\to\mathsf{HFS}$, which maps $n\in Nat$ to $$ ack(n)=\{ack(i) \mid BIT(n,i)\}, $$ where $BIT(n,i)$ is the BIT predicate, which is true precisely when the $i$th bit of the binary representation of $n$ is $1$.

This trivially gives the numbers $\mathsf{Nat}$ the structure of a lattice, where for example $$ n\vee n' = ack^{-1}(ack(n)\cup ack(n')). $$

(Note that this simple-seeming construction can do a lot. For example as Wikipedia notes with can use it to construct the Rado graph. I also remember reading somewhere that every nonstandard model of natural numbers gives rise to a model of ZF set theory, via $ack$.)

My question

The correspondence runs the other way too: $\mathsf{HFS}$ inherits a semiring structure from $\mathsf{Nat}$, via $ack$. But this invites us to ask:

  1. What is known about this structure?
  2. In more detail: what is known about the interaction between the semiring structure of $\mathsf{Nat}$ and its lattice structure via $ack$?
  3. Does a theory of "set-like semirings" exist: lattice-ordered semirings which are algebraic structures with the structure of semirings and lattices, along with axioms on the behaviour of $n\vee (n' + n'')$; as there are axioms on the behaviour of $n * (n' + n'')$ and $n \wedge (n' \vee n'')$? (I'm not particular about semirings and lattices; e.g. if some kind of bounded NAND operation is more natural than AND and OR, then that's fine too. What I care about is mixing the arithmetic structure with the natural bitwise/HFS sets structure in some sensible abstraction, above and beyond the bare fact of the definitions as noted above.)
  4. If no such algebra exists, why shouldn't it exist? What is the underlying barrier to constructing it?

Thank you.

Jim
  • 548
  • 2
  • 8