Official TSR Mathematical Society
Scroll to see replies
J.F.N
I see what you're saying, but that is counter-intuitive. I can provide a proof to show that L is not surjective.
can i see this proof ?
evariste
can i see this proof ?
L:X-->F(X)
Let us assume that all a in X goes to A in F(X). That is, L(a)=A. The key is to construct a set in which a is in X but a is not in L(a). Let this set be Y={a in X | {a} intersect L(a) = 0}. Obviously, Y is a subset of X. Hence, Y is an element of F(X) (recall that the elements of F(X) are sets themselves). If the map was a surjection, then there must be an element y in F(X) such that L(y)=Y. Assume that this element y is in Y. Y has the elements that are not in its associated set, hence y is not in L(y)=Y... contradiction. (Take a moment to see why this is true.. here's an example: if X=(1,2), then F(X)={0,{1},{2},{1,2}}. If, WLOG, 1 goes to {2} and 2 goes to {1,2}, then 1 is not in our set Y, but 2 is.} On the other hand, assume y is not in Y. But Y contains all the elements that are not in its associated set.. so Y contains y! Contradiction again. This means that L is not a surjection. Again, this makes intuitive sense aplenty: no surjection, and hence no bijection, and hence F(X) has larger cardinality than X.
Cantor was a very clever man 
for any set X define the map X->P(X) by x in X maps to a set containing x in P(x)
ie x maps to {x}.
this is required injection.
for any set X define the map X->P(X) by x in X maps to a set containing x in P(x)
ie x maps to {x}.
this is required injection.
Here's an interesting question I got on my math exam yesterday.
The general linear group, GL_n, is defined as follows:
GL_n(F)={A in M_n(F) s.t. A is invertible}
(If the notation is unclear, F is our field, M_n(F) is the set of matrices with nxn entries in F, and A invertible --> ad-bc=/=0.)
If F=Z/pZ, what is |GL_n(Z/pZ)| for n=1,2,3? I only managed to do n=1,2 during the exam, and did n=3 afterwards. If you need a hint, let me know. Enjoy.
The general linear group, GL_n, is defined as follows:
GL_n(F)={A in M_n(F) s.t. A is invertible}
(If the notation is unclear, F is our field, M_n(F) is the set of matrices with nxn entries in F, and A invertible --> ad-bc=/=0.)
If F=Z/pZ, what is |GL_n(Z/pZ)| for n=1,2,3? I only managed to do n=1,2 during the exam, and did n=3 afterwards. If you need a hint, let me know. Enjoy
.J.F.N
Here's an interesting question I got on my math exam yesterday.
The general linear group, GL_n, is defined as follows:
GL_n(F)={A in M_n(F) s.t. A is invertible}
(If the notation is unclear, F is our field, M_n(F) is the set of matrices with nxn entries in F, and A invertible --> ad-bc=/=0.)
If F=Z/pZ, what is |GL_n(Z/pZ)| for n=1,2,3? I only managed to do n=1,2 during the exam, and did n=3 afterwards. If you need a hint, let me know. Enjoy.
The general linear group, GL_n, is defined as follows:
GL_n(F)={A in M_n(F) s.t. A is invertible}
(If the notation is unclear, F is our field, M_n(F) is the set of matrices with nxn entries in F, and A invertible --> ad-bc=/=0.)
If F=Z/pZ, what is |GL_n(Z/pZ)| for n=1,2,3? I only managed to do n=1,2 during the exam, and did n=3 afterwards. If you need a hint, let me know. Enjoy
.for any n,p
GL_n(F_(p)) has (p^n-1)(p^n-p)(p^n-p^2)....(p^n-p^(n-1)) elements.
this is seen by considering the columns. in the first column we can have any of the combinations of the p elements except 0. for the second we exclude any multiple of the first column,etc,etc.
evariste
for any n,p
GL_n(F_(p)) has (p^n-1)(p^n-p)(p^n-p^2)....(p^n-p^(n-1)) elements.
this is seen by considering the columns. in the first column we can have any of the combinations of the p elements except 0. for the second we exclude any multiple of the first column,etc,etc.
GL_n(F_(p)) has (p^n-1)(p^n-p)(p^n-p^2)....(p^n-p^(n-1)) elements.
this is seen by considering the columns. in the first column we can have any of the combinations of the p elements except 0. for the second we exclude any multiple of the first column,etc,etc.
Wow. Nice work.
(2) Find all polynomials P(x) which satisfy the equality: P(a-b) + P(b-c) + P(c-a) = 2P(a+b+c) for all real numbers such that ab+bc+ca=0.
Solution:
Set a=b=c=0
P(0) + P(0) + P(0) + 2.P(0)
==> P(0) = 0
Polynomial is of form: a_1.x + a_2.x^2 + .... + a_n.x^n
Set b=c=0:
P(a) + P(0) + P(-a) = 2.P(a)
Now P(0) = 0
==> P(a) + P(-a) = 2.P(a)
==> P(-a) = P(a)
Hence our function is even of form:
a_1.x^2 + .... + a_n.x^n
Let the highest power of our polynomial be n:
Set a=6, b=3, c=-2
P(3) + P(5) +P(-8) = 2.P(7)
==> P(3) + P(5) +P(8) = 2.P(7)
match values of power n:
3^n + 5^n + 8^n = 2.7^n
n=2 and n=4 works.
Claim: 3^n + 5^n + 8^n > 2.7^n for all n>5 (n is even)
Proof: 3^n + 5^n + 8^n > 8^n
Therefore, it suffices to show: 8^n > 2.7^n
For n=6 : 8^6 > 2.7^6 is true
Assume true for n=k
==> 8^k > 2.7^k
==> 8.8^k > 8.2.7^k
==> 8^k+1 > 16.7^k
==> 8^k+1 > 16.7^k > 14.7^k
==> 8^k+1 > 14.7^k
==> 8^k+1 > 2.7.7^k
==> 8^k+1 > 2.7^k+1
Hence true for all n>5.
Therefore the highest power of our polynomial is 4 and is of form:
a.x^2 + b.x^4 , where a,b are real scalar coefficients
[Check that this works by direct substitution]
Hence infinitely many polynomials of form a.x^2 + b.x^4 satisfy the given condition.
NB: This is somewhat shabby proof, but gets the picture across. A more rigorous proof involves the use of vector spaces.
Solution:
Set a=b=c=0
P(0) + P(0) + P(0) + 2.P(0)
==> P(0) = 0
Polynomial is of form: a_1.x + a_2.x^2 + .... + a_n.x^n
Set b=c=0:
P(a) + P(0) + P(-a) = 2.P(a)
Now P(0) = 0
==> P(a) + P(-a) = 2.P(a)
==> P(-a) = P(a)
Hence our function is even of form:
a_1.x^2 + .... + a_n.x^n
Let the highest power of our polynomial be n:
Set a=6, b=3, c=-2
P(3) + P(5) +P(-8) = 2.P(7)
==> P(3) + P(5) +P(8) = 2.P(7)
match values of power n:
3^n + 5^n + 8^n = 2.7^n
n=2 and n=4 works.
Claim: 3^n + 5^n + 8^n > 2.7^n for all n>5 (n is even)
Proof: 3^n + 5^n + 8^n > 8^n
Therefore, it suffices to show: 8^n > 2.7^n
For n=6 : 8^6 > 2.7^6 is true
Assume true for n=k
==> 8^k > 2.7^k
==> 8.8^k > 8.2.7^k
==> 8^k+1 > 16.7^k
==> 8^k+1 > 16.7^k > 14.7^k
==> 8^k+1 > 14.7^k
==> 8^k+1 > 2.7.7^k
==> 8^k+1 > 2.7^k+1
Hence true for all n>5.
Therefore the highest power of our polynomial is 4 and is of form:
a.x^2 + b.x^4 , where a,b are real scalar coefficients
[Check that this works by direct substitution]
Hence infinitely many polynomials of form a.x^2 + b.x^4 satisfy the given condition.
NB: This is somewhat shabby proof, but gets the picture across. A more rigorous proof involves the use of vector spaces.
Euler
(3) If X is an infinite set and F(X) is the set of finite subsets of X, is there an injection from F(X) to X?
J.F.N
L:X-->F(X)
Let us assume that all a in X goes to A in F(X). That is, L(a)=A. The key is to construct a set in which a is in X but a is not in L(a). Let this set be Y={a in X | {a} intersect L(a) = 0}. Obviously, Y is a subset of X. Hence, Y is an element of F(X) (recall that the elements of F(X) are sets themselves). If the map was a surjection, then there must be an element y in F(X) such that L(y)=Y. Assume that this element y is in Y. Y has the elements that are not in its associated set, hence y is not in L(y)=Y... contradiction. (Take a moment to see why this is true.. here's an example: if X=(1,2), then F(X)={0,{1},{2},{1,2}}. If, WLOG, 1 goes to {2} and 2 goes to {1,2}, then 1 is not in our set Y, but 2 is.} On the other hand, assume y is not in Y. But Y contains all the elements that are not in its associated set.. so Y contains y! Contradiction again. This means that L is not a surjection. Again, this makes intuitive sense aplenty: no surjection, and hence no bijection, and hence F(X) has larger cardinality than X.
Let us assume that all a in X goes to A in F(X). That is, L(a)=A. The key is to construct a set in which a is in X but a is not in L(a). Let this set be Y={a in X | {a} intersect L(a) = 0}. Obviously, Y is a subset of X. Hence, Y is an element of F(X) (recall that the elements of F(X) are sets themselves). If the map was a surjection, then there must be an element y in F(X) such that L(y)=Y. Assume that this element y is in Y. Y has the elements that are not in its associated set, hence y is not in L(y)=Y... contradiction. (Take a moment to see why this is true.. here's an example: if X=(1,2), then F(X)={0,{1},{2},{1,2}}. If, WLOG, 1 goes to {2} and 2 goes to {1,2}, then 1 is not in our set Y, but 2 is.} On the other hand, assume y is not in Y. But Y contains all the elements that are not in its associated set.. so Y contains y! Contradiction again. This means that L is not a surjection. Again, this makes intuitive sense aplenty: no surjection, and hence no bijection, and hence F(X) has larger cardinality than X.
I feel that a correction to this is due. What I missed in Euler's question was that F(X) is the set of finite subsets of X. My proof of the lack of a surjection is for the power set of X, i.e. the set of all subsets, not only the finite ones. There is, in fact, an injection and a surjection between X and the set of finite subsets of X. It's easy to find this surjection from naturals to finite subsets of naturals -- first you order all the size-zero subsets of naturals, then you order all the size-one subsets, then all the size-two subsets, and so on. And the set of size-N subsets of natural numbers is countable for any N, using any sort of "diagonal" counting method.
Question (1)
A cosmonaut is walking in space next to a space station orbitting the Earth. She throws the lens cap of her movie camera directly towards the Earth. Where does it go? Justify your answer.
If you argue that the cosmonaut is moving at around 25000 mph (Orbital velocity - Kepler's 3rd law) in an elliptical orbit with the centre of the earth at one focus of the ellipse, then you can evidently say that the velocity that could be given to the lens cap is so small relatively that it will move in a slightly different elliptical orbit around the earth.
Galois.
Wow so many Mathmos here! - hehe cute mathmo collection LOL! Sorry 
And...
Wow you guys speak a different language!!!!! x^2y*^3x whatever...
Sorry... just can't do maths to save my life, don't like maths cus I can't do it, but like theoretical physics so I like bits of maths lol but can't understand it... so all in all I'm always impressed by people who are good at maths
LOL! Sorry And...
Wow you guys speak a different language!!!!! x^2y*^3x whatever...
Sorry... just can't do maths to save my life, don't like maths cus I can't do it, but like theoretical physics so I like bits of maths lol but can't understand it... so all in all I'm always impressed by people who are good at maths
J.F.N
Interesting number theory problem... Some of you will solve this in days/weeks... for others, it will take a term of your life! I'll rep the first person to solve it, if thats encouragement. Let m,n be positive integers.
Prove that (m+n)!/(m+n)^(m+n) < m!.n!/(m^m).(n^n)
I'll rep the first person to solve it, if thats encouragement. Let m,n be positive integers. Prove that (m+n)!/(m+n)^(m+n) < m!.n!/(m^m).(n^n)
Prove by contradiction so assume its not true i.e.
(m+n)!/(m+n)^(m+n) > m!.n!/(m^m).(n^n)
==> (m+n)!.(m^m).(n^n) > m!.n!.(m+n)^(m+n)
==> WLOG let m>=n
==> 1....n...m.(m+1)...(m+n).(m^m).(n^n) > m!.n!.(m+n)^(m+n)
==> (m!).(m+1)...(m+n).(m^m).(n^n) > m!.n!.(m+n)^(m+n)
==> (m+1)...(m+n).(m^m).(n^n) > n!.(m+n)^(m+n)
==> (m+1)...(m+n).(m^m).(n^n) > n!.(m+n)^m.(m+n)^n
We know that:
(m+1)....(m+n) < (m+n)^n
hence if we show:
(m^m).(n^n) < n!.(m+n)^m
we are done. Assume its not true:
(m^m).(n^n) > n!.(m+n)^m
and derive a contradiction, then we are done.
Thats the part im having trouble proving...
J.F.N
Let m,n be positive integers.
Prove that (m+n)!/(m+n)^(m+n) < m!.n!/(m^m).(n^n)
Prove that (m+n)!/(m+n)^(m+n) < m!.n!/(m^m).(n^n)
If you rearrange this as the inequality
(m+n)!/(m!n!) m^m n^n < (m+n)^(m+n)
and consider the binomial expansion of the RHS then you see the term where you choose m ms and n ns is precisely what's on the LHS. As there are (m+n) other positive terms in the expansion of the RHS then its clearly greater than that one particular term.
RichE
If you rearrange this as the inequality
(m+n)!/(m!n!) m^m n^n < (m+n)^(m+n)
and consider the binomial expansion of the RHS then you see the term where you choose m ms and n ns is precisely what's on the LHS. As there are (m+n) other positive terms in the expansion of the RHS then its clearly greater than that one particular term.
(m+n)!/(m!n!) m^m n^n < (m+n)^(m+n)
and consider the binomial expansion of the RHS then you see the term where you choose m ms and n ns is precisely what's on the LHS. As there are (m+n) other positive terms in the expansion of the RHS then its clearly greater than that one particular term.
I repped you, but I'd like to mention again how clever this is! Simple tools but great consequences. You're a great mathematician!
Quick Reply
Related discussions
- undergraduate to postgraduate
- UEA vs University of York for Actuarial Science
- Official Heriot-Watt University 2023 Applicant Thread
- Anyone going to University of Essex ?
- Ask a YSJ Student Ambassador 2024!
- NCS (newham collegiate sixth form) application with IGCSE
- A level choices help needed
- Official Keele University 2024 Applicants thread
- Question for people taking Discrete Maths at Warwick
- Applying to 2+ courses at the same University.
- The Official vBCms Comments Society
- Applying to 2 courses
- Hello Madmoselles.
- Queerness & University
- Online MSc Data Science
- University Application - Cambridge, Imperial, UCL, Manchester, Eidngurgh
- TSR Community Awards 2023 Winners
- October start
- cambridge biological natural sciences
- Academic vs Social Unis
Latest
Trending
Last reply 3 days ago
Did Cambridge maths students find maths and further maths a level very easy?Last reply 2 weeks ago
Edexcel A Level Mathematics Paper 2 unofficial mark scheme correct me if wrongMaths
71
Trending
Last reply 3 days ago
Did Cambridge maths students find maths and further maths a level very easy?Last reply 2 weeks ago
Edexcel A Level Mathematics Paper 2 unofficial mark scheme correct me if wrongMaths
71
