10
$\begingroup$

For experts who work in ZFC, it is common knowledge that one cannot in general define a countable intersection/union of proper classes. However, in my work as a ring theorist I intersect infinite collections of proper classes all the time.

Here is a simple example. Let a ring $R$ be called $n$-Dedekind-finite if $ab=1\implies ba=1$ for $a,b\in \mathbb{M}_n(R)$ (the $n\times n$ matrix ring over $R$). A ring $R$ is said to be stably finite if it is $n$-Dedekind-finite for every integer $n\geq 1$. The class of stably finite rings is the intersection (over positive integers $n$) of the classes of $n$-Dedekind-finite rings.

So my question is a straightforward one. What principle makes it okay for me to intersect classes in this manner?

Phrased a little differently my question is the following. Suppose we have an $\mathbb{N}$-indexed collection of sentences $S_n$ in the first-order language of rings. Why is it valid (in my day-to-day work) to form the class of rings satisfying $\land_{n\in \mathbb{N}}S_n$, even though the corresponding class doesn't necessarily exist if each $S_n$ is a sentence in the language of ZFC?

[Part of my motivation for this question is the idea that much of "normal mathematics" can be done in ZFC. That's how I've viewed my own work. I'm happy to think of my rings living in $V$, subject to all the constraints of ZFC. (In some cases I might go further, by invoking the existence of universes or the continuum hypothesis, but that is not the norm.) But I'm unsure how to justify my use of infinite Boolean operations on proper classes. Especially since, in some cases, my conditions on the rings are conditions on sets, from the language of ZFC!]


Another way to think about all of this:

Looking at the (currently three) answers to this question, it appears that people took my question to be asking about definability rather than existence. Under that interpretation of my question the answers are spot on, and I appreciate what they are saying.

Moreover, those three answers helped me realize that my question was more along the lines of the MathOverflow question "The set of Godel numbers of true sentences" as interpreted by Andreas Blass, from a Platonistic viewpoint, about existence rather than definability. So, I suppose that the answer I was looking for was something like:

Pace, you were wrong to say that the intersection "doesn't necessarily exist". It exists as a subcollection $S$ of the Platonistic universe $V$. You just cannot prove (or even properly state) in ZFC the fact that the class $S$ equals the intersection you are looking at. The "principle that makes it okay for [you] to intersect classes in this manner" is your personal Platonistic view of the universe of true sets, not any sort of logical principle that can be stated in a first-order way.

Any additional thoughts people have on this are welcome.

$\endgroup$
  • 8
    $\begingroup$ This is because here you don't have indepently generated sentences $S_n$, you have a single formula $\varphi(n,R)$ and so you can simply define the formula $\forall n, \varphi(n, R)$. $\endgroup$ – Max Jan 30 at 20:27
  • 4
    $\begingroup$ The definition of an $n$-DF ring is internal to the universe of sets. Not external. $\endgroup$ – Asaf Karagila Jan 30 at 21:10
  • 5
    $\begingroup$ Sure, there's nothing that prevents you from doing that. But this is kinda missing the urinal on purpose and complaining the toilet is wet. $\endgroup$ – Asaf Karagila Jan 30 at 21:22
  • 2
    $\begingroup$ By the way one can define in ZFC $M(R)$ as the set of (infinite) square matrices, with index set $\mathbf{N}$, which differ from a scalar matrix (= diagonal with constant diagonal) only at finitely entries. Then the formula is equivalent to the condition that $M(R)$ satisfies $ab=1\Rightarrow ba=1$. $\endgroup$ – YCor Jan 30 at 23:39
  • 5
    $\begingroup$ I hate to sound smug, but you don't seem to be working with enough of a fragment of $\mathsf{ZFC}$ for this to be a concern; or at least, aren't using it to it's full potential. The concern isn't so much sentences which require some parameter (as is the case for your notion of $n$-DF); as is the possibility that the sentences in the sequence require increasingly complex levels of quantification. $\endgroup$ – Not Mike Jan 31 at 4:19
21
$\begingroup$

You will have to come up with trickier examples.

