0708-1300/Class notes for Tuesday, October 30 - Revision history

Trefor: /* Second Hour */

2007-11-08T03:27:07Z

Second Hour

← Older revision		Revision as of 23:27, 7 November 2007
Line 187:		Line 187:
	''Tubular Neighbourhood Theorem''		''Tubular Neighbourhood Theorem''

	<math>\theta\|_{\mathcal{N}(N,\epsilon)}</math> is a smooth homeomorphism of <math>\mathcal{N}(N,\epsilon) =\{(x,v):\|\|v\|\|<\epsilon\}</math> with <math>\{p\in\mathbb{R}^k:d(p,N)<\epsilon\}</math> for small <math>\epsilon</math>.		<math>\theta\|_{\mathcal{N}(N,\epsilon)}</math> is a smooth homeomorphism of <math>\mathcal{N}(N,\epsilon) =\{(x,v)\in \mathcal{N}(N):\|\|v\|\|<\epsilon\}</math> with <math>\{p\in\mathbb{R}^k:d(p,N)<\epsilon\}</math> for small <math>\epsilon</math>.

Trefor: /* First Hour */

2007-11-08T02:58:25Z

First Hour

← Older revision		Revision as of 22:58, 7 November 2007
Line 99:		Line 99:
	'''Definition 2'''		'''Definition 2'''

	If <math>Y\subset X</math>, a ''retract'' is a continuous ~~fucntion~~ <math>f:X\rightarrow Y</math> such that <math>r\|_Y = id_Y</math>		If <math>Y\subset X</math>, a ''retract'' is a continuous function <math>f:X\rightarrow Y</math> such that <math>r\|_Y = id_Y</math>


Line 126:		Line 126:
	''Proof of Brouwer's Theorem''		''Proof of Brouwer's Theorem''

	Assume not. We define a function from <math>D^n</math> to <math>S^{n-1}</math> in the following way. Consider <math>x\in D^n</math> and consider <math>f(x)\in D^n</math>. These points are different by assumption. Consider the line from f(x) towards x. Let r(x) be the point on this line intersecting the boundary (choosing the point going from f(x) to x not the reverse). While we have not (but could) written down a precise formula for this, it is apparent that it is a smooth function from <math>D^n</math> to <math>S^{n-1}</math> that is fixed on the boundary. Hence this is a retract, which is proved could not exist and thus establishing the contradiction.		Assume not. We define a function from <math>D^n</math> to <math>S^{n-1}</math> in the following way. Consider <math>x\in D^n</math> and consider <math>f(x)\in D^n</math>. These points are different by assumption. Consider the line from f(x) towards x. Let r(x) be the point on this line intersecting the boundary (choosing the point going from f(x) to x not the reverse). While we have not (but could) written down a precise formula for this, it is apparent that it is a smooth function from <math>D^n</math> to <math>S^{n-1}</math> that is fixed on the boundary. Hence this is a retract, which is proved could not exist and thus establishing the contradiction.

	===Second Hour===		===Second Hour===

Franklin: /* Complexity of Fixed-Point search Algorithms */

2007-10-31T15:39:41Z

Complexity of Fixed-Point search Algorithms

