Monday, September 15, 2008

Proofs and Even/Odd Functions

Here is the second part of my chat discussion. I have edited this some, but I hope the essence of the questions and answers.

[Student]: ok, so im still iffy on how to structure proofs, ill know the assumption (obviosly) and the conclusion, but I'm unsure how to structure the premises and justify them
[Professor]: Well, basic ideas include starting the proof with your assumptions.
These are the basic statements you know are true.
[Student]: right

[Professor]: The very last line of the proof should match the conclusion. (and it shouldn't appear earlier) The hard part is what comes in between :-)
[Professor]: But seriously, usually, you take a look at your conclusion and see what type of statement it requires.

[Professor]: If it is an equation that is needed, then you can usually start with one side of the equation and then see what you can put on the other side that you know must be true. (Usually using a definition or algebra)

[Professor]: Then you see how you can use your assumptions to create a statement that leads to your conclusion.

After turning to an actual problem, we started to get into more specifics. The problem was stated as: Suppose that f1 and f2 are odd functions. Prove that f1*f2 is an even function.

[Professor]: What is given knowledge?
[Student]: f1 and f2 are both odd and g1 and g2 are even
[Professor]: What is desired? (conclusion)
[Student]: f1 * f2 is even
[Professor]: What does it mean that f1 is odd?
[Student]: that f(-x) = -f(x)
[Professor]: Make the f into f1, and correct.
[Student]: ah ok ya
[Professor]: So in the actual proof, one line would be...
f1 is an odd function
[Professor]: The next line would interpret...
f1(-x) = -f1(x) for all x in domain of f1
[Professor]: Repeat these two lines for f2.
[Professor]: So far, we have simply restated facts based on the assumptions and our knowledge of odd functions.
[Student]: and that is all stuff that is under the given part? rite
[Professor]: In the proof, it doesn't belong to a "given" part per se, but the reason on the right hand side (if in tabular form) would be that the statement was "Given"
[Professor]: So our proof now has 4 statements.

[Professor]: Now, (scratch work) look at what you need to show: f1*f2 is even. What does that mean?
[Student]: ok ya i have no idea, i feel like it would involve one of the multiplicative properties involving f1 and f2 but i dont really know where to start
[Professor]: What does it mean if I said that G is an even function? g(x) = g(-x) My name was G, so it would be G(x)=G(-x).
[Professor]: But the name could be Brian: Brian(-x)=Brian(x). Voila! I [Brian] am even.
[Professor]: f1*f2 is the name of a function. And for f1*f2 to be even, you need: f1*f2(-x) = f1*f2(x)
[Professor]: It just happens that the name looks like a formula.
[Student]: theres noit a step in between there?
[Student]: to justify how multiplying the functions is ok
[Professor]: Well, there are still steps. But we need to know what we are aiming for.
[Student]: ah
[Professor]: You know what f1 and f2 are. They are odd functions. But exactly what is this new function that we call f1*f2?
[Student]: idk f1(x) * f2(x)
[Professor]: Exactly!
[Student]: or f1(-x)
[Professor]: No
[Student]: * f2(-x)
[Student]: no ok
[Professor]: So we know f1*f2(x) = f1(x)*f2(x)
[Student]: yep
[Professor]: And it looks like you were in the middle of the thought: f1*f2(-x) = f1(-x)*f2(-x)
[Student]: ya
[Professor]: Okay, things are starting to come together.
[Student]: sort of
[Professor]: We want to show f1*f2(-x)=f1*f2(x)
[Student]: substitution?
[Professor]: Yep. Back to the proof. We need to use substitution to get our final result. But we do it one step at a time.

[Professor]: I'll type the left hand side, you type the right hand side.
[Professor]: f1*f2(-x) = ?
[Student]: f1(-x) * f2(-x)
[Professor]: Good. But f1(-x) = ? and f2(-x) = ?
[Student]: f1(x) * f2(x)
[Student]: oh
[Professor]: And finally, f1(x)*f2(x) = ?
[Student]: f1*f2(x)
[Professor]: Precisely. Putting those together, we now know f1*f2(-x) = f1*f2(x).
[Professor]: And that means ...
[Professor]: f1 * f2 is even
[Professor]: Q.E.D. :-)
[Student]: sooo i guess i then assemble all of those steps or just some of them
[Professor]: You can leave out the parts that I said belonged as scratch work.
[Professor]: There were four lines associated with the given information. Then I said "back to the proof" and there were probably four more lines. That is the proof.
[Student]: ic ok
[Student]: ugh, this is def not my fav stuff, i cant believe i haven't learned this before

In summary, here is our proof:
f1 is an odd function
f1(-x) = -f1(x) for x in domain
f2 is an odd function
f2(-x) = -f2(x) for x in domain
f1*f2(-x) = f1(-x) * f2(-x)
= (-f1(x))*(-f2(x))
= f1(x)*f2(x)
= f1*f2(x)
So f1*f2(-x) = f1*f2(x) for x in domain
f1*f2 is an even function

Now, back to the discussion. Another problem dealt with composition. That is, students were to prove: If f1 is an odd function and g1 is an even function, then g1•f1 is an even function. Here is where part of that discussion went.

[Student]: so how do the g1(f1(x)) differ, i guess proving that f1(x) is odd, and then proving then that g1(x) is odd because of f1(x)?
[Professor]: One key point is that the definition of odd or even --- f(-x) = -f(x) and g(-x)=g(x) --- is that the x is simply a place-holder and the same statement would be true regardless of what is in the place of the x.
[Professor]: So for example f(-(x+2)) = -f(x+2), where the "x" was actually the formula x+2.
[Student]: right
[Professor]: Now, be more specific on your question related to composition.
[Student]: so once i prove that f1 is even then it would be the same justification for g1
[Professor]: Careful! f1 is odd (from the given information), so you can't prove it is even.
[Student]: well, opposite justification
[Student]: I'm still not sure of the question.
[Professor]: g1 alone is known to be even. There is nothing to prove about that.
[Student]: ok
[Student]: timeout, so all id have to do is justify g1 as being even regardless of f1?
[Professor]: Why? What are your steps?
[Professor]: And what are you trying to prove?
[Student]: so its given that g1 is even and f1 is odd and we're trying to prove that g1(f1(x)) is even
[Professor]: Technically, g1•f1 is even.
[Professor]: g1(f1(x)) is a value, not a function.
[Professor]: So you need to show g1•f1(-x) = g1•f1(x).
[Student]: wait im confused
[Student]: ok
[Student]: i get it
[Student]: couldnt you just subsitute -x for f1(-x)
[Professor]: No for what you said. f1(-x) and -x are different, so they don't substitute.
[Professor]: But I don't think that is what you were thinking. Try to restate.
[Student]: you could justify g1(f1(x)) = g1(f1(x)) with g(x)=g(-x)
[Student]: -f1(x)*
[Professor]: I think you're on the right track. But be careful that you go step by step.
[Professor]: What are all the steps?
[Professor]: I'll start it off... g1•f1(-x) = ?
[Student]: thats where im confused, do you need a a step for that?
[Professor]: Yes. You must relate the function (g1•f1) to the rest of the formulas.
[Student]: g1(f1(-x))= g1(f1(x) )
[Professor]: What justifies that? The -x belongs to f1, not g1
[Student]: g1(-f1(x)) def of odd fcn
[Professor]: So don't skip that step
[Student]: so whats after that then?
[Professor]: Well, why don't you summarize the statements so far. Start again with: g1•f1(-x) = ...
[Student]: g1(f1(-x)) = g1(-f1(x)) b/c of the def of odd fcns
[Professor]: Very good. Now, what does g1 do when you have g1(-[anything])?
[Student]: g1(-x)=-g1(x) ? but that would make it odd
[Professor]: So use the fact that g1 is even. g1(-x)=?
[Student]: g1(x)
[Professor]: So g1(-U) = g1(U) or g1(-f1(x)) = g1(f1(x))
[Student]: k
[Professor]: It doesn't matter what appears.
[Professor]: g1(-[stuff]) = g1([stuff])
[Professor]: So you left off at: g1 o f1(-x) = g1(f1(-x)) = g1(-f1(x)) = ... (finish it off)
[Student]: g1(-f1(x))=g1(f1(x))
[Professor]: And how does that relate to g1•f1?
[Student]: g1(f1(x)) = even
[Professor]: not equal even. g1(f1(x)) = g1• f1(x).
[Professor]: Recall, you are working with the function g1•f1. You need to show g1•f1(-x) = g1•f1(x).
[Student]: i just got a little confused
[Student]: whats the diff between g1(f1(x)) = g1•f1(x)
[Student]: ah i c nev mind
[Professor]: same value but only g•f can be called the name of the function
[Student]: ok
[Student]: so g1•f1(x) = g1•f1(-x)
[Professor]: That would be the final line to show that g1•f1 is an even function.
[Student]: ok that makes sense

