A data set that is linearly separable is a precondition for algorithms like the perceptron to converge. It's well-known that we can project low-dimensional data to a higher dimension using kernel methods in order to make it linearly separable:
But is it always true that there is some transformation to convert every non-linearly separable data set into a linearly separable one? If not, what would be an example of such a data set where this is impossible?
For a given, finite data set it should always be possible—just let each data point have its own dimension! So, maybe a more interesting question would be for a stochastic model, generating a data set, such that for $n$ realizations, linear separability would require a dimension growing linearly with $n$?
Adding to @kjetil's answer:
There are simple datasets generated from stochastic processes where although you can trivially separate the in-sample data by giving each point its own dimension, you cannot create a separation that will work on out-of-sample data. For example, if the data is generated by two Gaussians, it is impossible to tell with certainty which one generated a given point.
The best you can do in this case is learn the generating distribution. Giving each point its own dimension to separate the in-sample data is actually overfitting.
There is also a case where you cannot even separate the in-sample data: if a given point is assigned different labels each time it appears. Technically, this could happen with the Gaussians, but the same point will almost surely not appear more than once if you are working with continuous data. However, this could happen if you use categorical data.
