The law that entropy always increases is a mathematical theorem, it is not a law of physics.
Postscript: A law of physics is an hypothesis about nature. It is considered valid until it is contradicted by an experiment. In that case the law is said to be falsified.
A law of physics can not be proved; but it can be disproved (by experiments).
The theory isof relativity is accepted because (and so long as) it has never been contradicted by an experiment.
The law that entropy always increases is different. It can actually be proved, as any mathematical theorem. It follows from the (mundane) observation that a system has the highest probability being in the state with the highest degree or freedom (or the most permutations).
I suppose it is considered a law of physics mainly for historical reasons...