Satisfying explanation of Aristotle's Wheel Paradox.

The velocity of any point $P$ on a wheel can be written as the sum of two velocities: the velocity $\vec V$ of the center $O$ and the velocity $\vec\omega\times\vec{OP}$ of rotation about the center, where $\vec\omega$ is angular velocity (perpendicular to the plane of the wheel).

A wheel turns without sliding with respect to a given path if the velocity of the contact point between wheel and path vanishes. Let then $C$ and $C'$ be the contact points of the two wheels. We have $$ \vec v_C=\vec V+\vec\omega\times\vec{OC} \quad\text{and}\quad \vec v_{C'}=\vec V+\vec\omega\times\vec{OC'} $$ If $\vec v_C=0$ then $\vec V=-\vec\omega\times\vec{OC}$ and $$ \vec v_{C'}=-\vec\omega\times\vec{OC}+\vec\omega\times\vec{OC'} =\vec\omega\times(\vec{OC'}-\vec{OC})=\vec\omega\times(\vec{CC'}). $$ This cannot vanish, unless $C=C'$. So the assumption that both circles turn without sliding is false.

Starting with three assumptions

1. Both wheels stay concentric all the way,

2. Both make full circle without sliding,

3. At the end the distance is equal to the perimeter

you get a contradictory result (both wheels have same perimeter). The principle of proof by contradictions tells us that the conjunction of your assumptions is erroneous. Of course, as you pointed out, it makes no sense to reject assumption 3 because one can always go on rolling the wheel until it crosses the right distance.

Therefore, this "paradox" is actually a proof by contradiction that the two wheels cannot simultaneously stay concentric and roll without sliding. If they are to stay concentric all the way, at least one has to slide.

Fix two aligned points (green and red) on the circles. And consider another circle identical to the smaller circle that is attached on top of the bigger circle. Refer to the figure below:

Case 1: If we consider the big circle and top small circle, both rotate with equal velocity and the top small circle will make full round at the red point (at this point the big circle has not made full round yet). Note that for convenience we may consider that the small circle rotates opposite to the big circle.

Case 2: Now if we consider the big circle and the cocentric small circle, the small circle will slide to catch up with the pace of the big circle.

In conclusion, the smaller the smaller circle is, the greater it slides.