Is there one binary operation foundational for set theory?

Question

The membership relationship "$\in$" is foundational for set theory, in the sense that the axioms of any set theory are formulated in the language of "$\in$". Naturally, the question arises whether there is one binary operation, which is foundational in this sense. With such an operation identified, the "algebraic set theory" would be a theory of universal algebras with this operation, and maybe with some constants (like the 0-ary operation selecting the empty set $\varnothing$). The supports of such algebras are also a foundational issue to be addressed, but such issues are resolved in literature - these supports can be "universes", that is sets "closed" under all operations in which we are interested. This issue is not in the focus of this question - important is the binary operation in the title.

I see two such operations, each of which sounds to be foundational for set theory:

• $f(x, y) = \{x\} \cup y$, since ($x \in y$) iff $f(x, y) = y$,

• $g(x, y) = \{x\} \cap y$, since ($x \in y$) iff $g(x, y) = \{x\}$.

Each of these two operations is foundational for set theory, because in any axiom of a set theory we can replace the atomic formulas of the form ($x \in y$) with corresponding equivalent equations in (1) and (2). But only this formal procedure is not very interesting. Way more interesting is whether there are algebraic properties of these two operations which would allow to replace other formulas (not only the atomic formulas) with equations in terms of $f$ (or $g$) - ideally, to replace all logical formulas with algebraic equations (identities). I believe, this ideal cannot be achieved because of quantifiers, unless some infinitary generalizations of these two operations are found. Therefore, instead of the ideal goal, a realistic goal is also interesting - to replace with algebraic equations all subformulas under each quantifier (or the matrix in a prenex form).

My research relates to set-theoretic modeling of natural languages and these two operations sound to model a linguistic phenomenon. I would appreciate even partial answers to my questions above, or references to something close. Here are some more concrete questions about this:

1. Are there known any properties of the operation $f(x, y)$ — properties interesting for the foundations? I see some of such properties, but a set-theorist or algebraist will probably indicate also other properties:

   • (a) The operation $f(x, y)$ allows to define in set theory the natural numbers (finite ordinals) by induction: $0 = \emptyset, \ n+ 1 = f(n, n)$. Here "$0$" is number "zero" and "$\varnothing$" is "empty set".

   • (b) For any $x_1, x_2, \ldots, x_n$, $[\{x_1, x_2, \ldots, x_n\} = f(x_1, f(x_2,..., f(x_n, \varnothing)\ldots))]$. Thus, the notion of finite set can be defined through operation $f$ (and the 0-ary operation selecting $\varnothing$). Here, "defined through" is same as "is superposition of".

   • (c) For any $x$, $\{x\} = f(x, \varnothing)$. Thus, the singleton formation operation can be expressed through $f$ (and $\varnothing$).

2. Can the binary operation of union be expressed through $f$? If not, then are there partial cases (like finite sets) when it can?

3. Are there any properties of operation $g(x, y)$ — properties interesting for the foundations?

4. Is there another binary operation similar to $f$ and $g$?

5. Could there be infinitary generalizations of $f$ or $g$ which would allow to axiomatize set theory in algebraic equations without quantifiers (except the external universal quantifiers in algebraic identities)?

If I correctly phrased (in mathematical terms) this last question, then I suspect, this is a really difficult question. To make it more precise, remember that infinitary unions and intersections play the role of universal and existential quantifiers. Also, notice that if we treat comma (,) as a symbol of a binary operation in the denotation of a finite set $\{x_1, x_2, \ldots, x_n\}$, then this operation is associative, commutative and idempotent (like union). This, together with 1(b), cannot help define an infinitary (in some sense) generalization of $f(x, y)$?

Answer 1

Your operation $f$ is called adjunction, and Laurie Kirby wrote an article extolling the virtues of adjunction in providing an alternative foundation for finitary set theory, in the development of the hereditarily finite sets, thus making an alternative (but equivalent) development of Peano arithmetic.

Laurence Kirby, Finitary Set Theory, Notre Dame J. Formal Logic Volume 50, Number 3 (2009), 227-244.

Abstract. I argue for the use of the adjunction operator (adding a single new element to an existing set) as a basis for building a finitary set theory. It allows a simplified axiomatization for the first-order theory of hereditarily finite sets based on an induction schema and a rigorous characterization of the primitive recursive set functions. The latter leads to a primitive recursive presentation of arithmetical operations on finite sets.

I couldn't find an online version of the article that isn't behind a paywall. My recollection is that the paper is well-written and has many attractive figures.

Answer 2

There is a whole area of algebraic set theory. The internal language of a topos can be expressed as an essentially algebraic theory, see Lambek & Scott's "Introduction to higher-order categorical logic". An essentially algebraic theory is a slight generalization of an equational theory, which you asked about. I am pretty sure that ZFC is not essentially algebraic, but can't think of a reason right now -- there must be a simple one.

If you're set on classical logic, you can always throw in one more equation, namely $p \lor \lnot p = \top$. The internal logic of a topos is more or less like bounded Zermelo set theory (where "bounded" means that only bounded separation is allowed).

In any case, I am surprised you're expecting set theory to do anything useful for linguistics. The language of set theory is notoriously not at all "natural" from a human perspective (although the concept of set is). How about categorical grammar and that sort of thing?