# Are there any objects which aren't sets?

What is an example of a mathematical object which isn't a set?

The only object which is composed of zero objects is the empty set, which is a set by the ZFC axioms. Therefore all such objects are sets.

Objects composed of many objects are obviously sets.

What about objects composed of exactly one object? Are there any which aren't sets?

• The number $1$ is a number, not a set. – ÍgjøgnumMeg Mar 22 '16 at 22:24
• @Ed_4434 arguably it is if you want to get technical. How about an object which contains itself (among possibly other things)? – JMoravitz Mar 22 '16 at 22:25
• @Ed_4434 In standard Zermelo-Fraenkel theory, $1=\{\emptyset\}$ by definition. – user228113 Mar 22 '16 at 22:25
• The class of sets not belonging to themselves is not a set. – Crostul Mar 22 '16 at 22:30
• Also the class of all ordinal numbers is not a set – Matt Dyer Mar 22 '16 at 22:31

The number two is not a set.

Textbooks in set theory will happily tell you how to use sets to represent numbers, often using the Von Neumann scheme in which the set $\{\{\},\{\{\}\}\}$ represents the number two. They will often, for convenience, even use the symbol $2$ to stand for that set, with the understanding that every formula in the book's formalism is about sets, so taking this context into account there's no risk of the symbol $2$ to be misunderstood as the actual number two.

This does not, however, mean that the number two is its set-theoretical representation. It is convenient, technically useful, and interesting to be able to express reasoning about numbers in a formalism made for reasoning about sets, but one should not confuse the model for the things it models.

It is perfectly possible to reason about numbers without committing to the philosophical baggage of set theory. Within mathematical logic, it's a sort of default assumption that Peano arithmetic rather than set theory is the standard vehicle for reasoning about numbers -- but both weaker and stronger non-set theories for aritmetic than this are studied for various purposes.

In particular, second-order arithmetic works for formalizing large parts of mathematics -- and while second-order arithmetic does have sets, the integers are explicitly not sets there, and $\{\{\},\{\{\}\}\}$ doesn't even exist in this theory.

• Great answer! Two was just arbitrarily chosen for the sake of discussion though, right? The opening gave me the impression that the simpler 1 (and possibly 0) somehow have to be regarded as sets as opposed to indivisible atoms. – Vandermonde Mar 23 '16 at 2:48
• I am curious to know then what is the number two? – Shahab Mar 23 '16 at 10:51
• I find the leading statement "The number two is not a set" rather strange. It seems to presume that there is a commonly agreed upon definition of "two" that is clearly not the set-theoretic one, and I don't believe that's the case. I think it would be more accurate, and less confrontative, to lead with "The number two is not necessarily a set". You make a good point that the set-theoretic definition/representation of two can be viewed as a model of some other kind of two. However it's also correct to say that, in the language of ZFC, two is precisely {{},{{}}}, by definition. – Don Hatch Mar 23 '16 at 12:26
• @Shahab: It's the concept we have of having just one more than one thing. In that situation we say that we have 2 things. Seriously, we can't get away from natural language when it boils down to natural numbers. We can capture proofs in any human-usable formal system using the rather weak formal system of PA, but we can't really go lower than that. See my answer for a little more detailed explanation of the distinction between the intended interpretation and encoding of such concepts. – user21820 Mar 24 '16 at 4:43
• @SarahPalinsAnger: That is possible in an alternative set theory called NFU. But again, it is an encoding of the concept, and not the concept itself, which is an uncatchable slippery fish. The various encodings might help people to grasp the concept, but never fully capture the concept. – user21820 Mar 24 '16 at 4:45

I think the answer is dependent on what we allow to be a "mathematical object". There exist collections of sets that are not themselves sets, for example. These are called proper classes. In particular there is no such thing as the set of all sets.

