# Predicate Calculus with Sets - Question about use of an axiom

Greets again StackExchange,

I am watching an online lecture, and I believe that my instructor has misused an axiom. Is my concern warranted? \begin{align*} \text{Given:}& {P \subseteq (Q \cap R)}\\ &{(Q \cup S) \subseteq T}\\ &{x \in (P \cup S) }\\ \text{Prove:}& {x, \in T} \end{align*}

I will reference a membership function, P(x), so onward then to the proof. Translating my givens into Predicate Calculus \begin{align*} \text{Given:}&\\ &1.\ {\forall x P(x) \rightarrow [Q(x)\wedge R(x)]}\\ &2.\ {\forall x [Q(x) \vee S(x)] \rightarrow T(x)}\\ &3.\ {\exists x [P(x) \vee S(x)] } \end{align*} So now comes my problem. She claims in the following line, that she just used straight simplification on the R.H.S. of line 1 to get Q(x) by itself as shown: $$\qquad\quad 4.\ {\forall x [Q(x) \wedge R(x)] \rightarrow Q(x)}$$

Wouldn't she need To have $P(x)$ first, and then use modus ponens to get the right side of that implication first, then use simplification? Is my understanding of simplification incorrect? Can you just simplify any conjoined statement at will?

Thank you. If you could also venture an answer at the answer to the proof I would appreciate it, because without this step she goes over, I am at a loss on how to solve.

-

"Wouldn't she need To have $P(x)$ first, and then use modus ponens to get the right side of that implication first, then use simplification?"

That depends on the exact set of rules and logical axioms you have to work with, which you haven't shown. There are multiple equivalent ways of formalizing first-order logic, and the details differ greatly at this level.

However, even if your formal definitions do require an argument along the lines you sketch, you shouldn't expect lecturers and textbooks to keep showing the arguments in such minute details for the entire course. Doing so would drown out any actual content of the course by completely mechanical, tedious and uninteresting details.

As soon as it can reasonably be expected of you to fill in the details of a formal proof (which it sounds like it can, because you seem to have a cogent idea of how the argument can be formalized in ways that would satisfy you better), you should be prepared to do so yourself.

-
Modus ponens is generally a universal rule, at least in my experience. She is basically doing this: x implies (y and z), then essentially snapping off the right side of the implication and using y and z to simplify to get y, and I am not sure why she is doing it here, regardless of whether the set of rules, axioms, formalizations, rules of inference are strict/lenient/moderate or whatever the case may be. All other things being equal, this is still a logical fallacy, and I don't see where she is inferring the antecedent. – treehau5 Jul 11 '12 at 18:48
@treehau5: To accuse something of being a "logical fallacy" requires that it is a mode of reasoning that can lead to falsehood. Here it is just an abbreviation of reasoning a that everybody seems to agree can be fleshed out to be formally impeccable. Calling that a "fallacy" is a wild overreaction to the harmless omission of some steps. – Henning Makholm Jul 11 '12 at 19:06
@treehau5: I see now that you seem to be objecting to where "$\forall x [Q(x) \wedge R(x)] \rightarrow Q(x)$" comes from, rather than what it is being used for. There I refer to Arturo's answer: $\forall x [Q(x) \wedge R(x)] \rightarrow Q(x)$ is always true no matter what $Q$ and $R$ are; it needs no further assumptions. It is one of the fundamental properties of $\wedge$ that $\phi\wedge\psi\to\phi$ is always true for any $\phi$ and $\psi$, and sticking a $\forall x$ in front of it does not make it any less true. (The other fundamental axiom is $\phi\to(\psi\to\phi\land\psi)$). – Henning Makholm Jul 11 '12 at 19:12

First, the validity:

Line 4 is an axiom. Then, line 1 has the form $$P\to(Q\land R)$$ and line 4 has the form $$(Q\land R)\to Q$$ and so, we can use the rule of inference that says: $$\begin{array}{l} A\to B\\ B\to C\\ \hline A\to C \end{array}$$ This is sometimes called "Hypothetical syllogism". It is a valid classical rule of inference, so it allows to use 1 and 4 to conclude $$\forall x P(x)\to Q(x).$$

As to solving the the problem itself. From $$\forall x (Q(x)\lor S(x))\to T(x)$$ we can deduce $$\forall x Q(x)\to T(x)$$ using first the rule that says $$\forall x Q(x)\to(Q(x)\lor S(x))$$ (Disjunction introduction) and then using the Hypothetical syllogism again.

So we have $$\forall x(P(x)\to Q(x))$$ obtained before, and $$\forall x(Q(x)\to T(x))$$ just obtained, and using the Hypothetical Syllogism again we conclude $$\forall x(P(x)\to T(x)).$$

Likewise, from $\forall x\; S(x)\to (Q(x)\lor S(x))$ and $\forall x\; (Q(x)\lor S(x))\to T(x)$ we conclude, using Hypothetical Syllogism, that $\forall x\; S(x)\to T(x)$. So we have both $$\forall x(P(x)\to T(x))\qquad\text{and}\qquad\forall x(S(x)\to T(x)).$$

The two together yield $$\forall x (P(x)\lor S(x))\to T(x).$$

-
Thank you for showing me a possible solution, and I even got as far as to your last two statements, however, you took her line 4 as being valid, and the first part of my question was questioning it's validity. I understand line 4 being an axiom, but the derivation of line 4 from line 1 is what I am questioning – treehau5 Jul 11 '12 at 18:55
@treehau5: An axiom is always a valid derivation of itself. If the person is justifying 4 as being a "consequence" of 1, then I agree that this is not correct; line 4, together with line 1, can be used to obtain $\forall x(P(x)\to Q(x))$ (i.e., to get "$Q(x)$ alone"). I interpreted it that way: that the person was saying that line 4 can be used to "simplify" line 1 to obtain $\forall x(P(x)\to Q(x))$ via hypothetical syllogism. – Arturo Magidin Jul 11 '12 at 18:57
Oh No I absolutely agree with your original reasoning. I agree line 4 and 1 with hypothetical syllogism can yield your result. On my homework, I went ahead and continued on assuming 4 was valid regardless because it was the only way I could get a solution (at least in my brain). Still, it was bothering me and I cannot get clarification from her on this since her PhD student-teacher administers the lectures in person. – treehau5 Jul 11 '12 at 19:01

If $x \in P$ then $x \in Q$. But then, if $x \in P \cup S$ we have $x \in Q \cup S \subseteq T$.

-