# Proof Question 2

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• January 15th 2008, 02:19 PM
TheMathsDude
Proof Question 2
http://common.replayers.com/temp/maths2.JPG

This is the second part of two questions that I could really do with some help with.

Any help with any part would be super!

The Maths Dude
• January 15th 2008, 02:49 PM
ThePerfectHacker
Let $f: A\mapsto B$ and $g: B\mapsto C$. Then $g\circ f : A\mapsto C$. If $f(x)=f(y)$ for $x,y\in A$ then $g\circ f(x) = g\circ f(y)$ thus $x=y$ since $g\circ f$ is injective, and thus, $f$ is injective.

The other problems is similar.
• January 15th 2008, 03:08 PM
Jhevon
Quote:

Originally Posted by TheMathsDude
http://common.replayers.com/temp/maths2.JPG

This is the second part of two questions that I could really do with some help with.

Any help with any part would be super!

The Maths Dude

(i) remember what it means to be injective

we say a function $f(x)$ is injective if and only if $f(a) = f(b)$ implies $a = b$

Proof:

Assume to the contrary that $(g \circ f)(x)$ is injective but $f(x)$ is not.

since $(g \circ f)(x)$ is injective, $(g \circ f)(a) = (g \circ f)(b) \implies a = b$, and since $f$ is not injective, we have $f(a) = f(b)$ and $a \ne b$.

but $(g \circ f)(x) = g(f(x))$

so $g(f(a)) = g(f(b)) \implies f(a) = f(b)$ as well

but that means we would have $f(a) = f(b)$ and $a = b$. A contradiction

QED

try to manipulate the definition of surjective to prove the others. you can find the definition here

EDIT: This is very similar to TPH's post. except he used a direct proof where I used contradiction. (direct proofs are generally preferred)
• January 15th 2008, 03:14 PM
ThePerfectHacker
Quote:

Originally Posted by Jhevon
(direct proofs are generally prefered)

Absolutely not. I challenge anyone in this forum to prove that there are infinitely many primes directly.

What is prefered is to not to use an indirect proof when the indirect proof is exactly identical to the direct proof. Like what happened here.
• January 15th 2008, 03:18 PM
Jhevon
Quote:

Originally Posted by ThePerfectHacker
Absolutely not. I challenge anyone in this forum to prove that there are infinitely many primes directly.

What is prefered is to not to use an indirect proof when the indirect proof is exactly identical to the direct proof. Like what happened here.

what i meant by that is that if both a direct and indirect proof exist, the direct proof is preferred--and it's professors that tell me this. in fact, there are entire bodies of mathematicians that hate indirect proofs with a passion
• January 15th 2008, 03:24 PM
ThePerfectHacker
Quote:

Originally Posted by Jhevon
what i meant by that is that if both a direct and indirect proof exist, the direct proof is preferred--and it's professors that tell me this. in fact, there are entire bodies of mathematicians that hate indirect proofs with a passion

I assume that has to do with one's philosophy on math*. There are some mathematicians that hate with a love indirect proof (though they do not deny them, just hate them). Also, there are some mathematicians that favor and existence proof over a constructive proof. And some mathematicians are even more extreme and perfer finitism, like the famous algebraist (Bow) Leopold Kronecker. I myself really do not bother myself with these things, I like existence proofs without any constructions, because all of these approaches work.

*)In particular his aesthetics.
• January 15th 2008, 03:44 PM
Jhevon
Quote:

Originally Posted by ThePerfectHacker
I assume that has to do with one's philosophy on math*. There are some mathematicians that hate with a love indirect proof (though they do not deny them, just hate them). Also, there are some mathematicians that favor and existence proof over a constructive proof. And some mathematicians are even more extreme and perfer finitism, like the famous algebraist (Bow) Leopold Kronecker. I myself really do not bother myself with these things, I like existence proofs without any constructions, because all of these approaches work.

*)In particular his aesthetics.

like you, i don't really like to bother wiuth these things. aesthetics is important to me to some extent, but not to the extent that i would write of a method of doing something or hate it with a passion. if it is proven to work, i'm fine with it. however, i don't know the poster's professor's outlook. he might be someone who hates using indirect proofs when a direct proof can be done, so i say, go with what's safe.

