1
$\begingroup$

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.

3 Answers 3

0

"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.

  • 0
    @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)$).2012-07-11
1

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).$

  • 0
    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 clari$f$ication from her on this since her PhD student-teacher administers the lectures in person.2012-07-11
0

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$.