Let ψ be a well-formed-formula (wff). Prove that

(ψ ≡ ⊥) ⇔ {x:ψ(x)}=Ø

that is, the formula ψ is a contradiction if and only if the set it describes has no members.

Note This question is not about understanding why this is true. The idea seems intuitively simple: If ψ is a contradiction, then it is false and no element x in set theory can possibly satisfy it. That is, ψ(x) is false for any x. So the set {x:ψ(x)} has no members, i.e. is equal to the empty set Ø. The other direction is also not hard to understand (if {x:ψ(x)}=Ø, then no set x satisfies ψ, so ψ(x) must be false for any x, and so it makes sense that ψ is a contradiction.)

My question is, how could one prove this formally (that is, formalize my argument not in terms of loose English sentences like I have provided, but in strict formal logic?) Please note my knowledge of logic and structure is very limited apart from introductory set theory and the ZFC axioms. But I am trying to formalize my basic understanding of logic similar to how ZFC formalized set theory for me. Thanks for your help!

  • 1
    From the way you are using ψ it seems to be a 1-place predicate, if so it can not be a contradiction, only a closed (e.g. fully quantified) formula can be that. So by "ψ is a contradiction" you probably mean ∃xψ(x) is a contradiction, i.e. ψ(x) is false for any value of x. Then formal proof will depend on the precise form of the definition of empty set, one definition is Ø:={x:x≠x}. But by assumption ψ(x) and x≠x have the same truth value on any x, so by the extensionality axiom {x:ψ(x)}=Ø. – Conifold Sep 1 '15 at 17:52

We have to remember that :

a ∈ {x:ψ(x)} ⇔ ψ(a)

(this is the definition of the "set-builder" symbol { _ : __ } ).

But {x:ψ(x)} = Ø, and thus :

for all a, a ∉ {x:ψ(x)} ⇔ for all a, ¬ψ(a).

  • Thanks Mauro. That's exactly what I was looking for. I had never seen the statement a∈{x:ψ(x)} ⇔ ψ(a), how come this isn't explicitly taken as an axiom in ZFC? Do you recommend any books that elaborate on this topic? – Mathemanic Sep 5 '15 at 19:53
  • @EthanAlvaree - see e.g Patrick Suppes, Axiomatic set theory (1960 - Dover reprint), page 34 : it is not an axiom of ZFC but a general definition of an "operator" (the set-builder) used in any set theory, – Mauro ALLEGRANZA Sep 5 '15 at 20:12

@EthanAlvaree I assume that you consider psi an unary predicate. And that your statement psi equivalent false means: For all x: psi(x) is false.

If that's what you mean, then nearly by definition:

psi equivalent false if and only if The set of all x, which satisfy psi, is empty.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.