Is it possible to see an ad for Tinder on lock screen if Tinder is not installed? An ad for Tinder appeared on lock screen of BF's phone. Says he doesn't have the app but did he used to? I know I only get ads/pop up notifications from existing apps. 
I'm not tech savvy enough to know.
It's possible to get text messages from a service after deleting the app, but if the notification is branded like the app on the lock screen (with the logo), then the app is still on the device. It's not possible to get those kinds of notifications without the app being currently installed.

You can search for apps from the home screen by swiping down. That should allow you to search for the Tinder app by name, instead of browsing around for it.