There is a formula $\phi(R, n)$ of ZFC with parameters $R$ and $n$ whose meaning is "$R$ is an $n$-Dedekind finite ring". One might think that $n$ is a "meta-level" number, i.e., a number which is "outside" of set theory. That is not how ordinary mathematics works. We take set theory as the ambient universe in which everything happens. The natural way of reading the definition you gave is that it all happens inside set theory, and that $n$ denotes an element of a certain set $\mathbb{N}$. If one were to play tricks with logic, one could of course consider a situation in which $n$ is a meta-level number outside of set theory, but that is not how mathematics is done. Only logicians do such things.

The class of all stably finite rings is simply $\{R \mid \forall n \geq 1 \,.\, \phi(R, n)\}$. In other words, the imagined intersection of a countable collection of classes is not needed at all, because $$\bigcap_{n \geq 1} \{R \mid \phi(R, n)\} = \{R \mid \forall n \geq 1 \,.\, \phi(R, n)\}.$$ The point is that the property of being $n$-Dedekind finite is uniform in $n$ and so a single formula $\phi(n, R)$ works. The situation would be different if you proposed an infinite sequence of classes $$C_1, C_2, C_3, \ldots$$ indexed by meta-level natural numbers, where each $C_i$ is defined by some formula $\psi_i$, so that $C_i = \{x \mid \psi_i(x)\}$. Furthermore, it would have to be the case that the formulas $\psi_i$ are non-uniform, i.e., there is no single formula $\Psi$ such that $\psi_i(x) \Leftrightarrow \Psi(\overline{i},x)$. Here $i$ is a meta-level numbers and $\overline{i}$ is the element of the set $\mathbb{N}$ which corresponds to it, i.e., the $i$-fold application of successor to the element $0$. This sort of thing never happens in "ordinary" mathematics, but it happens in logic precisely because in logic we do study meta-level properties of set theory.

Lastly, let me mention that there are conservative extensions of ZFC in which classes are part of the theory proper, for example the Von Neumann-Bernays-Gödel set theory. Such theories make handling of classes quite a bit easier, so perhaps we should switch over to them, lest we get entangled in technicalities concerning meta-level and object-level numbers.

$\endgroup$
  • $\begingroup$ I don't think it is that easy. The $n$ here is a meta-natural number (not a natural number from inside ZFC, but from my meta-theory). So there is no such formula $\phi(R,n)$ of ZFC. $\endgroup$ – Pace Nielsen Jan 30 at 20:36
  • $\begingroup$ That said, go ahead and replace the family I gave with a new family that isn't given with any indexing (either from inside or outside the theory). In my day-to-day practice, I'd still think that the intersection of classes exists. $\endgroup$ – Pace Nielsen Jan 30 at 20:40
  • 4
    $\begingroup$ Of course, if you consider an arbitrary family of classes then you have a problem, but the point of the question is precisely whether mathematical practice ever produces such classes. Regarding the remark about meta-level indices versus indices, I will comment on that in my answer. $\endgroup$ – Andrej Bauer Jan 30 at 21:53
  • 1
    $\begingroup$ @PaceNielsen Why is $\phi(R,n)$ indexed by meta-natural number? I mean, you definitely can define your class this way, e.g., you can define \phi(R,3) by saying that you consider matrices with distinct entries a,b,c,d,e,f,g,h,i. But you definitely don't have to, and you didn't when formulating your definition. If you really insisted on using meta-natural numbers in your definition, then you couldn't have phrase your example correctly with a formula in ZFC (which you clearly did) $\endgroup$ – user57888 Jan 30 at 22:04
  • $\begingroup$ I'm familiar with NBG. I suppose my question could be rephrased as: Is there a theory like NBG that has proper classes along arbitrary intersections of proper classes (even if the intersection is indexed over the meta-theory)? $\endgroup$ – Pace Nielsen Jan 30 at 22:51
7
$\begingroup$

Here is an example of a family of classes of rings which you couldn't intersect: The class $A_n$ consists of all rings of power greater than n and the rings of cardinality $k≤n$ such that $ϕ_k$, where $ϕ_k$ is your favorite enumeration of sentences of ZFC. So for example, if $ϕ_0$ is "there exists an infinite set" and $ϕ_3$ is "$\mathbb{N}$ has at least 17 elements", $\phi_2$ is "there are uncountable sets of cardinality less than continuum" and CH happens to hold and $ϕ_1$ is "ZFC is inconsistent" and ZFC happens to be consistent, then $A_3$ is the class consisting of rings of cardinality 0,3 or greater. This is something you cannot write internally.

