# Finding nearest value in a sorted set

I am interested in math notation of finding the nearest value in a sorted set of values to the given value.

3, 7, 10, 15, 20, 29, 48, 67, 94

If i want to find the nearest value to 23, it would be 20.

How to represent this using a math notation?

• not sure of the maths notation, but "for a given y find the x such that the distance between x and y is minimized" – Andrew Hill Nov 16 '16 at 3:37
• Actual math uses a lot of words. If something ends up well-defined using words, then it's okay. Not everything needs to be symbolic or fomulaic. – Fimpellizieri Nov 16 '16 at 3:38
• This is a peculiar question -- I think it needs more context (i.e. to what end would such a notation be used). And I expect the most likely answer is "this doesn't come up enough for there to be any established conventions", possibly with an addendum of either "so you should use words" or "so you should invent your own" depending on the application. – user14972 Nov 16 '16 at 3:41
• I've changed the tags; replaced "set theory" with real analysis / metric spaces / approximation. – goblin Nov 16 '16 at 4:12

This is an excellent question, and I don't know why you're getting all this flak in the comments. However:

• The term "sorted set" doesn't really mean anything AFAIK. The important observation is that your set $\{3,7,\ldots,94\}$ is a subset of a metric space, namely $\mathbb{R}$. So, lets work at this higher level of generality.

• There's no standard notation for this stuff. Some terms to look up are "metric projection" and "Chebyshev set." But your particular set isn't a Chebyshev set, which complicates the analysis. Gory details follow.

Okay, here's the math:

Given a metric space $X$ and a subset $A$, there's a relation $\underline{A}:X \nrightarrow A$ defined as follows:

$$\underline{A}(x,a)\iff \forall b \in A(d(x,b) \geq d(x,a))$$

If $A$ is compact, then $\underline{A}$ is entire; use the extreme value theorem applied to the map $X \rightarrow \mathbb{R}$ defined by $x \mapsto d(x,A),$ where $d(x,A)$ is shorthand for $\min_{a \in A}d(x,a).$

Unfortunately, the relation $\underline{A}$ won't usually be deterministic: for example, if $A = \{0,1\}$ and $X=\mathbb{R}$ with the usual metric structure, then $(1/2,0) \in \underline{A}$ and $(1/2,1) \in \underline{A}$.

There's a few ways of treating this. One is to accept that $\underline{A}$ yields a subset of $X$, rather than an element. That is, we re-analyse $\underline{A} : X \nrightarrow A$ as $\underline{A} : X \rightarrow \mathcal{P}(A)$, where $\mathcal{P}$ is the powerset function. For example: $$\underline{A}(1/2) = \{0,1\}.$$

Another option is to choose a subfunction $X \rightarrow A.$ If $A$ is compact, then this is always possible, because, by the axiom of choice, every entire relation has a subfunction. However, in the special case $X=\mathbb{R}$, the axiom of choice isn't really necessary, because we can choose an explicit strategy for disambiguating the values of $\underline{A}$. For example, each of "round toward the negative direction"/"round toward the positive direction"/"round toward zero"/"round away from zero" will give you a subfunction.

For instance, suppose we want to round toward the negative direction. Mathematically, this means defining $f_A : X \rightarrow A$ by $$f_A(x) = \min \underline{A}(x).$$

For example, if we go back to $A =\{0,1\}$ and $X=\mathbb{R}$, we obtain $$f_A(1/2) = \min\{0,1\} = 0.$$