Set Theory

The Iterative Conception

content/set-theory/story/story.tex

% Chapter: Naive\documentclass[../../../include/open-logic-chapter]{subfiles}\begin{document}\olchapter{sth}{story}{The Iterative Conception}\olimport{extensionality}\olimport{russells-paradox-again}\olimport{predicativity}\olimport{cumulative-approach}\olimport{urelements}\olimport{grundgesetze}\OLEndChapterHook\end{document}

content/set-theory/story/extensionality.tex

\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{sth}{story}{extensionality}\olsection{Extensionality}The very first thing to say is that sets are individuated by their!!{element}s. More precisely:\begin{axiom}[Extensionality]If sets $A$ and $B$ have the same !!{element}s, then $A$ and $B$ arethe same set.\[  \lforall[A][\lforall[B][(\lforall[x][(x \in A \liff x \in B)] \lif  \eq[A][B])]]\]\end{axiom}We assumed this throughout \olref[sfr][][]{part}. But it bearsrepeating. The Axiom of Extensionality expresses the basic idea that aset is determined by its !!{element}s. (So sets might be contrasted with\emph{concepts}, where precisely the same objects might fall undermany different concepts.) Why embrace this principle? Well, it is plausible to say that anydenial of Extensionality is a decision to abandon anything which mighteven be called \emph{set theory}. Set theory is no more nor less thanthe theory of extensional collections. The real challenge in \olref[sth][][]{part}, though, is to laydown principles which tell us \emph{which sets exist}. And it turnsout that the only truly ``obvious'' answer to this question isprovably wrong.\end{document}

content/set-theory/story/russells-paradox-again.tex

\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{sth}{story}{rus}\olsection{Russell's Paradox (again)}In \olref[sfr][][]{part}, we worked with a na\"{i}ve set theory. Butaccording to a \emph{very} na\"{i}ve conception, sets are just theextensions of predicates. This na\"ive thought would mandate thefollowing principle:\begin{defish}  \emph{Na\"{i}ve Comprehension.} $\Setabs{x}{\phi(x)}$ exists for any formula $\phi$.\end{defish}Tempting as this principle is, it is provably inconsistent. We saw this in \olref[sfr][set][rus]{sec}, but the result is so important, and so straightforward, that it's worth repeating. Verbatim.\begin{thm}[Russell's Paradox]There is no set $R = \Setabs{x}{x \notin x}$\end{thm}\begin{proof}If $R = \Setabs{x}{x \notin x}$ exists, then$R \in R$ iff $R \notin R$, which is a contradiction.\end{proof}Russell discovered this result in June 1901. (He did not, though, putthe paradox in quite the form we just presented it, since he wasconsidering Frege's set theory, as outlined in \emph{Grundgesetze}. Wewill return to this in \olref[blv]{sec}.) Russell wrote toFrege on June 16, 1902, explaining the inconsistency in Frege'ssystem. For the correspondence, and a bit of background, see\citet[pp.~124--8]{Heijenoort1967}. It is worth emphasising that this two-line proof is a result of\emph{pure logic}. Granted, we implicitly used a (non-logical?)\ axiom, Extensionality, in our notation $\Setabs{x}{x \notin x}$; for $\Setabs{x}{\phi(x)}$ is to be \emph{the unique} (by Extensionality) set of the $\phi$s, if one exists. But we can avoid even the hint of Extensionality, just by stating the result as follows:\emph{there is no set whose members are exactly the non-self-memberedsets}. And this has nothing much to do with sets. As Russell himself observed, exactly similar reasoningwill lead you to conclude: \emph{no man shaves exactly the men who donot shave themselves}. Or: \emph{no pug sniffs exactly the pugs whichdon't sniff themselves}. And so on. Schematically, the shape of theresult is just: \[\lnot \exists x \forall z(Rzx \liff \lnot R zz).\]And that's just a theorem (scheme) of first-order logic. Consequently,we can't avoid Russell's Paradox just by tinkering with our settheory; it arises before we even \emph{get} to set theory. If we'regoing to use (classical) first-order logic, we simply have to\emph{accept} that there is no set $R = \Setabs{x}{x\notin x}$. The upshot is this. If you want to accept Na\"{i}ve Comprehensionwhilst \emph{avoiding} inconsistency, you cannot just tinker with the\emph{set theory}. Instead, you would have to overhaul your\emph{logic}.Of course, set theories with non-classical logics have been presented.But they are---to say the least---non-standard. The standard approachto Russell's Paradox is to treat it as a straightforward non-existenceproof, and then to try to learn how to live with it. That is theapproach we will follow.\end{document}