EDIT: To stress my point: if you could intersect the family of classes described above, this would simply result in an inconsistency.

$\endgroup$
  • $\begingroup$ I agree that the intersection of these classes is not something that I could write internally in ZFC. So, in this context, my question becomes the following. Am I wrong, in my day-to-day actual mathematical practice, to go ahead and take the intersection anyway? It would appear that by doing so I'm no longer working in ZFC. Am I now in an inconsistent system? $\endgroup$ – Pace Nielsen Jan 30 at 22:21
  • $\begingroup$ @PaceNielsen I think the message is: whenever you can actually right down, for a general $n$, what the class $A_n$ is, then your family of classes is defined uniformly, and you really look at sections of one class. So you can freely intersect them. $\endgroup$ – user57888 Jan 30 at 22:27
  • 2
    $\begingroup$ @PaceNielsen Oh, I see what you're asking. No, in this case you cannot take intersection in ZFC. If you could define an intersection, then you would run in inconsistency. $\endgroup$ – user57888 Jan 30 at 22:35
  • 4
    $\begingroup$ It’s important to realise that the problem in this example is nothing to do with taking the intersection of these classes. The problem is that to even define these classes for arbitrary n, you are talking about satisfaction of arbitrary formulas, which can’t be defined without stepping outside ZFC (cf. Tarski’s undefinability of truth). $\endgroup$ – Peter LeFanu Lumsdaine Jan 31 at 13:58
  • 2
    $\begingroup$ @PeterLeFanuLumsdaine Well that is true but it also partly answers the question. In ZFC having classes whose intersection does not exist means precisely this: I have a family of definable subsets of the universe, whose intersection is not definable. $\endgroup$ – user57888 Jan 31 at 15:32
7
$\begingroup$

If in defining the classes, you’ve worked within ZFC in the usual way, then you can always take their intersection/union; that’s just universal/existential quantification over the parameter indexing the family. Unions/intersections are only problematic if, at some step in your reasoning, you’ve already done something which steps outside ZFC, and reasons about it from the outside, and hence have ended up with a family of classes indexed by some “meta-level” number or similar.

So the core of this question isn’t really about intersections/unions; it’s about when, in normal mathematical reasoning, does one step outside ZFC and work on the meta-level? And the answer to that is essentially never, unless you’re explicitly talking about logic, satisfaction of formulas, and the like.

It’s hard to accidentally step outside the foundational system you’re working in, because the foundational system is designed explicitly to include all the standard techniques of mathematical reasoning. And if you’re stepping outside it deliberately, e.g. by talking about formulas and their satisfaction like in user57888’s answer, then if you’re being as rigorous about that as you are about the rest of your mathematics, you should understand the logical issues involved well enough to understand which constructions are happening internally and which are happening at the meta-level.

The only way I’ve ever seen people accidentally step outside ZFC — that is, do something which actually requires meta-level reasoning, without realising it — is in examples like the one in user57888’s answer. It’s easy to mistakenly think that you can, within ZFC, talk about whether formulae of the language of set theory are satisfied by actual objects (that is, objects of the ZFC you’re working in). This is a lapse of rigour — if you try to fill in the details of the definition of that satisfaction relation, you’ll find you need to step outside outside your normal foundation at some point, e.g. by wanting to quantify over “all classes”. It’s an easy error to make, but once you know about it, you can recognise any talk of “satisfaction of formulas” or “definability” as a red flag. (To see why this is impossible, look at Berry’s paradox and Tarski’s undefinability of truth theorem.)

If however you’re talking about some more restricted language, e.g. the first-order language of rings, then yes — as you have presumably seen, one can (within ZFC) define satisfaction of such formulae in an arbitrary ring. So that’s why you can take rings satisfying $S_n$ for all $n$, where $S_n$ is a sequence of sentences in the language of rings, as you suggested.

In summary: If you are working rigorously, like a mathematician in principle should, then you can never step outside ZFC accidentally. Even if you’re a little less than perfectly rigorous, it’s hard to step outside it by mistake once you know what mistakes to look out for.

