The Mathematical Proof Thread

[Kernel Sohcahtoa]

Introduction

In this post, I’ll be posting the Proofs for the Distributive Laws for sets.  My objective is to provide key information and refresher material that can help people understand these proofs and write them if they want to (I will place the proofs in hide tags). In addition, this material contains some of the standard equipment requisite for tackling proofs.  Regarding proof techniques, for proof #1, I will be employing the standard technique of showing that if A ⊆ B and B ⊆ A, then A=B. However, this technique is more tedious and less direct than another approach. Hence, for the remaining three proofs, I will use an alternate form of proof, which transforms one side of the equation into the other side via a series of equalities (Hammack, p.138). 

For those people who want to work these out, I recommend that you use one Cartesian product proof and one non-Cartesian product proof as instructional examples before trying to tackle a proof head on. Also, formal definitions and a symbol legend will be provided in the Proof section (also, for whatever reason, in my proofs, the union symbols came out small, so I apologize for the inconvenience).

Sets

A set is a collection of elements.  For example, the set S={1,2,3} (notice that the elements of set S are in brackets; the brackets denote that the elements are in a set) is a collection of the numbers 1,2,3, which are the elements of this particular set.  In other words, 1,2,3 ∈ {1,2,3} or 1,2,3 ∈ S.  In addition, since S contains 3 elements, then S has a cardinality of three or |S|=3.

*Bars on the outside of sets denote cardinality; whereas, bars that are on the outside of variables denote absolute value. 

Subsets 

To illustrate the concept of a subset, let’s look at a few examples.   Suppose A={1,2} and B={1,2,3}.  Since, 1,2 are elements of A and 1,2 are also elements in B, then we can say that A ⊆ B.  However, B contains 1,2,3 while A only contains 1,2, so B ⊈ A. 

Now, it is also possible for two sets to be subsets of each other: in order for this to occur, each set must contain all of the elements of the other set.  For example, suppose A={1,2,3} and B={1,2,3}.  Since A contains the elements of B and B contains the elements of A, then they are subsets of each other, or A ⊆ B and B ⊆ A.  More importantly, since A and B are subsets of each other, then it must be the case that A=B.  This will be a key idea in proving the distributive laws for sets (Hammock, pp: 136,137).

In addition, a key fact to grasp is that the empty set, denoted as ∅ or { }, is a subset of every set. For simplicity, suppose that B is any set.  Now let’s say that ∅ ⊈ B. This means that the empty set contains at least one element that is not in B.  But, since the empty set contains no elements (it has a cardinality of zero), then ∅ ⊈ B is not true; therefore, it must be the case that the empty set is a subset of B or  ∅ ⊆ B (Hammack, p. 11). 

Intersection and Union

Another key concept to grasp is intersection and union.  The intersection between two sets is the point at which they overlap: it is the set that contains the elements that are common to both sets.  For example, suppose A={1,2,3} and B={3,4,5}.  Then the number that is in both sets is 3.  Hence, {3} represents the intersection of A and B or A∩B.  Naturally, this concept can be extended to 3 or more sets.

In contrast, the union of A and B or A∪B, is simply the set of all things that are in A or B (or in both) (Hammack, p.17).  For example, suppose we have X={0,1} and Y={2,3}.  Then X∪Y= {0,1,2,3}, where 0 and 1 are elements of X and 2 and 3 are elements of Y.  For another example, suppose A={1,2,3,} and B={3,4,5,6,7}.  Then A∪B={1,2,3,4,5,6,7,} (notice that 3 is an element of A and B).  Naturally, this idea can be extended to 3 or more sets (Hammack, p. 17).
 

The Cartesian Product.

Definition of an ordered pair: “An ordered pair is a list (x,y) of two things x and y enclosed in parentheses and separated by a comma.” (Hammack, p. 8).
Basically, the Cartesian product is the set of all ordered pairs of the product of two sets. For example, the Cartesian product of A={w,x} and B={y,z} is {(w,y), (w,z), (x,y), (x,z)}.  As an instructional aid, we could view A as the x axis and B as the y axis and then pair each (x,y) up accordingly (Hammack, p. 8).
 

Logic

A truth table is a good tool for checking the validly of statements.  Suppose we have two statements, P and Q. In order to build our table, we make a column for P and a column for Q.  In addition, each statement can either be true or false, and since we will be combining the statements P and Q in order to form a conclusion, we will need to list all of the possible true, false combinations

Truth Table

1)P is true and Q is true

2)P is true and  Q is false

3)P is false and  Q is true

4)P is false and Q is false

As a quick note, let me introduce the following symbols: ∧=and; ∨=or.  Via our truth table, in order for P∧Q to be true, then both elements in each entry must be true.  Thus, entry 1 is the only case where p and q are both true.  Also, in order for P∨Q to be true, then each entry must have at least one element that is true.  Hence, with the exception of entry 4, P∨Q is true.  (Hammack, pp: 38,39).

