mm-2939 ==== Subject: Re: proof about 1-1 function This is false as stated. It needs to be quantified before it is true .. > f is a 1-1 function if and only if for all subsets A and B of > dom(f), f(A/B)=f(A)/f(B). Ok, there seems to be slight mistake in my book (problem is copied as-is). .. > This does not make sense. f(A) is a set, namely, a subset of the > codomain of f. It is not a function, so you cannot talk about the > domain of it. What you mean is: True. Actually I saw the problem in proof but I just didn't know how to > So, take the correct statement, which I gave above. You assume that > WHENEVER you have two subsets of the domain A and B, you will have > f(A/B) = f(A)/f(B). > Let x and y be elements such that f(x)=f(y). What can you say about > {x} and {y}? About f({x}) and f({y})? I'll try. Assume f(A/B)=f(A) / f(B). Take arbitrary x and y (in A/B) for which f(x)=f(y). Since given equality holds for every subset of A and B it must hold for subsets {x} and {y}, hence x=y because otherwise f(emptyset)=f(x) for all x (=constant function). So f is 1-1. ==== Subject: Re: proof about 1-1 function days. My association with the Department is that of an alumnus. >>Prove: f(A n B) = f(A) n f(B) iff f is 1-1 function. >> This is false as stated. It needs to be quantified before it is true >> f is a 1-1 function if and only if for all subsets A and B of >> dom(f), f(A/B)=f(A)/f(B). >Ok, there seems to be slight mistake in my book (problem is copied >as-is). Or perhaps it is part of a longer exercise, and that exercise has some underlying quantification? Or perhaps it is not an if and only if statement. Note that if f is 1-1 then you get the result for any specific A and B. >> Let x and y be elements such that f(x)=f(y). What can you say about >> {x} and {y}? About f({x}) and f({y})? >I'll try. >Assume f(A/B)=f(A) / f(B). Take arbitrary x and y (in A/B) for which >f(x)=f(y). Since given equality holds for every subset of A and B it >must hold for subsets {x} and {y}, hence x=y because otherwise >f(emptyset)=f(x) for all x (=constant function). The for all x is wrong, as is the parenthetical comment. You do NOT have a constant function. You are only talking about the value of f at the points x and y, and x and y are already chosen so you do not get to quantify them retroactively with the last sentence of your proof. Simply, since f({x})/f({y}) is nonempty, it follows that f({x}/{y}), hence {x}/{y} is nonempty. And from that you get x=y. Thus, if f(x)=f(y), then x=y, which proves f is one-to-one. -- ' ==== Subject: Re: proof about 1-1 function as-is). > Or perhaps it is part of a longer exercise, and that exercise has some > underlying quantification? copy as I incorrectly stated. It seems I translated it from english and then back to english instead of using the original form. It says (this time literally :): Prove that f satisfies the condition f(A/B)=f(A)/f(B) for any A and B if and only if f is a 1-1 function My book has also a solution but I wanted to make it different way. There is no quantification on preceeding exercises explicitly mentioned but some quantification may exist in their solutions (I skipped 10 out of 32). I don't, however, see any difference... (Maybe I should concentrate on english instead of set theory :) > The for all x is wrong, as is the parenthetical comment. You do NOT > have a constant function. You are only talking about the value of f at > the points x and y, and x and y are already chosen so you do not get > to quantify them retroactively with the last sentence of your > proof. Simply, since f({x})/f({y}) is nonempty, it follows that > f({x}/{y}), hence {x}/{y} is nonempty. And from that you get > x=y. Thus, if f(x)=f(y), then x=y, which proves f is one-to-one. Ok, I see your point. It looks like I always make problems harder than they are and then somehow manage to get confused. input. ==== Subject: Re: proof about 1-1 function >>Ok, there seems to be slight mistake in my book (problem is copied >>as-is). >> Or perhaps it is part of a longer exercise, and that exercise has some >> underlying quantification? >copy as I incorrectly stated. It seems I translated it from english and >then back to english instead of using the original form. >It says (this time literally :): Prove that f satisfies the condition >f(A/B)=f(A)/f(B) for any A and B if and only if f is a 1-1 function >My book has also a solution but I wanted to make it different way. >There is no quantification on preceeding exercises explicitly mentioned >but some quantification may exist in their solutions (I skipped 10 out >of 32). What? The statement for any A and B is in fact a universal quantification on the subsets A and B. What you write now is hold for ANY choice of subsets A and B, not just for a fixed choice. -- ' ==== Subject: Re: proof about 1-1 function quantification on the subsets A and B. What you write now is > hold for ANY choice of subsets A and B, not just for a fixed choice. I have got used to no quantification=universal quantification (I know that strictly speaking this is not the case). This is why I didn't get your comment on this first. ==== Subject: Matrix inversion I have a little problem: I have an nxn matrix A what I want to invert. A^-1 * A = I A^-1 * (A * A^T) = A^T A^-1 * (L * L^T) = A^T A^-1 * L = A^T * L^T^-1 A^-1 = A^T * L^T^-1 * L^-1 L is a lower triangular matrix such that (L * L^T) = (A * A^T). We get L with the use of Cholesky decomposition. It needs a symmetric, positive definite matrix to decompose; and multiplying a matrix with its own transpose always results with such. Operation count: A * A^T -> 1/2 * n^3 (we need only the half of the matrix) cholesky decomposition: 1/6 * n^3 lower triangular inverting: 1/6 * n^3 A^T * L^T^-1 -> 1/2 * n^3 A^T * L^T^-1 * L^-1 -> 1/2 * n^3 total operation count: 11/6 * n^3 ~ 2 * n^3 -> BAAAAD! This is the problem! To my knowledge this algorithm can be done with about 1 * n^3 operation counts, but I don't know how. Can anyone help? --- And another problem: how can I decompose an nxn matrix A into a symmetric matrix and any other component that is easily invertible, with few operations, and great stability? ==== Subject: Re: binominal >> (2^n k) <- it's binomial theorem, not a fraction. >> How to prove that it is odd only for k=0 and k=2^n? > Here is a kind of silly and not entierly strict solution. > (2^n choose k) is the coefficien before x^k in (x + 1)^(2^n) > it's true when n = 0 for obvious reasons. > Assume it's true for n=p. > (x + 1)^(x^(p+1)) = ((x + 1)^(2^p))^2 = > The coefficients in the new polynomial will be a sum of products of the > coefficients from the previous polynomial, since all of those coefficients > were either 1 or even the sum will be even. > It might be possible to formalize the above reasoning, but I'm sure there is > a better way. Your proposal works. You're simply iterating the p p n n p p Iterating yields (x + 1) = x + 1 (mod p) n n [ p ] So 0 < i < p -> | | = 0 (mod p) [ i ] i follows by comparing the coefficients of x . More generally see the FROBENIUS ENDOMORPHISM http://en.wikipedia.org/wiki/Frobenius_automorphism --Bill Dubuque ==== Subject: Re: largest cube inside sphere > I have a what hopefully is a rather simple problem, > that has stumped two of my teachers and my boss. > I have a a sphere of a given size 24 inside > diameter. I'm simply trying to mathematically find > out what is the largest cube that can fit inside a > sphere of a Given Diamter. > This is for a fabrication project and I have a > relatively true sphere, and I need to build a fitting > cubic box frame to go inside (1/8 tolerance). I've > tried using a descriptive geometry route and still > no luck. > Any tips or pointers the most I got was taking an> angle off of the diagnol but that might be how to > solve for the largest square inside a circle (which > doesn't help) It should be clear that largest cube will be symmetric about the center of the sphere (if not, take the larger side and reproduce it on the other side of the center of the sphere- that gives you a larger cube). If one side of the cube has length x then the diagonal of a side as length x times sqrt(2) (Pythagorean theorem: 2 sides form legs of right triangle with diagonal as hypotenuse: d^2= x^2+ x^2= 2 x^2 so d= sqrt(2) times x). Now use the diagonal of the bottom of the cube along with one vertical side to form legs of a right triangle having diagonal of the entire cube as hypotenuse: D^2= x^2+ d^2= x^2+ 2x^2= 3x^2 and so D= sqrt(3) times x. Since that diagonal is twice the radius of the circle, taking R to be the radius, sqrt(3)x= R/2 so x= R/2(sqrt(3)) which can also be written x= sqrt(3)R/6. ==== Subject: Re: zero divided by zero n/0 is an arithmetic concern and not a concern of 'limits'. How we define x/y determines what x/0 means. If we define x/y as (the z: x=y*z), then x/0 does not exist for all x, including x=0. (because (the z: x=y*z) is not unique) That is to say, 1/0 and 0/0 are defined but, they do not exist. If we say: ~(y=0) -> x/y = (the z: x=y*z), then x/0 is not defined for any x, including x=0. That is to say, 1/0 and 0/0 are not defined. Either way, 1/0 and 0/0 are not sensible terms! ==== Subject: Online Voting Formula Problem [Question] Here is the site: http://www.helpastudent.com People post their profiles and general public votes Yes, No and Not Sure. What should be the best formula to calculate the scores? Requirements: Score should be from 0 to 10 Formula should take into consideration a Number of Referrals Scores should look good - as a modified Gaussian Distribution, but shifted to the right, so that the mean is somewhere in 6-7 range [Difficulty] Well, most difficult are the factors...Scores should look good for most people (in the range of 5-9), scores should represend the most likable and most active students (i.e. students inviting their friends to participate should get credit). [Thoughts] Here is what I have in mind: Score(Ny, Nn, Nns, r, R) = Ny/(Ny + F(Nn+Nns)) F = F(r,R) Ny = Number of Yes Votes Nn = Number of No Votes Nns = Number of Not Sure Votes r = Number of Referrals R = Max Referrals for Gender Type in entire Population