I'm not sure why the existence of a binary should depend on the environment variables.
However, this indeed is surprising. Yet, if you call env instead of sh -c set, you will get an empty output. This suggests to me that it's the shell that still somehow defines or bakes in defaults for some environment variables.