10

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.

Frank Quinn
  • 271
  • 1
    $x \in A$ is a "propositional function", it returns the values of truth or false for every two objects substituting the symbols x and the symbol A, I'm using the terms of Russell in his introduction to mathematical philosophy. The domain of that function is a set of all those sets that the theory is speaking about, i.e. of all those sets that can substitute those symbols mentioned above. I don't see any circularity here? it is called as the domain of discourse. – Zuhair Al-Johar May 21 '18 at 20:19
  • 2
    In ZFC set theoy it is implicitly understood that the domain of discourse we quantify over is the universe of sets ${x:x=x}$, although this question would be more appropriate over at math SE. – Alec Rhea May 21 '18 at 20:22
  • 1
    Reopened within less than 25 minutes after closing! This must be a record. – Mikhail Katz May 22 '18 at 12:41
  • 10
    You will always have some primitives. One might question your notions of operators and functions and ask how you define them noncircularly. – Monroe Eskew May 22 '18 at 15:34
  • 1
    That one is not a function (within the theory) hence it doesn't make sense to ask for it's domain. – Qfwfq May 22 '18 at 17:24
  • 8
    We use ZFC to help us understand sets. We use sets to formalize first-order logic, including ZFC. This is an example of a kind of hermeneutical circle - https://en.wikipedia.org/wiki/Hermeneutic_circle . To break the circle, the most common recourse is to not formalize ZFC using sets, for example by viewing it as solely a syntactic theory that can be studied in weak systems like PRA. The downside of that approach, of course, is that it eliminates our ability to talk about semantics - models of set theory - so we can only talk about provability. All of this is well known, in any case. – Carl Mummert May 22 '18 at 22:39
  • Many words have been minced on this over at [Mathematics.se]. – Asaf Karagila May 23 '18 at 07:23
  • 4
    I don't think the attempts to shut down this question are reasonable. The issue may be trivial for editors trained in logic and set theory, but notice that the OP is a leading specialist in 4-manifold topology. If this issue bothers him it is a sure sign that it is not a trivial issue for traditionally trained mathematicians. – Mikhail Katz May 23 '18 at 16:35
  • 10
    It's a trivial issue, despite the pedigree of the person asking it. It shows absolutely no effort to learn anything about first-order logic. It is a more elementary question than 50% of the questions at Math Stack Exchange. – arsmath May 23 '18 at 17:29
  • 3
    My challenge in writing an answer to the question is that I can't tell if the question is literally "what is the domain of $\in$", or whether it is something deeper. Clarification would be very welcome. – Carl Mummert May 23 '18 at 17:50
  • 11
    Frank's work in geometric topology is fundamental and deep. Given his contributions to the subject, he has in my opinion earned the right to ask questions here even if specialists find them naive (and what is more, as someone who has basically never paid attention to foundational issues, I found the answers useful and clarifying). I would be opposed to closing this question. – Andy Putman May 23 '18 at 17:51
  • 5
    @arsmath : I disagree that the question "shows absolutely no effort to learn anything about first-order logic." I'll grant that the question isn't clearly phrased, but it's not a "technical" question of the sort that can be answered by just picking up a textbook. It's a question about whether set theory can be used as a foundation for mathematics and is thus at least a partly philosophical question about a point that is often not clearly addressed in textbooks. – Timothy Chow May 23 '18 at 22:37
  • 3
    Andy's comment convinced me. – Andrés E. Caicedo May 24 '18 at 00:14
  • @TimothyChow: thanks for the link to your forcing paper. There seems to be a very clear point that ZFC encodes mathematics but is not the ontological basis for mathematics, and that makes perfect sense to me. (And of course the whole point of forcing is to use ZFC as an object itself to be studied mathematically.) But then, I don't see how one is not forced into a sort of naive Platonism that the math is already there, even if in some multi-verse form. – Jim Conant May 24 '18 at 05:09
  • 11
    So people are now just openly treating people differently because of their pedigree? No smart person can ever ask a dumb or lazy question? – arsmath May 24 '18 at 06:38
  • 8
    It's fine to find the question interesting if you've never thought of it. But that's equally true if the question was asked by a college sophomore who stayed up all night smoking pot and thinking about their philosophy and logic class. – arsmath May 24 '18 at 06:47
  • 2
    @arsmath In case the previous to last comment was (partly) meant for me, the convincing bit was "as someone who has basically never paid attention to foundational issues, I found the answers useful and clarifying". – Andrés E. Caicedo May 24 '18 at 10:17
  • 1
    @Jim Conant: rather than thinking of math as already there in Platonist-like terms, one can also see math as already there in practice, as a semi-formal theory. I think a larger issue lurking behind this kind of question is that the "foundationalist" mentality that there will be a single formal theory for mathematics (or that this is desirable) is much less common among logicians now than it was in the past - but the literature hasn't caught up, so questions like this might seem to ask about a particular kind of foundational role for ZFC that few are still trying to defend. – Carl Mummert May 24 '18 at 10:56
  • 6
    To my way of thinking, the answer to the question is the theory/meta-theory distinction, discussed at length in any good treatment of set theory, including a typical good undergraduate or graduate set theory course. A deep felicity with this distinction underlies the set-theoretic advances with the independence phenomenon. Set theorists build new models (or interpretations) from old, thereby showing the relative consistency of various set-theoretic principles, often in terms of the large cardinal hierarchy. In particular, this treatment is deeply understood and definitely not "missing." – Joel David Hamkins May 24 '18 at 14:47
  • 7
    People's pedigree is important in the sense that if someone has made important contributions to mathematics, then they have earned the right to be given the benefit of the doubt. One of the important functions of MO is that it is supposed to be a place where professional mathematicians can ask questions that interest them but are outside their speciality. Sometimes these questions might sound stupid to a specialist, but I can assure you that as someone whose education probably resembles Frank's more than that of a logician, the distinction between theory and meta-theory has never came up – Andy Putman May 24 '18 at 15:00
  • 4
    anywhere in my work or reading. I learned a lot from the various answers to this question. I would hate it if MO became just a place where specialists can ask other specialists their super-technical questions (after all, don't all of us mostly know the experts in our own special fields, and thus can more efficiently just email them?) – Andy Putman May 24 '18 at 15:03
  • 3
    Andy, I agree with you, and I don't think the question should be closed. – Joel David Hamkins May 24 '18 at 15:16
  • The new version of the question is not actually a new version but a separate follow-up question (which is less interesting than the original one IMHO). Moderators could consider reverting this substitution and encouraing the OP to post a separate question if necessary. – Mikhail Katz May 24 '18 at 15:58
  • 2
    For what it's worth, I think the question is better in its current form - it's not the axiom of extensionality in particular that's the focus, and I think that detracted from the clarity of the original question. I don't think it would be appropriate for the moderators to revert it. – Noah Schweber May 24 '18 at 16:02
  • 7
    I find somewhat strange the assumption that "Users of set theory need an implementation of the axioms". The entire point of them being axioms is that they are taken for granted, and you can reason from the axioms instead of reasoning directly about some "implementation". (This is closely related to the formalist approach that Noah discusses.) – Eric Wofsey May 24 '18 at 16:21
  • 5
    To put it another way, the axioms of set theory have a fundamentally different purpose from the axioms of group theory. We aren't trying to study models (or "implementations"); we're trying to set up formal deductive rules we can use to reason about mathematics as a whole. (Set theorists of course do also study models of set theory, but they do so already accepting some set theory as their framework. In other words, as Noah said, if you want to study models, your metatheory needs to already have set theory.) – Eric Wofsey May 24 '18 at 16:31
  • 2
    I have heard many times that “most ordinary mathematics” can be formalized in second-order arithmetic. In other words, we can believe that the only genuine mathematical objects are natural numbers and real numbers, and code everything with those. If you buy this position, then an implementation of ZFC is just a real number with certain properties. – Monroe Eskew May 24 '18 at 17:05
  • 3
    As @Monroe Eskew mentions, there is a hierarchy of metatheories we can use to study ZFC. In PRA or PA, we can talk about provability but not models, although we can often formalize forcing arguments syntactically in these settings. In second-order arithmetic we can talk about countable models of ZFC or any other countable theory. We can also use set theories such as ZFC itself or MK as metatheories to study ZFC, allowing us to look at more general models and also to do things such as perform ultraproduct constructions on models. – Carl Mummert May 24 '18 at 17:15
  • Incidentally, if you're interested in the idea of doing mathematics in weak (or perhaps more positively: more concrete) systems you may be interested in reverse mathematics. The connection with your question that I see is that reverse math can be thought of as a corollary of the formalist-as-defense position in my answer: if mathematical claims are ultimately only "guaranteed to be meaningful" when they are translated to statements about formal systems, we should be interested in what formal systems can prove them; (cont'd) – Noah Schweber May 24 '18 at 18:42
  • 1
    @AndyPutman, I agree. It's often difficult to pose the right question precisely because you don't know what you're talking about! Questions like these strike me as subtle, even for the experts. It's fair if someone has a vague notion to try to clarify that notion by asking an imprecise question. Perhaps if you knew how to state the question with precision, the answer wouldn't be that far away. And, as has been pointed out, if ever there was a place to ask such questions, it's here. – James Smith May 24 '18 at 19:06
  • 1
    I must admit that I understood nothing of this 'implementation'. Why not simply have models that satisfy the axioms? – Zuhair Al-Johar May 24 '18 at 19:29
  • 7
    The revised question is more clearly stated, except that Frank Quinn's insistence (in the comments to Noah's answer) that he is not asking about the logic or the metatheory are totally baffling to me. As far as I can tell, he is asking exactly for more clarification about the metatheory, and about whether using set theory for the metatheory is "circular." If he insists that he's not asking about the metatheory then I can't make any sense out of the question. – Timothy Chow May 24 '18 at 20:09

