Book on proofs?
Moderators: gmalivuk, Moderators General, Prelates

 Posts: 118
 Joined: Tue Jun 24, 2008 2:57 am UTC
 Location: Atlanta, GA
 Contact:
Book on proofs?
I'm going to be taking Calc 3 this fall, so I was hoping that someone might have a good book on proofs...
I basically just need to know the structure that is used, as I've never really done a formal proof before.
Suggestions?
I basically just need to know the structure that is used, as I've never really done a formal proof before.
Suggestions?
Re: Book on proofs?
I've heard good things about How to Prove It.
Code: Select all
_=0,w=1,(*t)(int,int);a()??<char*p="[gd\
~/d~/\\b\x7F\177l*~/~djal{x}h!\005h";(++w
<033)?(putchar((*t)(w??(p:>,w?_:0XD)),a()
):0;%>O(x,l)??<_='['/7;{return!(x%(_11))
?x??'l:x^(1+ ++l);}??>main(){t=&O;w=a();}
 Yakk
 Poster with most posts but no title.
 Posts: 11128
 Joined: Sat Jan 27, 2007 7:27 pm UTC
 Location: E pur si muove
Re: Book on proofs?
Try proving stuff.
Ie: Let N be the natural numbers, defined (slightly informally) as:
0 is an element of N
For each element x in N, succ(x) is an element of N.
"=" is an equivalence relation on elements of N (look up what an equivalence relation is)
"+" is an operator that takes two values from N, and returns a value from N. Ie, for a, b from N, a+b is an element of N.
"*" is an operator that takes two values from N, and returns a value from N. Ie, for a, b from N, a*b is an element of N.
1 = succ(0)
For each element a in N, a+0 = a
For each element a, b in N, a+b = b+a
For each element a, b in N, a+succ(b) = succ(a+b), and succ(a)+b = succ(a+b)
For each element a in N, a*1 = a
For each element a, b in N, a*b = b*a
For each element a, b in N, a*succ(b) = a*b + a, and succ(a)*b = a*b+b
For each element a, b, c in N, a*(b+c) = a*b + a*c
For each element a in N, a < succ(a)
For each element a, b in N, a<b is the same as b>a, and a<=b is the same as b>=a
For each element a, b in N, a<=b means a<b or a=b
For each element a, b in N, either a<b or a>=b.
For each element a, b, c in N, if a<b and b<c, then a<c.
For each element a, b in N, if a<b, then a<succ(b).
...
I think that is more than enough to give you the natural numbers, but I left out induction.
So your task:
Prove that the Well Ordering Principle is implies the Principle of Mathematical Induction.
Well Ordering Principle: Let X be some subset of N. Then there is an element a from X such that for all elements b of X, a<=b.
Principle of Mathematical Induction: Let P(x) be some property of elements of N.
If P(0) is true, and ( For all elements a of N, P(a) is true implies P(succ(a)) is true ), then:
For all elements a of N, P(a) is true
Step 2: Define the "Principle of strong induction" to be:
Let P(x) be some property of elements of N.
If P(0) is true, and for each element a from N ((For each element b < a from N, P(b) is true) implies P(a) is true), then
For each element a of N, P(a) is true.
Show that The Principle of Mathematical Induction implies the Principle of Strong induction.
Step 3: show that the Principle of Strong Induction implies the Well Ordering Principle.
Note that this implies that the three principles are equivalent, as assuming any one of them proves the other 2!
I think that was, roughly, the very first proof assignment given to me at university. I think the prof did one of the 3 steps in class, and we did the other 2.
Can you think of how to approach this?
Ie: Let N be the natural numbers, defined (slightly informally) as:
0 is an element of N
For each element x in N, succ(x) is an element of N.
"=" is an equivalence relation on elements of N (look up what an equivalence relation is)
"+" is an operator that takes two values from N, and returns a value from N. Ie, for a, b from N, a+b is an element of N.
"*" is an operator that takes two values from N, and returns a value from N. Ie, for a, b from N, a*b is an element of N.
1 = succ(0)
For each element a in N, a+0 = a
For each element a, b in N, a+b = b+a
For each element a, b in N, a+succ(b) = succ(a+b), and succ(a)+b = succ(a+b)
For each element a in N, a*1 = a
For each element a, b in N, a*b = b*a
For each element a, b in N, a*succ(b) = a*b + a, and succ(a)*b = a*b+b
For each element a, b, c in N, a*(b+c) = a*b + a*c
For each element a in N, a < succ(a)
For each element a, b in N, a<b is the same as b>a, and a<=b is the same as b>=a
For each element a, b in N, a<=b means a<b or a=b
For each element a, b in N, either a<b or a>=b.
For each element a, b, c in N, if a<b and b<c, then a<c.
For each element a, b in N, if a<b, then a<succ(b).
...
I think that is more than enough to give you the natural numbers, but I left out induction.
So your task:
Prove that the Well Ordering Principle is implies the Principle of Mathematical Induction.
Well Ordering Principle: Let X be some subset of N. Then there is an element a from X such that for all elements b of X, a<=b.
Principle of Mathematical Induction: Let P(x) be some property of elements of N.
If P(0) is true, and ( For all elements a of N, P(a) is true implies P(succ(a)) is true ), then:
For all elements a of N, P(a) is true
Step 2: Define the "Principle of strong induction" to be:
Let P(x) be some property of elements of N.
If P(0) is true, and for each element a from N ((For each element b < a from N, P(b) is true) implies P(a) is true), then
For each element a of N, P(a) is true.
Show that The Principle of Mathematical Induction implies the Principle of Strong induction.
Step 3: show that the Principle of Strong Induction implies the Well Ordering Principle.
Note that this implies that the three principles are equivalent, as assuming any one of them proves the other 2!
I think that was, roughly, the very first proof assignment given to me at university. I think the prof did one of the 3 steps in class, and we did the other 2.
Can you think of how to approach this?
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision  BR
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Re: Book on proofs?
I like Yakk's example very much and I can't help but give one that I found very enjoyable as well. This was on an exam in my Real Analysis class:
Let [imath]f,g: \mathbb{R} \to \mathbb{R}[/imath] be continuous functions. Define function [imath]h: \mathbb{R} \to \mathbb{R}[/imath] as [math]h(x)=\begin {cases} f(x),&x\in\mathbb{Q}\\g(x),&x\in\mathbb{R}\setminus\mathbb{Q}\\ \end {cases}[/math]Find the set [imath]C=\{x;h\mbox{ is continuous at }x\}[/imath].
I realize this isn't strictly a proof assignment, so I or somebody else can supply the answer for you to prove.
Let [imath]f,g: \mathbb{R} \to \mathbb{R}[/imath] be continuous functions. Define function [imath]h: \mathbb{R} \to \mathbb{R}[/imath] as [math]h(x)=\begin {cases} f(x),&x\in\mathbb{Q}\\g(x),&x\in\mathbb{R}\setminus\mathbb{Q}\\ \end {cases}[/math]Find the set [imath]C=\{x;h\mbox{ is continuous at }x\}[/imath].
I realize this isn't strictly a proof assignment, so I or somebody else can supply the answer for you to prove.
Re: Book on proofs?
Well it's probably fun to learn in general, you won't almost certainly won't need to do much in the way of formal proofs in calc 3. Unless 'Calc 3' is introductory Real Analysis for you.
Re: Book on proofs?
Harg: is it
Spoiler:
Re: Book on proofs?
But since this set Q isn't defined, can I not suppose that Q and R are disjoint, and so R\Q = R?
Let x be an element of R => x is an element of R\Q => h(x) = g(x). Since g(x) is continuous over all of R, would it not be continuous at x, regardless of whether or not f and g are equal?
Edit: Silly me, you must have meant R to be the reals and Q to be the rationals. Anyway, wouldn't you need more than just a single point where f=g? I don't know anything about continuity other than what intuition tells me, but it seems we would need an interval (a,b) where a!=b along which f=g in order for h to be continuous.
Let x be an element of R => x is an element of R\Q => h(x) = g(x). Since g(x) is continuous over all of R, would it not be continuous at x, regardless of whether or not f and g are equal?
Edit: Silly me, you must have meant R to be the reals and Q to be the rationals. Anyway, wouldn't you need more than just a single point where f=g? I don't know anything about continuity other than what intuition tells me, but it seems we would need an interval (a,b) where a!=b along which f=g in order for h to be continuous.
What they (mathematicians) define as interesting depends on their particular field of study; mathematical anaylsts find pain and extreme confusion interesting, whereas geometers are interested in beauty.
Re: Book on proofs?
Intuition can fail when talking about continuity at a single point, since we always imagine continuous functions to be these nice, connected, wavy lines. Because Q and R\Q are dense in R, you can imagine the graph of h as a superposition of the very (in fact infinitely) finely dotted graphs of f and g. You can probably now see that the only points where h could possibly be continuous is where these dots come very, very close together i.e. where f=g.
Re: Book on proofs?
Here's another one:
Prove that for all natural z, there exist x in {1...9} and y such that x + y = z and x = y (mod 9). Does it work for bases other than 9?
Prove that for all natural z, there exist x in {1...9} and y such that x + y = z and x = y (mod 9). Does it work for bases other than 9?
Re: Book on proofs?
heres a simple one.
note: assume all sets nonempty.
def 1a: Suppose S is a set. S is bounded above if there exists an M such that for every x in S, x <= M.
def 1b: S is bounded below if there exists an L such that for every x in S, x >= L.
def 1c: S is bounded if S is bounded above and bounded below.
def 2: Suppose S is a set. The statement that W is a least upper bound of the set S means that: a) W is an upper bound of the set S, and b) if T is an upper bound of S, then T is less than or equal to W (T <= W).
theorem 1: Suppose S is a set with least upper bound q. If p is a least upper bound of S then p=q.
theorem 2: Suppose S is a set with least upper bound q, and U is the set such that p is in U if and only if p is an upper bound of S, then q is the greatest lower bound of U.
theorem 3: Suppose S is a set with least upper bound M. If p is a number such that p < M, then there exists an x in S such that p < x <= M.
these theorems are fairly basic first semester analysis, and each come from careful application of the definitions. You may assume ZFC or some other basic notion of sets. I can post the answers if there is any trouble.
Also to the op, you will learn how to write good proofs by writing proofs and defending them before professors and students. A book will often be a hinderance and poor substitute for training good proof writing. See the Moore Method of teaching on Wikipedia for proofs and for more general problem analysis and solution approach see Polya's Principles. Also Calculus III at the university I attended was vector and multivariable calculus, which required no proofs whatsoever.
romulox
note: assume all sets nonempty.
def 1a: Suppose S is a set. S is bounded above if there exists an M such that for every x in S, x <= M.
def 1b: S is bounded below if there exists an L such that for every x in S, x >= L.
def 1c: S is bounded if S is bounded above and bounded below.
def 2: Suppose S is a set. The statement that W is a least upper bound of the set S means that: a) W is an upper bound of the set S, and b) if T is an upper bound of S, then T is less than or equal to W (T <= W).
theorem 1: Suppose S is a set with least upper bound q. If p is a least upper bound of S then p=q.
theorem 2: Suppose S is a set with least upper bound q, and U is the set such that p is in U if and only if p is an upper bound of S, then q is the greatest lower bound of U.
theorem 3: Suppose S is a set with least upper bound M. If p is a number such that p < M, then there exists an x in S such that p < x <= M.
these theorems are fairly basic first semester analysis, and each come from careful application of the definitions. You may assume ZFC or some other basic notion of sets. I can post the answers if there is any trouble.
Also to the op, you will learn how to write good proofs by writing proofs and defending them before professors and students. A book will often be a hinderance and poor substitute for training good proof writing. See the Moore Method of teaching on Wikipedia for proofs and for more general problem analysis and solution approach see Polya's Principles. Also Calculus III at the university I attended was vector and multivariable calculus, which required no proofs whatsoever.
romulox
n/a
Re: Book on proofs?
quintopia wrote:Here's another one:
Prove that for all natural z, there exist x in {1...9} and y such that x + y = z and x = y (mod 9). Does it work for bases other than 9?
I'm pretty sure the answer is only odd ones. I can explain the why and then the how if necessary.
pollywog wrote:I want to learn this smile, perfect it, and then go around smiling at lesbians and freaking them out.Wikihow wrote:* Smile a lot! Give a gay girl a knowing "Hey, I'm a lesbian too!" smile.
 xixheartxyoux
 Posts: 31
 Joined: Wed Jul 30, 2008 4:58 pm UTC
 Location: Michigan
 Contact:
Re: Book on proofs?
At my school, we teach proof writing as its own class, which is different than most other universities. One of our professors wrote a book specifically for the course and it was the best money I've ever spent in my life. It goes through basic logic, direct proofs, proofs by contradiction, proofs by induction, and even a bit of set theory. Its called Mathematical Reasonsing by Ted Sundstrom. Its a little pricey, but I think it is definately worth looking into.
“The highest form of pure thought is in mathematics”Plato
Who is online
Users browsing this forum: No registered users and 7 guests