11–20 of 39 posts
I don’t think it’s fair to call {}-> injective just because no two inputs map to the same output. That’s vacuous.
It's true precisely because it's vacuous. If you quantify over the empty set, anything is true. In other words, the statement "for every x in {} it holds that " is always true.
Earlier quoted context omitted.
It's true precisely because it's vacuous. If you quantify over the empty set, anything is true. In other words, the statement "for every x in {} it holds that " is always true.
What can be confusing is that the statement "for every x in {}, it doesn’t hold that " is always true as well.
I don’t think it’s fair to call {}-> injective just because no two inputs map to the same output. That’s vacuous.
It's also the definitions the book supplies though (and the standard ones). Mathematics works over definitions. Everyone is free to do math over whatever definitions they want - but what is or isn't true follows from them. Lots of definitions and theorems exclude things like empty-set cases because they're weird, but that has to be explicit (otherwise someone will apply a theorem to the empty set and it will lead them to incorrect conclusions).
This one is not just in Dummit and Foote; it's just too easy to miss. I'd guess it appears in half the places that state this result. Fixed it in my own lecture notes a few months ago.
Help me out, I feel dumb. The first criterion for a function is stated as: > The first item in each pair comes from A. The counter-evidence for the proposition says: > Let A = {}, and B = {1}. Let f: A -> B = {} How does this f satisfy the first criterion, if A is uninhabited? It feels like this function can't be invoked. Am I thinking too much in terms of types here?
When there are no pairs, its certainly true that the first element of each pair comes from A. Just like if there are no living dinosaurs its true that all living dinosaurs speak English.
I was trying to come up with something to explain why I couldn't see it myself: every element of an empty set of integers is both even and odd. This feels counterintuitive to me, until I flip it around into a question: what is the set of all integers that are both even and odd?
I don’t think it’s fair to call {}-> injective just because no two inputs map to the same output. That’s vacuous.
Edit: Removed incorrect claim that |B| > |A| sufficed for the counter example. It's also the definitions the book supplies though (and the standard ones). Mathematics works over definitions. Everyone is free to do math over whatever definitions they want - but what is or isn't true follows from them. Lots of definitions and theorems exclude things like empty-set cases because they're weird, but that has to be explici…
The point is you either send an element of the codomain to its (unique by injectivity) preimage if it's in the image, or to an arbitrary element of A if it's not, and that's a left inverse. But then if B has an element, A needs one for you to pick your arbitrary target.
In a sense, your claim that the problem is a smaller domain than codomain does contribute though; if f is also surjective, then this case can't happen, so bijective iff invertible (the empty function is vacuously bijective and its own inverse).
I think a more elegant solution would be to soften the definition of a left inverse from a function `g: B -> A` to a function `g: f(A) -> A` where `f(A)` is the subset of elements in `B`, that actually get mapped to by `f` or in the words of the book's function definition, the set of "right" elements in `f`.
This solves the edge-case too, as `f(A) = f({}) = {}` and there exists (exactly one) function `g: {} -> {}`, which also trivially is a left inverse of `f`.
The real problem here was, that the statement `g: B -> A` needlessly required `g` to map back elements in B to A, that couldn't even be produced by `f` and should therefore be irrelevant for a left inverse.
Earlier quoted context omitted.
Edit: Removed incorrect claim that |B| > |A| sufficed for the counter example. It's also the definitions the book supplies though (and the standard ones). Mathematics works over definitions. Everyone is free to do math over whatever definitions they want - but what is or isn't true follows from them. Lots of definitions and theorems exclude things like empty-set cases because they're weird, but that has to be explici…
No, empty A is critical to the counterexample. In your example, g(x) = 1 is a left inverse. The point is you either send an element of the codomain to its (unique by injectivity) preimage if it's in the image, or to an arbitrary element of A if it's not, and that's a left inverse. But then if B has an element, A needs one for you to pick your arbitrary target. In a sense, your claim that the problem is a smaller doma…
While the proposed fix of requiring "either that A be inhabited or that B be uninhabited" works, it seems tacked on just to solve this particular edge-case. I think a more elegant solution would be to soften the definition of a left inverse from a function `g: B -> A` to a function `g: f(A) -> A` where `f(A)` is the subset of elements in `B`, that actually get mapped to by `f` or in the words of the book's function d…
You could of course interpret some of these basic theorems as saying "well I'd might as well take my function to be surjective since the 'meat' is that case." Much like you could just take all functions to be injective by modding out the kernel since that's the real "meat." And indeed one might interpret the first isomorphism theorem as saying exactly those two things: the isomorphism A/ker f = im f is "the real substance of the map f."