Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: learning: questions

Topic: To say something “is a set”

Julius Hamilton (Jun 18 2024 at 14:43):

I was reading the definition of a Grothendieck universe, which starts out “…is a set $U$ such that…”.

When we say something “is a set”, we mean it is an element in a domain $A$, where $A$ is a model of a set theory $\Phi$ in signature $S$. Right?

In my logic textbook, the author states that domain $A$ is a set. I assume you can use naive set theory to define a domain, but later in the text I believe the author states that it is actually a set in ZFC.

One thing I have not yet thought about is what a domain “is like”.

A domain normally would not be a set of atoms (point-like elements that do not contain any elements themselves), because then there would be no way to interpret relation symbols. The formula $xRy$ would be satisfied if $R$ were mapped to a relation in $A$ for which $xRy$. Relations are commonly represented as sets of pairs. So if we have no pairs, we have no relations.

I know this is a common question to ask, but I want to make sure I fully understand it.

I thought the entire concept of “set” was going to be “an element of a domain $A$, where that domain satisfies all variable assignments for a collection of formulas”. In some ways, I think in the spirit of structural set theory, I thought that we did not need the conceptual picture of “things contained in other things” to reason about sets. Instead, we can treat the relation symbol “$\in$” as the real determiner of what “is a set” or not.

I was thinking that instead of saying something “is a set”, it’s more accurate to express that there is some element $x$ in the domain for which “$x \in y$”. If we know $y$ is in the domain, “$x \in y$” is a formal way of saying “is a set”.

But this implies that to be a set is to be contained by a set. So, whenever we say “$S$ is a set”, in theory, shouldn’t we be forced to say what set $S$ is an element of?

John Baez (Jun 18 2024 at 16:36):

Julius Hamilton said:

I was reading the definition of a Grothendieck universe, which starts out “…is a set $U$ such that…”.

When we say something “is a set”, we mean it is an element in a domain $A$, where $A$ is a model of a set theory $\Phi$ in signature $S$. Right?

Sometimes, but certainly not always. The concept of a model of set theory requires that we already know what sets are, since a model involves what you're calling a domain $A$, and if you ask what that is, the answer is: it's a set.

John Baez (Jun 18 2024 at 16:38):

You said that later:

Julius Hamilton said:

In my logic textbook, the author states that domain $A$ is a set.

John Baez (Jun 18 2024 at 16:40):

I guess you see the circularity here: if you define a "set" to be an element of the domain $A$, and you define $A$ to be a set with certain properties, then you're going in circles.

John Baez (Jun 18 2024 at 16:41):

The point is: you seem to be talking about some textbook on model theory. But to do model theory you need to already have decided what a set is - or maybe have decided to not decide, that's fine too.

John Baez (Jun 18 2024 at 16:44):

But if you're trying to be precise and non-circular in your work on logic and set theory, you can't start with model theory. You have to start with syntax: that is, symbols you write on the page, and rules for what strings of symbols count as a well-formed formulas, and rules for what strings of symbols count as a proof.

John Baez (Jun 18 2024 at 16:45):

Then you can write down some axioms for set theory. These are strings of symbols... they might look like this for example:

$\exists x (\forall y (\neg (y \in x) ))$

John Baez (Jun 18 2024 at 16:47):

This is an axiom saying that there is an empty set.

John Baez (Jun 18 2024 at 16:47):

And if we do set theory using axioms like this, e.g. the ZFC axioms, then all the variables $x, y, \dots$ stand for sets.

John Baez (Jun 18 2024 at 16:51):

When doing this, we never need to officially say what a set is: we just start writing strings of symbols called "theorems" starting from some strings of symbols called "axioms", following the "deduction rules" we have chosen.

John Baez (Jun 18 2024 at 16:52):

But off to the side, informally, you're allowed to whisper that each of the letters like $x, y, z, ...$ that we're writing down, called variables, stands for a "set".

For example, I did that just now when I whispered in your ear that

$\exists x (\forall y (\neg (y \in x) ))$

is the axiom asserting the existence of an empty set. That remark wasn't part of the formalism - that was just me helping you understand why I wrote down this string of symbols!

John Baez (Jun 18 2024 at 16:53):

Mind you, this is just one of many approaches, but it's a common traditional approach when people are trying to be ultra-rigorous.

