Hey there! Sign in to join this conversationNew here? Join for free
    Offline

    17
    ReputationRep:
    (Original post by Farhan.Hanif93)
    If only I could understand groups by doing integrals, then I'd be on to something...

    Out of interest, are questions on things like groups etc. suitable for this thread?
    Actually, I'll give you a question on groups:

    Problem 26 ***

    Let G_1 and G_2 be finite groups such that |G_1| and |G_2| are coprime and let K \leq G_1 \times G_2.

    Set H_1 = \{g \in G_1 : (g,e) \in K \} and H_2 = \{g \in G_2 : (e,g) \in K \}

    Show that K = H_1 \times H_2
    Offline

    17
    ReputationRep:
    Here's an additional problem:

    Problem 27 **/*** (the ** rating very loosely)

    Let a,b,c \in \mathbb{R}. Determine

    I =  \displaystyle\quad \iiint\limits_{x^2+y^2+z^2 \leq 1} \cos(ax+by+cz) \ \, \mathrm{d} x\,\mathrm{d} y\,\mathrm{d}z

    Also, show that your result is consistent with the fact the volume of the unit sphere is 4 \pi/3
    Offline

    3
    ReputationRep:
    (Original post by Boy_wonder_95)
    2 to the power of 60 - 1 = 1152921504606846795
    1152921504606846795 / 61 = 18900352534538475
    Therefore it's divisible by 61. Problem solved
    I suppose that works but the intention was that you weren't meant to evaluate 2^{60}-1.
    Offline

    1
    ReputationRep:
    (Original post by ukdragon37)
    Excellent. However the steps after this point can also be completed (more cleanly I think) without the use of contradiction.

    Consider any N \in \mathbb{N}_\omega satisfying f(N) = N. Since 1 \leq N we have  f(1) \leq f(N) = N. Hence by induction  f^n(1) \leq N for any natural n and therefore any N satisfying f(N) = N is an upper bound for the CPO \displaystyle \left\{f^n(1)|n \in \mathbb{N}\cup\{0\}\right\}. However out of all of them F is the supremum of the CPO, so by definition the smallest.

    The point of the question was to get you to prove an instance of Kleene's fixed-point theorem.
    Thank you for your remark.
    I wanted to ask you several questions. What can we say about the function that enumerates the set of fixed points of f? I mean, are there any special properties which that function has?



    Solution 25


    1. Consider two cases:
    If A is finite, then suppose f:A\rightarrow \mathcal{P}(A) is a surjection. Consequently, card(A) \ge card(\mathcal{P}(A))=2^{card(A)}-contradiction.
    Now let A be infinite. Suppose there exists surjection f:A\rightarrow \mathcal{P}(A). For every a \in A, f(a)\subseteq A. Denote B=\{a | a\in A, a \not\in f(a)\}.
    Since f is surjective, there must be some a' \in A with f(a')=B. Hence a' \not\in B and a' \in f(a')=B, which is a contradiction.
    Therefore, even if A is infinite, we have card(A) < card(\mathcal{P}(A)).

    2. The number of mappings from A to A is card(A)^{card(A)} \ge card(\mathcal{P}(A)) >card(A). Hence no surjection from the set of all maps from A to A to the set A exists.

    3. It is quite well-known that \aleph_{0}^{\aleph_{0}}=card( \mathbb{R}). I think we can use the fact that card((0,1))=card( \mathbb{R}). Then we shall find injections between  (0,1) and  \mathbb{N}^{\mathbb{N}}. Finally, Bernstein–Schroeder's theorem shows that \aleph_{0}^{\aleph_{0}}=card( \mathbb{R}). It would be interesting if we can construct bijection.
    • Political Ambassador
    Offline

    3
    ReputationRep:
    Political Ambassador
    (Original post by Felix Felicis)
    Solution 20
    Integral
    \displaystyle\int \sqrt{r^{2} - x^{2}} dx Let x = r \sin \theta \Rightarrow dx = r \cos \theta d \theta

    \Rightarrow \displaystyle\int \sqrt{r^{2} - x^{2}} dx = r^{2} \displaystyle\int \cos^{2} \theta d \theta = \frac{r^{2}}{2} \displaystyle\int (1 + \cos 2 \theta) d \theta

    = \frac{r^{2}}{2} \left( \theta + \sin \theta \cos \theta \right) We have \theta = \arcsin \frac{x}{r} and

    \sin \theta \cdot \cos \theta = \frac{x}{r} \cdot \frac{\sqrt{r^{2} - x^{2}}}{r}} = \frac{x \sqrt{r^{2} - x^{2}}}{r^{2}}

    = \frac{1}{2} \left( r^{2} \arcsin \dfrac{x}{r} + x \sqrt{r^{2} - x^{2}}\right)

    Let \arcsin \dfrac{x}{r} = \theta \Rightarrow \dfrac{x}{r} = \sin \theta and \cos \theta = \dfrac{\sqrt{r^{2} - x^{2}}}{r} \Rightarrow \tan \theta = \dfrac{x}{\sqrt{r^{2} - x^{2}}} \Rightarrow \arcsin \dfrac{x}{r} = \arctan \left( \dfrac{x} {\sqrt{r^{2} - x^{2}}} \right)

    So the integral is \dfrac{1}{2} \left(r^{2} \arctan \left( \dfrac{x}{\sqrt{r^{2} - x^{2}}} \right) + x \sqrt{r^{2} - x^{2}} \right) + \mathcal{C} as required.


    circle
    The area of the circle is given by 4 \displaystyle\int_{0}^{r} \sqrt{r^{2} - x^{2}} Let x = r \sin \theta \Rightarrow dx = r \cos \theta d \theta and r \to \frac{\pi}{2} and 0 \to 0

    \Rightarrow 4 \displaystyle\int_{0}^{r} \sqrt{r^{2} - x^{2}} = 2r^{2} \displaystyle\int_{0}^{\pi /2} (\cos 2 \theta + 1) d \theta = \pi r^{2}
    The second part can be done with considerably less work, and by using the first part, as long as you know that

    \lim_{x \to \infty} \arctan x = \frac{1}{2}\pi

    Offline

    1
    ReputationRep:
    (Original post by Farhan.Hanif93)
    ...
    PRSOM. Very good, indeed. This is sort of an example of a Landen transformation. More fun here.
    Offline

    12
    ReputationRep:
    (Original post by Mladenov)
    Solution 25

    1. ....
    Good.

    (Original post by Mladenov)
    2. The number of mappings from A to A is card(A)^{card(A)} \ge card(\mathcal{P}(A)) >card(A). Hence no surjection from the set of all maps from A to A to the set A exists.
    You want to make clear why card(A)^{card(A)} \ge card(\mathcal{P}(A)) in the infinite case, but if you can do part 1 then I'm sure it is obvious to you why.

    (Original post by Mladenov)
    3. It is quite well-known that \aleph_{0}^{\aleph_{0}}=card( \mathbb{R}). I think we can use the fact that card((0,1))=card( \mathbb{R}). Then we shall find injections between  (0,1) and  \mathbb{N}^{\mathbb{N}}. Finally, Bernstein–Schroeder's theorem shows that \aleph_{0}^{\aleph_{0}}=card( \mathbb{R}). It would be interesting if we can construct bijection.
    Good. Pick the two injections of your choice and you can constructively find a bijection through Tarski's fixed-point theorem in addition to Schroeder-Berstein (point 3).

    (Original post by Mladenov)
    Thank you for your remark.
    I wanted to ask you several questions. What can we say about the function that enumerates the set of fixed points of f? I mean, are there any special properties which that function has?[B]
    Well I can only give you the theoretical computer science/computation theory view. Such a (higher-order) function is related to the notion of a fixed-point combinator:

    Consider a higher-order function Y : (X\to X)\to X, which takes a function from a set to the same set and outputs a value in that set and has the property:

    Y(f) = f (Y(f))

    In other words, given a function f, Y is guaranteed to compute a fixed point of f (although not necessarily a particular one such as the lowest).

    Now if we define say a factorial-like function t : \mathbb{N}_0^2 \to \mathbb{N}_0^2 such that:

    \begin{array}{rl}

t\left( {0,n} \right) & = \left( {0,n} \right)\\

t\left( {m,n} \right) & = \left( {m - 1,m \times n} \right)

\end{array}

    which has fixed points (0,n) for all n. Suppose we have a particular instance of Y which is is built-in to "try" a starting value of say (3,1) and then repeatedly compute f(3,1),f(f(3,1)),f(f(f(3,1))) \dots until it fixes, we would then have Y\left( t \right) = \left( {0,6} \right), and this indeed is one fixed point of t. Different fixed points can thus be extracted by having different fixed-point combinators that try different starting values.

    Hence we can construct a higher-order function which enumerates all of the fixed points of a function f by first enumerating the elements of the domain of f and then use them as the starting values in different fixed-point combinators to exhaustively compute the fixed point reachable from each element.

    If we view recursive functions as programs, then a fixed point of a function is the computational result of the corresponding program which can be reached from some input - the attempted starting value. A function which creates a set of all fixed points therefore creates a set of all halting computation results. We normally don't deal with such a function since usually we are only interested in a single result from a single interesting input, or we wish to only look at the least (occasionally greatest) fixed points for their own special properties.

    Of course, if the resulting set of fixed points is empty then it means the function/program never produces a result - i.e. it does not halt. Since the halting problem is undecidable, this shows the function which computes all fixed points is not computable in finite time.

    Further reading (although it might be a bit too deep): Kleene's recursion theorems
    Offline

    1
    ReputationRep:
    Solution 24

    \displaystyle \prod_{n=1}^{2012} \sin \left(\frac{n\pi}{2013}\right)= \left(\frac{1}{2i}\right)^{2012} \left(\prod_{n=1}^{2012} e^{\frac{ni\pi}{2013}} \right) \prod_{n=1}^{2012} \left(1-e^{-\frac{2ni\pi}{2013}}\right). Consider \displaystyle F(x) = \prod_{n=1}^{2012} \left(x-e^{-\frac{2ni\pi}{2013}}\right). All the 2012 non trivial 2012th roots of unity are roots of F. Hence F(x)=1+x+...+x^{2012}.
    Thence, \displaystyle \prod_{n=1}^{2012} \sin \left(\frac{n\pi}{2013}\right)= \frac{2013}{2^{2012}}.
    Note the identity sinx=sin(\pi-x), and get \displaystyle \prod_{n=1}^{1006} \sin \left(\frac{n\pi}{2013}\right)= \frac{\sqrt{2013}}{2^{1006}}.

    (Original post by ukdragon37)
    .....
    The second part of problem 25 can also be done as follows:
    Suppose there is a surjection f :A \to A\to A. Therefore, we can denote A\to A by \{g_{a}| a \in A\}. Define h(a)=g_{a}(a)+1, where a\in A. Then h is obviously not in \{g_{a}| a \in A\}.
    In the infinite case, card(A)^{card(A)} \ge card(\mathcal{P}(A)) can be proved similarly.

    Tarski's fixed point theorem is quite powerful. It is more general than Kleene's theorem. With this theorem anyone can construct bijection - task, which seems rather tough otherwise.

    Thanks for your explanation.

    Kleene's recursion theorems appear to be exciting, yet I have not covered any recursion theory, which impedes considerably my comprehension of them.
    • Political Ambassador
    Offline

    3
    ReputationRep:
    Political Ambassador
    Problem 28 *

    Determine whether or not the line

    ax+by+r=0

    intersects the circle, C, with equation

    (x-a)^2 + (y-b)^2 = r^2

    If it does, give the coordinates.

    Is the line ever a tangent to C?
    Offline

    1
    ReputationRep:
    @Indeterminate, your problem should be 28.

    Problem 29**

    Let \left(a_{n}\right)_{n\ge 1} be a sequence of positive integers satisfying the following condition: 0< a_{n+1}-a_{n}\le 2001 for each n\ge 1. Then there exist infinitely many ordered pairs (p,q) of distinct positive integers such that a_{p} \equiv 0 \pmod {a_{q}}.
    Offline

    13
    ReputationRep:
    (Original post by shamika)
    (I wanted to edit this to restrict the choice of n, but actually it makes little difference. Do people need a hint?)
    I was having trouble understanding your notation more than anything But I'll have a go - just to confirm, S is the set of triples which add up to the number 'n' and the question is to evaluate the sum of the product of the triples of each set of integers that add up to make n?
    Offline

    15
    ReputationRep:
    (Original post by Star-girl)
    I suppose that works but the intention was that you weren't meant to evaluate 2^{60}-1.
    Sorry but I aint no mind-reader

    (Original post by Felix Felicis)
    ...
    :gasp: What happened to Richard Feynman?
    Offline

    17
    ReputationRep:
    (Original post by Boy_wonder_95)
    :gasp: What happened to Richard Feynman?
    He died in 1988 from cancer.
    Offline

    15
    ReputationRep:
    (Original post by Noble.)
    He died in 1988 from cancer.
    I meant as in his dp, as he is Felix's idol
    Offline

    17
    ReputationRep:
    (Original post by Boy_wonder_95)
    I meant as in his dp, as he is Felix's idol
    Ah sorry, I'm not a mind-reader.
    Offline

    16
    ReputationRep:
    (Original post by Felix Felicis)
    I was having trouble understanding your notation more than anything But I'll have a go - just to confirm, S is the set of triples which add up to the number 'n' and the question is to evaluate the sum of the product of the triples of each set of integers that add up to make n?
    Yep, that's right
    • Thread Starter
    Offline

    16
    ReputationRep:
    (Original post by shamika)
    Yep, that's right
    Does the order matter? Eg. is (1,1,2) the same as (1,2,1)?
    Offline

    16
    ReputationRep:
    (Original post by und)
    Does the order matter? Eg. is (1,1,2) the same as (1,2,1)?
    The order does matter. So when n = 4, the only other unique triple is (2,1,1) and the required sum becomes 6.

    I should've made it clear that i, j and k are positive integers.
    Offline

    1
    ReputationRep:
    Hint (Problem 23)

    Spoiler:
    Show
    Write k=n-i-j, so \displaystyle \sum_{S}ijk= \sum_{(2 \le i+j \le n-1)_{i,j \ge 1}}ij(n-i-j). Now for each m \in \{2,3,..,n-1\}, consider \displaystyle n\sum_{(i+j=m)_{i,j \ge 1}} ij, \displaystyle \sum_{(i+j=m)_{i,j \ge 1}} ji^2, and \displaystyle \sum_{(i+j=m)_{i,j \ge 1}} ij^2. Write i=m-j, and note that i takes each value from \{1,2,...,m-1\} exactly once. We are now able to evaluate each of these three sums. Then sum over \{2,3,...,n-1\} to find \displaystyle \sum_{S}ijk.


    There should be a more concise solution.
    Offline

    1
    ReputationRep:
    Subbing...
 
 
 
  • See more of what you like on The Student Room

    You can personalise what you see on TSR. Tell us a little about yourself to get started.

  • Poll
    What's your favourite Christmas sweets?
    Useful resources

    Make your revision easier

    Maths

    Maths Forum posting guidelines

    Not sure where to post? Read the updated guidelines here

    Equations

    How to use LaTex

    Writing equations the easy way

    Student revising

    Study habits of A* students

    Top tips from students who have already aced their exams

    Study Planner

    Create your own Study Planner

    Never miss a deadline again

    Polling station sign

    Thinking about a maths degree?

    Chat with other maths applicants

    Can you help? Study help unanswered threads

    Groups associated with this forum:

    View associated groups
  • See more of what you like on The Student Room

    You can personalise what you see on TSR. Tell us a little about yourself to get started.

  • The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

    Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

    Quick reply
    Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.