← Older revision		Revision as of 11:39, 31 October 2007
Line 58:		Line 58:
	It was conjectured the existence of better approaches but ''Hirsch, Papadimitriou and Vavasis'' proved lower exponential bounds for this problem in '''Exponential lower bounds for finding Brouwer fixed		It was conjectured the existence of better approaches but ''Hirsch, Papadimitriou and Vavasis'' proved lower exponential bounds for this problem in '''Exponential lower bounds for finding Brouwer fixed
	points'''. ''J.Complexity'', 5:'''379–416''', 1989.		points'''. ''J.Complexity'', 5:'''379–416''', 1989.

			'''References'''

			[http://delivery.acm.org/10.1145/1070000/1060638/p323-chen.pdf?key1=1060638&key2=3414483911&coll=GUIDE&dl=GUIDE&CFID=4811629&CFTOKEN=42524436]
			[http://itcs.tsinghua.edu.cn/papers/2006/2006012.pdf]

	==Typed Class Notes==		==Typed Class Notes==

Franklin: /* Complexity of Fixed-Point search Algorithms */

2007-10-31T15:37:55Z

Complexity of Fixed-Point search Algorithms

← Older revision		Revision as of 11:37, 31 October 2007
Line 56:		Line 56:
	Sn guarantees the existence of a sub-simplex with all		Sn guarantees the existence of a sub-simplex with all
	vertices differently labelled.) Many algorithms for solving the Sperner's Lemma have exponential time.		vertices differently labelled.) Many algorithms for solving the Sperner's Lemma have exponential time.
	It was conjectured the existence of better approaches but Hirsch, Papadimitriou and Vavasis proved lower exponential bounds for this problem in Exponential lower bounds for finding Brouwer fixed		It was conjectured the existence of better approaches but ''Hirsch, Papadimitriou and Vavasis'' proved lower exponential bounds for this problem in '''Exponential lower bounds for finding Brouwer fixed
	points. J.Complexity, 5:379–416, 1989.		points'''. ''J.Complexity'', 5:'''379–416''', 1989.

	==Typed Class Notes==		==Typed Class Notes==

Franklin: /* Constructive proof of Brouwer's Fixed-Point Theorem */

2007-10-31T15:36:51Z

Constructive proof of Brouwer's Fixed-Point Theorem

← Older revision		Revision as of 11:36, 31 October 2007
Line 51:		Line 51:

	Most of them motivated by the fact that the first proof of the fixed-point theorem was a non-constructive indirect proof i.e. using ''reductio ad absurdum'' and hence using the ''excluded middle axiom''. This axiom is rejected by Brouwer's itself paradigm of Foundations of Mathematics and the intuitionist school of which Brouwer is one of the founders.		Most of them motivated by the fact that the first proof of the fixed-point theorem was a non-constructive indirect proof i.e. using ''reductio ad absurdum'' and hence using the ''excluded middle axiom''. This axiom is rejected by Brouwer's itself paradigm of Foundations of Mathematics and the intuitionist school of which Brouwer is one of the founders.
			===Complexity of Fixed-Point search Algorithms===

			The complexity of finding fixed-point approximations is related to the search of solutions of the Sperner's Lemma (It ensures that a certain
			labelling rule on vertices of a simplicial partitioning of a simplex
			Sn guarantees the existence of a sub-simplex with all
			vertices differently labelled.) Many algorithms for solving the Sperner's Lemma have exponential time.
			It was conjectured the existence of better approaches but Hirsch, Papadimitriou and Vavasis proved lower exponential bounds for this problem in Exponential lower bounds for finding Brouwer fixed
			points. J.Complexity, 5:379–416, 1989.

	==Typed Class Notes==		==Typed Class Notes==

Franklin: /* Smooth Retracts and Smooth Brouwer */

2007-10-31T15:18:00Z

Smooth Retracts and Smooth Brouwer

← Older revision		Revision as of 11:18, 31 October 2007
Line 14:		Line 14:

	'''Challenge.''' Remove the word "smooth" everywhere above.		'''Challenge.''' Remove the word "smooth" everywhere above.

			'''Continuous Brouwer's Fixed-Point Theorem''' ''Proof:'' Let <math>f:D^n\to D^n</math> be a continuous function. By Weierstrass theorem and since <math>D^n</math> is compact there is a sequence of polynomials <math>p_n</math> converging uniformly to f. By the smooth Brouwers' Theorem each <math>p_{n}</math> has a fixed point <math>x_n</math>. By the compactness of <math>D^n</math> there is cluster point of <math>x_n</math> which should be a fixed point of f.

	===Smooth Approximation===		===Smooth Approximation===

Franklin: /* With Brouwer's fixed point theorem you can prove amazing things */

2007-10-30T18:41:11Z

With Brouwer's fixed point theorem you can prove amazing things

← Older revision		Revision as of 14:41, 30 October 2007
Line 32:		Line 32:
	===With Brouwer's fixed point theorem you can prove amazing things===		===With Brouwer's fixed point theorem you can prove amazing things===

	1) There are to antipodal points in the equator with the same temperature.		1) There are two antipodal points in the equator with the same temperature.

	2) There are two antipodal points with the same temperature and the same pressure.		2) There are two antipodal points with the same temperature and the same pressure.

