1
$\begingroup$

Show that $S\cap(T\,\cup \,T') = (S\,\cap\,T)\cup(S\,\cap\,T')$

I did this by creating 3 sets:

  • $S\,\,=\{a,b,c,d\}$

  • $T\,\,=\{c,d,e,f\}$

  • $T'=\{a,b,c,d\}$

And then I performed the operations and checked they are the same. Is there something else I should do or only this will suffice?

$\endgroup$
3
  • 1
    $\begingroup$ Why did this question get two downvotes? $\endgroup$
    – Git Gud
    May 25, 2013 at 14:27
  • 3
    $\begingroup$ Mathematical hipsters perhaps? $\endgroup$
    – Red Banana
    May 25, 2013 at 14:41
  • $\begingroup$ Does the question ask you to do it for any choice of $S,T$, and $T'$? If so, doing it for just one example will not suffice. $\endgroup$
    – Potato
    Jun 16, 2013 at 3:33

4 Answers 4

6
$\begingroup$

Checking one example is insufficient in order to conclude a general proof.

You need to do this for abstract sets. Pick an element from $S\cap (T\cup T')$, using the definitions of $\cap,\cup$ conclude that it has to be in $(S\cap T)\cup (S\cap T')$, and then do the same thing from the other direction.

That would be a proof.

$\endgroup$
4
  • $\begingroup$ I'm not sure on how to do that. I'm unable to pick elements in that manner (Can you expand a little?) - but I've made a Venn diagram with it - I do undestand that the Venn diagram is the manifestation of such abstraction (?) but I'm still confused. $\endgroup$
    – Red Banana
    May 25, 2013 at 14:00
  • $\begingroup$ Wait. It's an element that is in both $S$ and $(T\,\cup\,T')$. I feel they are the same but I can't explain it. $\endgroup$
    – Red Banana
    May 25, 2013 at 14:07
  • 2
    $\begingroup$ @Gustavo: We pick an arbitrary $x\in S\cap (T\cup T')$, therefore $x\in S$ and $x\in T\cup T'$. So either $x\in T$ or $x\in T'$. If $x\in T$ then $x\in S$ and $x\in T$ so by definition of the intersection, $x\in S\cap T$ and so $x\in(S\cap T)\cup(S\cap T')$ ... $${}$$The key point is not to limit yourself to particular sets, or to particular elements. We pick arbitrary sets and arbitrary elements from these sets. Then we can conclude that the statement holds for every set. $\endgroup$
    – Asaf Karagila
    May 25, 2013 at 14:07
  • $\begingroup$ Oh, got it! Thanks Asaf. $\endgroup$
    – Red Banana
    May 25, 2013 at 14:08
3
$\begingroup$

A different approach: let $x$ be any element in the universe. The following equivalences hold:

$$\begin{align} x\in S\cap (T\cup T') &\iff x\in S\land x\in T\cup T'\\ &\iff x\in S\land (x\in T\lor x\in T')\\ &\iff (x\in S\land x\in T)\lor (x\in S\land x\in T')\\ &\iff x\in S\cap T\lor x\in S\cap T'\\ &\iff x\in (S\cap T)\cup (S\cap T').\end{align}$$

$\endgroup$
9
  • $\begingroup$ Different from whose approach? $\endgroup$
    – Asaf Karagila
    May 25, 2013 at 14:13
  • 1
    $\begingroup$ If the OP did not yet prove that $\land$ is distributive over $\lor$, then this proof is not a very good one. $\endgroup$
    – Asaf Karagila
    May 25, 2013 at 14:15
  • 2
    $\begingroup$ It's not a bad proof per se, it just uses an assumption which may or may not be known to the OP. I find your comment unnecessary caustic, by the way. $\endgroup$
    – Asaf Karagila
    May 25, 2013 at 14:18
  • 1
    $\begingroup$ @AsafKaragila To be honest I don't even know how my answer differs from yours except for the fact that I didn't use words. How do you go from the second line in my proof to the third and back without using the aforementioned property? $\endgroup$
    – Git Gud
    May 25, 2013 at 14:21
  • 1
    $\begingroup$ @AsafKaragila: your answer —at least the expanded form you give in its comments—doesn’t quite (as I read it) “verify that the Boolean truth table of the distributive law works”; rather, it gets the distributive law from the “Frobenius law” of logic, that one can hold any assumption (in this case, $x \in S$) on the side, do some more reasoning (going from $x \in T \cap T'$ to the cases $x \in T$ or $x \in T'$), and then bring back the assumption in each case. This is somewhat stronger than the truth-table approach—it doesn’t depend on classicality—but is a bit subtler to formally explain. $\endgroup$ May 25, 2013 at 18:30
