3
$\begingroup$

I am really new to proofs, and I don't know why I am having some troubles understanding this and how do they get to the solution to this question:

For all sets $A$ and $B$, if $A \subseteq B$ then $(A \cap C) \subseteq (B \cap C)$

My teacher's explanation: \begin{align} \forall x \in A \cap C &\Longleftrightarrow x \in A \wedge x \in C & \text{By definition of intersection} \\ &\Longleftrightarrow x \in B \wedge x \in C & \text{Since } A \subseteq B\\ &\Longleftrightarrow x \in (B \cap C) & \text{As intersection mandates} \end{align}

$\therefore A \cap C \subseteq B \cap C$

I asked him more explanation about it, and the only thing he told me it's because $A$ and $B$ are subsets of $C$ thus the whole thing is possible. I kind of understood that, and that $A$ is a subset of $B$. But then standing to what my book says, you have to be clear in math to proof, and I would not say it like the above, because I seriously don't understand it.

I guess my question is, first of all, how comes the above is valid if $A \subseteq B$ then $(A \cap C) \subseteq (B \cap C)$. Second, can I represent it like this if I wanted to:

$$(A \Longrightarrow B) \Longrightarrow ((A \wedge C) \Longrightarrow (B \wedge C))$$

and third how would I prove it?

Thank you so much in advance, sorry for the silly question.

$\endgroup$
  • 3
    $\begingroup$ The proof as posted is wrong. The second $\iff$ should be an $\implies$ only. Also, "$A$ and $B$ are subsets of $C$" is not needed nor used here. $\endgroup$ – Hagen von Eitzen Jan 14 '17 at 23:22
  • $\begingroup$ I am just showing how I have it in my notes from my class, the instructor gave us this exactly how it's shown. So instead of $\Longleftrightarrow$ it should be if then ($\Longrightarrow$)? And what you mean that "A and B are subsets of C" is not used here? The notation? $\endgroup$ – The Law Jan 14 '17 at 23:30
3
$\begingroup$

I'd just like to remark that the arrows in your teachers explanation should not all be double arrows. They should be $\Rightarrow$ instead. The double arrow implies that containment would go both ways but this is only true if the sets are equal.

Your teacher has asked you to prove: For all sets A and B, if $A ⊆ B$ then $(A \cap C) ⊆ (B \cap C)$.

I suppose you could write it using your proposed notation:

Let $P$ be the sentence "x belongs to $A$, $Q$ be the sentence "x belongs to $B$," $R$ be the sentence "x belongs to $C$ and let $A ⊆ B$. Then this can be written:

$P \wedge R \Rightarrow Q \wedge R$

This conditional statement fails if $P \wedge R$ is true and $Q \wedge R$ is false. $P \wedge R$ is true if both $P$ and $R$ are true. Consider, can $Q \wedge R$ be false? Only if either $Q$ or $R$ is false. However we have assumed $R$ to be true and we know $Q$ is true because we have assumed $P$ to be true and $P \Rightarrow Q$.

Therefore, the statement is always true.

$\endgroup$
  • $\begingroup$ I don't think this works, even though the explaination is much more appealing than the other ones because it uses truth table. I have a problem with this statement "onsider, can Q∧R Q∧R be false? Only if both Q and R are false. However we have assumed R to be true" That's not true, p $\wedge$ q truth table is T T -> T, T F -> F, F T -> F, F F -> F, so if either or both are F then it will be false. The other part, where did we assumed that x $\in$ C is true? Where did we show that? $\endgroup$ – The Law Jan 15 '17 at 1:30
  • $\begingroup$ You are correct. I hate making these kinds of errors... Thank you for catching that. I will correct my answer now. Q and R are false if either Q or R (or both) is false. R is true (x is in C) because at the beginning I supposed P and R to be true. If either P or R is false then the conditional statement is automatically true. $\endgroup$ – CantorStudent Jan 15 '17 at 2:05
  • $\begingroup$ I think I ll post an answer to my question similar to yours, let me know if it makes sense. $\endgroup$ – The Law Jan 15 '17 at 2:15
  • $\begingroup$ Tell me what you think! $\endgroup$ – The Law Jan 15 '17 at 2:38
  • $\begingroup$ I like your approach! I have just a few minor things. Someone already mentioned it is not allowed to say "p=x..." so I will comment on this sentence: "This statement will be false, if and only if q∧r is false." This is only partially true. Remember that a conditional statement is false if and only if its premise is true and the conclusion false. If both the premise and conclusion of a conditional statement are false, then that actually makes the statement true. Anyways, you have provided a well thought-out argument. good job =] $\endgroup$ – CantorStudent Jan 15 '17 at 3:42
4
$\begingroup$

Several things play a role here:

  1. The definition of intersection is extensional, i.e., we define, as always(?) for sets, the intersection by the elements it contains. The intersection $A\cap B$ is thus characterized by the defining property $$ \forall x\colon (x\in A\cap B\leftrightarrow (x\in A\land x\in B))$$ This definition is used (with different sets) for the first and the third $\iff$ in your proof.
  2. The definition of "subset" is also extensional, namely $$ A\subseteq B:\leftrightarrow \forall x\colon(x\in A\to x\in B)$$
  3. for any statements $\phi,\psi,\chi$, the implicatoin $\phi\to\psi$ entails that $(\phi\land \chi)\to(\psi\land \chi)$. Here's a proof (using the rules of natural deduction): We are given that $\phi\to \psi$. Assume $\phi\land \chi$. Then $\phi$. As well as $\chi$. By modus ponens from $\phi\to \psi$ and $\phi$, we get $\psi$. So now $\psi$ and $\chi$. Therefore $\psi\land\chi$. We derived $\psi\land\chi$ on the aassumption $\phi\land\chi$; therefore $(\phi\land\chi)\to(\psi\land\chi)$. In summary, $$\phi\to \psi\vdash (\phi\land\chi)\to(\psi\land\chi).$$