$\endgroup$
  • 1
    $\begingroup$ Uh, proving full transfinite induction (for arbitrary formulae) for ZFC requires you (the prover) to step outside ZFC, since the claim itself is outside ZFC. Of course, any single instance of transfinite induction can be handled in ZFC itself, but the proof that every instance holds must be done outside. So I'm unsure it's not misleading to say that normal mathematical reasoning never steps outside. On the other hand, normal mathematics doesn't even use full transfinite induction, but almost always just induction on a specific well-ordering, in which case no stepping outside is needed. $\endgroup$ – user21820 Jan 31 at 15:40
  • 4
    $\begingroup$ @user21820: You can also reverse the quantifiers and stay within ZFC, and in fact omit Replacement for all practical purposes. In the sense that ZF proves transfinite induction for every well-ordered set. It is only when you want to apply this principle for the whole class of well-ordered sets you need Replacement, or to "step out" at all. And since "most normal mathematics" would only use well-ordered sets, I think one can rest easy well without the bounds of ZFC. $\endgroup$ – Asaf Karagila Jan 31 at 15:56
  • $\begingroup$ @AsafKaragila: Yes exactly hence my last sentence. And you probably meant ZC proves transfinite induction for every well-ordered set. =) $\endgroup$ – user21820 Jan 31 at 19:15
  • $\begingroup$ "Unions/intersections are only problematic if, at some step in your reasoning, you’ve already done something which steps outside ZFC, and reasons about it from the outside, and hence have ended up with a family of classes indexed by some “meta-level” number or similar." Yes, that's exactly what I wanted to do. Reason about collections of classes, indexed at the meta-level. I know my original post wasn't clear about that, sorry. $\endgroup$ – Pace Nielsen Jan 31 at 19:54
2
$\begingroup$

Your edit doesn't make sense to me. Just treat each family of classes as a parametrized formula over ZFC, where the last parameter is for the input and the other parameters are for parametrizing the family. Then it's obvious that the intersection of an $ω$-indexed family of classes is a class, because $ω$ is definable over ZFC. To be explicit, for convenience use set-notation for classes. Then if the $k$-th class in the family is $\{ x : φ(k,x) \}$ then the intersection is simply $\{ x : ∀k∈ω\ ( φ(k,x) ) \}$.

So there is absolutely no need to accept a "platonic" set-theoretic universe for it to be acceptable to manipulate classes in this manner, since "stepping outside" here is merely stepping outside to a syntactic meta-system that merely knows how to manipulate finite symbol strings. All you need in order to accept that permitting such intersection of classes does not go beyond ZFC is to accept the basic properties of finite strings, because there is a concrete translation from a proof that use classes in this manner to a plain ZFC proof that uses no classes.

Are you able to come up with a family that you cannot actually express as a parametrized formula over ZFC? If so, then yes you will have a problem. If not, then you're almost surely nowhere near the limit of ZFC, since you probably never use replacement, and even if you do it is really unlikely that you use unbounded replacement.

Even if you escape the reach of ZFC, it is still some way before you can escape MK. The difference is that MK classes are permitted to quantify over classes (but still only have sets for members). With such quantification we can no longer treat a class as a formula over ZFC, because we essentially have a full second-order world.

$\endgroup$
  • $\begingroup$ "Are you able to come up with a family that you cannot actually express as a parametrized formula over ZFC?" Yes, I can think of lots of examples. The simplest are of a form similar to that given by user57888, involving the set of Gödel numbers of true sentences. (Hence, my link to that other question.) $\endgroup$ – Pace Nielsen Jan 31 at 19:47
  • 1
    $\begingroup$ @PaceNielsen: As Peter LeFanu Lumsdaine said, it's irrelevant whether there 'exist' a conglomerate of classes whose intersection is not a class. What is relevant is that you don't need it in ordinary mathematics. I already showed you in my post that if your indexing set is definable, then you don't have any problem whatsoever. If you're talking about ZFC set theory, then I'd say that's not really ordinary mathematics. Obviously, if you want to have a model of ZFC to talk about truth of sentences over a model, then ZFC itself isn't enough... $\endgroup$ – user21820 Feb 1 at 9:38

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.