It helps to understand the concept of your "library" and "playlists" - I misunderstood at first.
[Note in iOS 9 and El Capitan the library is called "My Music" - it's quite confusing. For now I'll use the word library, as is used in iOS 10 and macOS Sierra.]
Your library is designed to contain all of
your music. This means all the music you buy from the iTunes Store, all the Apple Music tracks that you add to your library, and (by default at least) all the music you add to your playlists.
Because the library is for
your content, tracks from playlists made by other people or Apple Music curated playlists that you save are not automatically added to your library.
So in the conventional setup, everything in your own playlists
should be in your library. This is how Apple envisioned the library to work.
However, if you still want to have songs in your playlists but not have them added to your library, there is a setting for this:
- In iTunes: go to Preferences > General > Uncheck "Add songs to My Music/Library when adding to playlists"
- On iOS: go to Settings > Music > Uncheck "Add playlist songs"
But, if you remove songs from your library, they will automatically be removed from your playlists. That cannot be changed.