A lot of the confusion, as I noted above, is that neither Linux nor GNU are correct names for the object being named here. Linux is an operating systems kernel; GNU is a project to create a computing environment constructed totally from "free" source code (with exactly what "free" means being defined by Richard Stallman and his associates).

The funny thing is, all these commands were originally written by somebody, and all of them have their own story. "ls" was in the original AT&T Unix, and versions (with greater or lesser compatability) have been written for pretty much every Unix and Unix-like OS. Same with "tail". On the other hand, "more" was first created for BSD Unix.

One of my favorites. "vi" was created at Berkely as an extension to "ex", which itself was built on a foundation of editors going back to AT&T's "ed". Many extensions, clones, and complete rewrites of vi have been made over the years, including the very nice "vim". "vim" has the rather unique history of originally being written for the Commodore Amiga, based upon the code for a similar editor created for the Atari ST. Only later did it make its way to Unix systems. (BTW, vim is included with every copy of Apple's OS X. )

Ultimately, the people creating a Linux distribution are free to choose whatever they want to add into that distribution. Some distributions strive to maximize the amount of GNU-based or GNU-compatible software (e.g. Debian), some strive to minimize it (e.g. Android), others are more agnostic (Ubuntu, Fedora, Arch, etc.). And, of course, not only can you find Linux without GNU, you can find GNU without Linux (lots of GNU code is available for BSD, for OSX, for Windows, etc.).

So yeah, the world is complicated out there.