Circular, or missing, definition in set theory?

Question

Revision in response to early comments. Users of set theory need an implementation (in case "model" means something different) of the axioms. I would expect something like this:

An implementation consists of a "collection-of-elements" $X$, and a relation (logical pairing) $E:X\times X\to \{0,1\}$. A logical function $h:X\to\{0,1\}$ is a set if it is of the form $x\mapsto E[x,a]$ for some $a\in X$. Sets are required to satisfy the following axioms: ....

The background "collection-of-elements" needs some properties to even get started. For instance "of the form $x\mapsto E[x,a]$" needs first-order quantification. Mathematical standards of precision seem to require some discussion, but so far I haven't seen anything like this. The first version of this question got answers like $X$ is "the domain of discourse" (philosophy??), "everything" (naive set theory?) "a set" (circular), and "type theory" (a postponement, not a solution). Is this a missing definition? Taking it seriously seems to give a rather fruitful perspective.

Answer 1

Caveat: it's become clear from comments and revisions that the original portion of this answer - leading up to the horizontal line below - is not really addressing the heart of the OP. I'm leaving it up since I think it is still at least somewhat relevant and potentially useful to readers. See below the horizontal line for an answer I thnk is ultimately more on-topic.

There is no circularity here.

A model of ZFC is simply a set $X$ together with a binary relation $E$ on $X$, satisfying some properties. We intuitively think of elements of $X$ as sets, but this is an intuition we impose on models of the theory from outside; a priori, a model of ZFC is just a special kind of (directed) graph.

For example, thinking of models of ZFC as graphs, the extensionality axiom just says

If two vertices are connected "from the left" to the same vertices, then they are in fact the same vertex. (More precisely: if $u, v$ are vertices such that for every vertex $w$ we have $wEu\iff wEv$, then in fact $u=v$.)

So for example, the discrete graph (= no edges at all) on two vertices is not a model of ZFC: the two vertices are each connected "from the left" to the same vertices (namely, none), but they are distinct.

Note that this demonstrates a fundamental point about ZFC (which is an instance of a more general fact about first-order theories in general):

The ZFC axioms describe, but do not define, sets.

---

EDIT: OK, the following is a bit long. The tl;dr is the following:

If we're skeptical of philosophical commitments such as Platonism (which I think we should be), then the right response to the circularity involved in defining mathematical objects in terms of sets while recognizing sets as mathematical objects is this: that all semantic reasoning, such as the development of model theory, is really syntactic reasoning taking place in a formal theory which we're choosing to interpret as being "about" objects whose existence is dubious, false, or meaningless. These syntactic claims (such as "ZFC proves that no set contains itself") are just statements about finite strings, and we can make sense of them even in a purely empirical way.

OK, now the long version:

Based on your edit (as far as I can tell, your "implementations" are just models), I think you're asking:

To what extent do we need to make set-theoretic commitments to do model theory?

