Title: Logical view on fairness of a binary classification task. Abstract: Ethical, Interpretable/Explainable, and Responsible AI are an active area of research and important social initiative. 

We prove that, with no regards to data, fairness and trustworthiness are algorithmically undecidable for a basic machine learning task, the binary classification. Therefore, even the approach based on not only improving but fully solving the three usually assumed issues -- the insufficient quality of measurements, the complex consequences of (mis)measurements, and the limits of existing social theories -- is only heuristics. We show that, effectively, the fairness of a classifier is not even a (version of bias-variance) trade-off since it is a logical phenomenon. 
Namely, we reveal a language $L$ and an $L-$theory $T$ for binary classification task such that the very notion of loss is not expressible in the first-order logic formula in $L$. 