2

In Tao's Analysis I, one of the ways that a function can be described is as follows:

$f: X \to Y$

$f: x \mapsto f(x) = \text{ specific rule }$ (e.g. $f(x) = 2x$)

That is to say, a function can be sufficiently described by providing a domain, codomain, and a specific mapping rule.

While working through book exercises, I am running into situations where I do not yet know if a desired codomain is actually a set, and therefore I am reluctant to define functions that would otherwise help me with proofs.

For example, let's say that I need to prove some set $Y$ exists (i.e. at the start, I do not know if $Y$ is a set), but I know that all "would-be" elements of $Y$, as individual objects, certainly exist. There are times where it would be very useful for me to describe functions that map elements of a known set $X$ to these "extant" would-be elements of $Y$. However, in order to use this function, I first need to know that $Y$ exists as a set; otherwise, I do not have a codomain and cannot define the function!

From what I understand about ZFC axioms, I don't think I can just take an infinite collection of objects I know exist and slap on two surrounding set brackets and claim, "Voilia! This is a set!" (I think one can carry this out on finite collections of objects, however, by using the union axiom and the singleton & pair set axioms).

At first, I was tempted into thinking that I could just take some sort of "superset" that definitely contains these would-be elements of $Y$. However, after reading up on Cantor's theorem and Russel's paradox, I realize this strategy won't work (e.g. if my superset was defined as "the set of all sets").

Any help would be greatly appreciated!

Andrés E. Caicedo
  • 79,201
S.C.
  • 4,984
  • What is this object? What is the topic of this book? It's unusual for a book outside category theory to ask you to deal with objects that are not sets. – user744868 Mar 10 '20 at 00:03
  • @user744868 I'm not sure I understand your question. Are you asking what the "would-be" objects of the not-yet-confirmed codomain set are? Sure, you could view them as sets if you wanted to. Or numbers. Tao regards numbers and sets as different entities, but for the purpose of this question, I don't think it matters. The book is about real-analysis but the subject matter of the first 5 chapters is effectively set theory. – S.C. Mar 10 '20 at 00:06
  • As you say, "I am running into situations where I do not yet know if a desired codomain is actually a set". Can you provide a concrete example of this? – user744868 Mar 10 '20 at 00:09
  • 2
    Isn't that pretty much a description of exactly what the replacement axiom of ZFC allows you to do (assuming the domain is a set)? – Daniel Schepler Mar 10 '20 at 00:10
  • @user744868 sure. I actually made a post here, which provides an example: https://math.stackexchange.com/questions/3575232/is-this-a-valid-way-of-using-the-axiom-of-replacement-a-question-arising-when-d. In this post, the set $\Psi = { X \times D: D \in \Phi}$ would be one such example. – S.C. Mar 10 '20 at 00:13
  • @DanielSchepler hmmm. Perhaps I have consistently misunderstood the replacement axiom of ZFC. I always interpreted the replacement axiom as essentially behaving like this: ${y: x \in X \land y=f(x)}$ ...i.e. I interpreted the replacement axiom as requiring the utilization of a function. – S.C. Mar 10 '20 at 00:15
  • 1
    "I interpreted the replacement axiom as requiring the utilization of a function" - that is not correct, because if that were the case, then the axiom of replacement would be useless, i.e., it wouldn't give you any new sets beyond what you could create with the other axioms. – Ted Mar 10 '20 at 02:39

1 Answers1

4

The replacement schema says that if $\phi(x,y)$ is a formula, $A$ is a set and we have $$\forall x\in A\;\exists! y \;\phi(x,y),$$ then $$\{y: \exists x\in A\; \phi(x,y)\}$$ is a set.

(Actually, it says a little more than that: $\phi$ is allowed to have set parameters.)

One snappy way of putting this is that replacement says if we have a definable class function whose domain is a set, then its range is also a set.

Replacement's strength comes from the fact that it can be applied to class functions and not merely to functions that are already sets. If we already know the function is a set then we don't need replacement to show its range is a set: $$ \operatorname{ran}(f) = \{y\in \cup\cup f: \exists x \;(x,y)\in f \}.$$

spaceisdarkgreen
  • 58,508
  • thank you for the response! If you're willing, could you elaborate a little more on what a "class function" is? I keep seeing the term used but am having a difficult time finding anything online about it. Does it go by a different name? – S.C. Mar 10 '20 at 13:38
  • 1
    @S.Cramer In ZFC (where we only deal with definable classes and do so in the metatheory, as opposed to a class theory like NBG or MK), a class function with domain $D$ is a formula $\phi(x,y)$ (possibly with parameters) such that we have $\forall x\in D;\exists! y; \phi(x,y).$ (Note that $D$ is, in general, a class, so “$\forall x\in D$” is an abbreviation for something involving its defining formula.) – spaceisdarkgreen Mar 10 '20 at 15:21
  • Ahh! And a "formula" $\phi(x,y)$ does not require a codomain, correct? – S.C. Mar 10 '20 at 15:24
  • 1
    @S.Cramer It’s just a formula... it doesn’t require anything. Any two variable formula like that defines a relation on $V$. If there is some class $D$ such that this relation restricted so that the first coordinate $x\in D$ has the function property, then we can view this formula as a function with domain $D$. Its range is the class I wrote down in the first paragraph my answer. – spaceisdarkgreen Mar 10 '20 at 15:38
  • I just recent learned what a "Set function" is...and now understand the last portion of your response (i.e. about $\text{ran}(f)$ )...however, what exactly does the double union symbol mean: $\cup\cup$. I assume it has something to do with referencing the second component of a given ordered pair that is contained in the set function $f$. Thanks! – S.C. Mar 11 '20 at 13:51
  • 1
    @S.Cramer it means apply the union operation twice. Since ordered pairs are (conventionally) of the form $(x,y)={{x},{x,y}},$ we need to take two unions to get from a set containing $(x,y)$ to one we know contains $x$ and $y$. – spaceisdarkgreen Mar 11 '20 at 13:58
  • awesome. cheers~ – S.C. Mar 11 '20 at 13:59