We provide a complete reconstruction of George Boolos' proof of Solovay's Completeness Theorem for arithmetic, and use the mechanics of this proof to reprove a result due to de Jongh, Jumelet and Montagna, concerning an upper bound on the minimal set of properties an arithmetic system must have in order to satisfy Solovay's Theorem.