Micro Math Camp Definitions

Eric Andersen
Flashcards by Eric Andersen, updated more than 1 year ago
Eric Andersen
Created by Eric Andersen about 5 years ago
5
0

Description

Flashcards on Micro Math Camp Definitions, created by Eric Andersen on 08/18/2015.

Resource summary

Question Answer
Metric Space A pair \(\left(S, d \right)\) where \( S \) is a collection of points and \( d \) is a distance function on \( S \) that satisfies the properties of a metric.
Cauchy-Schwarz Inequality For any vectors \( x, \, y \) of an inner product space, \[ \left| \langle x, \, y \rangle \right|^2 \le \langle x, \, x \rangle \cdot \langle y, \, y \rangle. \] Equivalently, \[ \left| \langle x, \, y \rangle \right| \le \| x \| \cdot \| y \|. \]
Discrete Metric The discrete metric is: \[d \left(x, \, y \right) = \begin{cases} 1 \; \text{if } x \ne y, \\ 0 \; \text{if } x = y \end{cases} \]
an \(\epsilon\)-ball of \(x\) in \(S\) \[ B_\epsilon \left( x \right) \equiv \left\{ y \in S \,|\, d \left( x,\,y \right) < \epsilon \right\} \]
Open Set A set \(U \subseteq S\) is open if \( \forall x \in U, \; \exists \epsilon > 0 \) such that \( B_\epsilon \left( x \right) \subseteq U\)
Metric Topology A metric topology of a metric space \( \left(S, \, d \right) \) is the set of all open sets in \(S \). That is: \[ \mathcal{T} \equiv \left\{ U \subseteq S \, | \, U \text{ is open} \right\} \]
Power Set of \( X \) The power set \( 2^X \) is the set of all subsets of \(X\).
Topological Space A set \( X \) together with a set \(T \subseteq 2^X\) that satisfies the three properties of a metric topology on S
Closed Set A set \(U \subseteq S\) is closed if \( S \setminus U \) is open. Alternatively, a set \( C \subseteq S \) is closed if \( \forall \left\{ x_n \right\}_{n=1}^{\infty} \subseteq C \) for which \( \exists x \in S \) such that \( x_n \rightarrow x, \, x \in C\).
Sequence A countably indexed collection of elements \( \left\{ x_n \right\}_{n=1}^{\infty} \subseteq S \)
Convergent Sequence A sequence converges to a limit point \( x \in S \) if \( \forall \epsilon \in \mathbb{R}_+, \; \exists N_\epsilon \) such that \( d \left(x_m, \, x \right) < \epsilon \) for all \( m > N_\epsilon \)
Convergent Subsequence A sequence contains a convergent subsequence if there exists an index set \( N \subset \mathbb{N} \) such that \( \left\{ x_n \right\}_{n \in \hat{N}} \rightarrow x \) for some \(x \in S\)
Closure of a Set This is the smallest closed set containing \( C \). \[ cl \left( C \right) = \bigcap \left\{ K \in 2^S \, | \, C \subseteq K; K \text{ closed.} \right\} \]
Cauchy Sequence A sequence \( \left\{x_n\right\}_{n=1}^{\infty} \subseteq S \) such that \( \forall \epsilon \in \mathbb{R}_+, \; \exists N_\epsilon \in \mathbb{N} \) such that \( d \left(x_m,\,x_l\right) < \epsilon \) for all \(m, l > N_\epsilon\)
Bounded Set A set \(U \subseteq S \) is bounded if \( \exists M \in \mathbb{R}_+ \) such that \( \forall x,y \in U, \; d \left(x,\,y\right) \le M \)
Complete Set A set \( U \subseteq S \) is complete if for every Cauchy sequence \( \left\{x_n\right\}_{n=1}^{\infty} \subseteq U, \; \exists x \in U \) such that \( x_n \rightarrow x \).
Open Cover of a set \( K \) A collection of sets \( \left\{ U_\alpha \right\}_{\alpha \in A} \) such that \( U_\alpha \in \mathcal{T} \) for all \( \alpha \in A \) and \( K \subseteq \bigcup_{\alpha \in A} U_\alpha \).
Finite Subcover An open cover of \( K \) admits a finite subcover if there exists a finite set \( A' \subseteq A \) such that \( K \subseteq \bigcup_{\alpha \in A'} U_\alpha \).
Compact Set A subset \( K \) of a metric space \( \left( S, \, d \right) \) is compact if every open cover of \( K \) has a finite subcover.
Finite Intersection Property A collection \( \mathcal{A} \subseteq 2^S \) has the finite intersection property if \( \bigcap \mathcal{A}' \ne \emptyset \) for any finite, nonempty collection \( \mathcal{A}' \subseteq \mathcal{A} \)
Totally Bounded Metric Space A metric space \( S \) is totally bounded if for any \( \epsilon > 0 \), there exists a finite collection of points \( x_1, \, \ldots, \, x_N \) such that the open balls \( B_\epsilon \left( x_1 \right), \ldots, \, B_\epsilon \left(x_N\right) \) cover \( S \).
Connected Metric Space A metric space \( S \) is connected if there do not exist disjoint, nonempty open sets \( U \) and \( U' \) such that \( U \cup U' = S \)
Countably Infinite Set An infinite set \( S \) is countably infinite if there exists a bijection \( f : S \rightarrow \mathbb{N} \).
Countable set A set is called countable if it is finite or countably infinite.
Dense Set A set \( D \) is dense in a metric space \( \left( S, \, d \right) \text{ if } cl \left( D \right) = S \).
Separable A metric space \( \left( S, \, d \right) \) is separable if there exists a countable set \( D \) that is dense in \( S \).
Continuity A function \( f : X \rightarrow Y \) is continuous at \( x \in X \text{ if } \forall \left\{x_n\right\}_{n=1}^{\infty} \subseteq X \) such that \( x_n \rightarrow x \in X \), we have \( f \left( x_n \right) \rightarrow f \left( x \right) \). Alternatively, if \( \forall \epsilon > 0, \, \exists \delta > 0 \) such that for all \( z \in X \) such that \( d_X \left( x, \, z \right) < \delta, \, d_Y \left( f \left( x \right), \, f \left( z \right) \right) < \epsilon \).
Pointwise Convergence The sequence of functions \( \left\{f_n\right\}_{n=1}^{\infty} \) converges pointwise to the function \( f \text{ if } \forall x \in X \), the sequence \( f_n \left( x \right) \) converges to \( f \left( x \right) \).
Uniform Convergence The sequence of functions \( \left\{f_n\right\}_{n=1}^{\infty} \) converges pointwise to the function \( f \text{ if } \forall \epsilon > 0 \) there exists \( N_\epsilon \) such that \( \forall x \in S \text{ and all } n \ge N_\epsilon, \, d \left( f_n \left(x \right), \, f \left( x \right) \right) < \epsilon \).
Convex Set Given a vector space \( \left( S, \, +, \, \cdot \right) \), a set \( U \subseteq S \) is convex if \( \forall x, \, y \in U \text{ and } \forall \alpha \in \left[0, \, 1 \right], \) \[ \alpha x + \left(1-\alpha\right)y \in U \]
Convex Hull of a Set \( co \left( U \right) \) is the intersection of all convex sets containing \( U \).
Supremum Least Upper Bound
Infinum Greatest Lower Bound
\(i\)-th partial derivative \[ \lim_{h \rightarrow 0} \frac{ f \left( \tilde{x}_1, \ldots, \, \tilde{x}_i + h, \, \tilde{x}_{i+1}, \ldots, \, \tilde{x}_n \right) - f \left( \tilde{x}_1, \ldots, \, \tilde{x}_i, \, \tilde{x}_{i+1}, \ldots, \, \tilde{x}_n \right) }{h} \]
Gradient \[ \nabla f \left( x \right) = \left[ \frac{ \partial f }{ \partial x_i} \right] \] is the \( N \times 1 \) vector of first partial derivatives of \( f \text{ at } x \).
Hessian Matrix of \( f \text{ at } x \) matrix of well-defined partial and cross-partial derivatives
Jacobian Matrix of \( f \text{ at } x \) matrix of partial derivatives
Differentiable Function If there is an \( M \times N \) matrix \( Df\left(x\right) \) such that for any sequence of vectors \( w \rightarrow 0 \) \[ \lim_{w \rightarrow 0} \frac{ \| f \left( x + w \right) - f \left( x \right) - Df\left(x\right)w \|}{\|w\|} = 0 \]
Taylor's Approximation \[ f\left(x\right) \approx f \left(x_0 \right) + \sum_{k=1}^{n} \frac{f^k \left(x_0 \right)}{k!} \left(x - x_0 \right)^k \]
Concave Function A function \( f : A \rightarrow \mathbb{R} \) defined on a convex set \( A \subset \mathbb{R}^N \) is concave if and and only if \[ f \left( \alpha x' + \left(1-\alpha\right)x\right) \ge \alpha f\left(x'\right) + \left(1-\alpha\right)f\left(x\right) \] for all \( x, \, x' \in A \) and all \( \alpha \in \left[0,\,1\right] \)
Convex Function A function \( f : A \rightarrow \mathbb{R} \) defined on a convex set \( A \subset \mathbb{R}^N \) is concave if and and only if \[ f \left( \alpha x' + \left(1-\alpha\right)x\right) \le \alpha f\left(x'\right) + \left(1-\alpha\right)f\left(x\right) \] for all \( x, \, x' \in A \) and all \( \alpha \in \left[0,\,1\right] \)
Negative semidefinite matrix An \( N \times N \) matrix \(A\) is negative semidefinite if \( z'Az \le 0 \) for all \(z\in\mathbb{R}^{N}\). A strict inequality implies negative definiteness.
Positive semidefinite matrix An \( N \times N \) matrix \(A\) is positive semidefinite if \( z'Az \ge 0 \) for all \(z\in\mathbb{R}^{N}\). A strict inequality implies positive definiteness.
\(t\)-upper contour set The set of all points in \(A\) with values greater than \(t\). \[ C_t^+ \left(f\right) = \left\{x\in A \, | \, f\left(x\right) \ge t \right\} \]
\(t\)-lower contour set The set of all points in \(A\) with values less than \(t\). \[ C_t^- \left(f\right) = \left\{x\in A \, | \, f\left(x\right) \le t \right\} \]
Quasiconcave Function A function \(f: A \rightarrow \mathbb{R}\) is quasiconcave if its upper contour sets \(C_t^+ \left( f \right)\) are convex for any \(t\in\mathbb{R}\). That is, \(\forall t\in\mathbb{R}\) and \(\forall\, x,\,x'\in A\): \[ \min \left\{ f\left(x\right),\, f\left(x'\right) \right\} \ge t \implies f\left(\alpha x + \left[1-\alpha\right]x'\right) \ge t. \] Equivalently, \( f \) is quasiconcave if and only if \[ f \left(\alpha x + \left(1-\alpha\right)x^\prime\right) \ge \min \left\{ f\left(x\right),\, f\left(x'\right) \right\} \] for all \(x, \, x^\prime \in A \) and \( \alpha \in \left[0, \, 1 \right] \). Any concave function is quasiconcave. Any increasing function \( f: \mathbb{R} \rightarrow \mathbb{R} \) is quasiconcave.
Quasiconvex Function A function \(f: A \rightarrow \mathbb{R}\) is quasiconvex if its lower contour sets \(C_t^- \left( f \right)\) are convex for any \(t\in\mathbb{R}\). That is, \(\forall t\in\mathbb{R}\) and \(\forall\, x,\,x'\in A\): \[ \max \left\{ f\left(x\right),\, f\left(x'\right) \right\} \le t \implies f\left(\alpha x + \left[1-\alpha\right]x'\right) \le t. \] Equivalently, \( f \) is quasiconex if and only if \[ f \left(\alpha x + \left(1-\alpha\right)x^\prime\right) \le \max \left\{ f\left(x\right),\, f\left(x'\right) \right\} \] for all \(x, \, x^\prime \in A \) and \( \alpha \in \left[0, \, 1 \right] \).
Local Maximizer/Minimizer of \(f\) A local maximizer is a vector \(x^\ast \in A\) where for a \(\delta > 0 \) \[ f\left(x^\ast\right) \ge f\left(x\right) \text{ for all } x \in B_\delta \left(x^\ast\right) \]. A local minimizer is defined by reversing the inequality.
Global Maximizer/Minimizer of \(f\) A global maximizer is a vector \(x^\ast \in A\) where for a \(\delta > 0 \) \[ f\left(x^\ast\right) \ge f\left(x\right) \text{ for all } x \in A \]. A local minimizer is defined by reversing the inequality.
Critical Points of \(f\) All \( x \in A\) such that \[ \nabla f \left( x \right) = 0 \]
Complementary Slackness requires \(\lambda_k^\ast\) = 0 if the constraint \[ h_i \left(x\right) \le c_i \] does not bind
Constraint Qualification An optimization problem satisfies constraint qualification if and only if the \( M \times N \) matrix \[ G \left( x^\ast \right) = \left[ \begin{matrix} \frac{\partial g_1 \left( x^\ast \right)}{\partial x_1} & \ldots & \frac{\partial g_1 \left( x^\ast \right)}{\partial x_N} \\ \vdots & \ddots & \vdots \\ \frac{\partial g_M \left( x^\ast \right)}{\partial x_1} & \ldots & \frac{\partial g_M \left( x^\ast \right)}{\partial x_N} \\ \end{matrix} \right] \] satisfies \( \operatorname{rank} \left(G\right) = M \) at an optimum \( x^\ast \in A \).
Correspondence Let \( X \) and \( Y\) be metric spaces. The correspondence \( \Gamma : X \rightrightarrows Y \) is a function from \( X \) to \( 2^Y \setminus \emptyset \).
Upper Hemicontinuous Correspondence A correspondence \( \Gamma \) is upper hemicontinuous at \(x \in X\) if for every open set \( O \subseteq Y \) with \( \Gamma \left( x \right) \subseteq O \), there exists \( \delta > 0 \) such that \( \Gamma \left( B_\delta \left( x \right) \right) \subseteq O \). \( \Gamma \) is upper hemicontinuous if this holds for every \( x \in X \).
Compact-Valued Correspondence \( \Gamma \) A correspondence \( \Gamma : X \rightrightarrows Y \) is compact valued if \( \Gamma \left( x \right) \) is compact in \(Y\) for each \(x\).
Closed-Valued Correspondence \( \Gamma \) A correspondence \( \Gamma : X \rightrightarrows Y \) is closed valued if \( \Gamma \left( x \right) \) is closed in \(Y\) for each \(x\).
Convex-Valued Correspondence \( \Gamma \) A correspondence \( \Gamma : X \rightrightarrows Y \) is convex valued if \( \Gamma \left( x \right) \) is convex in \(Y\) for each \(x\).
Lower Hemicontinuous Correspondence A correspondence \( \Gamma : X \rightrightarrows Y \) is lower hemicontinuous at \(x \in X\) if for every open set \(O \subseteq Y \) with \( \Gamma \left( x \right) \cap O \ne \emptyset \), there exists a \( \delta > 0 \) such that \( \Gamma \left( x' \right) \cap O \ne \emptyset \) for all \( x' \in B_\delta \left(x\right)\). \( \Gamma\) is lower hemicontinuous if this holds at each \(x \in X \).
Upper Inverse Image \[ \Gamma^{-1} \left( O \right) \equiv \left\{ x \in X \, | \, \Gamma \left(x\right) \subseteq O \right\} \]
Lower Inverse Image \[ \Gamma_{-1} \left( O \right) \equiv \left\{ x \in X \, | \, \Gamma \left(x\right) \cap O \ne \emptyset \right\} \]
Continuous Correspondence A correspondence \(\Gamma\) is called continuous if it is both upper and lower hemicontinuous.
Closed Graph Property A correspondence is closed at \(x \in X\) if for all sequences \(x_n \rightarrow x \text{ and } y_n \rightarrow y \), we have \( y \in \Gamma \left( x \right) \) whenever \( y_n \in \Gamma \left( x_n \right) \) for all \( n \). If \(\Gamma\) is closed at every \(x\), then it has the closed graph property.
Hyperplane in \( \mathbb{R}^{N} \) A \(N-1\) dimensional subset of \(\mathbb{R}^{N}\) that can be described by a single linear equation: \[ H \left(p,\,r\right) = \left\{ x \in \mathbb{R}^N \, | \, p \cdot x = r \right\} \] where \(p\) is a non-zero vector in \(\mathbb{R}^N\) and \(r\) is a real number.
Separating Hyperplane Let \(A, B \subset \mathbb{R}^N, \, p \in \mathbb{R}^N \setminus \left\{ 0 \right\} \). The hyperplane \( H \left( p, \, r \right) \) separates \(A\) and \(B\) if \( p \cdot r \ge r \forall x \in A \) and \( p \cdot y \le r \forall y \in B \)
Proper Separation of Sets The separation of sets \(A, \, B \subset \mathbb{R}^N \text{ by } H \left(p, \, r \right) \) is proper if there exists \(x \in A \text{ and } y \in B \text{ such that } p \cdot x \ne p \cdot y \)
Strict Separation of Sets The hyperplane \(H \left(p, \, r \right)\) strictly separates sets \(A, \, B \subset \mathbb{R}^N\) if \[ p \cdot x > r \text{ for all} x \in A \text{ and } p \cdot y < r \text{ for all } y \in B \]
Partially-Ordered Set (poset) A pair \( \left(X, \succsim \right) \) where \(X\) is a set and \(\succsim\) is a partial order.
Partial Order A binary relation \( \succsim \subseteq X \times X \) that satisfies: (a) reflexivity: \( \forall x \in X, \, x \succsim x \), (b) antisymmetry: \(\forall x, y \in X\) if \(x \succsim y\) and \(y \succsim x\) then \(x = y\), and (c) transitivity: \(\forall x, y, z \in X\) if \(x \succsim y\) and \(y \succsim z\) then \(x \succsim z\).
Chain A poset is called a chain if the partial order \( \succsim \) is complete on \( X \). That is, for all \(x, y \in X \) either \( x \succsim y \) or \( y \succsim x \).
Bounds of a Poset Let \(E \subseteq X \) be a subset of a poset. If we have \(x^\prime \succsim x\) for all \(x \in E\), then \( x^\prime \) is an upper bound for E; similarly if \(x \succsim x^\prime \) for all \(x \in E\) then \( x^\prime \) is a lower bound for \(E\).
Supremum of \(E\) in \(X\) Denoted \(\sup_X \left(E \right) \), the supremum of \(E\) in \(X\) is an element \( x^\ast \in X \) such that \(x^\ast \) is an upper bound of \( E \) and if \( x^\prime \) is an upper bound of \( E \), then \( x^\prime \succsim x^\ast\).
Infimum of \(E\) in \(X\) Denoted \(\inf_X \left(E \right) \), the infimum of \(E\) in \(X\) is an element \( x_\ast \in X \) such that \(x_\ast\) is a lower bound of \(E\) and if \(x'\) is a lower bound of \(E\), then \(x_\ast \succsim x'\).
Join of \(x \text{ and } y\) For a two element subset \( \left\{x,\,y\right\} \subseteq X\), the supremum of \( \left\{x,\,y\right\}\) in \(X\) is called the join and is denoted \(x \vee y \).
Meet of \(x \text{ and } y\) For a two element subset \( \left\{x,\,y\right\} \subseteq X\), the infimum of \( \left\{x,\,y\right\}\) in \(X\) is called the meet and is denoted \( x \wedge y \).
Lattice A poset \( \left(X,\,\succsim \right) \) such that \(x \vee y \) and \(x \wedge y\) exist for every pair of elements \(x,y \in X\).
Sublattice Let \(\left(X,\,\succsim\right)\) be a lattice. A set \( E \subseteq X \) is called a sublattice of \(X\) if \(\forall x, y \in E\), we have \(\sup_X \left(\left\{x,\,y\right\}\right) \in E \) and \( \inf_X \left( \left\{x,\,y\right\}\right) \in E \). That is, \(E\) contains the meet and join of all combinations of its elements. The collection of all nonempty sublattices for a lattice \( \left(X, \, \succsim \right) \) is denoted \( \mathcal{L} \left( X \right) \).
Induced Set Ordering on \( \mathcal{L} \left( X \right) \) Denoted \( \sqsubseteq \) and defined by \( A \sqsubseteq B \) if and only if for all \( x \in A \text{ and } y \in B \), we have \(x \wedge y \in A \) and \(x \vee y \in B\).
Complete Lattice A lattice \( \left(X, \, \succsim \right) \) is called complete if \( \sup_X \left( E \right) \) and \( \inf_X \left( E \right) \) both exist for every nonempty subset \( E \subseteq X \).
Subcomplete Sublattice A sublattice \(E\) of \(X\) is subcomplete if \( \sup_X \left( F \right) \) and \( \inf_X \left( F \right) \) are both in \(E \) for every nonempty set \( F \subseteq E\).
Increasing and Decreasing Monotone Functions Let \( \left(X,\,\succsim_X\right)\) and \( \left( Y, \, \succsim_Y \right) \) be posets. A function \(f \,: \, X \rightarrow Y \) is increasing if \(x \succsim_X x' \implies f \left(x\right) \succsim_Y f\left(x'\right)\) for all \(x, x' \in X\). A function \(f \,: \, X \rightarrow Y \) is decreasing if \(x \succsim_X x' \implies f \left(x'\right) \succsim_Y f \left( x \right) \) for all \( x, x' \in X\). The function is monotone if it is either increasing or decreasing.
Increasing Differences Let \(X\) and \(T\) be posets and let \(S \subseteq X \times T\). A function \(f \, : \, S \rightarrow \mathbb{R} \) has increasing differences on \(S\) if \(f \left(x, \, t'\right) - f\left(x, \, t \right) \) is increasing in \(x\) on the set \(\left\{ x \in X \, | \, \left( x, \, t' \right) \in S \text{ and } \left(x, \, t \right) \in S \right\} \) for all \(t' \succ t \).
Supermodular Function Let \(X\) be a lattice. A function \(f \, : \, X \rightarrow \mathbb{R} \) is called supermodular iff \[ f \left( x \right) + f \left( x' \right) \le f \left( x \vee x' \right) + f \left( x \wedge x' \right)\] for all \(x, x' \in X \).
Quasisupermodular Function Let \(X\) be a lattice and \(Y\) be a poset. A function \(f : \, X \rightarrow Y \) is quasisupermodular if \[ f \left( x \right) \succsim \left( \succ \right) f \left( x \wedge x' \right) \implies f \left( x \vee x' \right) \succsim \left( \succ \right) f \left( x' \right) \] for all \(x, \, x' \in X\).
Single Crossing Property Let \(X, \, T, \text{ and } Y\) be posets and \( S \subseteq X \times T \). A function \( f : \, S \rightarrow Y \) satisfies the single crossing property on \(S\) if \[ f \left( x', \, t \right) \succsim \left( \succ \right) f \left( x, \, t \right) \] \[ \implies \] \[ f \left( x', \, t' \right) \succsim \left( \succ \right) \, f \left( x, \, t' \right) \] for all \( x' \succ x \) and \( t' \succ t \) with \( \left\{x, \, x'\right\} \times \left\{t, \, t' \right\} \subseteq S \).
Show full summary Hide full summary

Similar

Sociology- Family and Households Flashcards
Heloise Tudor
CUMULATIVE FREQUENCY DIAGRAMS
Elliot O'Leary
GCSE AQA Biology 2 Plants & Photosynthesis
Lilac Potato
Atomic numbers and mass numbers quiz
Sarah Egan
Salesforce Admin 201 Exam Chunk 3 (66-90)
Brianne Wright
Organigramas
Sindy Deydania
Teoria del Consumidor y del Mercado: Oferta, Demanda y Precio
Camila Nicole Quijano Escobar
MECANISMOS DE PARTICIPACIÓN CIUDADANA
AMADO S JOHAN
Data Types
Santiago Castillo
AUDITORIA INTERNA Y EXTERNA
Angel Chimbolema
Cells And Cell Techniques - Flashcards (AQA AS-Level Biology)
Chelsie Cottingham