Now we have all formal steps that are required to get from $$ x\in A\land x\in C$$ to $$ x\in B\land x\in C,$$ namely we have $x\in A\to x\in B$ because we are given that $A\subseteq B$, and then we imply the result from 3 above. Note that this is in fact only an $\implies$, not an $\iff$!


For what it's worth, the given proof has also some formal problems with treating the $\forall x$ (it disappears silently in the middle). A formally stricter (while still preferably written mostly in natural language) proof might read like this:

Claim. Let $A,B,C$ be sets. If $A\subseteq B$, then $A\cap C\subseteq B\cap C$.

Proof. Assume $A\subseteq B$. By definition, this means $$\tag1 \forall x\colon (x\in A\to x\in B)$.$$

Let $x$ be arbitrary. Assume $$\tag2x\in A\cap C.$$ By the definition of $\cap $, this is equivalent to $$\tag3c\in A\land x\in C.$$ Hence we have $x\in A$ and $x\in C$. If we specialize $(1)$ to $x$, we obtain $x\in A\to x\in B$. Together with $x\in A$, this implies $x\in B$. From this an d$x\in C$, we conclude $x\in B\land x\in C$. By the definitin of $\cap$, the latter is equivalent to $x\in B\cap C$. As we showed $x\in B\cap C$ from $x\in A\cap C$, we conclude that $x\in A\cap C\to x\in B\cap C$, and as $x$ was arbitrary, we have $$ \forall x\colon(x\in A\cap C\to x\in B\cap C).$$ By the definition of $\subseteq$, this simply states that $$ A\cap C\subseteq B\cap C,$$ as was to be shown. $\square$

$\endgroup$
  • $\begingroup$ Ah, fantastic, now this make much more sense, he never showed us to prove that we, just a bunch of steps that transforms it into predicate logic but says nothing on what is going on, this is much more clear, thank you very much and again sorry for the nooby question. $\endgroup$ – The Law Jan 15 '17 at 0:04
  • $\begingroup$ @IamtheLawTheLaw Then again, when really dealing with the itty-nitty details of predicate logic step by step, one might lose the overview over what is actually going on in the proof. Introduction to math (which means introduction into proving theorems) should dig around for a while in those logical details, but then proceed to work in larger steps. The problem (also depending on the course subject, audience, presentation, etc.) then however is that the bigger steps made should be small enough that everybody is confident that the details could be filled in easily, as opposed to handwaving. $\endgroup$ – Hagen von Eitzen Jan 15 '17 at 9:53
4
$\begingroup$

The given problem takes the following form:

For all sets $A, B$, and $C,\quad$ $A\subseteq B\implies A\cap C\subseteq B\cap C$.

Proof.(We call this Direct Proof)

Let $A, B,$ and $C$ be sets and assume that $A\subseteq B$. We want to show that $A\cap C\subseteq B\cap C$. Let $x\in A\cap C$. Then by using the definition of intersection, we get $x\in A$ and $x\in C$. Since $x\in A$ and $A\subseteq B$, it follows from the definition of subset that $x\in B$. So, were able to show that $x\in B$ and $x\in C$. Again, by using the definition of intersection, we conclude that $x\in B\cap C$. Because $x$ was arbitrarily chosen, we conclude that $A\cap C\subseteq B\cap C$.

$\endgroup$
2
$\begingroup$

Ok let me see if I can answer my own question now (I will not give my self credit for it, but if you can disprove it by all means).

If $A \subseteq B$ then ($A \cap C) \subseteq (B \cap C)$.

Assume $A \subseteq B$. Then by definition of subset, the statement $\forall x (x \in A \Longrightarrow x \in B)$ is true.

We want to show that $(A \cap C) \subseteq (B \cap C)$. This can be done if we can show that the statement $\forall x (x \in A \wedge x \in C) \Longrightarrow (x \in B \wedge x \in C)$ is true.

Let $p,q,r$ stands for the propositions $x \in A, x\in B$ and $x \in C$. Then we get $p\implies q$. Now, we want show that the statement $(p \wedge r) \Longrightarrow (q \wedge r)$ is true.

This statement will be false, if and only if $q \wedge r$ is false which is when either p or r is false and true or both are false. We know that q is true or false because we assumed that $p \Longrightarrow q$ is true, thus only if both p and q are true or false or if only p is false the statement is true. Hence the statement will be true either case, because if $q \wedge r$ is false then r must be, because if q is false $p \Longrightarrow q$ will not be true, and if r is false $p \wedge r$ will be false and $q \wedge r$ also making the statement still true.

$\therefore$ If $A \subseteq B$ then $(A \cap C) \subseteq (B \cap C)$ is a true statement.

$\endgroup$
  • $\begingroup$ Your idea is good but logically not correct. For instance, saying "$p=x\in A$" is not acceptable. Better say, let $p$ be the proposition $x\in A$. $\endgroup$ – Juniven Jan 15 '17 at 3:11
  • $\begingroup$ @I am the Law The Law You see the check mark at the left side of the answer? Click it to which ever you want to accept. Thank you. $\endgroup$ – Juniven Jan 15 '17 at 3:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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