Safe and Unsafe formulas

Properties of safe formulas:

• Any predicate function is safe
• An AND of a safe formula and any other formula whose free variables also appear in the safe formula is safe.
• The UNION of a safe formula with another whose free variables also appear in the first formula is safe.

The example shows that negation leads to unsafe formulas. To see that union can lead to unsafe formulas, consider

$$\{(x,y)\vert\mathrm{dog}(x)\vee \mathrm{rock}(y)\}$$

This is all pairs such that either:

1. is a dog from a finite list and is any object in the universe, or
2. is any object in the universe and is a rock from a finite list.