If you pursue this ultra-rigorous approach, you can eventually define "models" and prove theorems about them, including theorems about models of various theories of sets! At that point we're using set theory to study set theory. So at that point we've got two concepts of set floating around in our mind: the things that are variables like $x, y, z, ...$, and the things that are variables obeying $x \in a$ where $a$ is the domain of some model of some axioms of set theory.

John Baez (Jun 18 2024 at 16:59):

There's also another approach to math, even more common, where you're not so rigorous, and you just start talking about sets like an ordinary person, not necessarily explaining what they are, and using whatever intuitions you have about sets. And then you can do lots of stuff... and one thing you can do is model theory.

Julius Hamilton (Jun 20 2024 at 02:55):

Thank you. Do you know which text defines set theory in this ultra-rigorous way?

David Egolf (Jun 20 2024 at 03:26):

"A Mathematical Introduction to Logic" by Enderton might be a useful resource. For example, "well-formed formulas" are discussed starting on page 12.

Jean-Baptiste Vienney (Jun 20 2024 at 03:48):

I recommend you to take a look at "Foundations of Set Theory" by Fraenkel, Barr-Hillel, Levy (to decide if you want to read it). I find it a fascinating book.

dusko (Jun 20 2024 at 05:17):

Julius Hamilton said:

Thank you. Do you know which text defines set theory in this ultra-rigorous way?

julius, i have been teaching math for many years, and i did meet some people who tried to learn by finding ultra-rigorous definitions of things, and it always ended in frustration. thing is, math is an extension of the language we speak. when someone says "chair", everyone understands what they are talking about, but everyone imagines a slightly different chair. in math, when someone says "triangle", we all know what it is, but a triangle on a manifold is a different thing from a triangle in a vectors space, from a triangle in a graph, and godforbid from a triangle in a triangulated category.

like chairs, sets are many things to many people. an ultra-rigorous book may claim to define the notion of set, but then you take another ultra-rigorous book and the notion of set is different. and the two books may be by the same author. mathematicians call things $x$ and $z$ precisely for that reason: to be able specify ultra-rigorous definitions when convenient, and change them on the next page...

sets came about when cantor was trying to count how many iterations a particular construction (of the domain of convergence of some series) might take, and it turned out to be more than infinitely many times, so it was puzzling, and he started to peel off all irrelevant structure, to see why it was taking so long. what remained after he peeled off all structure was the concept of set. it only says how many elements are there. but then he started to struggle with the fact that, since there was no structure to distinguish the elements, another set with the same number of elements was indistinguishable. so he started identifying sets up to bijective functions between them. but to be sure that two sets with injections both ways were the same set, ie had a bijection between them, he needed to map the elements in order. so he distinguished the order types, with order-preserving bijections, from unordered sets with bijections. since these unordered sets might have injections but he couldn't prove that they had bijections, he reduced these sets-up-to-bijections to numbers. he fixed the well-ordered types as ordinal numbers, and cut them modulo permutations and defined the cardinal numbers. for all of it to work, he needed to be able to order any given set. he spent 10 years trying to prove that he could, and dedekind finally convinced him to let go. (dedekind used some of cantor's constructions in his epochal Zahlenbericht but attributed them to cantor only in the manuscript.) then came zermelo, and proposed that cantor's well-ordered sets should be replaced by his axiom of choice, and crossed out from cantor's collected works all constructions that he didn't understand. by that time, cantor was a broken man. enjoying zermelo's version of cantor's work, people proceeded to write 100 years of ultra-rigorous books about sets. about 50 years after cantor started writing about sets up to bijections, people started studying groups up to isomorphisms, spaces up to homeomorphisms, categories up to equivalence, a bit later 2-categories up to 3-cells, and so on...

sets, groups, chairs, elephants, modular forms, and pretty much all other words mean many things to many people, and different things in different contexts. believing that anything can be settled by being ultra-rigorous is a risky proposition.

dusko (Jun 20 2024 at 06:07):

oh and if you want to understand how the distinction between "sets" and "classes" works, you can define the universe of "sets" to be the set of all finite sets (or if you also take the functions between them, you get the category of finite sets); and you can define the universe of "classes" to be all sets, without the finiteness requirement. anything that you can put the curly brackets around. eg {Big Island} is a set. the idea is that a universe is closed under whatever operations you can hit them with.

