19
$\begingroup$

In my paper On the optimal error bound for the first step in the method of cyclic alternating projections, I defined functions $f_n:[0,1]\to\mathbb{R}$, $n\geqslant 2$, by $$ f_n(c)=\sup\{\|P_n\dotsm P_2 P_1-P_0\|\,|\,c_F(H_1,\dotsc,H_n)\leqslant c\}, $$ where

(1) the supremum is taken over all complex Hilbert spaces $H$ and systems of closed subspaces $H_1,\dotsc,H_n$ of $H$ such that the Friedrichs number $c_F(H_1,\dotsc,H_n)$ is less than or equal to $c$. The Friedrichs number is a quantitative characteristics of a system of closed subspaces, $c$ is a given number from $[0,1]$.

(2) $P_i$ is the orthogonal projection onto $H_i$, $i=1,2,\dotsc,n$ and $P_0$ is the orthogonal projection onto the subspace $H_1\cap H_2\cap\dotsb\cap H_n$.

Now I have some doubts in the validity of this definition. Namely, I know that all sets do not constitute a set and if I understand things right, all Hilbert spaces do not constitute a set (and even all one dimensional Hilbert spaces do not constitute a set). So, can I take the supremum?

Please help me; I will be very grateful for any comments, remarks, and answers.

In response to Mike Miller's comment: Unfortunately, I also know almost nothing about set theory. Yes, I understand that in fact I take the supremum of a "set" of real numbers, namely, of the "set" $A=A_n(c)$ which consists of all $a\in\mathbb{R}$ for which there exist a complex Hilbert space $H$ and a system of closed subspaces $H_1,\dotsc,H_n$ of $H$ such that $c_F(H_1,\dotsc,H_n)\leqslant c$ and $\|P_n\dotsm P_2 P_1-P_0\|=a$. But I do not understand why the "set" $A$ is a set.