3
$\begingroup$

Let $X$ be a set. For every $A,B,C$ subsets of $X$, you can check that $$\frac{(A\cap B)\subseteq C}{B\subseteq (A\rightarrow C)}$$ where $A\rightarrow C$ is defined as $(A\rightarrow C):=(\mathscr{C}A)\cup C$ and $\mathscr{C}A$ is the complementary set of $A$ in $X$ and horizontal line means "if and only if", i.e. the line above is true if and only if the line below is true.

More concisely, $$A\cap (-)\dashv A\rightarrow (-)$$ where $\dashv$ means left adjoint, $A\cap(-)$ is the function sending a subset $B$ of $X$ to $A\cap B$ and $A\rightarrow (-)$ the function sending a subset $C$ of $X$ to $A\rightarrow C$.

Being a left adjoint, $A\cap (-)$ preservs colimits, in particular it preservs unions, hence your desidered distributive law.

$\textrm{EDIT}$: let $f:X\longrightarrow Y$ be a function, $X,Y$ sets, $A$ subset of $X$, $B$ subset of $Y$. Then you have $$\frac{f(A)\subset B}{A\subset f^{-1}(B)}$$ Proceeding as in the main part of this answer, you have that the direct image of $f$ is left-adjoint to the inverse image $f^{-1}$, thus, being a left adjoint, direct image preserves colimits, for example unions, so that you immediately prove that $f(A\cup C)=f(A)\cup f(C)$, without computing on elements ( pick an element in $A\cup C$, do the image under $f$, check this image is in the image of $A$ or in the image of $C$, conversely, pick an element which is in $f(A)$ or in $f(B)$, check that it comes from an element....), while inverse image $f^{-1}$, being a right-adjoint, preserve limits, for example intersections, so that you have an "automatic" proof that $f^{-1}(A\cap C)=f^{-1}(A)\cap f^{-1}(C)$

So two facts apparently different as your distributive law and these properties of $f$ and $f^{-1}$ appear in some sense as two different manifestations of the same phenomenon

$\endgroup$
6
  • 1
    $\begingroup$ Well, it may help me in the future. $\endgroup$
    – Red Banana
    May 25, 2013 at 17:49
  • $\begingroup$ @GustavoBandeira I've added a part with a simple example $\endgroup$ May 25, 2013 at 18:09
  • 2
    $\begingroup$ While I agree this categorical analysis of the logic is beautiful, in this case feels like using a sledgehammer to crack a nut, and a highly abstract and complicated sledgehammer at that — almost certainly over the head of anyone struggling with the original question. $\endgroup$ May 25, 2013 at 18:30
  • 2
    $\begingroup$ @PeterLeFanuLumsdaine I don't completely agree with your remarks, the categorical/logic tools i used are all elementary, not advanced, and i'm pretty convinced that (maybe in the future) the OP will be able (if of some interest for him) to learn those tools in no more than one or two days $\endgroup$ May 25, 2013 at 18:42
  • 1
    $\begingroup$ @PeterLeFanuLumsdaine Yes, Peter. The answer is a great addendum to me. It may help me a lot in the near future. $\endgroup$
    – Red Banana
    May 25, 2013 at 20:08
1
$\begingroup$

HINT: is it possible to write the left hand side otherwise? Maybe draw it first, so you have a good idea.

$\endgroup$
2
  • 1
    $\begingroup$ This hint in not clear. If you suggest using the distributive property of $\cap$ over $\cup$, then this is exactly what needs to be proved here. $\endgroup$
    – Asaf Karagila
    May 25, 2013 at 13:30
  • $\begingroup$ Taking the brackets by using abstract sets as you concluded is a better way of putting it. $\endgroup$ May 25, 2013 at 13:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .