2.3: Interesting Problems in 2.3 Part A
Wow, this is a long set. This is one of those homework assignments you get in college where you think “only ten problems? I could do that?” and then all the problems are multiple part and require you to have worked even problems.
As I’ve mentioned earlier, discrete is not an area I’m comfortable in, so a lot of this is learning for me. As a result, I’m gonna work more problems on the blog. In real life, I work all the odd problems that I can’t immediately think of a solution for.
LET’S DIG IN.
Determine whether f is a function from the set of all bit strings to the set of integers if
a) f(S) is the position of a 0 bit in S.
b) f(S) is the number of 1 bits in S.
c) f(S) is the smallest integer i such that the ith bit of S is 1 and f(S)=0 when S is the empty string, the string with no bits.”
Christ, that was set up like a comic. Easy, easy, WAY HARDER. But, perhaps not as hard as it seems at first glance.
First, remember bit strings look like this: 010101001110010100010100101010, etc. Each digit is a “bit.”
So, a good way to get intuitive is to draw a set on the left that consists of all bit strings: 0, 1, 01, 10, 000, 001, 010, 100, 011, 110, 111, and so on. On the right, write the set of all integers. I just did -3 through +3. Now, start mapping. You’ll not that for (a) you quickly start getting preimages that map to more than one image. In fact, any time you have more than one 0, you have to map to multiple things in the second set. So, this is clearly not a function. In fact, as the bit strings get larger, pretty much all of them map to multiple images. NO GO.
For (b) we draw out the same left and right stuff. We note that each bit string identifies with just one element on the right. Why? Because it’s a sum of a bunch of ones. If you can figure out a way to sum a bunch of ones to more than one result, you can create an infinity machine and the universe will end. So, it’s not allowed. You may also note that it is common for two bit strings to point to the same integer. This is fine – it just means the function isn’t 1-to-1. BUT, it’s still a function. There is no place where f maps to a undefined and there is no place where an element in S maps to more than one element of the codomain. You are safe.
For (c), let’s parse that sentence. Mathematicians have a way of making simple things complex. “f(S) is the smallest integer i such that the ith bit of S is 1 and f(S)=0 when S is the empty string, the string with no bits.” This is saying something like… suppose you have a bit string. And suppose the first position in it is “bit 1,” and second position contains “bit 2,” the third “bit 3” and so on. Each of those bits is a 0 or a 1. For each bit string, find the 1 in the lowest position. The number value of the position is the element of the codomain to which that bit string maps. So, for example, for a given bit string, if the first 1 you encounter is in position 3, that bit string maps to 3 in the codomain.
OKAY, now that you understand, you must ask… is it a function? Well, draw it out. Similar to (a) it is not one-to-one, since (for example) 1 and 01 map to the same number (1). BUT, you notice something that nags you. What do I do with 0 or 00 or 0000000000? They are undefined, so you’ve got a bunch of preimages with no place to go. Thus, it’s not a function. If you were to define sets containing no 1s as equal to 0, that’d do it. BUT, you’ve only defined the empty string to equal 0, and the bit string 0000000 is not empty.
10 and 11
I’m combining those two into one uberquestion:
“Determine whether each of these functions from [a,b,c,d] to itself is one-to-one and/or onto.”
a) f(a)=b, f(b)=a, f(c)=c, f(d)=d
b) f(a)=b, f(b)=b, f(c)=d, f(d)=c
c) f(a)=d, f(b)=b, f(c)=c, f(d)=d
The easiest thing here is just to draw out your maps with a,b,c, and d on the left and right. Remember, 1-to-1 and onto are like sex parties with guests and hosts, with the preimages being guests, the images being hosts, and the function indicating that they got to hook up.
At a 1-to-1 sex party, only monogamous pairing is allowed, even if it means certain hosts get left out.
At an onto part, EVERYONE gets laid, even if it means more than one guest had sex with the same host.
That is, 1-to-1 is a bit more of a prudish sex party. Onto is where the kinky stuff happens.
The combination is called bijection, and it’s when everyone has sex, but the whole party is monogamous pairs.
In the case of problem (a), each preimage gets with exactly one image, and every image is mapped to (or, if you will, sexed up). Thus, it’s a bijection – it’s one-to-one and onto.
In problem (b) it’s not one-to-one OR onto. It’s the WORST kind of sex party. One person gets a threesome while another is left out entirely!
In problem (c), it’s once again neither. Mr. a gets left out, while Mr. d gets double teamed.
“Determine whether each of these functions is a bijection from R to R
a) f(x) = 2x+1
b) f(x) = x^2 +1
c) f(x) = x^3
d) f(x) = (x^2 + 1)/(x^2 + 2)”
In other words, for each function, make sure you can map from R to everything in R, and make sure that you don’t have a situation where one preimage maps to 2 or more images.
For problem (a), it’s pretty clearly a bijection. Visually, it’s a line that goes up. So you can’t draw a horizontal line that touches more than one value of f(x). And you can clearly get to every real number using that line.
For (b) it’s clearly not a bijection. Any time you have a squared x, you can have preimages of opposite sign map to the same image.
For (c), it’s a bijection. To map to another number, you just start with the cube root of that number.
For (d) you might get tripped up like I did. Since I’m working problems, I automatically tried to see if I could simplify this to a polynomial that’d be easier to work with. But, it’s actually not necessary. Because the numerator and denominator are each squared and added to, both have to be positive. So, you can’t map to the negative numbers in R. Thus, f(x) is not onto, and thus f(x) is not a bijection.
“Let f: R→R and let f(x)>0 for all x∈R. Show that f(x) is strictly decreasing if and only if the function g(x) = 1/f(x) is strictly increasing.”
I believe there’s actually a fairly simple calculusy way to solve this. The derivative of 1/x with respect to x is going to be negative. So, you can show that it’s is decreasing everywhere, so it has to be largest as you approach 0.
BUT, I’m guessing that’s not what they want. So, this becomes one of those problems that is annoyingly simple. The book provides a proof that basically says that if you know f(x) is shrinking, and you know dividing by a smaller number results in a larger output assuming the numerator is held constant, it’s clear that g(x) must be growing. And, you can just prove that the other way around, thereby getting yourself an “if and only if.” I have to admit, these sorts of proofs always feel weird to me. The more obvious the truth of something, the harder it is to show it’s true in math!
“If f and f∘g are onto, does it follow that g is onto?”
This one tricked me. At first, it seems like a definite yes. f maps A to everything in B. f∘g maps everything in A to everything in C. Where’s the room for a gap?
Well, suppose g maps from A to B. And suppose it’s not onto – that is, some elements are not mapped to. But, of course, everything in A is mapped to SOMETHING. Then, you map from B to C with f and it IS onto. So, by this means, everything in A gets mapped to something in C. It sounds a little weird, but draw it out and it makes perfect sense. The important thing to remember is that in f∘g, the g executes first.
OKAY, I’m gonna cut it off there for this post. We’ll round things out next time, and then go into summations, which will conveniently elucidate our calculus stuff.
Next stop: Interesting Problems in 2.3 Part B