I'm working through all of the problems in Set Theory and the Continuum Problem by Smullyan and Fitting. I am trying to prove exercise 3.2, page 83: "The axiom of substitition obviously implies that any class that can be put into a 1-1 correspondence with a set is a set. This ostensibly weaker condition, however, is actually equivalent to the axiom of substitution if the axiom of choice is assumed. Why is this?" From what I've read elsewhere, the axiom of choice is indeed necessary for this proof. However, I fail to see the error in what I have come up with.
Here's the relevant context from the book:
Page 82 defines the axiom of substitution as follows:
A8. For any function $F$ and any set $x$, $F''(x)$ is a set.
From page 79, some definitions and a proposition:
1) Definition of $F''(x)$: "For any class $A$ and function $F$, by $F''(A)$ is meant the class of all elements $F(x)$ where $x$ is in $A$."
2) Definition of $F\upharpoonright x$, where $F$ is a function and $x$ is a class: "the class of all ordered pairs $\langle a,F(a) \rangle$, where $a \in x$. Thus $F''(x)$ is simply the range of $F\upharpoonright x$."
3) Proposition 1.2: "For any set $x$, $F''(x)$ is a set if and only if $F\upharpoonright x$ is a set."
My (apparently erroneous) argument as to why the axiom of choice is not necessary to prove equivalence:
Assume the hypothesis of page 83, exercise 3.2: that any class that can be put in 1-1 correspondence with a set is a set. We will now derive the axiom of substitution.
Suppose that a function $F$ is defined upon a set $x$, whose range is a class $C$. By #2, $F\upharpoonright x$ is the class $\{ \langle a,F(a) \rangle \mid a \in x \}$. We wish to prove that $F\upharpoonright x$ is a set.
Define the function $g$, from $F\upharpoonright x$ onto $x$, as $g(\langle x,y \rangle) = x$. $g$ is clearly 1-1 and onto. I.e., $g$ is a 1-1 correspondence between the set $x$ and the class $F\upharpoonright x$. By hypothesis, then, $F\upharpoonright x$ is a set. Thus, by #3, $F''(x)$ is a set.
Therefore, under the hypothesis that any class that can be put into a 1-1 correspondence with a set is a set, we have proven that, for any arbitrary function $F$ and any set $x$, $F''(x)$ is a set -- this is the axiom of substitution.
Where did I go wrong?
Honestly, I'm not sure why the axiom of choice is even mentioned.
If $A$ is a class and $x$ is a set, and $F$ is a bijection between $A$ and $x$, then $F^{-1}$ is a bijection between $x$ and $A$, and therefore $A$ is a set. The point is that if $F$ is a bijection, it is a class function, and therefore $F^{-1}$ is also a class function.
Your proof is fine.
The axiom of choice is needed in order to argue things like "If $x$ is a set and $A$ is a proper class, then there is a surjection from $A$ onto $x$", or "... there is an injection from $x$ into $A$". For example, if $x$ is a set which cannot be well-ordered, then there is no surjection from the class of ordinals onto $x$, and no injection from $x$ into the class of ordinals either.
Typos are known to happen, and any sufficiently long documents will incorporate some mistakes. This is inevitable, even if undesirable.