Our server costs ~$56 per month to run. Please consider donating or becoming a Patron to help keep the site running. Help us gain new members by following us on Twitter and liking our page on Facebook!
Current time: 21st February 2017, 01:16

Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
The Mathematical Proof Thread
#31
RE: The Mathematical Proof Thread
Ok. My daughter looked at the first post in this thread and said that for the most part she understands it.
Please consider becoming a patron to help offset site costs and to get rid of EGO
Click here for more info and to sign up Smile
Avatar compliments of Luckie with some assistance by Losty Heart
Reply
#32
RE: The Mathematical Proof Thread
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.



Moderator Notice
added hide tags
In source code mode:
Code:
[hide]
secret
[/hide]

-AK
"I'm fearful when I see people substituting fear for reason." Klaatu, from The Day The Earth Stood Still (1951)


"It is possible to commit no mistakes and still lose.  That is not a weakness.  That is life." Captain Picard from the Star Trek TNG episode (season 2) "Peak Performance"

"A mathematician, like a painter or a poet, is a maker of patterns. If his patterns are more permanent than theirs, it is because they are made with ideas."  G.H. Hardy











Reply
#33
RE: The Mathematical Proof Thread
I got it!
I figured it out!

Reply
#34
RE: The Mathematical Proof Thread
(17th September 2016, 02:47)Kernel Sohcahtoa Wrote: 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.
Reply
#35
RE: The Mathematical Proof Thread
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.
"I'm fearful when I see people substituting fear for reason." Klaatu, from The Day The Earth Stood Still (1951)


"It is possible to commit no mistakes and still lose.  That is not a weakness.  That is life." Captain Picard from the Star Trek TNG episode (season 2) "Peak Performance"

"A mathematician, like a painter or a poet, is a maker of patterns. If his patterns are more permanent than theirs, it is because they are made with ideas."  G.H. Hardy











Reply
#36
RE: The Mathematical Proof Thread
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#2

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





Proof#3

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




Proof #4

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



 
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.
"I'm fearful when I see people substituting fear for reason." Klaatu, from The Day The Earth Stood Still (1951)


"It is possible to commit no mistakes and still lose.  That is not a weakness.  That is life." Captain Picard from the Star Trek TNG episode (season 2) "Peak Performance"

"A mathematician, like a painter or a poet, is a maker of patterns. If his patterns are more permanent than theirs, it is because they are made with ideas."  G.H. Hardy











Reply
#37
RE: The Mathematical Proof Thread
Modification to Part one of Proof#1

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


"I'm fearful when I see people substituting fear for reason." Klaatu, from The Day The Earth Stood Still (1951)


"It is possible to commit no mistakes and still lose.  That is not a weakness.  That is life." Captain Picard from the Star Trek TNG episode (season 2) "Peak Performance"

"A mathematician, like a painter or a poet, is a maker of patterns. If his patterns are more permanent than theirs, it is because they are made with ideas."  G.H. Hardy











Reply
#38
RE: The Mathematical Proof Thread
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




A Solution



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

Hint




A Solution
 

 
 

References

Hammack, Richard. Book of Proof.  Virginia: Richard Hammack (publisher), 2013.
"I'm fearful when I see people substituting fear for reason." Klaatu, from The Day The Earth Stood Still (1951)


"It is possible to commit no mistakes and still lose.  That is not a weakness.  That is life." Captain Picard from the Star Trek TNG episode (season 2) "Peak Performance"

"A mathematician, like a painter or a poet, is a maker of patterns. If his patterns are more permanent than theirs, it is because they are made with ideas."  G.H. Hardy











Reply
#39
RE: The Mathematical Proof Thread
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 = ...
Feel free to send me a private message.
Please visit my website here! It's got lots of information about atheism/theism and support for new atheists.

Index of useful threads and discussions
Index of my best videos
Quickstart guide to the forum
Reply
#40
RE: The Mathematical Proof Thread
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.
"I'm fearful when I see people substituting fear for reason." Klaatu, from The Day The Earth Stood Still (1951)


"It is possible to commit no mistakes and still lose.  That is not a weakness.  That is life." Captain Picard from the Star Trek TNG episode (season 2) "Peak Performance"

"A mathematician, like a painter or a poet, is a maker of patterns. If his patterns are more permanent than theirs, it is because they are made with ideas."  G.H. Hardy











Reply


Possibly Related Threads...
Thread Author Replies Views Last Post
  Million Dollar Prize for Math proof of NP problems emilynghiem 6 1847 22nd February 2015, 00:47
Last Post: vorlon13
  "Gödel's ontological proof" proves existence of God Belac Enrobso 41 8275 9th February 2015, 03:22
Last Post: Alex K
  Mathematical proof.. lifesagift 20 3524 26th September 2014, 17:01
Last Post: lifesagift
Information My proof for de morgans law LogicMaster 17 2382 29th May 2014, 19:55
Last Post: Stimbo
  Mathematician Claims Proof of Connection between Prime Numbers KichigaiNeko 10 4620 26th September 2012, 03:18
Last Post: Categories+Sheaves
  Need a proof (real analysis) CliveStaples 8 3716 2nd August 2012, 22:11
Last Post: CliveStaples
  Mathematical proof of the existence of God JudgeDracoAmunRa 20 8580 30th March 2012, 11:43
Last Post: JudgeDracoAmunRa
  Spot the Mathematical Fallacy Tiberius 16 5724 25th March 2010, 06:57
Last Post: Violet
  Mathematical claims of 'Bible Codes'...is there any truth in the maths? CoxRox 12 5423 9th January 2009, 17:23
Last Post: Tiberius



Users browsing this thread: 1 Guest(s)