We sample each other sample (01010101). Now say we have a signal - that is inside the original sample which has the pattern of (010-1). Decimation gives us 000 for this sub-signal. How to prove this is an example of aliasing? Or why else do we have lost information?
You really need to look at the problem in the frequency domain. There are too many bit patterns that will create an obvious dilemma with respect to decimation, but these will invariably be in violation of the rules of the sampling theorem—something obvious in looking at the frequency spectrum, but perhaps not obvious looking at a list of sample values.
For instance, the simple case of decimating the signal 10101010... by a factor of two can yield 000... or 111..., depending on where you start. But the original signal is at half the sample rate (for instance, a cosine at half the sample rate, amplitude 0.5, with a DC offset of 0.5). This does not satisfy the requirements of the sample rate being greater than twice the highest frequency component.
You'll find that other patterns that seem to produce results that make no sense will have similar problems with the initial condition. And while some cases, like the example I gave, are fairly easy to reason out, in general you won't be able to tell if the result of decimation is aliased without comparing it in some manner to the original.
That is, there is no way of known whether a series of samples is aliased without knowing more. For instance, you might know that the samples are a recording of flute solo—in that case, it might be very easy to answer whether it is aliased, even eithout the original signal to compare. Otherwise, if you can assume nothing, even bad sounding audio may be as intended.
The whole point of aliasing and the sampling theoreme is that you cannot (generally) know what an aliased signal was, as you cannot represent infinite bandwidth using finite infornation.
If you have extra knowledge of the input signal (eg that DC is not possible, then you might deduce what a string of 1-1-1 was originally.