(Note that I said "model theory," not "logic;" I'll say more about that in a moment.)

The answer is that we do in fact need to presuppose a notion of set. If one is a Platonist, this isn't necessarily problematic, and a formalist will dispense with the entire apparatus altogether and simply look at the formal system it takes place in (again, more on that in a moment).

There is also the option that what we really have here is a way of taking any "notion-of-set" and producing a corresponding model theory; this is exemplified by topos theory, where each topos can be understood as a universe of sets and model theory can be developed inside the topos. Based on your most recent comment to me, I think this might be interesting to you, but ultimately it runs into the same problem: we wind up having to talk about some sort of mathematical objects to develop semantics for mathematical statements, and this is ultimately no less circular or demanding of Platonism.

Now, what if we are unwilling to make any set-theoretic commitments at all? One approach is to argue that the whole semantic apparatus of model theory, and indeed all of mathematics, is not describing anything but rather is simply taking place inside a formal theory. That is, we don't view the statement "If there is a countable transitive model of ZFC, then there is a countable transitive model of ZFC + CH" as really referring to "countable transitive models," but rather is simply a string of symbols which has been produced by a certain formal system. The fundamental question of formalism, to my mind, is why the formal systems we do math in are valuable and interesting, but there's no doubt that formalism provides a vehicle for doing mathematics with the minimal philosophical commitment.

Now, after all, we do need some commitments to get off the ground. For "naive" formalism, this amounts to a commitment to the "existence" of the natural numbers in some sense; further examining this notion, we can try to reduce the philosophical commitment involved even further. For example, "truly empirical" mathematics is extremely ultrafinitist: the only things one is allowed to assert is "the string $\sigma$ is deducible from the strings $\sigma_1, ...,\sigma_n$," and only in the case when one actually has a formal deduction of $\sigma$ from $\sigma_1,...,\sigma_n$.

Why am I bringing this up? Well, the point I want to make is that formalism helps us not worry (as much) about circularity without invoking some kind of Platonism. Specifically, while one can be suspicious of set-theoretic foundations of mathematics because of the circularity involved in defining mathematical objects via sets while sets themselves are mathematical objects, a claim like "ZFC proves $\sigma$" is universally intelligible. Essentially, what this means to me is that we can do mathematics as if we were Platonists without actually making the philosophical commitments involved in any serious way, and still be doing "honest mathematics" - the point being that the formalist perspective gives us a bulwark to "fall back to."

This "optional Platonism," I think, is why mathematicians tend not to care about these issues; we tend to recognize that we could reduce all our reasoning to concrete statements about finite strings, and therefore that our Platonist statements can be translated into obviously meaningful ones.

Of course, this translates (one of) the Platonist challenge(s) - "In what sense can mathematical objects be said to exist, and why are we justified in claiming that they do?" - into the "formalist challenge:"

What criteria determine whether a formal theory is "mathematically valuable"?

I have strong and wrong opinions on this matter, but I think that's off-topic for this specific question.

Answer 2

Perhaps, your confusion may be resolved by realizing that we do not define what a set is, using the axioms of ZFC. Sets are to us like points are to Euclid. Sets are the primitive objects that we are going to work with.

Let me take a Platonist approach to elaborate. When you set up your axiomatic system, which is ZFC in this case, you assume that there is a universe of objects over which your quantification takes places. (Otherwise, you cannot attach semantics to your system.)

Sets are simply the objects in the universe. Nothing more, nothing less. When you include a binary relation symbol $\in$ in the language of your axiomatic system, you assume that between any two objects $x$ and $y$ in your universe, the atomic formula $x \in y$ is either true or false. So, the answer to your question "what is the domain of this function?" is the following: The Platonic universe of sets, which is somewhere in the sky!

Whether a sentence such as $\forall x \exists y \neg y \in x$ is true or not depends on whether for every set $x$ there is a set $y$ such that $x \in y$ does not hold. Since we do not have direct access to the Platonic universe of sets via our usual senses, we cannot directly check if this is the case. Consequently, we postulate that some statements about the universe of sets are true, namely, the axioms of ZFC. We then study the logical consequences of these axioms. Notice that the statement $\emptyset \in \omega$ is not true because we have some kind of logical function $\cdot \in \omega$ which checks the membership for $\omega$. It is true because it follows from the axioms which posit various facts about the relation $x \in y$.

I admit that I don't fully understand what your problem is. But as you can see, you may give a meaning to all these without circular reasoning. You may also take a formalist approach and simply think of the game of proving the logical consequences of the axioms of ZFC without worrying about questions such as "what is a set?", "what does $x \in y$ mean?".

Answer 3

This answer doesn't really have any ideas that are not already present in Noah Schweber's answer, but there are some points that I feel should be made more forcefully. In particular, I'd like to focus on a couple statements you've made which I think reflect a fundamental misunderstanding of the purpose of axiomatic set theory.

You start your question with the assertion that

Users of set theory need an implementation (in case "model" means something different) of the axioms.

You also stated in a comment that

I'm a working mathematician, so am concerned with usable implementations rather than the metatheory.

These statements are incorrect. Using the axioms of set theory (the way a working mathematician would) does not involve any contact whatsoever with models or "implementations" of the axioms. The primary purpose of axiomatic set theory is to provide a precise, formal framework for making statements and proofs in mathematics. In other words, it is "the rules of the game": the statements we are allowed to talk about are those which can be expressed in the first-order language of set-theory, and the statements we are allowed to prove are those which can be deduced using the deduction rules of first-order logic from our axioms of set theory.

The value of having such rules is that they eliminate any ambiguity about what is or is not a valid proof. We don't have to rely on any imprecise intuition about what sets are or how they behave; we can reduce all of our reasoning to manipulating finite strings of symbols according to certain formal rules. (This is the purely syntactic formalist approach described in Noah's answer.)

