8
$\begingroup$

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)$?

$\endgroup$
2
  • $\begingroup$ You might consider things like LISP and lambda calculus and Fitch's minimal calculus. While a set-theory version may have its advantages, these examples have a decent literature behind them, and may have ideas or formulations that may prove useful to your query. $\endgroup$ Jul 9, 2014 at 17:24
  • $\begingroup$ On a side note, finite algebras whose derived term operations constitute all operations on the base set are called primal, and an operation that (along with projections) generates those terms is sometimes called a Sheffer stroke. If you come up with a fundamental operation, slicing off a finite piece gives you a Sheffer stroke. There may be suggestive and useful literature for you in that realm. $\endgroup$ Jul 9, 2014 at 17:32

2 Answers 2

17
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Very useful article (had to buy it and now I am reading it) - and it makes reference to another article where also my operation $g$ is discussed. I am not sure"adjunction" is a good name for the operation $f$ (even though it comes from Boolos GST (Generalized Set Theory) - unless it really somehow has to do with adjoint functors (Internet searches of "adjunction" bring to "adjoint") $\endgroup$ Jul 10, 2014 at 15:05
  • 1
    $\begingroup$ I think the terminology for the operation comes entirely from natural language---one is adjoining a new element to a set---and the motivation has nothing to do with adjoint functors. $\endgroup$ Jul 10, 2014 at 15:10
4
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ I am not fluent with category theory and it takes me too long to catch the essence from diagrams. I will look into AST when I become fluent with categories. Categorical grammar looks really nice - maybe once I will also learn its basics $\endgroup$ Jul 10, 2014 at 15:29
  • $\begingroup$ It would help if you once share a reason why ZFC is not essentially algebraic. $\endgroup$ Jul 10, 2014 at 15:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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