5

In "continuous" mathematics there are several important notions such as covering space, fibre bundle, Morse theory, simplicial complex, differential equation, real numbers, real projective plane, etc. that have a "discrete" analog: covering graph, graph bundle, discrete Morse theory, abstract simplicial complex, difference equation, finite field, finite projective plane, etc. I would like to know if there are others. But the real question is: Are there any important "continuous" mathematical concepts without "discrete" analog and vice versa?

Tomaž Pisanski
  • 774
  • 8
    I'm not sure what kind of answers you're looking for. Would inner product spaces or normed vector spaces fit the bill? – Darsh Ranjan Mar 08 '10 at 21:38
  • 9
    Finite fields are not the discrete analogs of fields. – lhf Mar 08 '10 at 21:39
  • 5
    Maybe this should be tagged as soft-question – Andrea Ferretti Mar 08 '10 at 21:47
  • 2
    @lhf: you say that confidently. Is it so clear? Note that a characterization of fields which are algebraic over p is that these are the only fields which do not admit a compatible, nondiscrete topology. Let's be clear that the phrase discrete analogue does not have an a priori meaning: it requires interpretation in any given case. (Right?) – Pete L. Clark Mar 08 '10 at 21:47
  • I replaced a "field" by "real numbers". I hope this better illustrates my point. – Tomaž Pisanski Mar 08 '10 at 21:50
  • 5
    Your question is perhaps hopelessly vague. What purpose does the "analogue" have? If it has no purpose, you could call X a discrete analogue of Y for any pair (X,Y). An abstract simplicial complex isn't really "discrete" is it? If it was finite, sure, but if it's infinite, how would it qualify as discrete? – Ryan Budney Mar 08 '10 at 21:59
  • 6
    I suppose we can also do this in reverse... Are there any important mathematical concepts without continuous analog? – Gerald Edgar Mar 09 '10 at 01:31
  • Regarding my previous comment, it should read "algebraic over $\mathbb{F}_p$". – Pete L. Clark Mar 09 '10 at 02:28
  • 1
    @Ryan: Outside mathematics, even if speaking about maths everything becomes vague and subjective. For instance, the word "discrete" need not necessary mean "equipped with discrete topology". Unfortunately I could not find any word that would be less vague than "analogy".

    @Gerald: You are right. One should probably rephrase this question to make it more balanced. A step in the reverse direction would probably be a move from finite to infinite, say from matrices to Banach spaces and I am sure one can find more.

     – Tomaž Pisanski Mar 09 '10 at 06:59
  • 2
    I'm voting to close for vagueness. – Harry Gindi Mar 09 '10 at 07:15
  • 1
    +1 to Darsh Ranjan's comment about inner product spaces. Even in the $p$-adic world it is a constant sticking point that one has the notion of a non-degenerate symmetric bilinear form on a finite-dimensional vector space over the $p$-adics, but not the notion of a positive definite one. Over finite fields you're in just as bad shape because there's no notion of positivity on a finite field either. I can say more about this but am running out of space and am reluctant to take the credit for Darsh's comment. Darsh---can you post "inner product space" as an answer? – Kevin Buzzard Mar 09 '10 at 10:37
  • 1
    @Tomasz: "analogy" means: to have something similar or in common. You may use word: similar or have something in common. It is vague in the same level, but is less mysterious. – kakaz Mar 09 '10 at 11:05
  • @kakaz: I think he meant "give a rigorous mathematical definition", not a dictionary definition. I think his point is that in some sense this is not a mathematical question (e.g. it can't be reformulated as a proposition within ZFC set theory). – Kevin Buzzard Mar 09 '10 at 11:56
  • @Kevin - analogies, similarities etc. are useful for inspiration. But it cannot be formalized,because its meaning lays in someone opinion, understanding etc. Connection between ideas is sometimes related to deep understanding of something but in my opinion is not formalizable. Formalization here may lead You into bigger troubles than being vague... If You use word "similar" instead of "analogous", it is clear that You say only opinion, and next question is about criteria of similarity. If You use mysterious analogy, nothing is clear. – kakaz Mar 11 '10 at 07:26
  • @Kevin (part2): and mathematics is not so precise in discovery process as we usually think. Many mathematical discoveries was vague but very important, before someone formalize them. Important mathematical connections should be formalized, but process of creating such relations should not. The way we see relations (analogies) between discrete-continue is pure historical, wee treat it as important here and now. Laplace has seen determinism everywhere. And it was not mistake, it was the same type of reasoning as our now. – kakaz Mar 11 '10 at 07:31
  • Oh, didn't realize this question was prehistoric before CW convention. – Benjamin Steinberg Aug 20 '12 at 02:03
  • @GeraldEdgar: The answer to your question is yes! Busy-beaver numbers have no continuous analog. =D – user21820 Mar 23 '18 at 08:29

9 Answers9

14

Is there a discrete analogue of the notion of discreteness?

Reid Barton
  • 24,898
8

A timely example would be the lack of a combinatorial Ricci flow in dimensions $n \geq 3$. In principle I think many people believe there should be one, but a combinatorial/discrete formalism has yet to be found.

Ryan Budney
  • 43,013
4

A lot of ideas from topology and analysis don't have obvious discrete analogues to me. At least, the obvious discrete analogues are vacuous.

  • Compactness.
  • Boundedness.
  • Limits.
  • The interior of a set.

I think a better question is which ideas have surprisingly interesting discrete analogues, like cohomology or scissors congruence.

Douglas Zare
  • 27,806
  • 1
    It depends on what you mean by obvious... One example: the interior of a set $X$ of vertices in a graph may very well be defined as that subset of those elements in $X$ all of whose neighbors are in $X$. – Mariano Suárez-Álvarez Mar 08 '10 at 22:24
  • 3
    I'd agree that some of these discrete analogues can be vacuous, but isn't that the point? For example, when we study compact sets in topology are we not, at least sometimes, trying to find non-trivial analogues of results that are trivially true of finite sets in the discrete case? – Dan Piponi Mar 08 '10 at 22:41
  • 1
    Actually, boundedness is one of the possible continuous generalization of finiteness. Compactness is another. As for "the interior of a set", there is linear optimization where one is talking about interiors of polytopes, and while it is usually done in R^n, it could equally well be studied over Q^n or (any ordered field)^n, and actually is a combinatorial science where discrete algorithms such as the simplex method matter, and the continuous structure of the field is just a red herring. – darij grinberg Mar 08 '10 at 22:46
  • 22
    It amuses me that this answer has been accepted when discrete mathematicians would use analogues of every single one of these. I recommend a look at this post of Terry Tao: http://terrytao.wordpress.com/2007/05/23/soft-analysis-hard-analysis-and-the-finite-convergence-principle/ – gowers Mar 08 '10 at 23:51
  • The interior of a subset of a simplicial complex makes sense, so I've struck that out. It's not an inherently topological concept. I wouldn't consider $\mathbb Q^n$ discrete. I'm not convinced that compactness or boundedness are attempts to generalize important properties of finite sets rather than of $[0,1]$. Thanks for bringing up that blog entry. I certainly expected that my answer would bring out contrary ideas, and I hope people will contribute more. – Douglas Zare Mar 09 '10 at 00:08
  • 3
    I don't know if compactness is a "generalization of finiteness properties" as such, but it certainly gets used as a substitute for finiteness all the time. There are various parts of Banach space/Banach algebra theory where a desire to interchange the order of various iterated limits can be done by judicious appeal to weak compactness of various sets. – Yemon Choi Mar 09 '10 at 08:50
  • 2
    It should also be pointed out that in some sense discreteness and compactness sit at opposite ends of the spectrum of locally compact spaces, so that it's not clear what a "discrete analogue" (as opposed to a "quantitative, finite analogue" might be – Yemon Choi Mar 09 '10 at 08:52
  • I am coming from graph theory. I was fascinated by the fact, that "conectedness" and "path conectedness" coincide for graphs. Obviously, one has to prove that. However, the topological notion of a "path" corresponds to the idea of a "trail" in graph theory, while an "open set" corresponds to a union of connected components of graphs. – Tomaž Pisanski Mar 30 '10 at 19:33
  • I strongly would argue finiteness is the analogue of compactness for discrete. Just compare the representation theory of compact groups and finite groups. – Benjamin Steinberg Aug 20 '12 at 02:01
4

The intermediate value theorem wouldn't be true in a discrete setting.

Douglas S. Stones
  • 4,209
  • 3
    There is even a discrete analog (Sperner's lemma) to the fixed point theorem. – Gil Kalai Dec 13 '10 at 16:30
  • 5
    I've used the following discrete analogue of the intermediate value theorem in a paper. If you have a function $f$ from the integers to the integers such that $|f(x)-f(x-1)|\le 1$ for ever integer $x$, then having $f(x)<0$ and $f(y)>0$ implies there is some integer $z$ with $x<z<y$ or $y<z<x$ such that $f(z)=0$. – Patricia Hersh Jun 06 '12 at 12:46
3

Is "continuous function" an important concept? Does it have a discrete analog?

Gerald Edgar
  • 40,238
  • Wikipeadia claims:

    Any function from a discrete topological space to another topological space is continuous,

     – Tomaž Pisanski Mar 08 '10 at 21:41
  • 1
    @Tomaž: that's a very uninteresting analogy... I don't think it deserves that name, really! – Mariano Suárez-Álvarez Mar 08 '10 at 21:46
  • 2
    @Mariano: again, not necessarily. For instance, the (relative) Zariski topology on $\mathbb{F}_q^n$ is discrete, and this is a nonvacuous statement: it has the important consequence that every function $\mathbb{F}_q^n \rightarrow \mathbb{F}$ is a polynomial function. (I think I need a few more rules in order to be comfortable playing this particular game.) – Pete L. Clark Mar 08 '10 at 21:51
  • 1
    I agree with Pete. "Regular function between varieties over a finite field" is, in my opinion, a great discrete analogue of "continuous function between topological spaces." – Qiaochu Yuan Mar 08 '10 at 22:00
  • 24
    The discrete analog of "continuous function" is "function". – darij grinberg Mar 08 '10 at 22:04
  • 3
    Well, there are incredibly interesting discrete analogues of analytic functions (Google should find the notes by Lovász on the subject, for example; this is a whole subject by now) Discreteness of topologies is absolutely irrelevant there---I have no reason to believe the 'canonical' discrete analogue for continuous functions has anything to do with them, either! :) – Mariano Suárez-Álvarez Mar 08 '10 at 22:19
  • 1
    (In particular, darij's comment, while witty, is not sure to resist the ingenuity of future mathematicians :) ) – Mariano Suárez-Álvarez Mar 08 '10 at 22:33
  • In my question I tried to define "analogy" by examples. Sometimes, a motivation from "continuous" maths may be a great source of inspiration for "discrete" analogy. I find discrete Morse theory a "proof" of my claim. – Tomaž Pisanski Mar 08 '10 at 22:36
  • 1
    Well, "analytic" is not an analogue of "continuous" in any way, Mariano. Continuity is, in most contexts, just a well-behavedness condition, while analyticity means that derivatives in different directions exist and are related to each other by an equation, i. e., a well-behavedness condition plus an equation condition. This is why the discrete analogue of "continuous" is vacuous, while that of "analytic" is not (the equation condition survives). – darij grinberg Mar 08 '10 at 22:43
  • @DG: I agree with your distinction between continuous and analytic. For functions $f: \mathbb{Z}^+ \rightarrow \mathbb{R}$, every function should be continuous. A function should be analytic iff it coincides with its discrete Taylor expansion. But doesn't this happen iff $f$ is a polynomial? Or are you thinking of some multivariable case where there is a discrete analogue of the Cauchy-Riemann equations? Do tell... – Pete L. Clark Mar 08 '10 at 23:41
  • 5
    I'd say the discrete analogue of a continuous function is one that is continuous in some quantitative way (such as being Lipschitz) on a finite metric space. If the finite metric space is one of a sequence of spaces with unbounded size, this can be very useful. – gowers Mar 08 '10 at 23:53
  • 3
    I did not say that "analytic" is an analogue of "continuous", as far as I can tell. I simply cannot understand what argument there can possibly be supporting a claim of the form 'there is no discrete analogue of X', apart from a standard argument from ignorance. – Mariano Suárez-Álvarez Mar 09 '10 at 01:17
  • @Mariano: very good point. – kakaz Mar 09 '10 at 07:57
  • 2
    @Pete: I was imprecise; the discrete case I had in my mind was the notion of a harmonic function on a graph ( http://www.cs.elte.hu/~lovasz/telaviv.pdf ). – darij grinberg Mar 09 '10 at 08:14
  • @DG: Thanks, that's helpful. (Such discrete harmonic functions are popular in my neck of the woods.) – Pete L. Clark Mar 09 '10 at 18:26
3

It seems to me there is no good (powerful) discrete version of Atiyah–Singer theorem.

Petya
  • 4,686
  • Maybe Grothendieck-Riemann-Roch? But honestly I have no idea what exactly it states... At least I know there is no analysis involved in its statement. However, I fear getting something really discrete (= a statement on finite sets) out of it would require some serious constructivization. – darij grinberg Mar 08 '10 at 22:52
0

What do You mean by word analogy here? From wikipedia we have ( among others):

The word analogy can also refer to the relation between the source and the target themselves, which is often, though not necessarily, a similarity

So You see similarity in differential equation versus difference equation, but this is mostly matter of aesthetic. In practice if You need discrete equation for continues one, You have to put usually a large amount of work in order to make this analogy working. Of course in principle there is relation among differential and difference equation. But what is important here is not what is similar, but what is a gap between them.

When You say, that discrete case may approximate continues one, in fact You take many assumptions, for example about criteria which constitutes what is that mean approximation.

  1. Say what is analogy of holomorphic function? Is discrete complex function on lattice of Gauss integers, good approximation for some complex analytical function? In what meaning? What are criteria? Are all properties of holomorphic function shared by "discrete analogy" and vice versa?

  2. For example, it is not true that whole theory of differential equations may be deduced from difference equations. We have several equations when we cannot find correct approximations, for example Navier-Stokes equation has no discrete model, at least till now. You may say: but chaos is analogous to turbulence. Why? Because is similar? Why do You may say that? Is that someone think two things are similar enough to say that they are?

Then analogy is so broad in meaning word, that I may say, I can see analogy between every things You may point. It may be very useful as inspiration, sometimes it lead us to great discoveries. For every thing You say is analogous to some continues case, we may have differences between them which allows us to distinguish this cases. They nearly almost are non equivalent even in approximate meaning. They are never the same. It is a matter of criteria, if You may say two things are in analogy.

kakaz
  • 1,596
0

Contrary to the comments appended to the question, I think the notion of analogy can be made precise.

Definition: An analogy of concept A defined in setting SA, is a concept B defined in setting SB such that there exists a generalized setting SX which includes both SA and SB as example settings, and such that there also exists a concept X defined in setting SX which reduces to concept A or concept B when attention is restricted to either setting SA or SB.

In general, an analogy is not unique. A concept could have many analogies, and even for a particular analogous concept there could be more than one way in which it is considered to be analogous.

Example: In Time scale calculus which unifies difference and differential equations, there have been publications with differing answers over how to define the analogy between discrete and continuous transforms. A particular description which encapsulates both the integer and real number transforms may apply to other sets such as the rationals, but a different description might not apply to Q. So an analogy is not just two objects but also the link between them.

Bethnim
  • 1
-1

Searching Google Web, Google Books and Google Scholar for "no discrete version" OR "no discrete analog" OR "no discrete analogue" OR "no continuous version" OR "no continuous analog" OR "no continuous analogue" produces some examples including a comment that a continuous version of a discrete concept doesn't necessarily enable you to guess the properties of the discrete case.

Bethnim
  • 1