Il barbiere del villaggio

Il tuo esempio non è calzante, in quanto l'assioma b) non riguarda il problema in questione. Inoltre 2) non è conseguenza di a), in quanto tale affermazione non è decidibile, né di b) che afferma esattamente il contrario.
Ancora, non mi è chiaro come tu intenda definire l'operatore di somma in termini di una verità aritmetica definita a priori, ma che non fa parte degli assiomi. In termini tecnici, una struttura algebrica abbastanza potente da definire la struttura dei numeri naturali dotati delle operazioni di somma e prodotto, ovvero tale da rientrare nelle ipotesi di applicazione dei teoremi d'incompletezza di Gödel, dovrebbe essere almeno un anello.
Il sistema in questione, formato da N elementi unitari indefiniti con l'operatore "il barbiere rade", non è un anello e tantomeno un sistema del secondo ordine. Cionondimeno non è né completo né coerente: la sua contraddittorietà deriva dalla formulazione assiomatica stessa, in quanto l'operatore non gode della proprietà riflessiva e il barbiere è un elemento dell'insieme.