36
$\begingroup$

In Henning Makholm's answer to the question, When does the set enter set theory?, he states:

In axiomatic set theory, the axioms themselves are the definition of the notion of a set: A set is whatever behaves like the axioms say sets behave.

This assertion clashes with my (admittedly limited) understanding of how first-order logic, model theory, and axiomatic set theories work. From what I understand, the axioms of a set theory are properties we would like the objects we call "sets" to have, and then each possible model of the theory is a different definition of the notion of a set. But the axioms themselves do not constitute a definition of set, unless we can show that any model of the axioms is isomorphic (in some meaningful way) to a given model.

Am I misunderstanding something? Is the definition of a set specified by the axioms, or by a model of the axioms? I would appreciate any clarification/direction on this.

Update: In addition to all the answers below, I have written up my own answer (marked as community wiki) gathering the excerpts from other answers (to this question as well as some others) which I feel are most pertinent to the question I originally posed. Since it's currently buried at the bottom (and accepting it won't change its position), I'm linking to it here. Cheers!

|cite|improve this question
$\endgroup$
  • 8
    $\begingroup$ Isn't this question just a "What came first, the theory or its models?" $\endgroup$ – Ove Ahlman May 18 '16 at 5:49
  • 12
    $\begingroup$ Does this seem problematic in the case of groups? The group axioms have many non-isomorphic models, but I've yet to see anyone bothered by the idea that they define what a group is. $\endgroup$ – Malice Vidrine May 18 '16 at 6:08
  • 2
    $\begingroup$ @user21820 When I'm asked "What is a vector?", my usual reply is "an element of a vector space". Applied to here: The group axioms define the notion of group (and thus indirectly the notion of element of a group). One could then say that ZFC defines a notion of universe of sets and thus indirectly of set. $\endgroup$ – Hagen von Eitzen May 18 '16 at 6:19
  • 4
    $\begingroup$ @MaliceVidrine: Also, a lot of people don't consciously realize that ZFC cannot possibly have a unique model in any reasonable sense, nor what it means concerning the theorems that they prove within ZFC. Take the uncountability of the reals. It is provable in ZFC and hence true in the countable model, so what really is the theorem saying? It's not what people normally believe, namely "There are more reals than naturals in terms of bijections.", but rather "We cannot define (in ZFC) a bijection between the reals and naturals.". The latter has intrinsically different semantic content. $\endgroup$ – user21820 May 18 '16 at 11:09
  • 3
    $\begingroup$ @jdods: yes, to be more specific, ZFC proves just "there is no bijection from the reals to the naturals". This has as a corollary that we cannot define a bijection, but the actual result is that there is not a bijection, definable or otherwise. The point user21820 was making is that this just means that in each model of ZFC there is no bijection between the reals of that model and the naturals of that model; both those sets might be countable from a viewpoint external to the model in which there are more functions to consider than just the ones in the model. $\endgroup$ – Carl Mummert May 18 '16 at 17:01
41
$\begingroup$

This is the commonplace clash between the semi-Platonic view of the laymathematician and the foundational approach for mathematics through set theory.

It is often convenient, when working in "concrete" mathematics, to assume that there is a single, fixed universe of mathematics. And everyone who took a course or two in logic and set theory should be able to tell you that we can assume this universe is in fact a universe of $\sf ZFC$.

Then we do everything there, and we take the notion of "set" as somewhat primitive. Sets are not defined, they are just the objects of the universe.

But the word "set" is just a word in English. We use it to name this fickle, abstract, primitive object. But how can you ensure that my intuitive understanding of "set" is the same as yours?

This is where "axioms as definitions" come into play. Axioms define the basic ground rules for what it means to be a set. For example, if you don't have a power set, you're not a set: because every set has a power set. The axioms of set theory define what are the basic properties of sets. And once we agree on a list of axioms, we really agree on a list of definitions for what it means to be a set. And even if we grasp sets differently, we can still agree on some common properties and do some math.

You can see this in set theorists who disagree about philosophical outlooks, and whether or not some conjecture should be "true" or "false", or if the question is meaningless due to independence. Is the HOD Conjecture "true", "false" or is it simply "provable" or "independent"? That's a very different take on what are sets, and different set theorists will take different sides of the issue. But all of these set theorists have agreed, at least, that $\sf ZFC$ is a good way to define the basic properties of sets.