9 Answers9

34

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.

Phil Tosteson
  • 3,598
  • 1
  • 18
  • 23
Noah Schweber
  • 18,932
  • But some (most?) theories are introduced to try and provide an exhaustive characterization of one particular model, no? I mean, in most cases this is in fact impossible and there are other different models that the theory is not able to distinguish from the "real thing". But we still can try to approximate it better by strengthening the theory. And to do so we must have the "ultimate" model somehow present. So, does not it make sense to distinguish some class of "natural" models which have the property that $wEu$ in such a model implies that $w$ really is an element of $u$? – მამუკა ჯიბლაძე May 21 '18 at 21:18
  • 3
    @მამუკაჯიბლაძე Arguably, but that has nothing to do with any claimed circularity here. The point is that that distinction happens outside the theory ZFC, even if it motivated the construction of ZFC. – Noah Schweber May 21 '18 at 21:20
  • 4
    @noah I would like your answer very much, except that the circularity is right up front with the word "set" in "... a set $X$ with a binary relation ...". A statement like "$X$ is a set" is internal to an implementation of the axioms, and not available to describe an implementation. If you change this to ".. a collection-of-elements $X$ with a binary relation.." ("sets" are then defined in terms of the relation) then my question is: what is a "collection-of-elements"? – Frank Quinn May 22 '18 at 10:47
  • 1
    @FrankQuinn, no the statement "$X$ is a set" is not internal to an implementation of the axioms, actually there is no predicate "set" that is defined within the usual set theories (except in $MK$ were we artificially define it as an element of a class). Actually the statement $X$ is a set is very broad it involves objects within the universe of discourse of set theories and may involve the universe of discourse itself. "..is a set" is a characterization, not a definition internal to the theory. – Zuhair Al-Johar May 22 '18 at 11:28
  • 1
    Noah, I believe this answer might be more confusing for those naively believing that ZFC answers the question "what is a set". Sets are simply objects in the universe. @FrankQuinn: Once you set up your set theory, you notice that there is a way to formalize model theoretic notions within this system. Given a formal theory $T$, which is really a set whose elements encode strings, a model of $T$ is a(n actual) set $X$ together with... What Noah is saying is that, if we take a model of ZFC, the metatheoretic notion of a set and the internal notion of a set inside $X$ are different things. – Burak May 22 '18 at 13:37
  • 5
    @FrankQuinn : You might want to read the first few pages of my article on forcing, which addresses this apparent circularity. http://timothychow.net/forcing.pdf Another way out of the apparent circularity is to begin by treating sentences of ZFC as meaningless syntactic strings, not as "saying" anything about sets. After your machine has mindlessly generated enough strings, you then accidentally notice that the structure of these strings strongly resembles ordinary mathematical discourse, so you do a search-and-replace to convert journal articles to ZFC strings. – Timothy Chow May 22 '18 at 13:57
  • I like this graphical interpretation. In reality I'm one of the people who thinks there are just graphs, and 'set', 'class' are just a abstractions about parts of graphs. So I think the real backbone of foundation would ultimately be a kind of Mereotopological graph theory. Anyhow – Zuhair Al-Johar May 22 '18 at 16:31
  • 5
    @FrankQuinn So the circularity you're worried about is that we use "set" to define the semantics for first-order logic, but the things we believe about sets are expressed by a first-order theory to begin with (namely ZFC); is that right? – Noah Schweber May 22 '18 at 17:08
  • 3
    @FrankQuinn Can you clarify if I've interpreted your question correctly in my most recent comment? Once I understand what you're asking better, I can edit this answer to be more relevant. – Noah Schweber May 23 '18 at 18:15
  • @noah please look at the revised version; maybe it is clearer. The question is about usable implementations, not about the logic or metatheory. – Frank Quinn May 24 '18 at 15:21
  • 4
    @FrankQuinn If I understand correctly, your "implementation" is exactly a model in the sense of first-order logic, and indeed talking about models presupposes some amount of set theory. I don't understand your claim that this is not about the logic or metatheory; this is, as far as I can tell, exactly about the logic and metatheory, namely what commitments we need to make sense of the semantics for first-order logic. – Noah Schweber May 24 '18 at 15:26
  • @noah Try this: rather than "commitments we need to make sense of the semantics for first-order logic", I am asking about a description of domains in which first-order logic works reliably. My experience is that "commitments" and "sense" often have no logical force. Also, I want an interpretation for "model" that does not presuppose any amount of set theory, in order to avoid circularity. – Frank Quinn May 24 '18 at 15:49
  • 4
    @FrankQuinn "I want an interpretation for "model" that does not presuppose any amount of set theory" The point of talking about "commitments" is that I'm claiming that such a thing doesn't exist. I'm not sure, meanwhile, what you mean by a "domain in which first-order logic works reliably" - perhaps the idea of doing logic inside a topos, viewed as an alternative notion of "set," is on-topic for this? Regardless, see my edit. – Noah Schweber May 24 '18 at 15:51
  • 5
    Since my edit is quite long, let me state my view: there can be no semantic approach to mathematics which doesn't fall prey to either the need to make philosophical commitments (e.g. "sets exist") or circularity; however, mathematics can be developed on a purely formalist foundation, and this provides us with a method for ignoring the circularity while still doing "semantic" mathematics and not making any sort of Platonist commitment. – Noah Schweber May 24 '18 at 15:54
  • 3
    @FrankQuinn : If you think that using set theory to do model theory is 'circular' in some illegitimate sense, then I think you're still suffering from a basic confusion. The circularity is only apparent and is not real. If you insist on doing model theory in a non-set-theoretical way, then one could shoehorn it into some other framework; e.g., you can do a lot of finite model theory using arithmetic. There are probably ways to develop model theory using type theory. But I'd argue that this would be pointless; you'd be bending over backwards to avoid something that doesn't need to be avoided. – Timothy Chow May 24 '18 at 19:57
  • 3
    (cont'd) Furthermore, any "domain in which first-order logic works reliably" that one might propose is open to the same objection: What is your foundational basis for believing that first-order logic works reliably in that domain? Any answer to that question is no less "circular" than the standard approach. – Timothy Chow May 24 '18 at 20:01
  • 1
    @FrankQuinn The book "Foundations of Mathematics" by Kenneth Kunen may be of some assistance to you if your library has a copy. It is very up to date (published 2009) and explicitly discusses the roles of set theory, logic and model theory as they pertain to securing a foundation for mathematics without issue or paradox. – Alec Rhea May 24 '18 at 21:51
19

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?".

Burak
  • 4,135
  • 1
    "I admit that I don't fully understand what your problem is" - At first I 'understood' the problem, but then I realized the question is in fact not about set theory, but rather about logic. Set theory here is only an example. The deeper question (as I understand it now) is "What is the difference between symbols (of the language, as in logic) and functions/relations in any model (of the set of axioms etc.)" – Itai May 22 '18 at 13:43
  • Regardless from the rest of the answer, for me "Let me take a Platonist approach to elaborate" deserves a -1. Sorry. – Qfwfq May 22 '18 at 17:26
  • 2
    @Qfwfq: Well, if you do not like the idea of the universe of sets, we may choose a universe sets and restrict quantification to the objects in this universe, (informally) define truth of sentences with respect to this restricted universe and etc. The core of this answer has nothing to do with mathematical Platonism, it is trying to illustrate how the binary relation symbol $\in$ gets its meaning once you choose a universe to interpret it in. – Burak May 22 '18 at 17:28
  • 2
    @Burak: yes, you're of course right that the answer doesn't "use" platonism. Take my downvote as a "political" statement against a philosophical view of mathematics that I find immature and to be eradicated. Also this has few to do with your answer, but... you get my point ;) – Qfwfq May 22 '18 at 18:46
  • Are you sure we know what points are to Euclid? One colleague claims that Euclid wrote drawing instructions, and points for him are markings sufficiently small for unambiguously determining how to draw a line through any two of them. Accordingly, one might take the stance that we only need set theory as a substrate to do mathematics, and should only worry about unambiguity. Then sets would be not the objects of the universe but tools to express ("draw") what you want to say or learn about objects of the universe. – მამუკა ჯიბლაძე May 24 '18 at 04:54
  • 3
    @Qfwfq-- rather shameless. – Monroe Eskew May 24 '18 at 06:45
  • @burak Perhaps the question should be: what are the properties of the "universe" in a specific implementation. The revised version may be clearer. – Frank Quinn May 24 '18 at 15:24
  • @FrankQuinn: I believe, what you are trying to ask at the core, may have been addressed in my following answer to a closely related question: https://mathoverflow.net/questions/248965/do-set-theorists-use-informal-set-theory-as-their-meta-theory-when-talking-about/249006#249006. More specifically, what you are calling an implementation is simply a model $(X,E)$ of a (formalized) first-order theory. X is a set together with a binary relation which has an interpretation, just like your function $E$. If the model $(X,E)$ is a model of ZFC, then, for example, it satisfies the sentence... – Burak May 24 '18 at 18:08
  • @FrankQuinn: $\exists x \forall y \neg y \in x$. In other words, there is an object $x \in X$ such that for all $y \in X$ it is not the case that $y E x$. That is, if we interpret E as the membership relation, from the perspective of the model $(X,E)$, the object $x \in X$ is the empty set. Is $x$ the real empty set? Not necessarily. It behaves like the empty set within the model $(X,E)$. What does this have to do with what you are asking? I am trying to illustrate that there is no circularity with ZFC being able to talk about models of (the formalized theory) ZFC... – Burak May 24 '18 at 18:13
  • 3
    @FrankQuinn: Contrary to the popular belief, mathematics cannot bootstrap itself. You cannot prove something without assuming anything. If you want to talk about models of a theory mathematically, then this discussion has to take place within some other axiomatic system. (This is the theory/metatheory distinction.) Clearly, whatever axiomatic system you start with cannot be given proper semantics, unless you are willing to talk about it within some other system. At this point, you have to take this axiomatic system as is. You are just manipulating some strings, you may (or may not) give... – Burak May 24 '18 at 18:17
  • 3
    @FrankQuinn: ...some intuitive meaning to your symbols. But the point is, as Noah emphasized in his edit, whatever axiomatic system will be your "background" system, you have to either take a formalist approach or be willing to let go off your search for precise formulation of its semantics. – Burak May 24 '18 at 18:20
