Correct me if I am wrong, but I think this conclusion would only be possible with a set-theoretic approach
You don't need full notion of set, only second-order logic, i.e. logic which allows to quantify over predicates, as opposed to first-order logic, where you can quantify only over elements of universe. The equivalent formula is:
$\forall m \forall b(b(m) \rightarrow \neg \exists s \forall x( x(m) \rightarrow (s(b,x) \leftrightarrow \neg s(x,x))))$
Personally I prefer first version, first we select some men and the shaving relation, and then we show that existence of a barber leads to contradiction. In the second version, we select first some men, then a barber, then we select shaving relation, then we get contradiction. The resolution "there is no such barber, assumptions are wrong" might be disappointing, but it's the simplest possible. Perhaps you can write it like this:
$\forall m \forall b \forall s(b(m) \rightarrow \neg \forall x( x(m) \rightarrow (s(b,x) \leftrightarrow \neg s(x,x))))$
For any $m$, $b$ and $s$ it is impossible to fulfill the condition imposed on the barber.
(A) The "Barber paradox" is not really a paradox, properly so called.
What we have here is a perfectly good proof by reductio that there can't exist someone in the village who shaves all and only those in the village who don't shave themselves. For suppose there is such a person, $B$. Then, by hypothesis, for all $y$, $B$ shaves $y$ if and only if $y$ doesn't shave $y$, where the variable $y$ runs over people in the village. So, in particular $B$ shaves $B$ if and only if $B$ doesn't shave $B$ -- contradiction!
Now, we have no antecedent reason to suppose there might be a barber who shaves all and only those who don't shave themselves. Hence it should be no particular surprise to learn that as a matter of simple logic that there can't be one.
And it is indeed a matter of simple logic. Generalizing, take any binary relation $R$ defined over the domain $U$ of widgets. Then this is a straightforward theorem of first-order logic: $$\neg\exists x\forall y(Rxy \leftrightarrow \neg Ryy)$$ with the quantifiers running over the domain $U$. Hence, whatever relation $R$ you take, there can't be a widget which is $R$-related to all and only those widgets which are not $R$-related to themselves. (Exercise, prove that formal wff in your favourite system of first-order logic!)
So far, there is nothing paradoxical going on. We can only speak really of a paradox or antinomy when a (seemingly) compelling proof clashes with other (seemingly) compelling ideas. And that isn't yet the case here.
(B) Suppose though -- to make the famous historical connection -- that we are thinking not about the shaving relation but about set-membership. Then we have this particular instance of our first-order theorem: $$\neg\exists x\forall y(x \in y \leftrightarrow y \notin y)$$ with the quantifier running over all sets. Hence there is no set containing all and only the normal sets (where a set is normal if and only if it doesn't contain itself.
But now note that unlike the Barber case, this result does clash with some assumptions that we might rather naturally have had about sets. For suppose we start off wedded to the ideas that (i) we can collect together all the $X$s into a set of $X$s, whatever $X$s might me -- so in particular, there is a super-collection $U$ that collects together all the sets (so $U$ is a set of all the sets), and (ii) for any given set $X$ and property $P$, there will be a subset of it containing just those members of $X$ with property $P$, and (iii) there is a perfectly good property of being a normal set, i.e. one which doesn't have itself as a member.
Then (i), (ii) and (iii) commit us to the existence of a set $Russell$, the subset of the super-collection $U$ which contains all and only the normal sets -- so $Russell$ is the set of all sets which are not members of themselves.
But as we've seen the $Russell$ set can't exist because of our simple logical theorem. Which shows that we can't hold (i), (ii) and (iii) together. And this traditionally is called a paradox -- though it is, strictly speaking, only paradoxical to the extent to which we previously might have been firmly wedded to (i), (ii) and (iii).
Best Answer
You're right, the given solution is in error for exactly the reasons you and Alex have observed. There are two valid solutions: either (a) Roberto shaves Arturo but not himself, and Arturo shaves no one, or (b) its negation: Arturo shaves the both of them, and Roberto shaves only himself.
The stated conditions are that for any inhabitant $X$, $AsX = XsR$ and $RsX = \lnot XsA$, where $PsQ$ denotes that $P$ shaves $Q$. Assuming Arturo and Roberto are the town's only inhabitants, there are four variables in the situation, namely $AsA$, $AsR$, $RsA$, and $RsR$. The given conditions then reduce to $$\begin{align} AsA &= AsR, \\ AsR &= RsR, \\ RsA &= \lnot AsA, \\ RsR &= \lnot RsA, \end{align}$$ or in other words, $$\begin{matrix}AsA & \!\!=\!\! & AsR \\ \lVert & & \lVert \\ \lnot RsA & \!\!=\!\! & RsR\end{matrix}$$ which clearly has the two solutions above.