How can one characterise compactness-by-experiment? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T14:20:41Z http://mathoverflow.net/feeds/question/23683 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/23683/how-can-one-characterise-compactness-by-experiment How can one characterise compactness-by-experiment? Andrew Stacey 2010-05-06T10:34:09Z 2010-05-10T18:50:10Z <p>There are a myriad different variations on the theme of "compactness", and some of them have even made it on to Wikipedia. I'm interested in finding out more about types of compactness that fit the concept of doing experiments on an object to find out about it.</p> <p>Let me explain the idea in a little more detail. In some branches of mathematics, we try not to study an object itself too closely. Category theory could be viewed as the extreme example of this, but it also finds a home in homotopy theory, cohomology theory, differential topology and geometry, and no doubt in others as well. The idea being that one has a family of "nice" objects and uses them to "probe" or "coprobe" the object in question. More prosaically, one tries to figure out the shape of the object in question either by throwing mud at it (to see what sticks) or by taking photographs of it. Less prosaically, we study $X$ by looking at morphisms $g \colon Y \to X$ or $f \colon X \to Y$ (where $Y$ runs over our family of "nice" objects).</p> <p>For some property of our object, we can then ask "Can we detect it by doing these experiments?", or, more generally, "Is there something a bit like it that I can detect using experiments?" (the belief that these are the same question could go on the "false mathematical beliefs" question!).</p> <p>Let's home in on the case I'm interested in: compactness. If we were probing our space by looking at maps from $\mathbb{N}$ (aka sequences), then we would come up with the notion of "sequentially compact". If we were probing our space by looking at maps to $\mathbb{R}$ (aka functionals), then we would come up with the notion of "pseudocompactness" (no, I'd never heard of it either before I looked it up on Wikipedia a couple of days ago!).</p> <p>So, to my question: are there other examples of variations on the theme of compactness that fit this pattern? I'm particularly interested in the case of maps from $\mathbb{R}$ (path-compactness, perchance?) but anything of this flavour would be helpful.</p> <p>I'm specifically looking for stuff that's known. If there's nothing that's known then I'm interested in trying to figure out what it should look like, but that's not a good MO question so I'm not asking it. Anyone interested in this wider question is welcome to join in a discussion on it over at the <a href="http://www.math.ntnu.no/~stacey/Vanilla/nForum/comments.php?DiscussionID=1218" rel="nofollow">nForum</a>.</p> http://mathoverflow.net/questions/23683/how-can-one-characterise-compactness-by-experiment/23704#23704 Answer by Joel David Hamkins for How can one characterise compactness-by-experiment? Joel David Hamkins 2010-05-06T13:09:42Z 2010-05-06T13:09:42Z <p>Perhaps this isn't what you had in mind, but the <a href="http://en.wikipedia.org/wiki/Compactness_theorem" rel="nofollow">Compactness Theorem</a> of first order logic, proved by Goedel, fits your "experimental" metaphor quite well, and variations on its theme have led to some major subtopics of logic. </p> <p>Namely, the Compactness Theorem asserts that if $T$ is a first order theory and every finite subtheory $T_0\subset T$ is true in some structure, then $T$ also is satisfiable. </p> <p>For example, this theorem can be used to legitimize <a href="http://en.wikipedia.org/wiki/Nonstandard_analysis" rel="nofollow">nonstandard analysis</a>, since we may let $T$ be the theory of all truths of the standard model $\langle R,Z,+,\cdot,0,1,\lt\rangle$, together with all finite assertions $1+\cdots+1\lt c$, using a new constant symbol $c$. Every finite subtheory of this theory is satisfied simply by interpreting $c$ to be sufficiently large. Thus, by Compactness, the entire theory has a model. Any such model will satisfy all the same truths as the standard model (hence the Transfer principle), yet it will have infinitely large integers and so on.</p> <p>There are numerous other applications of Compactness in model theory, and its use is pervasive. These applications fit your experimental metaphor, since one probes a theory $T$ by underestanding its finite restrictions. </p> <p>But this is actual compactness (there is a topological space here, usually sublimated, whose compactness is expressed by the theorem), and you had asked for variations on the theme. So let me mention a few variations on the theme of the Compactness Theorem in logic. </p> <ul> <li>The concept of Weakly Compact and <a href="http://en.wikipedia.org/wiki/Strongly_compact_cardinal" rel="nofollow">Strongly Compact cardinals</a>, two large cardinals notions, are based on infinitary analogues of Compactness. Namely, an uncountable cardinal $\kappa$ is (strongly) compact if and only if every theory $T$ in the infinitary $L_{\kappa\kappa}$ logic (allowing meets and joins of size less than $\kappa$ and quantification over less than $\kappa$ many variables at once) which is $\kappa$-satisfiable (every subtheory of size less than $\kappa$ has a model) is satisfiable. This concept generalizes your "probing" idea to understand a very large object by looking at its small subobjects, where the concept of large and small is provided by the cardinal $\kappa$. Among numerous equivalent formulations, it turns out that an uncountable cardinal $\kappa$ is compact if and only if every $\kappa$-complete filter on a set extends to a $\kappa$-complete ultrafilter. </li> <li>That concept was generalized by Solovay to the <a href="http://en.wikipedia.org/wiki/Supercompact_cardinal" rel="nofollow">supercompact cardinals</a>, a touchstone in the large cardinal hierarchy. </li> <li>The <a href="http://en.wikipedia.org/wiki/Strongly_compact_cardinal" rel="nofollow">Barwise Compactness Theorem</a> is a generalization of the Compactness Theorem in (a much smaller) infinitary logic, using the concept of admissible sets. One understands a complex theory by looking at comparatively simple subtheories.</li> </ul> http://mathoverflow.net/questions/23683/how-can-one-characterise-compactness-by-experiment/23736#23736 Answer by Gerald Edgar for How can one characterise compactness-by-experiment? Gerald Edgar 2010-05-06T15:56:50Z 2010-05-06T15:56:50Z <p><strong>realcompact</strong><br> $X$ is called <em>real-compact</em> iff its canonical image in $\mathbb{R}^{C_b(X)}$ is closed.</p> <p><strong>measure-compact</strong><br> A completely regular Hausdorff space $X$ is called <em>measure-compact</em> iff every $\sigma$-smooth (finite, Baire) measure is $\tau$-smooth. Topologically, measure-compact is a property intermediate between Lindelof and realcompact.</p> <p>variants: <strong>strongly measure-compact</strong> and <strong>lifting-compact</strong></p> <p>For lifting-compact space $X$, you probe with measurable functions from a complete probatility space into your space $X$, for full definition, see:<br> My paper with Talagrand ... Proc. Amer. Math. Soc. 78 (1980) 345--349<br> This introduced "lifting-compact", but the term was not coined until later by Alexandra Bellow.</p> http://mathoverflow.net/questions/23683/how-can-one-characterise-compactness-by-experiment/23790#23790 Answer by Andrej Bauer for How can one characterise compactness-by-experiment? Andrej Bauer 2010-05-06T21:56:01Z 2010-05-06T21:56:01Z <p>There is a connection between compactness and universal quantifiers. Let $\Sigma = \lbrace{0, 1\rbrace}$ be the <a href="http://en.wikipedia.org/wiki/Sierpi%25C5%2584ski_space" rel="nofollow">Sierpinski space</a>. Given a space $X$ with topology $O(X)$ and a subset $S \subseteq X$, let $\forall_S : O(X) \to \Sigma$ be the map characterized by</p> <blockquote> <p>$\forall_S(U) = 1$ iff $S \subseteq U$.</p> </blockquote> <p>When $O(X)$ is equipped with <a href="http://en.wikipedia.org/wiki/Scott_topology" rel="nofollow">Scott topology</a> we have</p> <blockquote> <p>$S$ is compact iff $\forall_S$ is continuous.</p> </blockquote> <p>What does all this have to do with the question? Well, computing whether $\forall x \in S . x \in U$ is a way of <em>probing</em> the space $S$. To say that the universal quantifier is continuous is to say that the probing is topologically well behaved.</p> <p>For a surprising application of these ideas in computer science see Martin Escardó's "<a href="http://math.andrej.com/2007/09/28/seemingly-impossible-functional-programs/" rel="nofollow">Seemingly impossible functional programs</a>" in which he explains what compactness has to do with searching a space. For more advanced presentations of the role of compactness in computing you can have a look at the work of <a href="http://www.paultaylor.eu/" rel="nofollow">Paul Taylor</a> and of <a href="http://www.cs.bham.ac.uk/~mhe/" rel="nofollow">Martin Escardó</a>.</p> http://mathoverflow.net/questions/23683/how-can-one-characterise-compactness-by-experiment/24024#24024 Answer by Bill Kronholm for How can one characterise compactness-by-experiment? Bill Kronholm 2010-05-09T14:57:39Z 2010-05-09T15:11:31Z <p>If $J$ is a directed set and $X$ is a topological space, then a <i>net</i> in $X$ is a function $f\colon J \to X$. A net converges to $x \in X$ if for every neighborhood $U$ of $x$ there is $\alpha \in J$ so that $\alpha \preceq \beta \implies f(\beta)\in U$.</p> <p>Given a net $f \colon J \to X$, a <i>subnet</i> is a net $f\circ g \colon K \to X$ where $g \colon K \to J$ is a map of directed sets so that $g(K)$ is cofinal in $J$.</p> <p>Theorem. $X$ is compact iff every net in $X$ has a convergent subnet.</p> <p>So, rather than probing your space with sequences to determine compactness, you instead probe your space with directed sets. </p> http://mathoverflow.net/questions/23683/how-can-one-characterise-compactness-by-experiment/24029#24029 Answer by Henno Brandsma for How can one characterise compactness-by-experiment? Henno Brandsma 2010-05-09T16:27:01Z 2010-05-10T18:50:10Z <p>Another similar idea: a space $X$ is connected iff it has no non-constant continuous functions from $X$ to {0,1} in the discrete topology.</p>