17

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.

Eric Wofsey
  • 30,718
15

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.

Timothy Chow
  • 78,129
  • I'm a working mathematician, so am concerned with usable implementations rather than the metatheory. You say "everything is a set". In an implementation the collection of all sets is not a set, but it should be a thing of some kind. Just because it doesn't have the properties required of sets doesn't mean it can't make sense. Or to put it another way, if we cannot make concrete sense of "the collection of all sets" then we don't have a practically useful implementation. – Frank Quinn May 24 '18 at 15:33
  • 1
    It's trivial to use class-based theories, such as Morse-Kelley set theory, where there are both sets and proper classes - the collection of all "sets" in a model of MK is itself an object in the domain of that model. One thing that the last 100+ years of set theory have taught us is that there are many concrete questions about the "collection of all sets" that are not resolved by any generally accepted axioms - for example the existence of various kinds of large cardinals, the continuum hypothesis, etc. Arguably, this shows we do not have a completely concrete notion of "set" to refer to. – Carl Mummert May 24 '18 at 17:09
  • 1
    @FrankQuinn : The standard way to handle classes in ZFC is to define them to be formulas with one free variable. But you're changing the question. The original question was about circularity. If your real question is about the usability of an implementation, then of course the answer is going to be different. – Timothy Chow May 24 '18 at 19:45