As we've thrown Plato's name into the mix, let's talk a bit about "essence". How do you define a chair? or a desk? You can't really define a chair, because either you've defined it along the lines of "something you can sit on", in which case there will be things you can sit on which are certainly not chairs (the ground, for example, or a tree); or you've run into circularity "a chair is a chair is a chair"; or you're just being meaninglessly annoying "dude... like... everything is a chair... woah..."

But all three options are not good ways to define a chair. And yet, you're not baffled by this on a daily basis. This is because there is a difference between the "essence" of being a chair, and physical chairs.

Mathematical objects shouldn't be so lucky. Mathematical objects are abstract to begin with. We cannot perceive them in a tangible way, like we perceive chairs. So we are only left with some ideal definition. And this definition should capture the basic properties of sets. And that is exactly what the axioms of $\sf ZFC$, and any other set theory, are trying to do.

|cite|improve this answer
$\endgroup$
  • 3
    $\begingroup$ "a chair is a chair is a chair"... Hehehe; it's the first time I've seen you put forth significantly philosophical points in your posts. =) $\endgroup$ – user21820 May 18 '16 at 6:26
  • $\begingroup$ Couldn't be the first time! $\endgroup$ – Asaf Karagila♦ May 18 '16 at 6:38
  • 1
    $\begingroup$ math.stackexchange.com/questions/1417042/… and math.stackexchange.com/questions/1452425/… seem to mention "chairs" in a similar context... :-) $\endgroup$ – Asaf Karagila♦ May 18 '16 at 6:47
  • 25
    $\begingroup$ So by ZFC, a chair is something we can set on ... $\endgroup$ – Hagen von Eitzen May 18 '16 at 16:13
  • 1
    $\begingroup$ @justin: No. This is why (a) mathematicians dislike the whole independence problem; and (b) it is important that we are able to prove things from ZFC, since that ensures that whatever we proved holds in all the universes of ZFC. $\endgroup$ – Asaf Karagila♦ May 30 '16 at 18:26
18
$\begingroup$

In axiomatic set theory, the axioms themselves are the definition of the notion of a set: A set is whatever behaves like the axioms say sets behave.

I half-agree with this. But recall that the axioms of group theory don't axiomatize the concept "element of a group." Rather, they axiomatize the concept "group." In a similar way, the axioms of ZFC don't axiomatize the concept "set." They axiomatize the concept "universe of sets" (or "von Neumann universe" or "cumulative hiearchy", if you prefer).

|cite|improve this answer
$\endgroup$
8
$\begingroup$

There is an axiomatic definition of "set", but it's actually rather uninteresting:

(this space intentionally left blank)

The point of things like the ZFC axioms isn't to define the notion of a set: it's to define the notion of a "universe (of sets)".

Each universe can be said to give a notion of "set", but that must be understood in the same sense that each vector space gives a notion of "vector".

Now, the desire to study the universe isn't unique to set theory; e.g. group theory wants to study the 'universe' of all groups and its relation to the universe of sets.

In principle, one could then give an axiomatic definition of a universe of groups, a universe of group actions, and other relevant things.

But as a practical matter, we prefer to give one definition of a whole mathematical universe which is used by other subjects — e.g. group theory is presented in a way that presumes that we already have a universe (of sets) to work with.

In the usual formulation of mathematical foundations, set theory is the place where we define a 'mathematical universe'. And thus, formalizing set theory has a somewhat different flavor than formalizing group theory.

Aspects of the practice of set theory has a different flavor too; while group theory is content with studying the groups in a universe of sets, one aspect of set theory is to study and compare multiple universes of sets.

|cite|improve this answer
$\endgroup$
  • 2
    $\begingroup$ I don't know... if you want to study uncountable Whitehead groups, you might be more content in some universes than in others. :-) $\endgroup$ – Asaf Karagila♦ May 18 '16 at 15:07
8
$\begingroup$

