Empty Function

alexfloo

I'm currently reading Sterling Berberian's Foundations of Real Analysis, and the first chapter had an overview of foundational mathematics from axiomatic set theory to constructive proof of the real numbers. I was looking over this chapter, and I found this exercise in the functions section:

- If [itex]f\circ h=g\circ h[/itex] and h is surjective, then f=g.

He notes afterwards that this cancellation law would fail if we admit the empty function. However, the way I see it empty functions are as follows:

• Functions from the empty set to the empty set
• Functions from the empty set to a nonempty set
• NOT functions from a nonempty set to the empty set

The first two cases, regardless of the initial and final sets, always have the same graph: the empty set. Admitting these (as far as I can tell) don't change any of the properties of functions. The third case, however, even if we "admitted" empty functions still would not exist, because by the definition of a function, every member of the initial set must be mapped to exactly one member of the final set. There are no members of the final set, however. That is, if our definition of the function made no mention of empty function one way or another, and you told me that:

[itex]f:X\rightarrow Y[/itex]

I can logically conclude that:

[itex](Y=\{\})\Rightarrow (X=\{\})[/itex].

Essentially, although empty functions are degenerate, I don't see that the actually complicate the machinery. One of the three types is problematic, and that particular type is tautologically nonexistent.

Am I missing something, or did Berberian likely just choose not to with all this because it's rather trivial anyways?

spamiam

I think he's saying that, if we allow h to be the empty function, then we can have [itex] f \circ h = g \circ h [/itex] without having f=g. The empty function [itex]h : \emptyset \to \emptyset [/itex] would still be trivially surjective, but you could plug in any unequal functions f and g and get [itex] f \circ h = g \circ h [/itex] since both [itex] f \circ h [/itex] and [itex] g \circ h [/itex] will be empty as well.

So the empty function does cause a problem in this case.

alexfloo

I'm not sure that's true. There are other assumptions that I didn't copy that are necessary for that cancellation to hold. Namely:

[itex]f,g:X\rightarrow Y[/itex] and
[itex]h:W\rightarrow X[/itex]

These are necessary because the composition of two functions is only well-defined if the sets that the functions map are compatible.

Now the possibility that we're discussing is that [itex]X=\emptyset[/itex]. Presume this is true. Since h is a function, it must be the case that [itex]W=\emptyset[/itex]. If this were not the case, then h would not be a function. (Each element in W would not be mapped to an element of X).

Anyways, if we presume h is the unique function from the empty set onto itself, then in fact it must be the case that f=g, because they are both the unique function from the empty set to Y. The cancellation appears to hold either way.

I think the problem with your logic is that you presume that you actually can compose arbitrary functions f and g with h. This is not the case, though. You can only compose those functions if they are mapping from the empty set.

spamiam

This is the part that's not right: I was suggesting W is empty. The empty function can map into any set you like since it doesn't have to be surjective. So given [itex] f, g : X \to Y [/itex], I can let [itex]h : \emptyset \to X [/itex] be the empty function and then conclude [itex] f \circ h = g \circ h [/itex]. Since the image of h is empty, it is a subset of any possible domain for f and g. And in general the composition [itex] f \circ g [/itex] is only defined if the image of g is a subset of the domain of f.

alexfloo

I think you have it backwards. That is, presume [itex]h:W\rightarrow \emptyset[/itex]. By the definition of a function, for each [itex]w\in W[/itex], there must exist one (not necessarily unique. It's only unique if h is an injection) element [itex]x\in X[/itex] such that [itex]w\mapsto x[/itex]. However, there are no [itex]x \in X[/itex], so this can only be the case if there are no elements of W, either. Every possible "input" needs to be mapped to something, but there are no available destinations.

You're correct that the empty set can be mapped to any set (and that this mapping is trivial and unique), but I believe it is still the case that the empty set can only be mapped from itself.

spamiam

Oh right, sorry, I forgot that h had to be onto for cancellation... So then if h is an onto empty function, this forces X to be empty as well.

Well, you've convinced me now that the empty function doesn't pose a problem. I wonder what the author was getting at...

Hurkyl

You are correct -- whether or not you include the empty function is irrelevant. (I assume we are talking about functions between sets)


That said, it might be possible that the textbook is defining function concepts in a way that is subtly different than usual, and this variation simply gets things wrong when the empty set is involved.


But it is an unfortunate fact of life that some people tend to gratuitously exclude degenerate cases. This could very well be an instance of that.


If W is empty and h is surjective, then X is empty. If h is not surjective, then the hypothetical is irrelevant.


In the standard interpretation of the arithmetic of functions, the composition is defined if and only if the codomain of g is exactly equal to the domain of f. What you actually mean when you write [itex]f \circ g[/itex] is the composition [itex]f \circ i \circ g[/itex] where i is the inclusion function from the image of g to the domain of f.


(edit: I started writing this before the previous post appeared)

alexfloo

Thanks a lot, that makes sense. To be fair, excluding the degenerate case doesn't actually likely effect the exposition in the book, however it did end up being a stumbling block for me, if only because I thought about it too much.