What I want to emphasize here is that an ordinary "user" of axiomatic set theory only ever encounters this syntactic approach. If you are an ordinary mathematician using set theory as your foundation for mathematics, you are always just using the axioms as your formal foundation. If you do imagine that you are working with some "implementation" of set theory, this is a philosophical (Platonist) statement, not a mathematical one.

Now, some mathematicians do also study models of set theory (and such mathematicians are usually called "set theorists"). But this is separate from the use of set theory as a foundation, and so the apparent circularity of using sets to do so is not a problem. We study models of set theory because they are an interesting type of mathematical structure, and also because they provide a means of proving that our formal syntactic approach to set theory cannot prove certain statements (e.g., the continuum hypothesis). But even if no one had ever invented the notion of a model of set theory, we would still be able to use the axioms of set theory as a foundation for mathematics.

Answer 4

I'm not sure I understand your question, since at first it sounds like you're thinking of $\in$ as a multi-valued function that sends a set $A$ to an element $x$ of $A$, but then I would expect you to be asking about the range of such a function rather than its domain. I'll assume that you are, loosely speaking, asking about where all those elements of sets come from.

Mathematics as commonly practiced is atomic in the following sense: When we define something, such as a group, we typically think of the ground set of the group as comprising "things" or "atoms." The identity of these atoms is left vague, since after all, we want to allow them to be anything—numbers, matrices, functions, formal sums, etc. All that matters is that they have some kind of tangible identity.

In particular, most of us have a vague feeling that these atoms are distinct from sets. Of course it is possible for an atom to itself be a set, since we can form sets of sets, but intuitively, most of us feel that there is a distinction between atoms and sets. Therefore we may come to axiomatic set theory with a tacit expectation that it will formalize atoms as well as sets.

Though this can be done, the most common axiomatic set theories are not atomic. In particular, in ZFC, there are no atoms that are distinct from sets. Everything is a set. If you need some atoms, then you have to build them out of sets, starting with the empty set and working your way up. This is a little unintuitive and takes some getting used to. But once you get used to it, it has technical advantages. Most notably, you don't have to fuss with two different "kinds" of things (atoms and sets); you only ever have to deal with one kind of thing. Experience shows that everything you would want to do with atoms can also be done with sets standing in for the atoms.

I hope this explains why the axioms about atoms that you seem to be expecting to see in ZFC are absent.

Answer 5

Thinking about the distinction between language and metalanguage may be helpful here. When one describes set theory as possessing a single binary relation denoted $\in$, one is operating at the level of metalanguage. Specifying axioms satisfied by $\in$ is at the level of the language. At this stage sets could be beer mugs as Hilbert famously said in a slightly different context.

Next, one assumes the existence of a model of the language, and interprets the meaning of the language, or more precisely of the theory expressed in the language, in that model (no more beer mugs).

In my experience, traditionally trained mathematicians (who have never taken a logic course) have great difficulty with the language/metalanguage and theory/model distinctions. This is because some of them tend to think of mathematics as "one great monolithic thing" and introducing such dichotomies goes counter to that philosophy. I don't think Paul Halmos ever overcame his suspicious attitude toward the standard dichotomies in logic; for details see this 2016 publication in Logica Universalis.

As far as the OP's comment to the effect that "Philosophical analysis of the question is unhelpful" I would agree in the sense that there is a lot of unhelpful philosophy of mathematics out there; a sterling example is the work of Hide Ishiguro on Leibniz which manages to combine bad mathematics, bad history, and bad philosophy in a single chapter 5; see this 2016 publication in History of Philosophy of Science. On the other hand, the OP's problem with alleged "circularity" is based precisely on certain philosophical partis pris as I tried to suggest above.

