Set theory: Problem 2

Correct line of attack

To prove a subset inclusion like this, your proof should start by choosing an element z from the smaller set. It should end by showing that z is in the larger set. So for this particular example, the start and end of your proof should look something like

Suppose (p,q) is an element of \(A \cap B\).

Then (p,q) is an element of A, so \(3pq + 15p -5q -25 \ge 0\}\). But (p,q) is also an element of B, so \(q \ge 0\).

.....

So \(p \ge 0\), and therefore (p,q) is an element of C.

If your proof doesn't have this basic outline, go back and fix it before proceeding to the full solution. See below for what's wrong with some other tempting approaches.

Buggy line of attack 1

Here's a common wrong way to start this proof:

Suppose (p,q) is an element of \(A \cap B\).

Also suppose that (p,q) is an element of C.

Then \(3pq + 15p -5q -25 \ge 0\) and \(q \ge 0\) and \(p \ge 0\).

....

The difficulty is that you are assuming your conclusion, i.e. (p,q) is an element of C, is true from the start, rather than showing it follows from (p,q) being an element of \(A \cap B\). This line of reasoning can't show that the claim's conclusions FOLLOW FROM its hypotheses. It can only show that the claim's conclusions are CONSISTENT with its hypotheses, which is much weaker.

Buggy line of attack 2

Some people also try the following sort of approach:

\(A = \{(p,q) \in \mathbb{Z}^2 \ \mid 3pq + 15p -5q -25 \ge 0\}\) and \(B = \{(s,t) \in \mathbb{Z}^2 \ \mid t \ge 0\}\)

So \((A \cap B) = \{(p,q) \in \mathbb{Z}^2 \ \mid 3pq + 15p -5q -25 \ge 0 \text{ and } q \ge 0\}\).

.... [something where each line of the proof contains a set definition] ...

Or perhaps something like this

\(x \in \{(p,q) \in \mathbb{Z}^2 \ \mid 3pq + 15p -5q -25 \ge 0\}\) and \(x \in \{(s,t) \in \mathbb{Z}^2 \ \mid t \ge 0\}\)

So \(x \in \{(p,q) \in \mathbb{Z}^2 \ \mid 3pq + 15p -5q -25 \ge 0 \text{ and } q \ge 0\}\).

.... [a chain of statements about x being in some set] ...

Technically, these approaches can sometimes be made to work. However, the method is clumsy. So these proofs tend to become very long or have poorly justified steps. The recommended approach scales better to problems that are harder or more complex.