Aside: one of the things i like about math is that it doesn't matter what your professor's personal opinion is, if it's right and mathematically sound, he has to mark it right, regardless of his biases. this is not so with the arts, and even some of the sciences. but anyway, getting good grades in college is half about pleasing your professor, might as well practice on our math professors as well
• January 15th 2008, 04:07 PM
Plato
Quote:

Originally Posted by Jhevon
what i meant by that is that if both a direct and indirect proof exist, the direct proof is preferred--and it's professors that tell me this. in fact, there are entire bodies of mathematicians that hate indirect proofs with a passion

That my friend is just B.S.
Only a very small school of philosophers reject the rule of excluded middle.
Law of excluded middle - Wikipedia, the free encyclopedia
• January 15th 2008, 04:11 PM
Jhevon
Quote:

Originally Posted by Plato
That my friend is just B.S.
Only a very small school of philosophers reject the rule of excluded middle.
Law of excluded middle - Wikipedia, the free encyclopedia

"philosophers" not "mathematicians" huh? well, that kind of makes more sense

so the "law of excluded middle" covers proofs by contradiction?

a small school is still a whole school, right? :D
• January 15th 2008, 04:41 PM
topsquark
Quote:

Originally Posted by ThePerfectHacker
What is prefered is to not to use an indirect proof when the indirect proof is exactly identical to the direct proof. Like what happened here.

I really don't want to get in the middle of all this, but I just have to ask: If the indirect proof is exactly the same as the direct proof, then aren't they the same? In which case you can't say if it's one or the other?

-Dan
• January 15th 2008, 04:54 PM
Jhevon
Quote:

Originally Posted by topsquark
I really don't want to get in the middle of all this, but I just have to ask: If the indirect proof is exactly the same as the direct proof, then aren't they the same? In which case you can't say if it's one or the other?

-Dan

the ideas used were exactly the same, but the structure or presentation was different. things like "assume to the contrary" or "this leads to a contradiction" makes it seem unaesthetic to some people. proving something by contradiction seems unsavory to them somehow. it's like arguing for something right based on something wrong (that's not how i interpret it, but i assume they would)
• January 15th 2008, 05:30 PM
ThePerfectHacker
Quote:

Originally Posted by topsquark
I really don't want to get in the middle of all this, but I just have to ask: If the indirect proof is exactly the same as the direct proof, then aren't they the same? In which case you can't say if it's one or the other?

I agree with Jhevon an indirect proof is really a direct proof by the contrapositive. But for some reason it loses its elegance.

Maybe a bad analogy: Playing the 5th with an orchestra is much more elegant then listening it to be played by a band using synthensized instruments.

Quote:

Originally Posted by Jhevon
"philosophers" not "mathematicians" huh? well, that kind of makes more sense

Eventhough they are called philosophers over here, these are actually mathematicians. These type of philosophers actually know what they are talking about. For some reason mathematicians that do work in the foundations of math, set theory, logic, category theory, ... are sometimes called philosophers.
• January 15th 2008, 05:59 PM
Plato
Quote:

Originally Posted by Jhevon
"philosophers" not "mathematicians" huh? well, that kind of makes more sense

I dare say that I am the only member of the board who has been a NHF fellow in the philosophy of mathematics. There is a very small school of so-called intuitionalist who reject the law of excluded middle. This notion has been active in the ‘mathematics education’ community. It has produced a plethora of doctoral thesis in mathematics education.

Now this may by strictly my owe biases, but I personally do not know any active PhD level mathematician who accepts that position. The truth is: there are just so many other real problems in mathematics education it is lunacy go against a majority of mathematicians.
• January 16th 2008, 01:10 AM
Jhevon
we're starting to go so much off topic that we might have to move this thread to the "Philosophy of Math" forum :D it's a good talk though

did you get through the other problems ok, TheMathsDude?
• January 16th 2008, 01:13 AM
TheMathsDude
Finding it hard to manipulate the surjective definition to fit the previous examples written.

Any clues?
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last