Note 1. In response to the new version of the question that shifts the emphasis somewhat to functions and relations, note that it may be helpful to consult the article

Leinster, Tom. Rethinking set theory. Amer. Math. Monthly 121 (2014), no. 5, 403–415

which seeks to present an accessible introduction to a category-theoretic approach to the foundations focusing on functions (instead of points and sets).

Answer 6

If by "the domain of $x \in A$" you mean the objects you can put in $x$ and $A$ then the answer is everything. This is due to the fact that in set theories such as ZFC and NBG all objects are set/classes (they have all the same type).

I am assuming your thinking $x \in A$ as an operation that associates to a pair of sets $(x,A)$ a truth value. This way of thinking it is fine as long as you consider the concept of operation as a primitive one and you do not identify it with the set theoretic defined one.

I hope this helps.

Answer 7

I think what you mean when you said that $x \in A$ must be a logical "function", is that it is an assignment that sends a pair of sets to a truth value, of course each object in each pair is a set that can substitute the symbol $x$ or the symbol $A$, in this sense $x \in A$ is called a "propositional function", you can refer to Russell on this in his "History of mathematical philosophy". Your question is legitimate since in order to know a function, then its domain must be specified in order to complete the characterization of a function, now its range is known which in binary logic it is $\{T,F\}$. So the domain can be seen as a set of all $sets$ that the axioms are speaking about, notice that the circularity is only apparent, i.e. if you think that the domain of discourse must include ALL sets as elements of it, then clearly the domain of discourse cannot be a set, and you'll be into searching for this "weaker" notion that you mentioned. But that's not how things are understood, the understanding is that the elements of the domain of discourse are the sets that we are speaking about by our axioms and this doesn't include the domain itself. If you want you can add a primitive constant symbol $V$ and relativize all axioms to this constant [i.e. all quantifiers are written bounded in $V$]. So the theory is not aiming to speak about all sets, it is only aiming to speak about sets within $V$, more specifically it only speaks about sets that have the characteristics that are specified by the axioms, not of every possible set. Given this partial sectoral understanding, the apparent circularity would vanish. Of course I'm speaking in relation to $\text{ZF}$ and related extensions. On the other hand there are indeed theories that includes the universe of all sets spoken about by the theory among the objects its speaking about, $\text{NFU}$ would be such an example, but here the circularity is obvious and actually admitted. But in the context of $\text{ZF}$ set theories, nothing of that is endeavored, so you can keep having stronger and stronger extensions with each extension defining the universe of discourse of the lower theory, and you can go along that indefinitely, and again without being involved in any circular issue.

If you are not content with this and want some other kind of 'collection' other than sets and classes, then you can go to Mereological totalities, perhaps those would prove to be weaker than sets in your sense. So you can refer to work on "Mereology" which is about Part/Whole relation. A less radical shift is to think of the universe of discourse to be a set/class of a higher sort than its elements, this would simply break the acyclicity, so the variables in the theory are substituted by "elements" of the domain of disocurse, but the domain of disocurse itself being of a higher sort do not substitute any of those variables, and we can liberally define sets of higher sorts as collection of the lower sort objects, so you need to refer to type theory and "Predicativity" issues to break the circularity that you think it exists between sets at theoretic/metatheoretic levels.

Another main concern is that the question itself is a little bit unclear, sometimes it appears as if the $OP$ is asking for a specific domain of discourse? and he states that this is a mathematical concern, but did any mathematician stated 'before-hand' the domain of discourse for the 'addition' operator for example, we can also incorporate it to logic and by then the formula $x + y = z$ would indeed qualify as a "logical function" in the sense written here, since it is a 'propositional function' a ternary one really sending triplets to truth values, now had a mathematician cared to find an apriori way to 'specify' "all possible numbers" before we define numbers inside an arithmetical system? this can be done in set theory, yes, but I don't think it was done in mainstream mathematics, we can indeed have many domains that fulfill the same rules about the addition operator, we can take it to be $Z$ or $Q$ or $R$ etc.. All what a logical theory needs is a clear set of syntactical rules, and semantics can be attached to it to explain it, and it need not be fixed to one kind of explanation. Perhaps the $OP$ was objecting to the "nature" of possible domain(s) of discourse, seeing circularity between saying that the domain is a 'set' and having the theory speaking internally about 'sets', this can be resolved in type theory, predicative definitions, or even more radically in Mereological totalities, etc.., I don't see a deep issue to describe it as being something that philosophical account on it was unhelpful? It is just a simple distinctive issue, simple distinctive speciation would resolve it! I don't see a deep argument raised here.