$\endgroup$
9
  • 16
    $\begingroup$ I do not know anything about the context and almost nothing about set theory. But you are not taking the supremum over a `set' of Hilbert spaces and collections of subspaces. Rather, from all of those Hilbert spaces, you produce a set of real numbers, and you take the supremum of that set. No issue there: subclasses of sets are sets. $\endgroup$
    – mme
    Nov 5, 2020 at 21:40
  • $\begingroup$ Dear Mike Miller, thank you for your comment. I edited the question. $\endgroup$ Nov 5, 2020 at 22:37
  • 1
    $\begingroup$ @LSpice Yes, the "set" $A$ consists only of real numbers and $\mathbb{R}$ is a set. But I do not understand why these facts imply that $A$ is a set. $\endgroup$ Nov 5, 2020 at 23:36
  • 3
    $\begingroup$ An example from operator algebras rather than operator theory: given a star-algebra $A_0$, one sometimes seeks to define a "maximal" Cstar-envelope of $A_0$ by defining a seminorm $\Vert a\Vert = \sup\{ \Vert \pi(a) \Vert\}$ where the supremum is taken over all star-representations of $A_0$ on all possible Hilbert spaces. Once again, one is referring to a proper class of objects, but one is only looking at a set of real numbers, and hence the definition above can be used safely $\endgroup$
    – Yemon Choi
    Nov 5, 2020 at 23:58
  • 4
    $\begingroup$ @IvanFeshchenko Because Separation says exactly that any time you can define (via a first-order formula) a collection of elements of a set, that collection is itself a set. We have a definition of $A$ (never mind how complex it is) and a set within which $A$ lives (namely, $\mathbb{R}$), so we get that $A$ is a set. $\endgroup$ Nov 6, 2020 at 1:17

2 Answers 2

32
$\begingroup$

It is true that we cannot use an arbitrary property$^1$ $P$ to define a set, in the sense that the collection of all things with property $P$ need not be a set. However, the axiom (scheme) of separation says that we can use an arbitrary property to define a subset: whenever $X$ is a set, the collection $\{x\in X: P(x)\}$ is also a set.

So just take $X=\mathbb{R}$ and $P(x)$ = "There is a Hilbert space such that …". Per Separation, we get that your collection of reals $A$ is in fact a set. And we may now take its supremum.

Note that this illustrates an important point about how $\mathsf{ZFC}$ (and its variants) get around Russell's paradox:

It's size,$^{2}$ not complexity of definition, which controls whether or not a collection is a set or a proper class in $\mathsf{ZFC}$.$^{3}$

Part of the success of $\mathsf{ZFC}$ is due to the ease with which we can in fact verify that something is a set. The only time you'll run into trouble is when you want to form a set which isn't a priori part of some bigger thing you already know is a set; here we may have to think a bit (although the axiom (scheme) of replacement similarly makes things usually very easy, once it's mastered).


EDIT: Per the comments below, let me sketch how to define "complete metric space" in the language of set theory. As you'll see, even the sketch is quite lengthy; if there's a particular point you'd like further information on, I suggest asking a separate question at MSE.

Here's the sequence of definitions we need to whip up:

  1. We need to talk about ordered pairs, functions, and Cartesian products.

  2. We need to build $\mathbb{N}$, so that we can build $\mathbb{Q}_{\ge 0}$, so that we can build $\mathbb{R}_{\ge 0}$; along the way we'll need the notions of equivalence relation and equivalence class, of course.

  3. While the previous two points will be enough to define metric spaces ("An ordered pair $(X,\delta)$ where $X$ is a set and $\delta:X^2\rightarrow\mathbb{R}$ such that [stuff]"), to define complete metric spaces we'll also need the notions of infinite sequence and equivalence relation/class.

The first bulletpoint is standard set-theoretic fare which you'll see treated in the beginning of any text on set theory, so I'll skip it; if you're interested, though, you can start with the wiki page on ordered pairs.

The third is really the first in disguise: an infinite sequence is just a function with domain $\mathbb{N}$.

So all the "meat" is in bulletpoint 2. We proceed as follows:

  • First, we'll use the von Neumann approach to $\mathbb{N}$: an ordinal is a hereditarily transitive set, ordinals are ordered by $\in$, and the finite ordinals are the ordinals which do not contain any (nonempty) limit ordinal. We then identify $\mathbb{N}$ with the finite ordinals — more jargonily, $\mathbb{N}=\omega$. We define addition and multiplication of ordinals via transfinite recursion as usual.

  • Next, we consider the equivalence relation $\sim$ on $\omega\times(\omega\setminus\{0\})$ as follows: $$\langle a,b\rangle\sim\langle c,d\rangle \iff ad=bc,$$ and we let $\mathbb{Q}_{\ge0}$ be the set of $\sim$-classes. We lift the ordering on $\omega$ to $\mathbb{Q}_{\ge 0}$ in the obvious way.

  • Now we're ready to define $\mathbb{R}_{\ge 0}$, via Dedekind cuts: an element of $\mathbb{R}_{\ge 0}$ is a nonempty, downwards-closed, bounded-above subset of $\mathbb{Q}_{\ge0}$. The ordering on $\mathbb{R}_{\ge 0}$ is just $\subseteq$.

With all this in hand, the naive definitions of metric space, Cauchy sequence, and complete metric space translate into the language of set theory directly (if tediously). The point is that all of this is first-order in set theory, with axioms like Powerset (which, despite what they mean intuitively, are indeed first-order) doing the heavy lifting needed to show that the objects we want actually exist at all. (For a bit more about the nuance of "first-order in set theory," see this recent answer of mine.)


$^1$Really I mean "first-order formula," but I don't want to get too much into the details.

$^{2}$Specifically, in a precise sense we have: a class is a proper class iff it surjects onto the class of ordinals. This is not the same as the principle of limitation of size, but it's of similar flavor.

$^3$I should observe that this isn't the only possible response to the need to distinguish between sets and proper classes: there are other set theories (e.g. $\mathsf{NF}$, $\mathsf{GPK^+_\infty}$, ...) which take the other approach. However, these theories make it harder to check whether something is in fact a set.

$\endgroup$
23
  • 5
    $\begingroup$ @IvanFeshchenko No, that's not a problem: the axiom of separation says that any formula can be used to define a subset of a given set. "Use a proper class in its definition" makes things sound more mysterious than they are: what it really does is involve quantification over the whole universe, but that's just something "$\forall$" and "$\exists$" do by default. $\endgroup$ Nov 6, 2020 at 1:12
  • 4
    $\begingroup$ @Arno Why? $\mathbb{R}$'s already in the picture: the thing $A$ we want is explicitly a collection of reals, hence a subcollection of a thing we already know is a set. (Besides, given the logical strength of Replacement I think it's better to use Separation when it will suffice.) $\endgroup$ Nov 6, 2020 at 1:14
  • 2
    $\begingroup$ @IvanFeshchenko Your (1) is correct, but with an important caveat - $P$ needs to be a first-order formula of set theory. The domain of discourse in question is the whole universe, so - even though our logic is first-order! - we can quantify over sets, sets-of-sets, etc. (Perhaps it may help to think of this as using first-order language to describe a high-order context.) So what we need to do is show how to "code" all the relevant objects and properties - sequences, vector spaces, norms, topologies, closedness, etc. - by sets in an appropriate way. This is tedious, but not hard. (cont'd) $\endgroup$ Nov 7, 2020 at 0:06
  • 2
    $\begingroup$ Basically, we take the usual natural-language definition and unpack it carefully. A heavy mover here is the set-theoretic implementation of ordered pairs (and so of arbitrary functions and arbitrary-indexed Cartesian products). This lets us define for example an abelian group as a pair $\langle G,*\rangle$ where $G$ is a nonempty set, $*$ is a set of ordered triples of elements of $G$ (thought of as the graph of the group operation), and certain properties are satisfied. "Is a (set coding a) group" is then first-order expressible in set theory. $\endgroup$ Nov 7, 2020 at 0:10
  • 2
    $\begingroup$ There are also a couple "starting tricks," like the von Neumann implementation of the natural numbers (and von Neumann ordinals in general). Ultimately with some practice anything you can describe in natural language is first-order definable in the universe of sets. Note that the context - "in the universe of sets" - is absolutely crucial here. First-order logic is only as strong as its ambient context: there is a first-order formula $\varphi$ in the language of set theory which, in the universe of sets, names exactly the (sets coding) finite groups, but by the compactness theorem (cont'd) $\endgroup$ Nov 7, 2020 at 0:13
6
$\begingroup$

The purpose of this answer is to recall that the classical proof of the existence of suprema of bounded families of reals (as found in any analysis textbook) continues to work without any modifications whatsoever for proper classes. (In particular, we do not assume that the existence of suprema of bounded nonempty subsets of reals has been proved yet.)

In fact, the proof works in the Zermelo set theory, without the axiom of replacement and the axiom of choice.

Theorem. Suppose $C$ is a nonempty class (possibly proper) and $g\colon C\to \mathbf R$ is a map bounded from above. Then $\sup_{c\in C} g(c)$ exists.

Proof. Denote by $U$ the set of upper bounds for $g$, i.e., $U=\{u\in\mathbf R\mid \forall c\in C\colon g(c)\le u\}$, which exists by the axiom of separation.

Since $\sup_{c\in C} g(c)$ is by definition the smallest upper bound for $g$, we have to show that $U$ has the smallest element. By assumption, $U$ is nonempty. Since $C$ is nonempty, the set $U$ is bounded from below, namely, it is bounded from below by $g(c)$ for any $c\in C$. Thus, $U$ is a nonempty upward-closed subset of reals bounded from below, i.e., an upper Dedekind cut, so $\inf U$ exists. It remains to show that $\inf U \in U$.

Indeed, $\inf U \in U$ is equivalent to $$\forall c\in C\colon g(c) \le\inf U,$$ which in its turn (by definition of $\inf$) is equivalent to $$\forall c\in C \forall u\in U\colon g(c) \le u,$$ equivalently, $$\forall u\in U \forall c\in C\colon g(c) \le u,$$ i.e., $$\forall u\in U\colon u\in U,$$ which is tautologically true. Thus, $\inf U \in U$, so $\inf U$ is the smallest upper bound for $g$, which, therefore, exists.

$\endgroup$
4
  • 1
    $\begingroup$ More directly, use separation to show that the image of $g$, $I=\{u\in\mathbb R:\exists c\in C\,g(c)=u\}$, is a set, and then $\sup_{c\in C}g(c)=\sup I$. $\endgroup$ Apr 12, 2021 at 6:00
  • $\begingroup$ @EmilJeřábek: More directly than what? How do you show that sup I exists in your proof? Note that inf U exists because U is an upper Dedekind cut. $\endgroup$ Apr 12, 2021 at 15:09
  • 3
    $\begingroup$ sup $I$ exists because $I$ is a nonempty, bounded-above subset of the reals. The point being that you don't have to reexamine the proof to check whether it works for class-sized families; instead you can immediately reduce to the standard fact (and not care about how it was proved). $\endgroup$ Apr 12, 2021 at 17:57
  • 2
    $\begingroup$ @ReidBarton: This is already indicated in the other answer, so I see no point in duplicating it here. The point of this answer is that the classical proof works just fine for proper classes, without any modifications. $\endgroup$ Apr 12, 2021 at 18:22

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.