compact

(mathematics)

(a) Set S is compact if every open cover of S can be reduced to a finite open cover.

(b) Set S is sequentially compact if every sequence has a convergent subsequence.

(c) Set S is countably compact if every infinite set has a limit point.

In metric spaces, (a), (b), and (c) are equivalent, while in general topology this is not always the case. The Heine-Borel Theorem explains more about what properties are associated with compact sets, based on the definition of compact.

Updated 20 June 2002: Revised for clarity.

Source: Set Theory and Metric Spaces, by Irving Kaplansky. ISBN 0-8284-0298-1

The definition above by tongpoo is valid, but there's some more that should be said about compactness.

There are actually two very different definitions of compactness:

• A subset E of a metric space X is said to be Heine-Borel compact if for every open cover {G_i}, there exists a finite list of indices a₁,a₂,...,a_k such that {G_a1,G_a2,...,G_ak} covers E. This says just what tongpoo's definition above says: that every open cover of E can be reduced to a finite open cover.
• On the other hand, E is said to be Weierstrass-Bolzanno compact if every infinite subset S of E has a limit point in E.

As it turns out, these two properties are in fact equivalent; the proof is pretty involved, so I won't include it here.

Note: (sorry for splitting hairs here)
The Heine-Borel Theorem is slightly weaker than the statement in tongpoo's writeup. It actually states that a subset S of R^n is compact iff it is closed and bounded.
This is not necessarily true of metric spaces in general. For example, consider the metric space Q, the rational numbers, with the metric d defined by d(p,q)=|p-q|. In this metric space, the set E := {p in Q | 2 < p^2 < 3}, i.e. the set of rational numbers between sqrt(2) and sqrt(3), is in fact both closed and bounded, but not compact. Since sqrt(2) is not in the metric space Q, it is not a limit point of E. However, it is not hard to see that we could construct an infinite subset of E with limit point sqrt(2); since sqrt(2) is not in E, this would violate the Weierstrass-Bolzanno property above, so that E is not compact.

It's hard to know if I've been clear in this writeup. Please /msg me and let me know either way.

What isn't clear from the above is why anyone bothered to define the notion of compactness: in my opinion it is an idea which perfectly embodies the notion of mathematical elegance.
I suppose a deep reason why the notion of compactness is useful comes from the defining axioms of topological spaces: that any finite intersection of open sets is open, but that arbitary intersections are not (eg. consider the intersection of all the open sets (-ε,ε) for all ε between 0 and 1 - the intersection is {0}, which is not open). Given compactness, we can reduce the arbitary intersections to finite ones and then there is no problem.

Here are a few nice consequences of compactness:

• Proofs get a lot shorter. Compare these two proofs that a continuous image of [ 0,1 ] is closed and bounded:
  • Given any sequence of points (x_n) in [ 0,1 ] , it will have a subsequence converging to some point in [ 0,1 ] (because closed and bounded). Knowing this, one can show that the image set also has convergent subsequences to arbitary sequences too: let (y_n) be such a sequence in the image set, and then for each y_n define a x_n such that f(x_n)=y_n. The given the convergent subsequence of the (x_n), can define one for the (y_n), which agree in the limit by the continuity of f.
    The subsequence property on the image set, one can show that it is closed and bounded: if not could produce a sequence (y_n) such that |y_n| > n for every n, which could not have a convergent subsequence. Nasty.
  • [ 0,1 ] is closed and bounded, so compact. The continuous image of a compact set is compact - and hence too closed and bounded. Nice.
  In this way, you can prove many similar things quickly by simply stringing together known lemmas about compact spaces.
• You can make lots of spaces compact simply by adding an extra point (and making a change to the topology)- eg. adding 'infinity' to the complex plane turns it into the Riemann Sphere. Doing this gives you a sensible way to deal with infinity, and gives rise to the notion of Riemann Surfaces, which are things of great beauty.
• Its simple formulation and applicability to all topological spaces make it a powerful abstraction mechanism.

B(0,1)={x \in R²| |x|<1} is not a compact disc, since {B(0,t) | t \in (0,1)} is an open cover with no finite subcover (such a subcover would have a maximal t,t_n, and then B(0,t₀) U B(0,t₁) U ... U B(0,t_n) = B(0,t_n) does not cover B(0,1) since t_n <1).

Some elementary results on compact spaces, a couple of simple proofs, and one deeper result.

Lemma Let X be a compact topological space and let C be a closed subset of X. Then C is compact.

Proof Let A be an open cover of C.

Since C is closed in X, the set X\C is open in C, and so A union {X\C} is an open cover of X. Since X is compact, this has a finite subcover B of X, and then B\{X\C} is a finite open cover of C which is a subcover of A. So C is compact.

Lemma A compact subspace of a Hausdorff topological space X is closed in X.

Proof Let x be in X\C. X is Hausdorff, so for each c in C there are disjoint open sets U_c and V_c such that U_c contains c and V_c contains c.

Then the collection {U_c : c in C} is an open cover of C. Since C is compact, this has a finite subcover {U_c1, U_c2, ..., U_ck}.

Now let V_x = Intersect{V_c1, V_c2, ..., V_ck}. V_x is the intersection of finitely many open sets containing x, and so is an open set containing x. Moreover, V_x does not intersect C; for if y is in C then y is in U_cr for some r, and so y is not a member of V_cr, and hence is not in V_x.

What we have shown so far is that whenever x is in X\C then there is an open set V_x which contains x and does not meet C. Then Union{V_x : x in X\C} is open, contains X\C, and does not meet C, so in fact it must equal X\C.

Then X\C is open, so C is closed.

