「数学のロジックと集合論」によると
完全性定理は選択公理よりもちょっと弱いらしいよ
こないだ立ち読みしてたら書いてあった