• Nice to see a reference to why a set cannot contain itself... – Serge Ballesta Mar 23 '16 at 7:18
• @SergeBallesta: Russell's paradox does not prevent sets from containing themselves in general. In fact, there are set theories that are equiconsistent with ZFC and contain solutions to $x=\{x\}$ (so-called Quine atoms). – Henning Makholm Mar 23 '16 at 10:09
• More precisely, if $X$ is a set that contains itself, then $Y=\{a\in X\mid a\notin a\}$ may well be a set -- but as long as $X$ is not claimed to be the set of all sets, nobody says that $Y$ must be an element of $X$, so Russell's paradox does not ensue. – Henning Makholm Mar 23 '16 at 10:15
• @HenningMakholm: OP spoke of ZFC theory. This theory includes the axiom of regularity that implies that a set cannot contain itself. But I also know that mathematician imagination is unbounded... and that the negation of one of the axioms of Euclian geometry leaded to Riemann's one – Serge Ballesta Mar 23 '16 at 11:19
• @SergeBallesta: It is correct that ZFC is usually taken to include that axiom nowadays -- bit it still is not something that is referenced in this answer. – Henning Makholm Mar 23 '16 at 11:41

It depends on your foundational point of view. For instance, you can work with non-set-theoretic foundations (homotopy type theory, or categorical foundations, for instance).

Not only that, but if you start with a set-theoretic framework you will quickly discover that plenty of interesting objects are too big to be sets. For instance, the class of all groups is a proper class. You could however restrict to set-theoretic universes to avoid dealing with proper classes in category theory, but this requires axioms for inaccessible cardinals.

Thinking of mathematical objects as being sets in general can be counterproductive anyway. I doubt that many practicing mathematicians care that $1 := \{ \emptyset \}$ in some set-theoretic construction of the natural numbers, because this definition is irrelevant to the practical usage of the natural numbers.

The categorical point of view tells us that we care about objects because of how they relate to other objects via morphisms; this is closer in spirit to how most mathematicians work.

• Counterproductive? How? Does the fact all types of data are stored in the memory is a sequence of bit is counterproductive to programming somehow? – Asaf Karagila Mar 23 '16 at 16:13
• @AsafKaragila , if you try programming in binary - yes. Yes, it is. – Anton Fetisov Mar 23 '16 at 18:40
• @Anton: Has someone who dabbled with assembly code a lot, no. I disagree. Also in CL where code is data, and data is lists. Everything is a list. And 'lo and behold, CL is amazing and all powerful. – Asaf Karagila Mar 23 '16 at 18:47
• @AsafKaragila , anything that implements a Turing machine is all-powerful, but I wouldn't pick asm or even C over Python and Haskell except for perfomance reasons. Because data is much more than bytes. – Anton Fetisov Mar 23 '16 at 18:59
• @AsafKaragila , if you regard data as a sequence of bytes and work with it as a sequence of bytes, then you rely on arbitrary encoding and conventions too much, making your code unmaintainable. It's inevitable for low-level libraries, but in general for big projects picking bytes over readabilty, scalability and accessibility is a self-headshot. Not to mention how much your inner layouts can be screwed by compilers and how many technical issues can arise. The analogy with maths works wonderfully. – Anton Fetisov Mar 23 '16 at 19:06

In my answer I'll list three things that are worth thinking about, that most people wouldn't intuitively consider as sets.

Symbols

To expand a bit on Henning's answer, I'll give another example. No symbol is a set. This includes the symbol "2", which is why in a strict sense "2" can never be a set, although "2" can be interpreted as a set in some models of some formal systems such as ZFC.

Each symbol is designed and described in a meta-language to convey an intended meaning, but the symbol itself has no intrinsic structure. It is only the interpretation of the symbol that can be said to have any structure at all, and that of course depends on the interpretation. In ZFC the intended interpretation is that every object in the set-theoretic universe is a set, but what about the symbols used in the language of ZFC itself? You can encode each symbol as some set in ZFC, exactly like you can encode the concepts of natural numbers as sets, but that is still merely a representation and not the real thing, as Henning's answer explains.

Similarly consider the fact that any proof in ZFC is a string of symbols. Again you can encode any finite string of symbols as a set in ZFC (or even as a natural number in PA) and be able to perform the usual operations on strings using suitable first-order formulae. But again the encoding is not the real thing. And this time it is even more obvious that it cannot be the real thing. For it is actually a theorem of Godel that any sufficiently strong formal system does not fully capture everything that is true about itself. In particular there is a first-order statement Con(ZFC) over ZFC that states "There does not exist an encoding of a proof of a contradiction within ZFC.". According to the intended interpretation of the encoding, one would think that Con(ZFC) means the same thing as "ZFC is consistent" in the meta-system, but it does not, since if ZFC has a model whose encodings of strings are isomorphic to the strings in the meta-system, then Con(ZFC) is independent over ZFC. Furthermore, it is possible that ZFC is consistent but disproves Con(ZFC). The whole problem lies in the fact that no sufficiently strong formal system can pin down their intended interpretation, at least in classical first-order logic. So it is not just that strings are not sets, but even more so that it is impossible to fully define them in any formal system (not just ZFC).

