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: What does set membership “look like” in Rel?

Julius Hamilton (Jul 28 2024 at 21:46):

The category of sets and relations has the set of all relations between $A$ and $B$ as the Hom-set $Hom(A, B)$.

But you only need a single binary relation ‘$\in$’ in a first-order signature to write the axioms of ZFC.

The set of all relations between two sets can be defined as the power set of their product - $P(A \times B)$.

But the power set can be defined in terms of subsets, which can be defined in terms of set-membership. And the product can be defined in terms of a function $A \times B := \{\{a, \{a, b\}\} | a \in A, b \in B\}$.

Does the $\in$ relation even “show up” in $\mathbf{Rel}$? It could be defined as ordered pairs, for all sets $A, B$ for which $A \in B$. But that would indicate that it is in the Hom-set between the class of all sets and itself. But that would indicate that we are actually talking about a “Hom-set between proper classes”, which are not objects in the category $\mathbf{Rel}$. Right?

Ryan Wisnesky (Jul 28 2024 at 23:16):

you might be looking for the notion of "power allegory", to define "membership" in Rel etc

Julius Hamilton (Jul 31 2024 at 11:46):

One add-on thought I’ve been having lately:

The concept of isomorphism seems quite paramount in category theory and mathematics in general.

It is really interesting to consider that the axioms of a category are an attempt to identify key properties of functions; so that abstract categories are “abstractions” of “sets and functions”. I don’t know if that’s true, but Awodey says in his intro to category theory book that categories can be seen as “algebras of functions”. I have been thinking about how the axioms of a category could be seen as capturing some essential aspects of the nature of functions, perhaps as “transformations”, basically, the identity “transformation”, and the fact that transformations can be meaningfully composed to correspond to another transformation; etc. I have been interested in weakening a condition on categories to study what might happen, such as removing the requirement for associativity of composition of morphisms.

Even with the same collection of objects, our choice of morphisms has “great power” in reflecting what that collection of objects “comes to look like”. I read a post by Mike Shulman online in response to a question, “Why don’t we just study the skeleton of a category?” That idea occurred to me as well. Abstractly, it seems like the axioms of a category are set up to make isomorphic objects indistinguishable, where there is no category-theoretic property that would not apply universally to all objects isomorphic to an object (I don’t know if that’s true, though). I am pretty sure Shulman’s post may have been saying that when we look at the concrete objects, the fact that they are isomorphic can be what gives us some of the most useful results or information.

But I would still wonder, would there be any other reason to keep isomorphic objects separate, in an abstract category? The skeleton of $\mathbf{Set}$ should be something like the class of ordinal or cardinal numbers, I believe. I wonder, by “merging” all sets into equivalence classes based on their cardinality, do we lose any information that was present in $\mathbf{Set}$? Or does it just make the information “less apparent”?

It relates to ideas I’ve been exposed to where the “goal” is actually not always to be as general as possible, because this can actually cause us to lose information or “rich structure”, something that hadn’t occurred to me earlier, as a paradigm. For example, I was asking myself what a natural progression would be, from $\mathbf{Set}$ to $\mathbf{Rel}$, and from $\mathbf{Rel}$ to what? I wondered if there could be a category whose Hom-sets are Cartesian products $A \times B$ for sets $A$ and $B$. I haven’t checked yet if it would meet the axioms of a category, but I read that such a category is possible, but it would have almost no “structure”. I need to check and confirm if that’s true.

I feel like that’s a very interesting paradigm to keep in mind. It reminds me of some ideas in information theory I’d like to study. That there’s actually a way in which generality may not be “the goal”, but rather the opposite, that by decreasing generality you actually increase “information” (in a formally defined way).

I’ve been interested, both in first-order logic and in category theory, about how with some sort of “minimal definition”, “all the information is already there”. For example, you can define a Boolean algebra with a single operation, NAND or NOR. You could in theory derive all the theorems of ZFC without defining any functions or relations beyond ‘$\in$’; maybe we could say it would just be more cumbersome, and the formulae much longer. When we define more symbols in the theory, even though we have a logically equivalent theory or structure, it just makes aspects of the structure “more apparent”, to the human. I am very interested in exploring that idea mathematically: if we act like all logically equivalent theories are “the same”, we are clearly missing what is so valuable, apparently, about having all these theories which can be translated into each other, but which reflect something in a totally different way. I would be interested in expressing that idea mathematically, beyond just claiming that “it helps the human think of new ideas for theorems”.

