The Mathematical Proof Thread

[Joods]

Ok. My daughter looked at the first post in this thread and said that for the most part she understands it.

[Kernel Sohcahtoa]

Hello, everyone.  Thanks for all of the beautiful posts.  I am posting a proposition and my attempted proof of it (it is far from beautiful).  I'd appreciate any tips or incites.  Please do not assume this proof is correct until others have had a chance to pick it apart.  This was exercise 36 (page 130) in Hammack's Book of Proof.  Hammack only gives solutions for the odd exercises, so I'm not sure if this proof is valid.  Also, I was not sure how to use a hide tag, so I apologize for posting the proof out in the open.

Relevant definitions:

Definition of Divisibility: Suppose a and b are integers.  We say that a divides b if b=ac for some integer c.  In this case we also say that a  is a divisor of b, and that b is a multiple of a (Hammack, Book of Proof, pg 90).


Definition of the Least Common Multiple (LCM): The lcm of non-zero integers a and b, denoted lcm(a,b), is the smallest positive integer that is a multiple of both a and b (Hammack, Book of Proof, pg 90).


Proposition: Suppose a and b are natural numbers.  Then a=lcm(a,b) if and only if b divides a

Proof Mini Strategy.

---

 We have a bi-conditional statement here (p if and only if q).  Hence, in order to prove that this proposition is true, we'll need to show that p implies q and that q implies p.  In other words, we need to show that if a=lcm(a,b), then b divides a.  In addition, we need to show that if b divides a, then a=lcm(a,b).


Proof.  Suppose a=lcm(a,b).  Then by the definition of the lcm, a is a multiple of a and b, so a=ax and a=by for some integers x and y.  Thus, a=by means that b divides a by the definition of divisibility.

To prove the proposition in the other direction, suppose b divides a.  Then a=bu for some integer u, so a is a  multiple of itself and b.  Thus, a is greater than or equal to lcm(a,b).  On the other hand, lcm(a,b) is a multiple of a.  Thus, lcm(a,b)=aw  for some integer w.  Consequently, by the definition of divisibility, a divides lcm(a,b), which means that a must be less than or equal to lcm(a,b).  Hence, we have demonstrated that a is less than or equal to lcm(a,b) and a is greater than or equal to lcm(a,b), so it follows that  a=lcm(a,b).  Hence, the proof is complete.

---

Moderator Notice
added hide tags
In source code mode:

Code:

[hide]
secret
[/hide]

-AK

[A Handmaid]

I got it!
I figured it out!

---

a=lcm(a,b)

The output of lcm(a,b) gives us an ax and by that are equal(which in this case are equal to a).
ax=by=a      (x and y are Integers)
Thus,
by=a
a=by
For a number to divide another number, they must satisfy x=yc where c is an integer
Since y is an integer, b divides a.
Q.E.D.

---

[A Handmaid]

Proposition: Suppose a and b are natural numbers.  Then a=lcm(a,b) if and only if b divides a

Do I win?
EDIT: Oh, your proof was the same, hehe.

[Kernel Sohcahtoa]

Hello everyone.  I found this tool online.  Basically it allows you to copy and paste math symbols, which can make posting math related content much simpler.  I hope this is useful.  Also, I do plan on posting some more cool stuff concerning sets.  I've been learning how to do proofs involving sets, and I must say that it is rather fascinating.  Thanks.  Live long and prosper.

[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.

[Kernel Sohcahtoa]

Modification to Part one of Proof#1

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

---

[secret]
Let’s first demonstrate that A∩(B∪C) ⊆ (A∩B)∪(A∩C)  IMO, the text in bold adds more clarity to the proof.


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. So, x ∈ A and x ∈ B or x ∈ A and x ∈ C. Thus, by the definition of intersection, 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.
 

---

[Kernel Sohcahtoa]

Here is one existence statement and one universally quantified statement that I came across.  In order to prove an existence statement, simply find one example that makes the statement true.  On the other hand, in order to disprove a universally quantified statement, find one example that makes the statement false. 

Would anyone like to insert some quarters and play?

Tools

Definition of a prime number: A natural number n is prime if it has exactly two positive divisors, 1 and n.

Prime number calculator

Real numbers


1)There exist prime numbers p and q for which p-q=1,000

