Accessibility by reversible processes and the Second Law of Thermodynamics One common way of motivating the existence of Entropy as a state function is the following. Let us take the Clausius/Kelvin-Planck statement of the second law, from which we can deduce Clausius' theorem
$$\oint \frac{\delta Q}{T} \le 0,$$
where equality holds if and only if the cyclic process is reversible.
This of course means that the quantity
$$\int_C \frac{\delta Q}{T} $$
is path independent for reversible paths $C$, and so it defines a function of state which we call Entropy.
But this only seems to hold on the presumption that all states within our state space is mutually accessible through reversible processes, i.e. given any two states $A$ and $B$ in our state space, there exists some reversible process $A\rightarrow B$ and some reversible process $B\rightarrow A$. I don't see why this is necessarily true. Is this taken to be an additional (and apparently implicit) assumption? Or is this assumption provable? Or is it not actually needed to define entropy this way?
 A: 
Is this taken to be an additional (and apparently implicit) assumption? 

You are correct.
Take two arbitrary points $A,B$ on the $PV$ (or any other) plane, and draw an arbitrary curve connecting them: you have just defined a reversible transformation connecting $A$ and $B$.
This is because every point in the $PV$ (or any other) plane represents an equilibrium state, so every continuous set of points (such as the curve you drew) represents a reversible transformation.
The existence of reversible processes is one of the postulates of thermodynamics. Of course, a reversible process is an idealization, because it would require that the system is in equilibrium at every instant during the process, which is clearly absurd, because if the state variables are changing then clearly there is no equilibrium. This is why we talk of "quasi-static" transformations, in which an infinite number of infinitesimal steps is performed in such a way that the system is always in equilibrium.
Regarding your last question, it is actually possible to define entropy in another way in statistical mechanics. Between 1872 and 1875 Boltzmann formulated the equation 
$$S=k \log(\Omega)$$
where $k$ is a constant with dimensions of $J/K$ and $\Omega$ is the number of microstates corresponding to a the macrostate of the system.
This definition is in some way more fundamental than the thermodynamic one, as it gives the connection between the microscopic and the macroscopic description of Nature.
A: So, you want to prove that between any arbitrary two states of a system, it exists at least one reversible path. You can prove this if you accept continuity of properties of substances. I.e. for example, if we have an ideal gas in equilibrium at initial state $(P_i,T_i)$ and final state $(P_f,T_f)$; then certainly there are infinite equilibrium states between initial and final states.

In diagram above $(P_1,T_1)$ is an equilibrium state so that $P_1=P_i+\Delta P$ and $T_1=T_i+\Delta T$.
If, $(\Delta P,\Delta T)\to (0,0)$ then $(P_1,T_1)\to(P_i,T_i)$ So, we can reach from $(P_1,T_1)$ to $(P_2,T_2)$ through infinite number of equilibrium states so that for each two adjacent states $(\Delta P,\Delta T)\to(0,0)$ and if we do this quasi-static process by insulating the system; then that process will be an isentropic process and we know that an isentropic process is a reversible process.