The idea that is still taking shape in my mind is that not only does a category of the same objects possibly look completely different based on what morphisms we choose for the objects (even though all that information was “already there”, before we chose this or that definition for the morphisms), but maybe we can go even further and explore modifications to the definition of a category itself, as seemingly with power allegories, to see what analogous concepts to isomorphism come about, as yet another way to look at sets and how they relate to each other.

I guess it’s interesting to consider that prior to choosing a definition for morphisms, or something analogous to them, all the sets in ZFC look “completely different”, and there are so many different ways to choose to relate them to each other, so that suddenly, perhaps unexpectedly, two sets “are isomorphic” or “related” that we did not initially expect to be. The paradigm I want to explore mathematically is, “Isomorphism is a concept relative to a context, not an intrinsic attribute of a thing. There is no isomorphism, only isomorphism under a definition of isomorphism”, sort of.

And reminds me of the quote by Walter Pater, “it is only the roughness of the eye that makes two persons, things, situations, seem alike”.

Joshua Meyers (Jul 31 2024 at 13:10):

Mainly a reply to your OP - I only skimmed the "add-on".

When discussing logical systems such as ZFC, it's important to distinguish between syntax and semantics. ZFC itself is purely syntactic, and "$\in$" is a relation symbol, not a relation.

Furthermore, you can't write the axioms of ZFC purely in terms of the symbol "$\in$". You also need the symbols $\wedge$, $\vee$, $\forall$, $\exists$, etc. the whole apparatus of predicate logic with equality.

Where actual relations come into play is in models of ZFC. A model of ZFC is an interpretation of each symbol such that the axioms (which in themselves are just strings of symbols) hold, when each symbol is interpreted. So a model of ZFC would be a set (in some ambient set theory) with a relation $\llbracket \in \rrbracket$ interpreting $\in$ which satisfies all the (suitable interpreted) axioms of ZFC. As a set with a relation, this would indeed show up in $\mathsf{Rel}$.

Joshua Meyers (Jul 31 2024 at 13:11):

But there are many models of ZFC, not just one, so it does not make sense to speak of the $\in$ relation.

Julius Hamilton (Jul 31 2024 at 13:40):

Thank you.

I have been wondering for a while:

• What ambient set theories do people usually use to define a model for ZFC?

• Is there a smallest model of ZFC?

• Do people ever consciously choose to work in a particular model of ZFC as opposed to a different one?

• Even using an ambient set theory $T_2$ with a relation $[[\in]]$, do we still have to define a relation as a subset of the product of two sets? Wouldn’t this still necessitate that $[[\in]]$, as a relation, is actually a subset of a product of the structures containing all the sets in this domain, for example, on the proper class of those sets? I think that Morse-Kelley set theory enables us to do more “mathematics” on the proper classes along with the sets.

• If we use an ambient set theory to define a model for ZFC or another first-order theory, shouldn’t that ambient set theory have its own deductive rules? Wouldn’t that imply it has its own formal language describing it?

• Does that mean that we end up with a language we use to define the theory of a weak set theory, and then we have a second language we use to describe ZFC, and we are technically checking if the proofs of the second language correspond to proofs in the first?

• If we use a second “set” theory to define a model for a first “set” theory, then if we cease to use the word “set”, what we actually have are two different logical theories describing two distinct classes of entities (ie, the “sets” of the one theory are not the “same group of things” as the second, so we can name them as different things, if we like). Thus, in trying to define sets, we actually imply that there are at least two “levels” of “sets”. Is that correct?

I was thinking maybe instead of defining a relation as a subset of a product, we could just list the elements of the relation as ordered pairs. But I think ordered pairs, categorically, could be global elements of product objects, and we can have subobjects as well. It makes me wonder if we can create a kind of “algebra of set theories” where we study each one’s capability to define or describe the other ones, including itself; and perhaps explore if weaker set theories can be expressed as having weaker categorical properties, like the presence or absence of products, exponential objects, limits, etc. And maybe, to go further, we can explore the properties of such an “algebra of set theories” depending on which set theory we define/construct it in.

Julius Hamilton (Jul 31 2024 at 14:08):

I found some reading material on this.

Barton, N., Caicedo, A. E., Fuchs, G., Hamkins, J. D., Reitz, J., & Schindler, R. (2020). Inner-Model Reflection Principles. Studia Logica, 108(3), 573-595. https://doi.org/10.1007/s11225-019-09860-7

Beckmann, A., Buss, S., Friedman, S., Müller, M., & Thapen, N. (2017). Cobham Recursive Set Functions and Weak Set Theories. In S. D. Friedman, D. Raghavan, & Y. Yang (Eds.), Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore (Vol. 33, pp. 55-116). World Scientific.

Cohen, P. J. (1963). A Minimal Model for Set Theory. Bulletin of the American Mathematical Society, 69(4), 537-540.