content/set-theory/story/predicativity.tex

\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{sth}{story}{predicative}	\olsection{Predicative and Impredicative}The Russell set, $R$, was defined via $\Setabs{x}{x \notinx}$. Spelled out more fully, $R$ would be the set which contains alland only those sets which are not non-self-membered. So in defining$R$, we quantify over the domain which would contain $R$ (if itexisted).This is an \emph{impredicative} definition. More generally, we mightsay that a definition is impredicative iff it quantifies over a domainwhich contains the object that is being defined.  	In the wake of the paradoxes, Whitehead, Russell, Poincar\'{e} andWeyl rejected such impredicative definitions as ``viciouslycircular'':\begin{quote}	An analysis of the paradoxes to be avoided shows that they all	result from a kind of vicious circle. The vicious circles in	question arise from supposing that a collection of objects may	contain members which can only be defined by means of the	collection as a whole[\ldots. \textparagraph]	The principle which enables us to avoid illegitimate totalities	may be stated as follows: `Whatever involves \emph{all} of a	collection must not be one of the collection'; or, conversely:	`If, provided a certain collection had a total, it would have	members only definable in terms of that total, then the said	collection has no total.' We shall call this the `vicious-circle	principle,' because it enables us to avoid the vicious circles	involved in the assumption of illegitimate totalities.	\citep[p.~37]{WhiteheadRussell1910}\end{quote}If we follow them in rejecting the \emph{vicious-circle principle},then we might attempt to replace the disastrous Na\"{i}veComprehension Scheme (of \olref[sth][story][rus]{sec}) with something like this: \begin{defish}\emph{Predicative Comprehension.} For every formula $\phi$ quantifying only over sets: the set$^\prime$ $\Setabs{x}{\phi(x)}$ exists.\end{defish}So long as sets$^{\prime}$ are not sets, no contradiction will ensue.  Unfortunately, Predicative Comprehension is not very\emph{comprehensive}. After all, it introduces us to new entities,sets$^\prime$. So we will have to consider formulas which quantifyover sets$^\prime$. If they always yield a set$^\prime$, thenRussell's paradox will arise again, just by considering theset$^\prime$ of all non-self-membered sets$^\prime$. So, pursuing thesame thought, we must say that a formula quantifying oversets$^\prime$ yields a corresponding set$^{\prime\prime}$. And then wewill need sets$^{\prime\prime\prime}$,sets$^{\prime\prime\prime\prime}$, etc. To prevent a rash of primes,it will be easier to think of these as sets$_0$, sets$_1$, sets$_2$,sets$_3$, sets$_4$,\ldots. And this would give us a way into the(simple) theory of types. There are a few obvious objections against such a theory (though it isnot obvious that they are \emph{overwhelming} objections). In brief:the resulting theory is cumbersome to use; it is profligate inpostulating different kinds of objects; and it is not clear, in theend, that impredicative definitions are even  \emph{all that bad}. 	To bring out the last point, consider this remark from\citeauthor{Ramsey1925}:\begin{quote}	we may refer to a man as the tallest in a group, thus identifying	him by means of a totality of which he is himself a member without	there being any vicious circle. \citep{Ramsey1925}\end{quote}Ramsey's point is that ``the tallest man in the group'' \emph{is} animpredicative definition; but it is obviously perfectly kosher. One might respond that, in this case, we could pick out the tallestperson by \emph{predicative} means. For example, maybe we could justpoint at the man in question. The objection against impredicativedefinitions, then, would clearly need to be limited to entities whichcan \emph{only} be picked out impredicatively. But even then, we wouldneed to hear more, about why such ``essential impredicativity'' wouldbe so bad.\footnote{For more, see \citet{Linnebo2010}.}Admittedly, impredicative definitions are extremely bad news, if wewant our definitions to provide us with something like a recipe for\emph{creating} an object. For, given an impredicative definition, onewould genuinely be caught in a vicious circle: to create theimpredicatively specified object, one would \emph{first} need tocreate all the objects (including the impredicatively specifiedobject), since the impredicatively specified object is specified interms of all the objects; so one would need to create theimpredicatively specified object before one had created it itself. Butagain, this is only a serious objection against ``essentiallyimpredicatively'' specified sets, if we think of sets as things thatwe \emph{create}. And we (probably) don't.As such---for better or worse---the approach which became common doesnot involve taking a hard line concerning (im)\-pre\-di\-ca\-tiv\-ity.Rather, it involves what is now regarded as the cumulative-iterativeapproach. In the end, this will allow us to stratify our sets into``stages''---a \emph{bit} like the predicative approach stratifiesentities into sets$_0$, sets$_1$, sets$_2$, \ldots---but we will notpostulate any difference in kind between them. \end{document}