Trefor at 17:32, 30 October 2007

2007-10-30T17:32:16Z

← Older revision		Revision as of 13:32, 30 October 2007
Line 49:		Line 49:

	Most of them motivated by the fact that the first proof of the fixed-point theorem was a non-constructive indirect proof i.e. using ''reductio ad absurdum'' and hence using the ''excluded middle axiom''. This axiom is rejected by Brouwer's itself paradigm of Foundations of Mathematics and the intuitionist school of which Brouwer is one of the founders.		Most of them motivated by the fact that the first proof of the fixed-point theorem was a non-constructive indirect proof i.e. using ''reductio ad absurdum'' and hence using the ''excluded middle axiom''. This axiom is rejected by Brouwer's itself paradigm of Foundations of Mathematics and the intuitionist school of which Brouwer is one of the founders.


			==Typed Class Notes==

			<span style="color: red;">The notes below are by the students and for the students. Hopefully they are useful, but they come with no guarantee of any kind.</span>

			===First Hour===

			'''Claim 1''':

			Consider <math>f:X\rightarrow Y</math> to be continuous and proper and Y being locally compact. Then it is closed.


			'''Definition 1'''

			A set <math>F\subset X</math> (X a topological space) is called ''locally closed'' if every <math>x\in X</math> has a neighbourhood U such that <math>U\cap F</math> is closed in U.


			'''Claim 2:'''

			Locally closed <math>\Leftrightarrow</math> closed.


			''Proof of Claim 2:''

			(<math>\Leftarrow</math>) is tautological

			(<math>\Rightarrow</math>) If <math>x\in F^c</math> then <math>\exists U_x</math> such that <math>U\cap F</math> is closed in U so <math>U\cap F^c</math> is open in U and hence also in X. Thus, x has a neighbourhood in <math>F^c</math> so <math>F^c</math> is open and thus F is closed.


			''Proof of Claim 1:''

			To be repeated next class.


			'''Definition 2'''

			If <math>Y\subset X</math>, a ''retract'' is a continuous fucntion <math>f:X\rightarrow Y</math> such that <math>r\|_Y = id_Y</math>


			'''Theorem 1'''

			There is no smooth retract <math>f: D^{n+1}\rightarrow S^n</math> where

			<math>D^{n+1} =\{x\in\mathbb{R}^{n+1}\ :\ \|\|x\|\|\leq 1\}\supset S^n = \{x\in\mathbb{R}^{n+1}\ :\ \|\|x\|\|= 1\}</math>


			''Proof of Theorem 1''

			Assume not. Then <math>\exists r:D^{n+1}\rightarrow S^n</math> such that r is a smooth retract. By Sard's theorem we can find a non critical value y of r. So <math>r^{-1}(y)</math> is a submanifold (with boundary) of dimension 1 of <math>D^{n+1}</math>.

			Previously we proved that such things were manifolds but only if they were without boundary. The proof with boundary works in exactly the same was, that is, use the theorem that immersions looks like projections in <math>R^n</math> only this time allow neighborhoods to be homeomorphic to the half space <math>H^n</math>.

			Now the classification theorem for 1 dimensional manifolds shows that <math>r^{-1}(y)</math> must be homeomorphic to a closed interval (as it has at least one boundary point at y) and hence it must also have a second boundary point. But <math>\partial(r^{-1}(y))\subset \partial D^{n+1} = S^n</math> and hence this second boundary point must be some other point y' on <math>S^n</math>. But such points map to themselves by assumption so <math>y' = r(y') = y</math>. This establishes the contradiction.


			'''Theorem 2'''

			''Brouwer's Fixed Point Theorem''

			Consider a function <math>f:D^n\rightarrow D^n</math>, f being smooth. Then <math>\exists p\in D^n</math> such that f(p)=p, i.e., there exists a fixed point of the function.

			''Proof of Brouwer's Theorem''

			Assume not. We define a function from <math>D^n</math> to <math>S^{n-1}</math> in the following way. Consider <math>x\in D^n</math> and consider <math>f(x)\in D^n</math>. These points are different by assumption. Consider the line from f(x) towards x. Let r(x) be the point on this line intersecting the boundary (choosing the point going from f(x) to x not the reverse). While we have not (but could) written down a precise formula for this, it is apparent that it is a smooth function from <math>D^n</math> to <math>S^{n-1}</math> that is fixed on the boundary. Hence this is a retract, which is proved could not exist and thus establishing the contradiction.

			===Second Hour===

			'''Theorem 3'''

			Let A be a closed subset of M and let <math>f:M\rightarrow \mathbb{R}</math> be continuous such that <math>f\|_A</math> is smooth. Then, <math>\forall\epsilon>0\ \exists g:M\rightarrow\mathbb{R}</math> such that <math>g\|_A = f\|_A</math> and <math>\|\|f-g\|\|_{L^{\infty}}<\epsilon</math> and g is smooth.


			'''Corollary 1'''

			This implies that there doesn't not exist such ''continuous'' retracts which in turn implies the continuous version of Brouwer's Theorem.

			''Proof of theorem 3''

			The idea is as follows: It is obviously locally true and hence it is globally true. Lets justify this.

			First off, by "locally true" what we mean is that <math>\forall x\in M\ \exists U_x</math> such that <math>\exists g_x:U_x\rightarrow\mathbb{R}</math> such that the rest of the conditions are true.

			Why is this locally true? Well, if <math>x\in A</math>, by smoothness of <math>f\|_A</math> <math>\exists</math> smooth extension g of <math>f\|_A</math> to a neighborhood of x. Lets take this extension. Now if <math>x\notin A</math> then let y = f(x) and set <math>g_x = y</math>. This works in a neighborhood of x.

			We now want to extend this to being globally true. To do this we use a partition of unity to assemble the local property to a global property.

			Consider our previous cover <math>\{U_x\}</math>. <math>\forall\alpha\exists x(\alpha)</math> such that supp <math>\lambda_{\alpha}\subset U_{x(\alpha)}</math> and <math>\sum \lambda_{\alpha} = 1</math>.

			Set <math>g(p) = \sum_{\alpha} \lambda_{\alpha}(p)g_{x(\alpha)}(p)</math>. Smoothness is obvious.

			Now, if <math>p\in A</math> then <math>g(p) = \sum_{\alpha} \lambda_{\alpha}(p)g_{x(\alpha)}(p) = \sum_{\alpha} \lambda_{\alpha}(p)f(p) = f(p)</math>

			Now, if <math>p\in M</math> then <math>\|\|g(p)-f(p)\|\|\leq\sum_{\alpha}\lambda_{\alpha}\|\|g_{x(\alpha)} - f\|\|=\sum_{\alpha:p\in U_{\alpha}}\lambda_{\alpha}\|\|g_{x(\alpha)} - f\|\|\leq \sum_{\alpha:p\in U_{\alpha}}\lambda_{\alpha}\epsilon = \epsilon</math>

			''Q.E.D''


			We can now generalize the previous theorem with the following theorem.

			'''Theorem 4'''

			Let N be a compact metrized manifold (i.e. we have actually specified a metric not just claimed one can exist which we always know for manifolds). Also let <math>A\subset M</math> be closed in the manifold. Let f<math>:M\rightarrow N</math> be a continuous function such that <math>f\|_A</math> is smooth. Let <math>\epsilon> 0</math> then <math>\exists</math> a smooth <math>g:M\rightarrow N</math> such that

			1) <math>g\|_A = f\|_A</math>

			2) <math>\forall p\in M,\ d(f(p),g(p))<\epsilon</math>.


			''Proof of Theorem 4''

			By the Whitney embedding theorem we let N be a submanifold of <math>\mathbb{R}^{2n+1}</math>.
			We consider our function f from M to N but thought of as going into <math>\mathbb{R}^{2n+1}</math>. By the previous theorem we can approximate this by a smooth function g' going into <math>\mathbb{R}^{2n+1}</math>. The problem is that this may not take points actually onto N but near by it in the ambient space. We then want to construct from g' a smooth function g that actually goes into N as we would want. To do this we will use the idea of tubular neighbourhoods.


			'''Definition 3'''

			Let N be a (compact) submanifold of <math>\mathbb{R}^k</math>. Then ''the normal bundle'' of N in <math>\mathbb{R}^k</math> is <math>\mathcal{N}(N) = \{(x,v)\|x\in N\subset\mathbb{R}^k,\ v\in T_x(\mathbb{R}^k),\ v\perp T_x(N)\}</math> where <math>T_x(N) = \theta_* T_{\theta^{-1}(x)}(N)</math> from an immersion <math>\theta:N\rightarrow\mathbb{R}^k</math> (also an embedding as N is compact).

			<math>\mathcal{N}</math> is a manifold of dimension n+ (k-n) = k. We of course would need to verify that this is in fact a manifold.

			'''Theorem 5'''

			''Tubular Neighbourhood Theorem''

			<math>\theta\|_{\mathcal{N}(N,\epsilon)}</math> is a smooth homeomorphism of <math>\mathcal{N}(N,\epsilon) =\{(x,v):\|\|v\|\|<\epsilon\}</math> with <math>\{p\in\mathbb{R}^k:d(p,N)<\epsilon\}</math> for small <math>\epsilon</math>.

