Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have a set of indexes of integer $\mathbb{I} =\{i_0, i_1, ..., i_n\}$, and an environment $f: \mathbb{I} \rightarrow \mathbb{Z} \times \mathbb{Z}$ which assigns a pair of integer to each index. For instance, $f(i_0) = (-3, 7)$ means the value of $i_0$ is an integer in $[-3, 7]$, in short, $i_0 \in [-3, 7]$. $f(i_1) = (2,5)$ means the value of $i_1$ is an integer in $[2,5]$, in short, $i_1 \in [2,5]$.

I have also 4 variables $a, b, c, d \in \mathbb{V}$, which are constructed with integers, indexes, and the operator $+$. For example, $a = 4, b = i_0, c = i_0 + 2,d = i_1 + 5$.

We define a notation $[[u, v]]= [\min(u, v), \max(u, v)]$ to represent an interval (which could be empty) formed by $u$ and $v$.

So given $a, b, c, d$ and an enviroment $f$, $[[a, b]]$ forms an interval, so is $[[c, d]]$. Then I am looking for an algorithm to calculate $[[a, b]] \cap [[c, d]]$ and $[[a, b]] \cup [[c, d]]$, which means respectively their intersection and union, let's note $Intersection(a, b, c, d, f) = [[a, b]] \cap [[c, d]]$ under $f$, and $Union(a, b, c, d, f) = [[a, b]] \cup [[c, d]]$ under $f$.

$Intersection, Union: \mathbb{V} \times \mathbb{V} \times \mathbb{V} \times \mathbb{V} \times \mathbb{F} \rightarrow \mathbb{V} \times \mathbb{V} \cup \{NotDecidable\} \cup \{NotAnInterval\}$

For instance, given $\{a = 4, b = i_0, c = 8, d = i_0 + 6\}$ and $f: i_0 \mapsto [2,3]$, $Intersection(a, b, c, d, f)$ returns always $\emptyset$, and $Union(a, b, c, d, f)$ returns always "NotAnInterval"; given $f: i_0 \mapsto [8,10]$, $Intersection(a, b, c, d, f)$ returns always $(c, b)$, and $Union(a, b, c, d, f)$ returns always $(a, d)$.

So we can see that it is quite possible that $Intersection$ or $Union$ could not return a fixed answer, in that case, let's make it return "NotDecidable"

It is a complex problem, to simplify a little bit, in the first place, we may assume that the variables are constructed with integers, the operator $+$, and only one index: $i_0$.

I hope my question is clearly described, could anyone help me figure out this algorithm?

Thank you very much

share|cite|improve this question
I'm not clear about the definition of $f$, as $f(4)$ could be any interval that at least one of the end points is $4$. I am also not sure what does this have to do with set theory, elementary set theory; as well I am generally opposed to [intersection] as a tag. – Asaf Karagila Jul 27 '11 at 12:01
Thanks for your comment, do you have any other tag to recommand? – SoftTimur Jul 27 '11 at 12:36
$f$ could not be applied to an integer (4), $f$ is actually an environment which gives the range of the values of indexes. $Intersection(a=4,b=i_0,c=i_1,d=i_0+6,f:i_0 \mapsto [2,3]; i_1 \mapsto [5,6])$ means $Intersection(a=4,b=i_0,c=i_1,d=i_0+6,i_0 \in [2,3]; i_1 \in [5,6])$ – SoftTimur Jul 27 '11 at 12:40
I am not quite sure which other tag would fit. I don't fully understand the definition of $f$, or whether or not it is taken arbitrarily from a family of functions; I did not sit to contemplate the actual question itself. It seems perhaps related to computability or algorithms. I honestly have no idea. I do know that the fact that there are sets involved does not make this a question in set theory. – Asaf Karagila Jul 27 '11 at 13:05
I retagged the question. Effectively making it someone else's problem, I hope this retag is somewhat better than the original. – Asaf Karagila Jul 27 '11 at 14:01

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.