Training set of a NN that classify Cat or Not Cat
It is possible to build that kind of a CNN. It is important to maintain uniform distribution for both the classes ('cat' and 'not cat'). That is you should have an almost equal number of samples for each of these classes to avoid biasing your model to the 'non-cat' class just because it has huge number of examples.
The number of non-cat examples can be potentially trillion because it's everything in the world apart from cat. You don't want to include those many examples in your training set just because trillions of examples are available. As I told, it's important to match the class distributions. You can choose any animal or object you want for the 'non-cat' class. You can even mix multiple classes for 'non-cat'.