And that leads us to our second proof:
f1 is an odd function
f1(-x) = -f1(x) for x in domain
g1 is an even function
g1(-x) = g1(x) for x in domain
g1•f1(-x) = g1(f1(-x))
= g1(-f1(x))
= g1(f1(x)
= g1•f1(x)
So g1•f1(-x) = g1•f1(x) for x in domain
g1•f1 is an even function

Do you know how to do the justifications of each line now?

Domain and Codomain

I had a nice chat this afternoon with one of my students. The first topic had to do with the notation f : D→S. Here is what we said:

hi prof walton, i have a quick question
Shoot (but don't hurt me.)
haha, ok so i am under the impression that when functions
say f: x → x that means that the domain and the codomain
are the same but the ranges can be different correct?

The codomain (after arrow) lists the type of numbers
that might be values in the output, while the domain
(before arrow) lists all of the numbers that are in the
list of potential inputs. The range is the list of numbers
that actually are outputs. Is this the question?

yep, so the range is a sub"field" of the codomain rite
it lists all possibles while the range is what numbers
are in the function ?

subset instead of sub"field". Otherwise, yes.
haha ya i was lookin for that word
The cheapest answer for codomain would be simply R
(all real numbers). If the codomain is listed as something
more specific, that helps us understand the function better,
but we still might skip some of the numbers in the set.
ic, so when im looking at f and g that have the same
codomain, that then would not imply that f(g) = g(f)
because the ranges could be different?
or is
f(g) being = to g(f) relational to the domain only
Equality of functions requires that they have the same
domain and the same values at every point in that
If the domain is different, then the functions
must not be equal.
If the functions have different
values for any point, then the functions are not equal.

so d → s just means that the domain could produce
these outputs right?

That's right. The outputs must be somewhere in the
list known as S.
And the inputs only make sense if they
are in D.

but s just means possible outputs because its the codomain rite
Yes, because it is the codomain (after arrow)
rite rite rite, gotcha, this stuff is weird

Monday, September 8, 2008

Fun with Functions

Cryptography is an interesting application of functions. A cipher allows you to take text (for example) and encrypt it into a new form of information that can then be transmitted. Most children learn a particularly simple cipher that is called a substitution cipher. Such a cipher does a direct translation of letter for letter. Below is a simple example, motivated by the "stage-appearance" of the letters in the phrase "The quick brown fox jumps over the lazy dog."

Other simple ciphers include shifting the alphabet a fixed number of letters or reversing the alphabet.

If we think of encrypting a message as being a function from character sequences to new character sequences, then we might imagine applying two different encryptions one after the other. This is function composition. Or we might want to decrypt a message. This is applying the inverse function. In particular, note that for an encryption method to be useful, the inverse must exist. That is, the function must be one-to-one.

Here is a message that I constructed using the QUICKBROWN cipher (above) followed by a shift cipher where an A becomes an R. Have fun!