Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Similar question to this question (This question was actually the motivation for the other question, which - if I haven't got it wrong - generalizes this one): I have to prove a proposition of the following form: $$\forall T \subseteq V: \ P(T) \ \& \ Q(T)$$where $T,V$ are sets and $P,Q$ are some properties the set $T$ has to satisfies (which are irrelevant for this question). Now, if no $T$ satisfies $P(T)$, the proposition os obviously false. But if I would rewrite the set of which $T$ is a subset in the following manner $$ \forall T \in \left\{ F \in \mathcal{P}(V) \ | \ P(F) \right\}: \ Q(T)$$ it should be equivalent to the above proposition, because all I did was constrain the possibilities what a set $T$ can be such that my first property $P$ is already included (so if the above proposition would be true, this one, with the $T$'s that already satisfy $P$ would also have to be true and if the above is false, this one ought to be false as well since all I did was move the property $P$ around). But in this form the proposition is vacuously true. What have I done wrong ?

share|improve this question

2 Answers 2

up vote 4 down vote accepted

The reason the kind of "rewriting" you are doing is not in general valid is that the universal quantifier does not specify a domain; when we write something like "$\forall T\in X (U(T))$", we are actually abusing notation, because the $\forall$ only quantifies over all objects, not over some objects. The above formula is actually shorthand for "$\forall T( T\in X\rightarrow U(T))$" (that is, when we say "for all $T$ in $X$, $U$ holds", we are really saying "for all $T$, if $T$ is in $X$ then $U$ holds").

So you have gone wrong in assuming the two statements are equivalent. The second statement is actually of the form $\forall T\bigl((T\in \mathcal{P}(V)\land P(T))\rightarrow Q(T)\bigr)$ (that is, if $T$ is a subset of $V$ and satisfies $P$, then it satisfies $Q$). The first statement, on the other hand, is $\forall T\bigl(\mathcal{P}(V)\rightarrow (P(T)\land Q(T))\bigr)$.

The two statements are not equivalent: $(R\land T)\rightarrow S$ is equivalent to $R\rightarrow(T\rightarrow S)$; but $T\rightarrow S$ is not equivalent to $T\land S$, it's equivalent to $\neg T\lor S$.

So even though you think the two statements "say" the same thing, they really aren't because you are not writing them in full, you are writing abbreviations and those abbreviations are leading you astray.

share|improve this answer
    
I still have one minor question: When you said "$\forall$" quantified over all objects, did you meant "$\forall$" quantified over all sets ? –  temo Jul 12 '11 at 10:37
1  
@temo: In first order logic, all quantifications are over the universe of "objects". In the usual set theory, the "objects" are the sets. –  Arturo Magidin Jul 12 '11 at 14:09
    
@ Arturo Magidin: A last question: Do you now of a good book, that trains these kind of conversions of statements between first-order logic and the usual mathematical formulation / explains the first-order logic for the "working mathematician"? –  temo Jul 12 '11 at 15:50
    
@temo: There is nothing mysterious about first order logic when dealing with set theory, since in most set theories either all objects are sets, or else the universe contains both sets and ur-elements as objects. The problem here is not one of first order vs. non-first-order, it's an issue of understanding what a well-formed formula is. As was noted in your other question, you were mixing two different ways in which one can write down a sentence, which is what led to the "issue". If you stick to a single, well-formed way/syntax, you will not run into this apparent paradox. –  Arturo Magidin Jul 12 '11 at 18:54

The proposition $(\forall T \in \{F \in \mathcal P(V):P(F)\})Q(T)$ is not vacuously true: it says that if $P(T)$ is true, then so is $Q(T)$. It's equivalent to $(\forall T \subseteq V)[P(T) \to Q(T)]$, not to $(\forall T \subseteq V)[P(T) \land Q(T)]$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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