Competition - post a photo you've taken of nature >>

The Proof is Trivial!

Scroll to see replies

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

Reply 101

Noble.

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

Reply 102

Star-girl

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 :smile:

I suppose that works but the intention was that you weren't meant to evaluate

2^{60}-1

Reply 103

Mladenov

Original post by ukdragon37

Excellent. :smile:

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

A

card(A)^{card(A)} \ge card(\mathcal{P}(A)) >card(A)

. Hence no surjection from the set of all maps from

A

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.

(edited 11 years ago)

Reply 104

Indeterminate

Original post by Felix Felicis

Solution 20

Integral

circle

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

(edited 11 years ago)

Reply 105

jack.hadamard

Original post by Farhan.Hanif93

...

PRSOM. Very good, indeed. :smile:

This is sort of an example of a Landen transformation. More fun here.

Reply 106

ukdragon37

Original post by Mladenov

Solution 25

1. ....

Good.

Original post by Mladenov

2. The number of mappings from

A

A

card(A)^{card(A)} \ge card(\mathcal{P}(A)) >card(A)

. Hence no surjection from the set of all maps from

A

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).

[QUOTE="Mladenov;42149165"]
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?

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:

Unparseable latex formula:

\begin{array}{rl}[br]t\left( {0,n} \right) & = \left( {0,n} \right)\\[br]t\left( {m,n} \right) & = \left( {m - 1,m \times n} \right)[br]\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

(edited 11 years ago)

Reply 107

Mladenov

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

2012

th 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

\{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.

(edited 11 years ago)

Reply 108

Indeterminate

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?

(edited 11 years ago)

Reply 109

Mladenov

@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}}

Reply 110

Felix Felicis

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 :colondollar:

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? :colondollar:

Reply 111

Boy_wonder_95

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 :colondollar:

Original post by Felix Felicis

...

What happened to Richard Feynman?

(edited 11 years ago)

Reply 112

Noble.

Original post by Boy_wonder_95

What happened to Richard Feynman?

He died in 1988 from cancer.

Reply 113

Boy_wonder_95

Original post by Noble.

He died in 1988 from cancer.

I meant as in his dp, as he is Felix's idol :tongue:

Reply 114

Noble.

Original post by Boy_wonder_95

I meant as in his dp, as he is Felix's idol :tongue:

Ah sorry, I'm not a mind-reader. :wink:

Reply 115

shamika

Original post by Felix Felicis

I was having trouble understanding your notation more than anything :colondollar:

Yep, that's right

Reply 116

und

Original post by shamika

Yep, that's right

Does the order matter? Eg. is (1,1,2) the same as (1,2,1)?

Reply 117

shamika

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.