1. Proving equality of sets

We will spend most of our time during this meeting on proving that two sets (usually defined by some set operations) are always equal, e.g. we will prove, that (A\cup B)\setminus C= (A\setminus C)\cup (B\setminus C) for all sets A,B,C. You already know from the lecture that there are three methods, out of which we will prefer the third one, because it is the most general method and it will be useful further in the course.

  • Venn’s diagrams method. We draw a diagram of the set which is on the left side of the equation and a diagram of the set which is on the right, computing the subsequent set operations. This method works for at most 3 sets, because it is impossible to draw more independent sets on a plane in an easy way (it is possible but not with circles and becomes definitely more complicated when number of sets increases).
    venn
  • independent family method. We construct an independent family of sets, i.e. such family of sets that each intersection of sets or their complements is non-empty. For three sets it is sufficient to take the set \{0,1,2,3,4,5,6,7\} and set A=\{1,4,5,7\}, B=\{2,4,6,7\}, C=\{3,5,6,7\}. Then it is sufficient to check the equality on this family of sets — and we know it will work for any family. In our case we calculate left-hand side: A\cup B=\{1,2,3,4,5,6\}, (A\cup B)\setminus C=\{1,2,5\} and right-hand side: A\setminus C=\{1,2\}, B\setminus C=\{2,5\}, (A\setminus C)\cup(B\setminus C)=\{1,2,5\}, and we are done.
  • the third method starts with an observation that X=Y if and only if X\subseteq Y and Y\subseteq X. We can therefore split our proof into two parts: proving the first inclusion and proving the second one.

But how to prove that X\subseteq Y? We start our prove by taking x form X, so let x\in X. Next by a sequence of implications we prove that also x\in Y, which proves the inclusion.

Sometimes proving that X=Y, the proofs of X\subseteq Y and of Y\subseteq X can be easily done simultaneously. We simply pay attention whether the implications in the proof of that if x\in X, then x\in Y, work also in the other direction. Whether the implications are actually equivalences.

When we prove that a given statement if false, it is sufficient to show a counterexample, i.e. an example of such sets that the statement is false for them.

In our case:
We prove that: (A\cup B)\setminus C\subseteq(A\setminus C)\cup (B\setminus C). Let x\in (A\cup B)\setminus C, then x\in A\cup B oraz x\notin C, so x\in A lub x\in B, but x\notin C, so (x\in A \land x\notin C)\lor (x\in B\land x\notin C), so x\in A\setminus C or x\in B\setminus C, therefore x\in (A\setminus C)\cup (B\setminus C).
Now we prove that: (A\setminus C)\cup (B\setminus C)\subseteq (A\cup B)\setminus C: Let x\in (A\setminus C)\cup (B\setminus C), so x\in A\setminus C or x\in B\setminus C, therefore x\in A lub x\in B, but in both cases if x\notin C. Therefore x\in A\cup B, but x\notin C, so x\in (A\cup B)\setminus C.

When we prove that one statement holds if and only if some other statement holds, then usually we split the proof into two proofs of left side and right side implications.

Sometimes proving that an implication holds we use a proof by contradiction. We assume the assumption and a negation of the hypothesis, and next we try to get a contradiction.