Hint

---

Now, this is an existence proof, which means that all we have to do to prove its truth, is to find one prime number p and one prime number q for which p-q=1,000

---

A Solution

---

Let p=1,013 and q=13. Then p-q=1,000.  Now, since 1,013 and 13 are both prime numbers and 1,013-13= 1,000, then our statement is true.

---

 
2)The inequality 2^x is greater than or equal to x+1 is true for all positive real numbers x.

Hint

---

Now employ disproof here.  To disprove a universally quantified statement, all you need to do is find one real number x, which makes the above statement false.

---

A Solution
 

---

Suppose x=1/2.  Then 2^1/2=sqrt(2).  Now, 1/2 + 1= 3/2.  Thus, sqrt(2) is less than 3/2, which contradicts our statement.  Hence, our statement is false.

---

 
 

References

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

[robvalue]

Interesting! I'll have a look at those later if my brain starts working.

Just as an aside, we don't allow 1 to be a prime number because we would lose unique factorisation of integers into primes. For example:

6 = 2 * 3 Unique

6 = 2 * 3 * 1 = 2 * 3 * 1 * 1 = ...

[Kernel Sohcahtoa]

Here's a pretty cool proof of the binomial theorem via mathematical induction

Ron Joniak


Here are some additional notes which may be helpful.

At 6:35, RonJoniak uses the concept of the index shift.  Now, this may seem extraneous, but we actually need to use the index shift: this will eventually allow us to combine the two summations into one summation (after stripping out terms from the non-shifted summation); and once we get it into one summation, this will get us closer toward manipulating the left hand side of the proof into the right hand side of the proof.  Here's a site that explains the concept of the index shift (the index shift material will be toward the middle/bottom of the page)

P.S. Toward the end of the video he actually puts the stripped out x^(m+1) and y^(m+1) terms back into the summation.  Hence, when he does this, putting the x^(m+1) term back into the summation (using k=0) puts the lower limit of the summation back to zero.  Likewise, when he puts the y^(m+1) term back into the summation (using k=m+1), this puts the summation's upper limit back to m+1, enabling us to reproduce the right hand side of the proof, which was the objective all along.  


You will encounter index shifts in differential equations.  In particular, you will need index shifts when finding series solutions to differential equations.

At 11:55, Ron Joniak mentions Pascal's rule.  Pascal's rule is the following equation:

C(n+1,k)=C(n,k-1) +C(n,k).  Assume that we have a set A={0,1,2,3,.....,n}. Then our set has n+1 elements (including the zero gives it an additional element), so the number of k element subsets in A can be represented as C(n+1,k)  (note, if A={1,2,3...n}, then it would have n elements and it could be represented as C(n,k)). Another way to think about C(n+1,k) is that we are choosing k elements from a set with n+1 elements.  For example, C(3,1) means that we are choosing one element from a set with 3 total elements).

P.S. Also, for the sake of curiosity, if we wanted to put C(n+1,k) into equation form then we would get C(n+1,k)= (n+1)!/(k!(n+1-k)!). However, this is not needed for the proof, as it is unnecessary.

 Now, Pascal's rule states that "the number of k element subsets in A is equal to the number of k element subsets that contain zero plus the number of k element subsets that do not contain zero."(Hammack, Book of Proof, pg 78). 

Please note that I used the form C(n+1,k)=C(n,k-1) +C(n,k) to illustrate Pascal's rule.  In the video, the author uses a different form, but the two forms are just different ways of expressing the exact same idea; in this post, the form I used is easier to write via a keyboard, so my apologies for any inconvenience.