∀x: P(x) → Q(x) ⇒ {x | P(x)} ⊆ {x | Q(x)}
I really do think this is a stupid question, but I'm stuck, so pardon my logical/set-theoretic ignorance!
2
-
2The mix of first-order logic and set theory language is quite weird... but YES. The part {x | P(x)} ⊆ {x | Q(x)} is an abbreviation for ∀x: (x ∈ {x | P(x)}) → (x ∈ {x | Q(x)}). – Mauro ALLEGRANZA Sep 6 '17 at 15:01
-
2And that in turn is ∀x: (P(x) → Q(x)). – Mauro ALLEGRANZA Sep 6 '17 at 15:02
Add a comment
|
To prove this conditional, you need to prove {x | P(x)} ⊆ {x | Q(x)} under the assumption that ∀x: P(x) → Q(x). To prove a subset relationship S ⊆ T, you need to prove that for every s ∈ S also s ∈ T. For some v ∈ {x | P(x)} we have P(v), hence by assumption Q(v), hence v ∈ {x | Q(x)} which concludes the proof.
Note that the expression can be slightly hard to read, because you're using both → and ⇒. It is not immediately clear what the priority rules of these operators are and thus how far the ∀ reaches (i.e., if the ∀ is a subexpression for the ⇒ or vice versa). This also could make it difficult to see that the xs on the left of the ⇒ are different from the xs on the right side. The expression "∀x: P(x) → Q(x) ⇒ {y | P(y)} ⊆ {y | Q(y)}" is equivalent to yours. If you're having issues with that, it can be helpful to first draw a parse tree of the expression. If not, then never mind.
We say that properties define sets and some people like to use the same letter for the property and the set (property P defines set P = {x | P(x)} and vice versa set S defines property S(x) = x ∈ S). In that notation, your expression would be ∀x: P(x) → Q(x) ⇒ P ⊆ Q.