Regarding conditional statements (if P then Q), they can only be true in the following circumstances (we are using the truth table above as a reference): 1) P is true and Q is true; 3) P is false and Q is true; 4) P is False and Q is False.
 
In order to make sense of 2, 3, and 4, let’s use the following example.  Let P=you pass the exam and Q=you pass the course.  Then the statement if P then Q becomes the following: if you pass the exam then you pass the course.  Now regarding 2, the professor said that if we passed the exam, then we would also pass the course.  Hence, since we did P and still failed the course, then the professor lied and the statement is false.  Regarding 3, the professor did not say what would happen if we failed the exam, as there may be other ways to pass the course.  Hence, since the professor did not lie, she did tell the truth and 3 is true.  Regarding 4, you failed at P and Q.  Hence, the professor promised that if you pass the exam then you will pass the course, so she did keep her word and the statement is true (Hammack, p. 43).

Now, this was just a quick crash course in basic logic (there is much more to logic, especially as it relates to solving other proofs).  However, I included this material because, IMO, it is requisite in understanding and solving these proofs.  In addition, I will be making use of the fact that the statement P is equivalent to P∧P in proof#3.  For example, observe that if you created another column for P∧P in the truth table above, then it would contain the same entries as P.

Prove The Distributive Laws for Sets

Definition of a Subset:

Suppose A and B are sets.  If every element of A is also an element of B, then we say that A is a subset of B or A ⊆ B.  We write A ⊈ B, if A is not a subset of B, that is, if it is not true that every element of A is also an element of B.  Thus, A⊈B means that there is at least one element of A that is not an element of B. (Hammack, p. 11).

Definition of Union: the union of A and B is the set A∪B={x: x ∈ A or x ∈ B} (Hammack, 17)

Definition of Intersection: the intersection of A and B is the set A∩B={x: x  ∈ A and x ∈  B} (Hammack, 17)

Definition of the Cartesian Product: The Cartesian product of two sets A and B is another set, denoted as A x B and defined as A x B= {(a,b): a ∈ A, b ∈ B} (Hammack, p. 8).

Distributive Law with Logic Symbols:

Suppose we have the expression a*(b+c).  From high school algebra, the distributive law says that a*(b+c)= a*b + a*c.  Now, the distributive law is used in the same manner with logical symbols: they behave in the same way that multiplication, addition, and subtraction symbols do.  For example suppose we have a ∧ (b ∨ c).  Think of ∧ as the multiplication symbol and ∨ as the addition symbol.  Then we get a ∧ (b ∨ c)=(a ∧ b) ∨ (a ∧ c) (Hammack, p. 50).


Fact: P=P∧P

Math Symbol Legend


∩=intersection 
∪=union            
⊈= not a subset 
⊆=subset
∉=not an element of
∈=an element of
∧=and
∨=or
∅=the empty set

Proof #1
If A ,B, and C are sets, then A∩(B∪C)=(A∩B)∪(A∩C)

Hint:

---

Proof strategy
[secret]
We will employ the standard technique for proving that A=B.  Prove that A ⊆ B.  Prove that B ⊆ A. Therefore, since A ⊆ B and B ⊆ A, then it follows that A=B (Hammack, 136).

However, as we are proving that A ⊆ B and B ⊆ A, we need to employ the technique for proving A ⊆ B and B ⊆ A respectively.  For example, to prove that A ⊆ B, we use the following technique: suppose that a ∈ A…..Therefore a ∈ B.  Thus, a ∈ A implies that a ∈ B, so it follows that A ⊆ B.  We use the same reasoning to prove B ⊆ A (Hammack, p. 136).

---

---

[secret]

Let’s first demonstrate that A∩(B∪C) ⊆ (A∩B)∪(A∩C)


Suppose x ∈ A∩(B∪C).  Then by the definition of intersection, x ∈ A and x ∈ B∪C.  Now, by the definition of union, x ∈ B or x ∈ C. Thus, x ∈ (A∩B) or x ∈ (A∩C).  Consequently, by the definition of union, x ∈ (A∩B)∪(A∩C).  Hence, we have shown that x ∈ A∩(B∪C) implies x ∈ (A∩B)∪(A∩C), so it follows that A∩(B∪C) ⊆ (A∩B)∪(A∩C).

Let’s demonstrate that (A∩B)∪(A∩C) ⊆  A∩(B∪C)

Suppose x ∈ (A∩B)∪(A∩C).  Then by the definition of union, x ∈ (A∩B) or x ∈ (A∩C). By the definition of intersection, x ∈ A and x  ∈ B or x ∈ A and x ∈ C.  Thus, x ∈ A and x ∈ B or C.  By the definition of union, x ∈ A and x ∈ (B∪C).  Also, by the definition of intersection, x ∈ A ∩(B∪C).  Hence, we’ve shown that x ∈ (A∩B)∪(A∩C) implies  x ∈ A ∩(B∪C), so it follows that (A∩B)∪(A∩C) ⊆  A∩(B∪C).