10

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).

Mikhail Katz
  • 15,081
  • 1
  • 50
  • 119
  • 3
    Can you give grounds for your belief about Halmos? – Todd Trimble May 23 '18 at 02:06
  • 1
    See the article linked in the answer. @ToddTrimble – Mikhail Katz May 23 '18 at 08:44
  • Thanks; unfortunately it's behind a paywall. The abstract is certainly provocative and intriguing! – Todd Trimble May 23 '18 at 11:50
  • 2
    See this for arxiv version as well as mathscinet link. – Mikhail Katz May 23 '18 at 11:56
  • 2
    My own feeling is that while your co-authored article is interesting and makes some good points, on this particular conclusion about Halmos I think there is overreaching. Halmos in his "automathography" (which you liberally draw on) reports how the scales fell from his eyes where he answered, "What is the propositional calculus?" with "the theory of free Boolean algebras" (p. 206) -- the same kind of insight was developed most penetratingly later by Lawvere who clearly realized how syntax was concentrated in free structures, and thus "theory" (e.g. a Lawvere theory) and "model" really (cont.) – Todd Trimble May 24 '18 at 01:28
  • 2
    could be treated on the same playing field. It seems to me that Halmos was trying to extend his insight about propositional calculus as about free Boolean algebras by algebraizing first-order logic in terms of cylindric or polyadic algebras. Now it may be true that cylindric or polyadic algebras isn't the most flexible or convenient formalism for this program -- I happen to believe Lawvere's hyperdoctrines are much better, by allowing a multi-typed, not a single typed algebraic signature. But in any case the same algebraizing impulse guided much of Halmos's logical work, and (cont.) – Todd Trimble May 24 '18 at 01:35
  • 3
    that's a sound mathematical impulse. Cf. this interview with Lawvere, http://www.mat.uc.pt/~picado/lawvere/interview.pdf, page 20, where he says "What is the primary tool for such summing up of the essence of ongoing mathematics? Algebra!" But to return to the answer: it's not at all clear to me that Halmos did not understand the theory/model distinctions; on the contrary, I think he tried hard to understand those types of things better, by mathematizing them in terms of algebraic structures -- this was a motif in one era of his professional life. – Todd Trimble May 24 '18 at 01:42
  • 3
    Halmos clearly and repeatedly states that he was suspicious of the type of dichotomies I mentioned. Do you have a source for claiming that he developed things like cylindrical algebras to help explain logic to mathematicians? From what I have seen, his motivation stemmed from his discomfort with the dichotomies standard for a logician, which motivated his attempt at algebraization, more than pedagogical concerns. In one of his last articles, he still includes a dig against "non-standard models" which in my mind is a sign of philistinism and intolerance, which was in particular his attitude.. – Mikhail Katz May 24 '18 at 08:59
  • ...toward Robinson's framework. This included false claims made in his "automathography" about the dating of his first encounter with Robinson's paper on invariant subspaces, which we also document in our article. @ToddTrimble – Mikhail Katz May 24 '18 at 09:13
  • 1
    I never made the claim you say I did, so I don't feel compelled to offer you a source for precisely that. My own reading (readers can draw their own conclusions from some relevant passages here: https://pdfs.semanticscholar.org/f269/3ca54467330231a9be81a094a694f3b942fb.pdf) is that he felt impatience with standard presentations, and I think he explains it well in terms of an analogy: imagine that groups were typically introduced, not as sets with an operation obeying simple axioms, but in terms of presentations (generators and relations), prefaced by a syntactic discussion of words (cont.) – Todd Trimble May 24 '18 at 12:14
  • and word reductions and substitutions based on relators and whatnot. So I think he's finding standard presentations of logic (propositional, predicate, etc.) as similarly needlessly fussy and complicated, and felt a desire to determine the real algebraic essence of logic (hence, algebraic logic). And I happen to think he's got a good point. (He may have well also felt a strong pedagogical impulse to share what he found with others.) Again I think that it's too strong to claim that he never did understand theory/model distinctions -- I think he likely understood them well after his struggles. – Todd Trimble May 24 '18 at 12:20
  • 1
    Meanwhile, the business about NSA is a matter separate from whether he had great difficulty with the dichotomies you speak of -- given that the thread is about understanding those dichotomies, the suggestion seems to be that Halmos didn't understand them, and that I would find too strong to be supported by the evidence. I repeat that it might be right that he was impatient with standard explanations, and I would direct you to the analogy with group theory which I think is quite apt, especially in the advent of Lawvere's thesis which was very clarifying. – Todd Trimble May 24 '18 at 12:25
  • 2
    I never claimed that Halmos did not understand these standard dichotomies. What I did claim is that Halmos never overcame his distrust of these dichotomies, and consistently felt that these dichotomies were vague. I would have to disagree with your claim that the business about NSA is a separate matter. As I mentioned in my answer, he is still pouncing on non-standard models in one of his last published articles, and if you look at the context you will probably agree with me that the context does not justify the pouncing. His suspicious attitude toward NSA has the same source... – Mikhail Katz May 24 '18 at 13:18
  • 2
    ...as his suspicion of the standard dichotomies, namely the menace stemming from the idea that we are merely working with theories which unavoidably have distinct models. Such an idea is a challenge to a monolithic philosophy of mathematics which was Halmos'. @ToddTrimble – Mikhail Katz May 24 '18 at 13:20
  • Okay, in view of your edit, let's leave it at that. – Todd Trimble May 24 '18 at 13:37
  • OK. Note that my edit did not change the substance of my answer but merely clarified it (the earlier version did not make it clear what "this" was exactly). @ToddTrimble – Mikhail Katz May 24 '18 at 13:38