content/set-theory/story/cumulative-approach.tex

\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{sth}{story}{approach}\olsection{The Cumulative-Iterative Approach}Here is a slightly fuller statement of how we will stratify sets intostages:\begin{quote}	Sets are formed in \emph{stages}. For each stage $S$, there are	certain stages which are \emph{before} $S$. At stage $S$, each	collection consisting of sets formed at stages before $S$ is	formed into a set. There are no sets other than the sets which are	formed at stages. \citep[p.~323]{Shoenfield:AST}\end{quote} This is a sketch of the \emph{cumulative-iterative conception ofset}. It will underpin the formal set theory that we present in\olref[sth][][]{part}. Let's explore this in a little more detail. As Shoenfield describesthe process, at every stage, we form new sets from the {sets} whichwere available to us from earlier stages. So, on Shoenfield's picture,at the initial stage, stage $0$, there are no \emph{earlier} stages,and so \emph{a fortiori} there are no sets available to us fromearlier stages.\footnote{Why should we assume that there \emph{is} afirst stage? See the footnote to \stagesord{} in\olref[z][story]{sec}.} So we form only one set: the setwith no !!{element}s $\emptyset$. At stage $1$, exactly one set isavailable to us from earlier stages, so only one new set is$\{\emptyset\}$. At stage $2$, two sets are available to us fromearlier stages, and we form two new sets $\{\{\emptyset\}\}$ and$\{\emptyset, \{\emptyset\}\}$. At stage $3$, four sets are availableto us from earlier stages, so we form twelve new sets\ldots. As such,the cumulative-iterative  picture of the sets will look a bit likethis (with numbers indicating stages):\begin{center}	\begin{tikzpicture}[scale=0.6]	\tikzset{cut_here/.style={densely dotted}}	\draw (-4,6) -- (-1, 0)-- (2,6); 	\draw[cut_here] (-5,8)--(-4,6);	\draw[cut_here] (2,6)--(3,8);	\draw(-1.5, 1)--(-0.5, 1);	\draw(-2, 2)--(0, 2);	\draw(-2.5, 3)--(0.5,3);	\draw(-3, 4)--(1, 4);	\draw(-3.5, 5)--(1.5, 5);	\draw(-4, 6)--(2, 6);	\node[label] at (0, 0) {\small 0};	\node[label] at (0.5, 1) {\small 1};	\node[label] at (1, 2) {\small 2};	\node[label] at (1.5, 3) {\small 3};	\node[label] at (2, 4) {\small 4};	\node[label] at (2.5, 5) {\small 5};	\node[label] at (3, 6) {\small 6};	\end{tikzpicture}\end{center}So: why should we embrace this story? One reason is that it is a nice, tractable story. Given the demise ofthe most obvious story, i.e., Na\"ive Comprehension, we are in want ofsomething nice. But the story is not \emph{just} nice. We have a good reason tobelieve that any set theory based on this story will be\emph{consistent}. Here is why. Given the cumulative-iterative conception of set, we form sets atstages; and their !!{element}s must be objects which were available\emph{already}. So, for any stage~$S$, we can form the set \[	R_S = \Setabs{x}{x \notin x \text{ and $x$ was available before $S$}}\]The reasoning involved in proving Russell's Paradox will now establishthat $R_S$ itself is not available before stage $S$. And that's not acontradiction. Moreover, if we embrace the cumulative-iterativeconception of set, then we shouldn't even have \emph{expected} to beable to form the Russell set itself. For that would be the set of allnon-self-membered sets that ``will ever be available''. In short: thefact that we (provably) can't form the Russell set isn't\emph{surprising}, given the cumulative-iterative story; it's what wewould \emph{predict}.%In one sense, then, the cumulative-iterative conception of set yields a response to Russell's Paradox which is rather like the \emph{predicativist}'s response. After all, the predicativist said that the collection of all non-self-membered sets$_n$ is a set$_{n+1}$, and this set$_n$ will not be self-membered. (Indeed, most predicativists will treat it as \emph{ungrammatical} to try to ask whether a set is self-membered.)%%But there is an important difference between the cumulative-iterative approach and the predicativist approach: the cumulative-iterative approach treats all of our entities as being \emph{of the same kind}. The predicativist will presumably have an empty set$_0$ (i.e., a set$_0$ with no !!{element}s), and an empty set$_1$ (i.e., a set$_1$ with no !!{element}s), and these will be \emph{different entities}. But on the cumulative-iterative approach, there is just one empty set, $\emptyset$, and it will be available at every stage of the hierarchy. %Indeed, the Axiom of Extensionality, stated at the start of this chapter, will hold true of the elements in this hierarchy (so that there can be \emph{only one} ``empty'' set). But I do not intend to use the cumulative-iterative conception to justify Extensionality (see \cite{Boolos1971}). Again: I suggest that we should accept Extensionality, just because we are interested in extensional collections. \end{document}