Franklin: /* Constructive proof of Brouwer's Fixed-Point Theorem */

2007-10-30T16:55:01Z

Constructive proof of Brouwer's Fixed-Point Theorem

← Older revision		Revision as of 12:55, 30 October 2007
Line 45:		Line 45:

	===Constructive proof of Brouwer's Fixed-Point Theorem===		===Constructive proof of Brouwer's Fixed-Point Theorem===
	Several proves of Brouwer's theorem had been given. [http://www.jstor.org/view/00361429/di976189/97p0407b/0?frame=frame&userID=80644483@utoronto.ca/01cc99331100501cb2b9a&dpi=3&config=jstor See]		Several proves of Brouwer's theorem had been given. [http://www.jstor.org/view/00361429/di976189/97p0407b/0?frame=frame&userID=80644483@utoronto.ca/01cc99331100501cb2b9a&dpi=3&config=jstor See] '''A Constructive Proof of the Brouwer Fixed-Point Theorem and Computational''',

	A Constructive Proof of the Brouwer Fixed-Point Theorem and Computational,
	R. B. Kellogg; T. Y. Li; J. Yorke		R. B. Kellogg; T. Y. Li; J. Yorke

Franklin: /* Constructive proof of Brouwer's Fixed-Point Theorem */

2007-10-30T16:54:41Z

Constructive proof of Brouwer's Fixed-Point Theorem

← Older revision		Revision as of 12:54, 30 October 2007
Line 47:		Line 47:
	Several proves of Brouwer's theorem had been given. [http://www.jstor.org/view/00361429/di976189/97p0407b/0?frame=frame&userID=80644483@utoronto.ca/01cc99331100501cb2b9a&dpi=3&config=jstor See]		Several proves of Brouwer's theorem had been given. [http://www.jstor.org/view/00361429/di976189/97p0407b/0?frame=frame&userID=80644483@utoronto.ca/01cc99331100501cb2b9a&dpi=3&config=jstor See]

	A Constructive Proof of the Brouwer Fixed-Point Theorem and Computational~~'''~~,~~R. B. Kellogg; T. Y. Li; J. Yorke ''SIAM Journal on Numerical Analysis'', '''Vol. 13''', ''No. 4''. (Sep., 1976), pp. 473-483.~~		A Constructive Proof of the Brouwer Fixed-Point Theorem and Computational,
			R. B. Kellogg; T. Y. Li; J. Yorke

	Most of them motivated by the fact that the first proof of the fixed-point theorem was a non-constructive indirect proof i.e. using ''reductio ad absurdum'' and hence using the ''excluded middle axiom''. This axiom is rejected by Brouwer's itself paradigm of Foundations of Mathematics and the intuitionist school of which Brouwer is one of the founders.		Most of them motivated by the fact that the first proof of the fixed-point theorem was a non-constructive indirect proof i.e. using ''reductio ad absurdum'' and hence using the ''excluded middle axiom''. This axiom is rejected by Brouwer's itself paradigm of Foundations of Mathematics and the intuitionist school of which Brouwer is one of the founders.