5

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.

Giorgio Mossa
  • 3,299
1

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.

Zuhair Al-Johar
  • 9,152
  • 50 years as an active mathematician may have made me too rigid, but all this strikes me as philosophical tail-chasing. Type theory seems to postpone the problem, not solve it. – Frank Quinn May 24 '18 at 14:30
0

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.

Zuhair Al-Johar
  • 9,152
-1

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.

Greg S
  • 146
  • Uh, no, your first line is not true. – Asaf Karagila May 24 '18 at 06:21
  • 2
    I think it is precisely this type of blurry pseudo-philosophical discussion that the OP is reacting against in his question in the first place. – Mikhail Katz May 24 '18 at 09:48
  • I think you made a typo, you forgot to write 'theory' after 'set' in the first line. – Zuhair Al-Johar May 24 '18 at 09:58
  • 1
    current work in foundation doesn't hope to 'reduce' notions of 'relations' and 'sets' to 'logical notions', this was the program of logicisim, nowadays we are 'extending' logical notions by extra-logical notions of 'set' , 'identity' [for the case of set theory], or by "Part-hood", "connectedness" [for the case of mereotopology] or simply by "number, addition, multiplication" [for the case of arithmetic], etc... Extending logic is a different concept from 'reducing to logic' – Zuhair Al-Johar May 24 '18 at 10:27
  • Updated and clarified based on edited question and comments by Asaf, Mikhail and Zuhair – Greg S May 25 '18 at 03:47