content/set-theory/story/urelements.tex

\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{sth}{story}{urelements}\olsection{Urelements or Not?}In the next few chapters, we will try to extract axioms from thecumulative-iterative conception of set. But, before going any further,we need to say something more about \emph{urelements}. The picture of \olref[approach]{sec} allowed us only to form new setsfrom old \emph{sets}. However, we might want to allow that certain\emph{non-sets}---cows, pigs, grains of sand, or whatever---can be!!{element}s of sets. In that case, we would start with certain basicelements, \emph{urelements}, and then say that at each stage $S$ wewould form ``all possible'' sets consisting of urelements or setsformed at stages before $S$ (in any combination). The resultingpicture would look more like this:\begin{center}	\begin{tikzpicture}[scale=0.6]	\tikzset{cut_here/.style={densely dotted}}	\draw (-4,6) -- (-1, 0) -- (1,0) -- (4,6); 	\draw[cut_here] (-5,8)--(-4,6);	\draw[cut_here] (5,8)--(4,6);	\draw(-1.5, 1)--(1.5, 1);	\draw(-2, 2)--(2, 2);	\draw(-2.5, 3)--(2.5,3);	\draw(-3, 4)--(3, 4);	\draw(-3.5, 5)--(3.5, 5);	\draw(-4, 6)--(4, 6);	\node[label] at (2, 0) {\small 0};	\node[label] at (2.5, 1) {\small 1};	\node[label] at (3, 2) {\small 2};	\node[label] at (3.5, 3) {\small 3};	\node[label] at (4, 4) {\small 4};	\node[label] at (4.5, 5) {\small 5};	\node[label] at (5, 6) {\small 6};	\end{tikzpicture}\end{center}So now we have a decision to take: \emph{Should we allow urelements?}Philosophically, it makes sense to include urelements in ourtheorising. The main reason for this is to make our set theory\emph{applicable}. To illustrate the point, recall from\olref[sfr][siz][]{chap} that we say that two sets $A$ and~$B$ havethe same size, i.e., $\cardeq{A}{B}$, iff there is a bijection betweenthem. Now, if the cows in the field and the pigs in the sty both formsets, we can offer a set-theoretical treatment of the claim ``thereare as many cows as pigs''. But if we ban urelements, so that the cowsand the pigs do \emph{not} form sets, then that set-theoreticaltreatment will be unavailable. Indeed, we will have no straightforwardability to apply set theory to anything other than sets themselves.(For more reasons to include urelements, see \citealt[pp.~vi, 24,50--1]{Potter2004}.)Mathematically, however, it is quite rare to allow urelements. Inpart, this is because it is \emph{very slightly} easier to formulateset theory without urelements. But, occasionally, one finds moreinteresting justifications for excluding urelement from set theory:\begin{quote}	In accordance with the belief that set theory is the foundation of	mathematics, we should be able to capture all of mathematics by	just talking about sets, so our variable should not range over	objects like cows and pigs. 	%But if $C$ is a cow, $\{C\}$ is a set, but not a legitimate mathematical object. 	\citep[p.~8]{Kunen1980}\end{quote}So: a focus on applicability would suggest \emph{including}urelements; a focus on a reductive foundational goal (reducingmathematics to pure set theory) might suggest \emph{excluding} them.Mild laziness, too, points in the direction of excluding urelements. We will follow the laziest path. Partly, though, there is apedagogical justification. Our aim is to introduce you to the elementsof set theory that you would need in order to get started on thephilosophy of set theory. And most of that philosophical literaturediscusses set theories formulated \emph{without} urelements. So thisbook will, perhaps, be of more use, if it hews fairly closely to thatliterature.\end{document}

