Understanding the Number Line through Convexity

convex-analysisintegersreal numbers

I came across the following picture:

enter image description here

According to this picture, it would appear that Natural Numbers, Integers, Rational Numbers and Real Algebraic Numbers are all Non-Convex sets – but Real Numbers are Convex.

For instance, if you take the set of integers – it is impossible to "go from" the number 2 and "reach" the number 2.1 without remaining within the set of integers : This makes me think of integers as Non-Convex. However, if you consider the set of real numbers, it seems like you can go from any element to any other element in the set – thus making the set of real numbers as Convex.

  • Is this interpretation correct?

For some reason, I think my interpretation is not correct. If my interpretation were correct – this would mean that it would be impossible to have a "Convex Hull" (https://en.wikipedia.org/wiki/Convex_hull) over any set of integers.

For example, Discrete Optimization Problems are over the set of integers, the set of integers are non-convex – yet a Convex Hull can still be defined for such problems (e.g. https://www2.isye.gatech.edu/~mgoetsch/cali/VEHICLE/TSP/TSP017__.HTM). As I understand, a Convex Hull is the biggest Convex Set contained within an otherwise Non-Convex set.

(For some reason, identifying the Convex Hull in Optimization Problems is said to be important, but I don't quite understand why identifying the Convex Hull is important – for example, in problems like the Travelling Salesman … why would identifying the Convex Hull be important?)

How is this then possible?

  • In the above picture, are all sets of numbers "Non-Convex" except the Real Numbers?

  • How is it possible to have a Convex Hull within the sets of Integers that contains more than one integer? Since we can not "reach" any integer from any other integer without leaving the set of integers – how can a Convex Hull within the set of integers contain more than a single element?

For instance, over the set of integers (a Non-Convex set) – suppose for a specific optimization problem we identified a Convex Hull containing the elements (-2,-1,0,1,2) : Within this Convex Hull, we can not go from -2 to -1.9, thus violating the definition of Convexity. It would appear as though in this case, the Convex Hull itself is Non-Convex.

Can someone please help me better understand this?

Thank you!

Best Answer

You've got it backward: a set's convex hull is a superset of the given set, not a subset. Thus, the convex hull of the set of integers is the real line.

Related Question