and the only new nullary predicate is [R.sup.y,y,y].
Let P and Q be fresh nullary predicate variables, and let [Psi]'(y, [x.sub.1], [x.sub.2]) (respectively, [Psi]"(y, [x.sub.1], [x.sub.2])) be obtained from [Psi](y, [x.sub.1], [x.sub.2]) by replacing E([x.sub.1], [x.sub.2]) with P (respectively, Q) and replacing E([x.sub.2], [x.sub.1]) with Q (respectively, P).
R(x) where R is any (monadic) predicate from R, and remove atoms R(c) where c [element of] {min, max, [y.sub.1], ..., [y.sub.k]} by using fresh nullary predicate variables.
(4) Observe that we assume MSO allows one to use nullary predicate variables (i.e., propositional variables) along with unary predicate variables.