so now you have two universes, Sets and Classes. you can prove that the universe Sets is not a "set" in itself, so it is a "class" in Classes. but then you can also prove that the universe Classes is not a "class". so you have an object from a third universe. if you want to be able to see each universe as an object, you get a tower of grothendieck's universes. (he apparently thought that it was ridiculous that his name got attached to them.) if you want to close the tower under some trans-universe constructions, the tower becomes transfinite, and we are back to cantor :)

(computation lives in the above two universes, separated by what would be the first inaccessible cardinal if people didn't go out of their way to patch the definition of inaccessibility to preclude it :)

John Baez (Jun 20 2024 at 07:56):

Dusko is right that you need to learn a lot of mathematics and learn how to do a lot of stuff with sets before you build up the mathematical strength to take an ultra-rigorous approach to set theory. Otherwise it'll be hard to understand what's going on.

He's also right that there are many ultra-rigorous approaches to set theory, and no one of them is right.

So I would check to make sure you know almost all the stuff in a non-rigorous introduction to set theory before diving into rigorous stuff. I just looked around, and Hrbacek and Jech's Introduction to Set Theory is the kind of book I mean. The very last chapter, called Axiomatic Set Theory, introduces the ZFC axioms in ordinary English. All these, and some of their main consequences, have been covered earlier in the book.

Once you know the ZFC axioms in plain English, and you know classical first-order logic (e.g. from Kleene's Mathematical Logic) you can write down the ZFC axioms in the formalism of first-order logic yourself, and then you're at the point of being able to do ultra-rigorous set theory in a very traditional style.

John Baez (Jun 20 2024 at 07:57):

And this may be one of those things that's better to know how to do than to actually do.

David Michael Roberts (Jun 20 2024 at 09:28):

I would even recommend Halmos' Naive set theory as a warm-up

Julius Hamilton (Jun 20 2024 at 11:18):

I want to save up a little money and do a little one week mathematical hermitage. Sometimes you need to break through and make some serious progress.

Patrick Nicodemus (Jun 20 2024 at 11:36):

I recommend

• the first chapter of Munkres's textbook on point set topology for a practical introduction to sets as they are used in mathematics
• "Set theory" by Enderton as a first look at formal set theory (ZFC)

John Baez (Jun 20 2024 at 12:07):

By the way, I get the feeling that some of Julius' worries about set theory may arise from reading Enderton's A Mathematical Introduction to Logic, which develops the study of logic based on a bit of informal set theory which Enderton explains in "Chapter Zero: Useful Facts About Sets". Enderton then goes on to develop first-order logic. This may give some people the misimpression that first-order logic relies on set theory, and also that set theory is somehow inherently informal. I haven't read Enderton's book; I hope he clears up these possible misimpressions somewhere.

John Baez (Jun 20 2024 at 12:08):

But I'm just making guesses about Julius' internal state: I don't even remember for sure whether he's reading this book by Enderton or some other book by Enderton!

Julius Hamilton (Jun 20 2024 at 13:16):

I’m reading Ebbinghaus. I have really enjoyed sticking to a single text. There are just a few spin-off questions that do indeed perplex me. I think the smart thing is to remind myself to have patience and that understanding comes with time.

Julius Hamilton (Jun 20 2024 at 13:18):

By the way, after surveying some recommended texts plus some others I found, some texts I like the most so far include Quine’s textbook on logic, Church’s textbook on logic, Mendelssohn’s textbook on logic, Hodges’s textbook on model theory, and the Fraenkel one on Foundations of Set Theory.

John Baez (Jun 20 2024 at 13:24):

I agree it's good to stick to a single text when first learning logic. What does Ebbinghaus say about sets? I think you were studying some model theory from Ebbinghaus. For model theory, meaning the study of $\models$ rather than the study of $\vdash$, you need some set theory. Often texts bring in this set theory informally, which can be disconcerting if you were thinking that logic is ultra-rigorous.

This makes me feel it's good to get really clear on the basics of proof theory and $\vdash$ before getting into model theory and $\models$.

Julius Hamilton (Jun 20 2024 at 13:31):

That would probably be a good use of my time. Took the day off today.