Lemma Let X,Y be topological spaces with X compact and let f:X->Y be continuous and onto. Then Y is compact.

Lemma A topological space X is compact if and only if the following property holds: whenever Z is a collection of closed sets in X such that the intersection of finitely many elements of Z is nonempty, then Intersection(Z) is nonempty.

Proof Repeated application of De Morgan's laws for sets.

Lemma A compact subset of a metric space is bounded.

Proof Let (X,d) be a metric space, C a compact subset.

If Y is empty, then Y is vacuously bounded. Otherwise let y be in Y, and let U_n = {y' in Y : d(y,y')<n}. Then {U_n : n in N} is an open cover of Y, and so it has a finite subcover {U_n1, U_n2, ..., U_nr}. Then d(y,y')<r whenever y' is in Y, so Y is bounded.

Lemma A finite product of compact spaces is compact.

While the last result can be proven using elementary methods, the generalisation to infinite products is much harder to prove, and is in fact equivalent to the axiom of choice.

Theorem (Tychonoff) An arbitrary product of compact spaces is compact in the product topology.

Commonwealth Hackish = C = compiler jock

compact adj.

Of a design, describes the valuable property that it can all be apprehended at once in one's head. This generally means the thing created from the design can be used with greater facility and fewer errors than an equivalent tool that is not compact. Compactness does not imply triviality or lack of power; for example, C is compact and FORTRAN is not, but C is more powerful than FORTRAN. Designs become non-compact through accreting features and cruft that don't merge cleanly into the overall design scheme (thus, some fans of Classic C maintain that ANSI C is no longer compact).

--The Jargon File version 4.3.1, ed. ESR, autonoded by rescdsk.

In non-standard analysis, we have the following equivalent definition for a (standard) topological space X which is a Hausdorff space to be compact:

X is compact iff every non-standard pseudo-element of X^* has a standard approximation in X.

Here is a clear advantage of using NSA. The "standard" (pun intended) definition of compactness has two quantifiers: For all open coverings of X, there exists a finite subcovering. Worse, we're quantifying over sets of subsets of X! The "non-standard" (but equivalent) definition uses only one quantifier, and only on pseudo-elements of X.

In a compact space, every pseudo-element is close to some element. Compare with the example given for N in standard approximation, where no pseudo-element is infinitesimally close to a standard element.

---

Proof of the equivalence

⇒:

Suppose X is a compact topological space. We must prove that every element of X^* has a standard approximation in X. That is, for any non-standard y in X^*, we must find x∈X such that for any (standard!) open neighborhood x∈U⊆X of x in X, y is a pseudo-element of U ("y∈U^*").

Suppose some y had no standard approximation. Then for any standard x∈X there is some open neighborhood U_x⊆X of which y is not a pseudo-element. Obviously, the set of all U_x's contains all x's, thus is a covering of X. As X is compact, it has a finite sub-covering U_x1,...,U_xn. But then the proposition "∀t.t∈X→t∈U_x1 v ... v t∈U_xn" is true of the standard world (it just says "U_x1,...,U_xn is a covering of X"), but not of the non-standard world -- a contradiction, as all propositions are true of the standard world iff they are true of the non-standard world! Thus, every y has a standard approximation. Note the use of finiteness: if X had only infinite sub-coverings with U_x's, then we would be unable to form our proposition -- all propositions have finite length!

⇐:

Suppose now every y has a standard approximation. Given any open covering {U_α}_α∈I of X, we must find a finite sub-covering. Suppose no such finite sub-covering existed. Then for any choice of α₁,...,α_n there would be some x_α1,...,αn not in any of U_α1,...,U_αn. Form all the propositions "∃x.x∈X&x∉U_α". Then any finite subset of these propositions has some standard x∈X satistfying it, thus some (non-standard) y∈X^* satisfies all these propositions, simultaneously. But this y cannot have a standard approximation -- every standard x is in some U_α, and y is in none of them.

Thus, if every non-standard y has a standard approximation in X, then X must be compact.

Com*pact" (?), p. p. & a [L. compactus, p. p. of compingere to join or unite; com- + pangere to fasten, fix: cf. F. compacte. See Pact.]

1.

Joined or held together; leagued; confederated.

[Obs.] "Compact with her that's gone."

Shak.

A pipe of seven reeds, compact with wax together. Peacham.

2.

Composed or made; -- with of.

[Poetic]

A wandering fire, Compact of unctuous vapor. Milton.

3.

Closely or firmly united, as the particles of solid bodies; firm; close; solid; dense.

Glass, crystal, gems, and other compact bodies. Sir I. Newton.

4.

Brief; close; pithy; not diffuse; not verbose; as, a compact discourse.

Syn. -- Firm; close; solid; dense; pithy; sententious.

 

© Webster 1913.

---

Com*pact", v. t. [imp. & p. p. Compacted; p. pr. & vb. n. Compacting.]

1.

To thrust, drive, or press closely together; to join firmly; to consolidate; to make close; -- as the parts which compose a body.

Now the bright sun compacts the precious stone. Blackstone.

2.

To unite or connect firmly, as in a system.

The whole body fitly joined together and compacted by that which every joint supplieth. Eph. iv. 16.

 

© Webster 1913.

---

Com"pact (?), n. [L. compactum, fr. compacisci, p. p. compactus, to make an agreement with; com- + pacisci to make an agreement. See Pact.]

An agreement between parties; a covenant or contract.

The law of nations depends on mutual compacts, treaties, leagues, etc. Blackstone.

Wedlock is described as the indissoluble compact. Macaulay.

The federal constitution has been styled a compact between the States by which it was ratified. Wharton.

Syn. -- See Covenant.

 

© Webster 1913.