Skip to main content

Equicontinuity on a Compact Metric Set implies Uniform Equicontinuity

Equicontinuity: A collection \(\mathcal{F}\) of real-valued functions on a metric space \(X\) is equicontinuous at the point \(x\in X\) provided for every \(\epsilon>0,\ \exists\) \(\delta>0\) such that \(\forall\ f\in\mathcal{F}\) and \(y\in X\) $$d(x,y)<\delta \implies |f(x)-f(y)|<\epsilon$$The collection \(\mathcal{F}\) is said to be equicontinuous on \(X\) provided it is equicontinuous at every point in \(X\)

Uniform Equicontinuity: A equicontinuous collection \(\mathcal{F}\) of real-valued functions on a metric space \(X\) is uniformly equicontinuous if for every \(\epsilon>0,\ \exists\) \(\delta>0\) such that \(\forall\ f\in\mathcal{F}\) and \(x,y\in X\) $$d(x,y)<\delta \implies |f(x)-f(y)|<\epsilon$$


Just like we know that a continuous function on a compact set is uniformly continuous here we are showing that for a collection of functions the same \(\epsilon-\delta\) pair works.


Now coming to the proof, since \(\mathcal{F}\) is equicontinuous for every \(\epsilon>0,\ \exists\) \(\delta>0\) such that \(\forall\ f\in\mathcal{F}\) and \(y\in X\) $$d(x,y)<\delta \implies |f(x)-f(y)|<\epsilon$$Hence if we fix \(\epsilon\) for every \(x\in X\) we get a \(\delta_x\) such that for all \(y\in B_{\delta_x}(x)\) \(|f(x)-f(y)|<\epsilon\). Now these \(\{B_{\frac{\delta_x}{2}}(x)\}\) covers \(X\). Since \(X\) is compact it has a finite subcover $$B_{\frac{\delta_1}{2}}(x_1),B_{\frac{\delta_2}{2}}(x_2),\dots,B_{\frac{\delta_n}{2}}(x_n)$$Now take$$\delta=\frac{1}{2}\min\left\{\delta_i\mid i\in\{1,2,\dots,n\}\right\}$$Now if \(d(x,y)<\delta\) suppose \(x\in B_{\frac{\delta_i}{2}}(x_i)\) then \(y\in B_{\delta_i}(x_i)\) because  $$d(x_i,y)\leq d(x_i,x)+d(x,y)<\frac{\delta_i}{2}+\delta\leq \frac{\delta_i}{2}+\frac{\delta_i}{2}=\delta_i$$ Hence $$d(x,y)<\delta \implies |f(x)-f(y)|<\epsilon$$Since this is true for any \(f\in\mathcal{F}\), for every \(\epsilon>0,\ \exists\) \(\delta>0\) such that \(\forall\ f\in\mathcal{F}\) and \(x,y\in X\) $$d(x,y)<\delta \implies |f(x)-f(y)|<\epsilon$$Therefore \(\mathcal{F}\) is uniformly equicontinuous. $\blacksquare$

Cite this page: Get the BibTeX

Labels:

Comments

Post a Comment

Popular posts from this blog

Hierarchy Theorems (Time, Space, Alternation)

There are many hierarchy theorems based on Time, Space, Nondeterminism, Randomization etc. Time Hierarchy Theorem (Version 1) : If $f, g$ are time-constructible functions satisfying $f(n) \log f(n)=o(g(n))$, then $$ DTIME(f(n)) \subsetneq DTIME (g(n)) $$ Proof:  Consider the following Turing machine $D$: "On input $x$, run for $f(|x|)\log (f(|x|))$ steps the Universal $TM$ $\mathcal{U}$ to simulate the execution of $M_x$ on $x$. If $\mathcal{U}$ outputs some bit $b \in\{0,1\}$ in this time, then output the opposite answer (i.e., output $1-b$ ). Else output 0.” Here $M_x$ is the machine represented by the string $x$.      By definition, $D$ halts within $f(n)\log (f(n))$ steps and hence the language $L$ decided by $D$ is in $DTIME(g(n))$. Claim:  $L \notin$ DTIME $(f(n))$ Proof:  For contradiction's sake, assume that there is some $TM$ $M$ and constant $c$ such that $TM$ $M$, given any input $x \in\{0,1\}^*$, halts within $cf(|x|)$ steps and outputs $D(x)$.      The time to si
1 comment
Read more

Function Automata: A Technique to Solve Finite State Automata Problems

Here I will describe a strategy or technique to solve some finite state automata problems. This strategy was first taught to us by my Theory of Computation Professor. The term 'Function Automata' is given to me since we use function-like structures in this.     Suppose you are given a language that is a regular set \(L\). So there exists a \(DFA\) for \(L\), \(L_D=(Q,\Sigma,\delta, q_1, F)\) where \(Q\) is the set of states, \(\Sigma\) is the set of alphabets, \(\delta\) is the transition function, \(S\) is the starting state and \(f\) is the set of final states. Now let \(Q=\{q_1,q_2,\dots,q_n\) where \(n\in\mathbb{N}\). Now we will do a kind of subset construction but every new state will have \(n\) states of \(Q\) but they can repeat. So $$(\underbrace{q_1,q_1,\dots,q_1}_{n\text{ times}})$$ is a state of the new automata. Now, what is the meaning of these new states? Let \(f=(q_{k_1},q_{k_2},\dots,q_{k_n})\) be a new state where \(q_{k_i}\)'s are not necessary to be diff
Post a Comment
Read more

Cook - Levin Theorem

Around 1971, Cook and Levin independently discovered the notion of \(NP-completeness\) and gave examples of combinatorial \(NP-complete\) problems whose definition seems to have nothing to do with Turing machines. Soon after, Karp showed that \(NP-completeness\) occurs widely and many problems of practical interest are \(NP-complete\). To date, thousands of computational problems in a variety of disciplines have been shown to be \(NP-complete\). \(SAT\) is the language of all satisfiable \(CNF\) formulae. Cook-Levin Theorem : \(SAT\) is \(NP-complete\) Before we go into the proof first we need to define some things Configuration of a Turing Machine: A configuration of a Turing Machine at any point of time \(t\) is basically the snapshot of the turning machine at that time. It is an ordered pair of the head position, current state, and tape content. Any configuration is initialized and ended with a special symbol, let \(\#\) mark its ending. Then the contents of the tape at the left of
Post a Comment
Read more