Forssell, H. (2004). Categorical Models of Intuitionistic Theories of Sets and Classes. Master's thesis, Carnegie Mellon University.

Freire, A. R., & Hamkins, J. D. (2021). Bi-interpretation in weak set theories. Journal of Symbolic Logic, 86(2), 609-634. https://doi.org/10.48550/arXiv.2001.05262

Koellner, P. (2009). On reflection principles. Annals of Pure and Applied Logic, 157(2-3), 206-219.

Mathias, A. R. D. (2001). Weak set theories in foundational debates. Mathematical Proceedings of the Cambridge Philosophical Society, 130(1), 1-10.

Morse, A. P. (1965). A Theory of Sets. Pure and Applied Mathematics XVIII, Academic Press. Second Edition, xxxi+130 pp.

Pakhomov, F. (2019). A Weak Set Theory that Proves its Own Consistency. Preprint, arXiv:1907.00877.

Rathjen, M. (1994). Proof Theory of Reflection. Annals of Pure and Applied Logic, 68, 181-224.

Sato, K. (2011). The Strength of Extensionality II — Weak Weak Set Theories Without Infinity. Annals of Pure and Applied Logic, 162(8), 579-646.

Stanford Encyclopedia of Philosophy. (2021). Alternative Axiomatic Set Theories.

Mike Shulman pointed me towards a passage in a logic textbook in which the authors say something like, that what we can do is use a first formal theory to study a second one, and if they are the same theory, say, ZFC, it is actually a clean form of self-justification, because we are looking at how “a formal system defines a second copy of itself”. So to me, philosophically, this can be seen as a kind of infinitism or coherentism, which interests me.

Joshua Meyers (Jul 31 2024 at 14:15):

Those are great questions and I don't know the answers

Joshua Meyers (Jul 31 2024 at 14:17):

For your fourth question, I think that the answer is Yes, but I don't understand part 2 of your fourth question. I would help if you were more rigorous in distinguishing the symbol $\in$ from its interpretation in a particular model

John Baez (Jul 31 2024 at 14:26):

I can only answer a few of these.

Julius Hamilton said:

• What ambient set theories do people usually use to define a model for ZFC?

I imagine the most common is ZFC, perhaps supplemented by some extra axioms.

• Do people ever consciously choose to work in a particular model of ZFC as opposed to a different one?

Most mathematicians just prove theorems that could be proved in ZFC. (I say it this way because most mathematicians don't actually remember the ZFC axioms, or even care about them... but set theorists could take what they do and redo it in ZFC.) By the soundness theorem, these theorems are satisfied in every model of ZFC.

A few mathematicians prove theorems that could be proved in ZFC plus extra axioms, like the Continuum Hypothesis or various large cardinal axioms. (These mathematicians are more likely to know the ZFC axioms.) These theorems are satisfied in all models of ZFC that also obey those extra axioms.

Notice, the mathematicians above aren't thinking about "models of ZFC". They are thinking about theorems and proofs, and I'm saying these proofs could be carried out in ZFC, perhaps plus extra axioms. Then, just for fun, I'm saying stuff about how this is related to model theory. But the mathematicians aren't thinking about models, usually.

As far I can tell, it's only model theorists who deliberately "work within a model of ZFC". I.e., they may prove theorems like "let X be a model of ZFC such that blah-di-blah. Then...."

• Even using an ambient set theory with an $\in$-relation, do we still have to define a relation as a subset of the product of two sets?

If you're choosing a model of ZFC, yes you have to choose a membership relation for your model. This doesn't need to be at all like the $\in$ relation in your ambient set theory! Why should it? No reason.

For example, you can have a model of ZFC where all the elements of the universe are countable sets in the ambient theory, but not countable in the model.

Wouldn’t this still necessitate that $\in$ is a relation defined on the containing structures of those sets, such as the proper class of those sets?

I don't know what that means.

-If we use an ambient set theory to define a model for ZFC or another first-order theory, shouldn’t that ambient set theory have its own deductive rules? Wouldn’t that imply it has its own formal language describing it?

If you ask most classical model theorists this question, I'm guessing they will probably say the ambient set theory is ZFC formulated in the usual way in first-order logic. But I doubt most of them lose much sleep over this. There is a limit to how many meta-levels most people want to think about!

(I could be wrong, and if so I'd like to hear about it. Note also that I'm not talking about constructivists here. They will probably have a different answer.)

Jencel Panic (Aug 03 2024 at 13:26):

Perhaps it is slightly off-topic, but I was enlightened when I read the comparison between type theory and set theory in 1lab:
https://1lab.dev/1Lab.intro.html