Urelements

Unrelated to the above is the notion in some formal systems that not everything is a set. NFU is one such formal system invented by Quine, where there are urelements that are not sets, and it is meaningless to ask whether something is a member of an urelement. The concept of urelements can be said to be motivated by the philosophical position of not assuming a particular kind of structure when it might be absent. In formal systems we can therefore handle real-world objects without any philosophical concern as to whether they are sets, since they could be urelements. One does not have to assume that urelements are totally atomic or indivisible in some sense; rather it is just that the formal system does not know about their internal structure.

Functions and algorithms

Lastly, we have functions. As you probably know, in ZFC a function can be encoded as a set of ordered pairs from its domain and codomain that exactly one pair with first item $x$ for any $x$ in the domain. As before, this encoding is not the only possible way, so what really is a function? Moreover, we write things like "$f(g(x) \cup y) \in z$" where $f,g$ are functions with appropriate domains and codomains, which is technically impossible in pure ZFC but requires a syntactic transformation. This is because our intuitive notion of functions is not the encoding even though it is more or less captured by the encoding. It is not completely captured because we can trivially conceive of the identity function on the entire universe, but that cannot be encoded in ZFC without the pain of contradiction. Nor can it be done in any extension of ZFC. Incidentally it can be done in NFU, but some would argue that NFU is about as unintuitive as ZFC, just in different aspects.

Also, algorithms are the natural extension of functions. They still start with the intuitive notion of doing something based on the input and producing some output, but usually involve iterations of some sort. Again, we can encode them using unions of chains of the encodings of functions constructed by induction, but it's arguable whether that is natural. For this reason there are other notations devised in history, such as [typed] lambda calculus and μ-recursion and most intuitively programming languages. No programmer conceives of the algorithm embodied by his program as a set under normal circumstances.

This depends entirely on the foundations you adopt for set theory (or for mathematics).

You are correct in stating that in ZFC every object is a set. In a typical development of mathematics using ZFC, the natural number $2$ is the set $\{\varnothing,\{\varnothing\}\}$.

But there are also versions of set theory where classes exist as formal objects, for example in Bernays-Gödel set theory. In that case, an example of an object that is not a set would be the class V of all sets. Proper classes have elements, but they are never elements of other objects.

Another example of a theory where not all objects are sets is ZFA, or “Zermelo-Fraenkel set theory with atoms” (as in Jech's Set Theory, p. 250). In this case there is a constant set $A$ whose elements are called “atoms” or “urelements”; all other objects are called “sets.” Atoms can be elements of sets, but they never have elements themselves. The axiom of extensionality is modified so that it applies only to sets.

You ask whether an object “composed of one object” is necessarily a set. This seems to be synonymous with an object “having one element.” (The words “composed of” strongly suggest that you are working within some version of set theory.) In all the systems I've mentioned, this can occur only when that object is a set. It is conceivable that this might not be the case if you had a system with different levels of classes, but this would be something rather far removed from the usual version of set theory.

You say that objects composed of many objects must be sets. In set theory with classes, this is plainly not true. For example, the universal class V is not a set.

Defintion: A set M is called proper if and only if M does not contain itself.

(M proper set $:\Leftrightarrow$ M $\notin$ M)

Question: Is the set P of all proper sets proper?

Suppose P is not a proper set, that is P $\in$ P. However, because of the defintion of P it then follows that if P $\in$ P, P should be a proper set. Thus: P not proper $\Rightarrow$ P is proper.

Furthermore, suppose that P is indeed a proper set, that is P $\notin$ P, but because of the definition of P, if P $\notin$ P then P is not part of the collection of proper sets. Thus: P proper $\Rightarrow$ P not proper.

All in all we have: P proper $\Leftrightarrow$ P not proper.

This is obviously a contratdiction. One of the assumptions must have been wrong. Indeed it was the assumption that the collection of all proper sets forms a set. P is not a set!

• I like this answer as it shows that even if we construct arithmetic via set theory (which op implicitly assumes), there are nonexamples of sets. – Szmagpie Mar 24 '16 at 17:52