Is the collection of all bijective string maps a set or a class?

Question

Let $\Sigma$ be a finite alphabet and $B = \{ f: \Sigma^* \to \Sigma^* \text{ bijectively} \}$, where a string map is not always a homomorphism. I am always having trouble deciding whether something is a set or a class. Need to study more category theory!

Answer 1

This isn't really a question about category theory; rather, it's about set theory. The following is the key fact you want:

If $A, B$ are sets, then the class of functions from $A$ to $B$ is a set.

(Note that one application of this is that $\Sigma^*$ is a set if $\Sigma$ is.)

Why is this true?

• First, show that $A\times B$ is a set.

• Now any map $f: A\rightarrow B$ is a subset of $A\times B$ (in set theory, we identify a function with its graph)

• So the class of all bijective maps $A\rightarrow B$ is contained in the powerset of $A\times B$ which is a set . . . by the Powerset axiom.

• Do you see how to show, therefore, that the class of all bijective maps $A\rightarrow B$ is a set? (HINT: Separation . . .)

You will probably get a lot out of reading through the axioms of ZFC in detail. Note that there are some variations: e.g. Separation/Subset/Specification, Replacement/Collection, Foundation/Regularity, and the axiom of Emptyset (which isn't necessary due to the behavior of first-order logic, but which is necessary if you want to consider empty structures and you want to ditch the axiom of Infinity).