In summary, we’ve shown that A∩(B∪C) ⊆ (A∩B)∪(A∩C) and (A∩B)∪(A∩C) ⊆  A∩(B∪C).  Therefore, A∩(B∪C)=(A∩B)∪(A∩C).   Hence, the proof is complete.
 
 

---

Proof#2

If A ,B, and C are sets, then A∪(B∩C)=(A∪B)∩(A∪C)

---

[secret]

To demonstrate this proof, let’s observe the following equalities

A∪(B∩C)={x: x ∈ A∪(B∩C)}
={x: (x ∈ A) ∨ (x ∈ B∩C)} by the definition of union
={x: (x ∈ A) ∨ (x ∈B ∧ x ∈ C)} by the definition of intersection
={x: (x ∈ A) ∨ (x ∈B) ∧ (x ∈ A) ∨ (x ∈ C)} distributive property
={x: (x ∈ A) ∪ (x ∈ B)} ∧ {x: (x ∈ A) ∪ (x ∈ C)} definition of union
= (A∪B)∩(A∪C)  the definition of intersection
Hence the proof is complete

---

Proof#3

If A,B, and C are sets then A x (B∩C)= (A x B) ∩ (A x C)

---

[secret]

To demonstrate this proof, let’s observe the following equalities


A x (B∩C)= {( x,y): (x ∈ A) ∧ (y ∈ B∩C)} by the definition of the Cartesian product
= {( x,y): (x ∈ A) ∧ (y ∈ B) ∧ (y ∈ C)} by the definition of intersection
={( x,y): (x ∈ A) ∧ (x ∈ A) ∧ (y ∈ B) ∧ (y ∈ C)} via the fact that P=P∧P
={( x,y): ((x ∈ A) ∧ (y ∈ B)) ∧ ((x ∈ A) ∧ (y ∈ C))} rearrange terms
={( x,y): (x ∈ A) ∧  (y ∈ B)} ∩ {(x,y): (x ∈ A) ∧  (y ∈ C)} definition of intersection
= (A x B) ∩ (A x C) definition of the Cartesian product.  (Hammack, p. 138)
Hence, the proof is complete

---

Proof #4

If A, B, and C are sets then A x (B∪C)= (A x B) ∪ (A x C)

---

[secret]


To demonstrate this proof, let’s observe the following equalities

A x (B∪C)={(x.y): (x ∈ A) ∧ (y ∈ B∪C)} definition of the Cartesian product
={(x,y): (x ∈ A) ∧ (y ∈ B) ∨ ( y ∈ C)} definition of Union
={(x,y): (x ∈ A) ∧ (x ∈ A) ∧ (y ∈ B) ∨ ( y ∈ C)} P=P∧P
={(x,y): (x ∈ A) ∧ (y ∈ B) ∨ (x ∈ A) ∧ ( y ∈ C)} rearrange terms. *(please see note below)
={(x,y): (x ∈ A) ∧ (y ∈ B)} ∪ {(x,y): (x ∈ A) ∧ ( y ∈ C)} definition of union
=(A x B) ∪ (A x C) definition of the Cartesian product
Hence the proof is complete
 
*Notice that in {(x,y): (x ∈ A) ∧ (y ∈ B) ∨ (x ∈ A) ∧ ( y ∈ C)}, the first two terms are (x ∈ A) ∧ (y ∈ B).  All we did here was combine the first (x ∈ A) with ∧ (y ∈ B).  Now notice for the second two terms, we did not obtain ∧ (x ∈ A) ∨ ( y ∈ C).  To understand this, let’s say that ∧ is a plus sign.  Now for the sake of simplicity let’s say that ∧ (x ∈ A) is equal to positive 1.  Furthermore, let’s say that ∨ is a negative sign, and lets allow ∨ ( y ∈ C) to equal negative 2 (for simplicity).  If we multiply these two numbers we get 1*(-2).  Now we can factor out the negative one from the two to get 1*(-1)(2) or (-1)*(+2).  Notice that the negative sign is in front of the two combined terms while the positive sign is now in front of the 2.  Hence, the ∨ and  ∧ symbols worked in a similar fashion, which is why we ended up with ∨ (x ∈ A) ∧ ( y ∈ C) as the last two terms in this step.

---

 
Thanks for your time, patience, and understanding.  Please be sure to point out any errors on my part.  Well, I hope this post can be useful to others.  Live long and prosper.

References

Hammack, Richard. Book of Proof.  Virginia: Richard Hammack (publisher), 2013.