# Proof of Statements involving Sets

1) $(P \vee Q) \Rightarrow R$
2) $(P \Rightarrow R) \wedge (Q \Rightarrow R)$

Explain why 1 and 2 are equivalent statements.

Attempt at solution:

I converted 1 and 2 to these statements which are equivalent:

1) $(P \cup Q) \subseteq R$

2) $(P \subseteq R) \cap (Q \subseteq R)$

This now seems logical but I dont know how to prove it? Any help is appreciated, thanks.

EDIT: I should have said truth tables are not necessary.

-
Have you tried forming truth tables for both, and checking if the statements are respectively true? – InterestedGuest Feb 7 '11 at 7:03
Are you attempting to prove that $(P\cup Q)\subseteq R$ and $(P\subseteq R)\cap(Q\subseteq R)$ are equivalent to each other? Or are you trying to prove that they are essentially the same as the first two statements you wrote? – yunone Feb 7 '11 at 7:11
I don't see how they relate! What does this notation mean? Is $(P\subseteq R)\cap(Q\subseteq R)$ a set or what? – milcak Feb 7 '11 at 7:20
I retagged the question, it has nothing to do with abstract algebra. – Asaf Karagila Feb 7 '11 at 13:57
There is a difference between "truth tables are not necessary" and "truth tables are not allowed." Yes, the problem may be solved without truth tables, but truth tables happen to provide an easy, straightforward way of checking the equivalence. So, while you may be able to solve it without using truth tables, a question is why you would want to do that. There may be good reasons for wanting to do that, but then you have to tells us what they are so that the answers can be suitably written. – Arturo Magidin Feb 7 '11 at 16:45

If you are unwilling to use truth tables then the following are equivalent $$(P \lor Q) \rightarrow R$$ $$\lnot(P \lor Q) \lor R$$ $$(\lnot P \land \lnot Q) \lor R$$ $$(\lnot P \lor R) \land (\lnot Q \lor R)$$ $$(P \rightarrow R) \land (Q \rightarrow R)$$

-
But whats the reason behind this? Like the second line, how did you come to know you had to do this? – 1337holiday Feb 7 '11 at 16:40
@1337holiday: the steps in Henry's proof were (probably) not motivated by any direct foreknowledge that that particular step was the way to go, but more likely just using the strategy of simplifying (or translating out) the '$\rightarrow$' (which is a useful strategy because the identities involving '$\land$' and '$\lor$' are easier to manipulate. – Mitch Feb 7 '11 at 17:56
Indeed. The question was how to translate the $\rightarrow$. An alternative approach, which would have introduced an extra step or two, might have been $\lnot ((P \lor Q) \land \lnot R).$ – Henry Feb 7 '11 at 18:55

You should either use truth tables, or you can argue by contrapositive.

To prove $(P \vee Q) \Rightarrow R$ then $(P \Rightarrow R) \wedge (Q \Rightarrow R)$, it is equivalent to show that when $(P \Rightarrow R) \wedge (Q \Rightarrow R)$ is false, then $(P \vee Q) \Rightarrow R$ is false as well.

When is $(P \Rightarrow R) \wedge (Q \Rightarrow R)$ false?

Then to prove the other direction reverse the formulas above, and again;

When is$(P \vee Q) \Rightarrow R$ false?

In both of these cases you can find sufficient conditions on $P,Q,R$, then establish the other statement.

-

It is usually the other way around: the basic properties of propositionsal calculus and logical connectives are established from first principles, and then the corresponding properties for sets and set-theoretic operations are concluded from them. So the properties of $\cap$ are deduced from the properties of $\wedge$; the properties of $\subseteq$ are deduced from the properties of $\Rightarrow$, etc.

You seem to be trying to go the other way. Unless this is how it was done in your class or book, chances are this would not be acceptable. Moreover, the second set-theoretic statement that you write doesn't really make a lot of sense as a set-theoretic statement: $$(P\subseteq R)\cap(Q\subseteq R)$$ is not a well-formed formula of set theory: $\cap$ is an operator between sets, but $\subseteq$ is a relation; $P\subseteq R$ is not a set, but a statement about sets, and $\cap$ cannot operate on statements about sets, only on sets.

-
I agree with this and with milcak above: $(P \subseteq R) \cap (Q \subseteq R)$ is nonsensical with the usual meanings of the symbols in mathematics. You get away with it (but maybe get confused by it) in $(P \Rightarrow R) \wedge (Q \Rightarrow R)$ because you confuse a binary connective with a binary relation. Or you confuse a proposition with its truth value. Or something. – GEdgar Aug 13 '11 at 17:34

Instead of working with truth-tables or Venndiagrams you could just reason with these statements:

Assume (1) holds. Then R is true, whenever P or Q is true. So assume P holds, then "P or Q" holds and therefore R holds. Likewise Q implies R. We have that (2) holds.

Now assume (2) holds. Let "P or Q" be true, one can assume without loss that P is true. But from (2) we know that P implies R, therefore R holds. The means that (1) holds.

Now (1) implies (2) and (2) implies (1), this means both are indeed equivalent.

This is certainly less 'formal' than what you might be expecting (although it can be made formal). But it is this kind of reasoning one will usually make in a mathematical proof and because of that it's useful to be able to think about it this way.

-