content/set-theory/story/grundgesetze.tex

\documentclass[../../../include/open-logic-section]{subfiles}\begin{document}\olfileid{sth}{story}{blv}\olsection{Appendix: Frege's Basic Law V}In \olref[rus]{sec}, we explained that Russell's formulated hisparadox as a problem for the system Frege outlined in his\emph{Grundgesetze}. Frege's system did not include a directformulation of Na\"{i}ve Comprehension. So, in this appendix, we willvery briefly explain what Frege's system \emph{did} include, and howit relates to Na\"ive Comprehension and how it relates to Russell'sParadox.Frege's system is \emph{second-order}, and was designed to formulatethe notion of an \emph{extension of a concept}.\footnote{Strictlyspeaking, Frege attempts to formalize a more general notion: the``value-range'' of a function. Extensions of concepts are a specialcase of the more general notion. See \citet[pp.\ 8--9]{Heck2012} forthe details.} Using notation inspired by Frege, we will write$\fregeext{x}{F(x)}$ for \emph{the extension of the concept~$F$}. Thisis a device which takes a \emph{predicate}, ``$F$'', and turns it intoa (first-order) \emph{term}, ``$\fregeext{x}{F(x)}$''. Using thisdevice, Frege offered the following \emph{definition} of membership:\[	a \in b =_\text{df} \exists G(b = \fregeext{x}{G(x)} \land Ga)\]roughly: $a \in b$ iff $a$ falls under a concept whose extension is$b$. (Note that the quantifier ``$\exists G$'' is second-order.) Fregealso maintained the following principle, known as \emph{Basic Law V}: $$\fregeext{x}{F(x)} = \fregeext{x}{G(x)} \liff \forall x (Fx \liff Gx)$$roughly: concepts have identical extensions iff they are coextensive. (Again, both ``$F$'' and ``$G$'' are in predicate position.) Now a simple principle connects membership with property-satisfaction:\begin{lem}[in \emph{Grundgesetze}]\ollabel{lem:Fregeextensions}$\forall F \forall a(a \in \fregeext{x}{F(x)} \liff Fa)$\end{lem}\begin{proof} Fix $F$ and $a$. Now $a \in \fregeext{x}{F(x)}$ iff $\exists G(\fregeext{x}{F(x)}= \fregeext{x}{G(x)} \land Ga)$ (by the definition of membership) iff$\exists G(\forall x(Fx \liff Gx) \land Ga)$ (by Basic Law V) iff $Fa$(by elementary second-order logic).\end{proof}And this yields Na\"ive Comprehension almost immediately:\begin{lem}[in \emph{Grundgesetze}.]$\forall F \exists s \forall a (a \in s \liff Fa)$\end{lem}\begin{proof}Fix $F$; now \olref{lem:Fregeextensions} yields $\forall a (a \in\fregeext{x}{F(x)} \liff Fa)$; so $\exists s\forall a(a \in s \liff Fa)$ byexistential generalisation. The result follows since $F$ wasarbitrary.\end{proof}Russell's Paradox follows by taking $F$ as given by $\forall x(Fx \liff x \notin x)$. \end{document}