Answer 8

This is in response to the new edited version of the question.

You are using "indicator" functions on $X$ but with respect of membership in $X$ instead of subset-hood of $X$ [although one better take $X$ to be transitive, so that every member of $X$ be a subset of $X$].

This is more complex, your $X$ is what we usually think of as a domain of a model, your relation $E$ is the membership relation of the model which is defined on the domain, and your $\in$ is the element-hood in the domain, possibly this approach can work, but what's the point of it really. I mean why not take the simpler way of saying that we have a non empty collection $X$ and stipulate ordered pairing as a primitive, axiomatize $\forall a,b \in X (\langle a,b \rangle \in X)$ and of course axiomatize the basic property of ordered pairs, then let $E$ be a non empty collection of ordered pairs in $X$, then Define the atomic formula $x \ E \ y$

$$ x \ E \ y \iff \langle x,y \rangle \in E$$

Then write the axioms in terms of atomic formulas using $E$ with all there quantifiers bounded by $X$. Of course 'sets' are defined simply as 'elements of $X$' [i.e.; $a$ is a set iff $ a \in X$]

Those axioms would serve to lay down the basis for characterization of $E$.

It needs to be noticed that the customary $\in$ spoken about in ZFC would be the relation $E$ here, since the axioms will speak about $E$, I mean "Extensionality, pairing, union,..." all would be characterizing the relation $E$

To me that's simpler than taking indicator functions on the whole domain respective to elements in that domain, those functions would be outside of the domain itself, so how for example you'll quantify over those functions (you call as sets)? If you quantify over them then you enter second order logic arena? If you wont quantify over them, then you may use the constant logical pairing function $E$ of yours, and possibly another constant one place function symbol $h(a): X \to \{0,1\}$ for $a \in X$, then you present the axioms quantified over elements of $X$, and write down formulas in terms of $h$ and $E$, not that easy but it can be done I think. You need to have ordered pairs $\langle,\rangle$ as primitives, symbols $0,1$ as constants, also $\in$ and favorably $=$ as primitives. It can be done I suppose, but I don't know what is the point behind this? It appears more complex to me.

Answer 9

The relevant quantifiers and relations in mathematical axioms should be understood as predicate logic. In the case of ordinary first-order predicate logic, the membership operator $\in$ is defined as a binary relation over the universe, or domain of discourse, sometimes denoted $\Omega$.

Ordinarily, you can consider $\in$ to be a function and $\Omega$ to be a set of possible elements*. Yet as you've noticed, if you try to use mathematics founded in set theory (e.g. set-based domains and functions) to interpret set axioms, you'll introduce a form of circularity**.

One solution is to consider logic to be valid independent of mathematics. In the case of ZF or other systems, the axiomatization is first-order predicate logic. So long as first-order logic works, you don't need a mathematical interpretation.

Alternatively, you can consider sets as primitive and foundational to mathematics. ZFC is an example of how to interpret sets as primitive notions equivalent to objects in a formal logic and suitable as part of a foundation of mathematics. In this case, set axioms could be a description of non-foundational sets which are defined in terms of the primitive foundational sets used in definitions.

---

*Usually, objects in the domain of discourse could be anything in ordinary first-order logic, or for set membership, anything of which you could ask "is this a member of that set?". But in the context of mathematics it could be limited to defined mathematical objects, or in the context of pure set theory reduce to only sets.

**Actually, circularity isn't necessarily a problem as long as the axioms are satisfiable.