The axioms of ZFC (or any other sufficiently strong first-order formal system) cannot define the notion of "set", in the sense that you're looking for, namely that ZFC cannot pin down a unique structure that satisfies ZFC. Why so? Because ZFC cannot prove its own consistency, by Godel's incompleteness theorem, and hence ZFC cannot prove that there is a model of ZFC. Furthermore, ZFC can prove that if ZFC is consistent then it has infinitely many models, not at all a single one.

Similarly, no recursive extension of first-order PA can (completely) define the natural numbers, because we can prove (in our meta-system that is usually ZFC) that PA has non-standard models. However, second-order PA is categorical (has a unique model up to isomorphism) and arguably captures completely the natural numbers. The catch is that you need to be in a meta-system that already has the standard model of PA before you can prove this fact about second-order PA, so in a way there is a priori no way to define the natural numbers.

You might want to read this post that I wrote about what every usable formal system (as of today) ultimately depends on, which cannot be further broken down into simpler notions.

There's a partial way to get around the circularity, that appears to be what many mathematicians do in practice. We can use natural language and define "set" to be a type of object such that the ZFC axioms hold, and insist that we can only call something a set when we have proven its existence in ZFC. Note that there is no need to have a model of ZFC here, because we're saying that if you can't prove it then I don't accept that it exists (but neither am I insisting that it doesn't), so it becomes a purely syntactic notion.

In other words, if we define "set" syntactically using the axioms of ZFC, then we've escaped most of the circularity (except what we already need to know about string manipulation). What we still can't escape is that we can't define "model" in the usual sense without collections of some sort, and so we can't even articulate that ZFC has successfully defined any structure. (Unless of course our natural language is so powerful, but then we're in trouble.)

|cite|improve this answer
$\endgroup$
  • $\begingroup$ @CarlMummert: I'm using the word "define" in the fuller sense of the English word, according to what the asker was looking for: But the axioms themselves do not constitute a definition of set, unless we can show that any model of the axioms is isomorphic (in some meaningful way) to a given model. That is why my first sentence is the correct answer to his/her question. I also mentioned the weaker interpretation of "define" later in my answer. The axioms of a group defines the type of all groups. Similarly ZFC defines the type of all models of ZFC, but not what the asker was asking about. $\endgroup$ – user21820 May 18 '16 at 15:19
  • $\begingroup$ @CarlMummert: I've edited the first sentence to specify the notion of "define". Do you like it better now? =) $\endgroup$ – user21820 May 18 '16 at 15:33
  • 1
    $\begingroup$ Thanks, I understand your point completely. The key point is to define "define", I suppose. I already voted the post up, so I can't do it again. $\endgroup$ – Carl Mummert May 18 '16 at 15:48
  • $\begingroup$ @CarlMummert: Oh no.. it's definitions all the way down... How can we possibly define "define"? =) $\endgroup$ – user21820 May 19 '16 at 5:41
  • $\begingroup$ @user21820: Mandatory SMBC reference. (The votey of this comic.) $\endgroup$ – Asaf Karagila♦ May 19 '16 at 14:36
8
$\begingroup$

There are thorough answers by Asaf Karagila and user21820. I want to point out a different issue: there is more than one concept or notion of "set". Paradoxes like Russell's paradox showed that the original "naive" concept of "set" is inconsistent, and so some of the properties of these sets needed to be discarded. But there are many ways to do that.

ZFC set theory is intended to capture the idea of the iterative cumulative hierarchy. This means that the kind of "set" that ZFC is intended to study -- the "ZFC-set" -- has several limitations:

  • The only elements of ZFC-sets are other ZFC-sets. For example, I am not a member of any ZFC-set.
  • The nature of ZFC-sets is that no ZFC-set can contain every ZFC-set (there is no ZFC-set that is universal for ZFC-sets)
  • ZFC sets are well-founded: there is not an infinite sequence $x_1, x_2, \ldots$ of ZFC-sets with $x_1 \ni x_2 \ni \cdots$.

These limitations are inherent in the specific choices made in the formulation of ZFC, which are not part of other conceptions of "set":

  • In the most naive conception of "set", sets can contain not only other sets, but also other objects like me, or like my car. This concept of "set" is likely to be more recognizable to non-mathematicians. Even among mathematicians, there are some who dislike the idea that all mathematical objects might be viewed as sets.

  • In the set theory known as New Foundations, NF, there is a NF-set that contains all NF-sets. NF attempts to avoid the paradoxes by restricting the set-existence axiom scheme instead.

  • There are set theories that are not well founded. One example uses the Aczel's anti-foundation axiom. These are of particular interest for some applications in computer science.

So the key point of the ZFC axioms is to define, in a particular sense, the notion of a "ZFC-set" (actually, the notion of a "universe of ZFC-sets" or a "ZFC-universe of sets"). It is easy to forget that there are other notions of "sets", if everything that you see uses ZFC, and these all say "set" instead of "ZFC-set". Indeed, some set theorists completely internalize the notion of "ZFC-set", so that to them a "set" is a "ZFC-set", and the other notions of "set" are not actually "sets".

|cite|improve this answer
$\endgroup$
  • $\begingroup$ So everything is a set? There are no non-set "objects" (urelements) in ZFC? $\endgroup$ – Heimdall May 18 '16 at 16:49
  • 2
    $\begingroup$ @Heimdall: yes. This is a consequence of the extensionality axioms in ZFC - if there were urelements, they would have no elements, and so the extensionality axiom then says they are all equal to the empty set, and hence equal to each other. There are modifications of ZFC that do have urelements, but they require changing various axiom schemes. See e.g. philebus.tamu.edu/cmenzel/Papers/Menzel--ZFCU.pdf $\endgroup$ – Carl Mummert May 18 '16 at 16:58
  • $\begingroup$ @Heimdall: To put it another way, if you are inside the system defined as ZFC (your world really follows the rules of ZFC) then everything you see follows the axioms of ZFC. For instance every object you pick up has a power set, and so on... From outside we call everything you can touch a "set", but from inside you don't even have such a notion of "set". From outside we also can see that every two different objects you can touch has different "elements", so that tells us that there aren't any "urelements" in your world, but again from inside you know nothing about "[ur]elements". $\endgroup$ – user21820 May 19 '16 at 5:45
  • $\begingroup$ Your answer certainly complements ours! What you describe as the naive conception of sets is not far from NFU which allows urelements, though it still doesn't allow constructing the collection of sets that are members of themselves, which non-set-theorists would still find weird, same as with ZFC. I didn't realize non-well-founded set theories were used in CS though, which is interesting. $\endgroup$ – user21820 May 19 '16 at 5:56
  • $\begingroup$ @user21820: I saw a talk in a conference a while ago where they use permutation models (specifically Mostowski's ordered model) to do some quick computations of algorithms. It was a very interesting talk. $\endgroup$ – Asaf Karagila♦ May 19 '16 at 9:37
5
$\begingroup$

Update: I'm marking this answer as community wiki so as not to "leech reputation."

OP here. I want to include some information I've gathered from answers and comments to this question (as well as several others) which I think most directly address what I was asking about.

I think the most succinct answer to my question is goblin's, where they write that

the axioms of group theory don't axiomatize the concept "element of a group." Rather, they axiomatize the concept "group." In a similar way, the axioms of ZFC don't axiomatize the concept "set." They axiomatize the concept "universe of sets" (or "von Neumann universe" or "cumulative hiearchy", if you prefer).

This is essentially what Hurkyl says in the following excerpt from their answer:

The point of things like the ZFC axioms isn't to define the notion of a set: it's to define the notion of a "universe (of sets)".

Each universe can be said to give a notion of "set", but that must be understood in the same sense that each vector space gives a notion of "vector".

Likewise, Carl Mummert writes in his answer to a related question, What is the definition of a set?,

A set on its own does not satisfy the ZFC axioms, any more than a vector on its own can satisfy the vector space axioms or a point on its own can satisfy the axioms of Euclidean geometry. [...] Instead of saying "a set is anything that satisfies the ZFC list of axioms", you need to start with the entire model of set theory. Then, it does make sense to say, for example, that a ZFC-set is an object in a model of ZFC set theory.

There are some circularity concerns that may arise while reading these answers. First is that of how we are able to discuss the manipulation of finite strings of symbols in first-order logic without having defined what a "set" is. Addressing this issue, Stefan Geschke writes in his answer to a related question on MO:

The conclusion that I have arrived at is that you need to assume that we know how to deal with finite strings over a finite alphabet. This is enough to code the countably many variables we usually use in first order logic (and finitely or countably many constant, relation, and function symbols).

So basically you have to assume that you can write down things. You have to start somewhere, and this is, I guess, a starting point that most mathematicians would be happy with. Do you fear any contradictions showing up when manipulating finite strings over a finite alphabet?

Similarly, arjafi explains in their answer to When does the set enter set theory?,

Properly, logic shouldn't concern itself with notions of set. We can use the notion in an almost metaphorical sense, such as saying that our (first-order) language consists of a set of symbols, and from these symbols we define the set of formulae. This is not really a problem, since the basic objects of logic are symbols that can be written down, and our set or [sic] symbols can be just a listing of these symbols (or a description of how to write them), and our set of formulae is just a method for analysing a written expression and determining whether or not it is a formula.

However, a potential problem still arises when talking about models. Henning Makholm writes in the same answer I quoted when first asking this question that "if you want to do model theory on your first-order theory you need sets," and user21820 asks in a comment on Carl Mummert's answer I quoted above,

Just how do you define model? Aren't you working in set theory already with "set" as a given concept?

Some possible solutions can be found in the answers to a question I posed earlier on the site, Is the "domain of discourse" in axiomatic set theory also a "set"?. Rory Daulton suggests in his answer that

we have two concepts of "sets": those that can be described in the formal theory, and those that cannot but can be described in some "larger" theory. Yes, this is weird, but so is formal set theory.

Meanwhile, Peter Smith writes in his answer,

It is even better not to think of 'the domain' as a single object at all (whether 'set', 'class' or 'collection'). Instead of talking of a domain (singular) of individuals, just talk directly of the relevant individuals (plural). [...] If you want to formalize the metatheory in plural style, use a formal plural logic.

Finally, returning to my question of whether set theory can uniquely define a model of itself (which could then be considered to define the concept of a set in the same sense that a vector space defines the concept of a vector), user21820 explains in their answer,

The axioms of ZFC (or any other sufficiently strong first-order formal system) cannot define the notion of "set", in the sense that you're looking for, namely that ZFC cannot pin down a unique structure that satisfies ZFC. Why so? Because ZFC cannot prove its own consistency, by Godel's incompleteness theorem, and hence ZFC cannot prove that there is a model of ZFC. Furthermore, ZFC can prove that if ZFC is consistent then it has infinitely many models, not at all a single one.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Looks like you got it! =) One crucial point that most people miss is the one that arjafi (whom you quoted) and my answer raises about the core strength the meta-system must have to start talking about models. The most constructive approach seems to be to consider a collection not as a finished whole but as a deterministic conceptual procedure that specifies whether or not to reject the input. This gives us collections in a weak sense, related to what you quote from Peter Smith about plurality. Specifically, you can manipulate members of these collections but not the collections as wholes. $\endgroup$ – user21820 May 20 '16 at 2:20
  • 1
    $\begingroup$ The unfortunate inevitable consequence of this point in general (not just about models) is that all foundations ultimately require natural language (with all of its intrinsic circularity) to set up. Natural language is extremely powerful because of that; it can be used to set up any formal system we can dream of! But there are paradoxes lurking in it as well, such as: " preceded by its quotation is a false sentence." preceded by its quotation is a false sentence.. Somehow, we still get by with the parts that work well in conveying our intended meaning. $\endgroup$ – user21820 May 20 '16 at 2:26
-1
$\begingroup$

Every axiomatic system begins with undefined concepts, definitions, and axioms. For example, in geometry, some of the undefined concepts are "point", "line", and "incidence".

Likewise, in set theory, some undefined concepts might be "element", "set", and "is a member of". The peculiar thing about undefined concepts is that when you do a dictionary search, you always get back to the thing you are looking up if you look into synonyms of synonyms of synonyms. There is no way to get a hard definition. Nevertheless, we all know what element, set, and membership mean.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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