3
$\begingroup$

I am reading the logic paper "Interpolation in fuzzy logic" by Matthias Baaz and Helmut Veith http://www.springerlink.com/content/654wl9u5mcj7qtva/

On page 479 it is claimed that "It suffices to show that continuous piecewise linear functions are closed under taking suprema and infima of a single coordinate $y$; geometrically, this means taking the upper boundary of the union of orthogonal projections of all polytopes on the hyperplane y = 0, [15]."

Unfortunately, reference [15] is non helpful at all because it is said that [15] is "Hryniv, O.: Personal Communication."

Thus, I am wondering how to prove that if $f: [0,1]^{n+1} \longmapsto [0,1]$ is a continuous piecewise linear function then the function $\bigwedge f: [0,1]^n \longmapsto [0,1]$ defined by $ (\bigwedge f) (\vec{x}):= \inf \{ f(y,\vec{x}): y \in [0,1] \} $ is also a continuous piecewise linear function. Can anybody suggest a way to prove this statement?

Indeed, I am more interested in a similar statement: if $f$ is a continuous piecewise linear function with rational coefficients then $\bigwedge f$ is also continuous piecewise linear with rational coefficients. I suspect that a proof of the previous result can give me hints about how to prove this statement.

  • 0
    Yes, there are finitely many pieces (and each one of them can be thought as the convex hull of a finite set of points)2011-06-30

1 Answers 1

3

I'll denote elements of $[0,1]^{n+1}$ by $\vec z$ and elements of $[0,1]^{n}$ by $\vec x$.

First, $\bigwedge f$ is continuous. For each linear piece $f_i$, there is $\lambda_i$ such that $|f_i(\vec z)-f_i(\vec z_0)|<\lambda_i|\vec z-\vec z_0|$. Then by dividing the segment between $\vec{z}$ and $\vec{z_0}$ into parts according to the linear pieces, we can conclude that $|f(\vec z)-f(\vec z_0)|<\lambda|\vec z-\vec z_0|$ with $\lambda=\max \lambda_i$.

For $\vec x,\vec x_0\in[0,1]^n$, let $\hat y$ and $\hat y_0$ be the respective values of $y$ and $y_0$ at which the infima of $f(y,\vec x)$ and $f(y_0,\vec x_0)$ are attained. If $f(\hat y,\vec x)\ge f(\hat y_0,\vec x_0)$, then

$ \begin{eqnarray} \left|(\bigwedge f) (\vec{x})- (\bigwedge f) (\vec{x}_0)\right| &=& f(\hat y,\vec x)-f(\hat y_0,\vec x_0) \\ &=& (f(\hat y,\vec x)-f(\hat y_0,\vec x))+(f(\hat y_0,\vec x)-f(\hat y_0,\vec x_0)) \\ &\le& f(\hat y_0,\vec x)-f(\hat y_0,\vec x_0) \\ &\le& \lambda\left|\vec x-\vec x_0\right|\;, \end{eqnarray} $

and likewise, if $f(\hat y,\vec x)\le f(\hat y_0,\vec x_0)$, then

$ \begin{eqnarray} \left|(\bigwedge f) (\vec{x})- (\bigwedge f) (\vec{x}_0)\right| &=& f(\hat y_0,\vec x_0)-f(\hat y,\vec x) \\ &=& (f(\hat y_0,\vec x_0)-f(\hat y,\vec x_0))+(f(\hat y,\vec x_0)-f(\hat y,\vec x)) \\ &\le& f(\hat y,\vec x_0)-f(\hat y,\vec x) \\ &\le& \lambda\left|\vec x-\vec x_0\right|\;. \end{eqnarray} $

Thus $\bigwedge f$ is continuous. To see that it is piecewise linear, orthogonally project all the points defining the pieces of $f$ to $[0,1]^n$ and triangulate the resulting set of points. For each piece $f_i$ of $f$, let $D_i$ be the orthogonal projection of the domain of $f_i$ to $[0,1]^n$. Then for each simplex of the triangulation and each piece $f_i$, the simplex is either entirely inside or entirely outside $D_i$, and the infimum $\bigwedge f_i$ of $f_i$ with respect to $y$ is a linear function on the simplex (since it is attained at the boundary of the domain of $f_i$, that boundary is a linear function of $\vec x$ within the simplex, and $f_i$ is linear). Thus, on each simplex, $\bigwedge f$ is the infimum with respect to $i$ of the infima $\bigwedge f_i$ of all pieces $f_i$ for which $D_i$ contains the simplex. For each pair of these $\bigwedge f_i$, find the hyperplane on which they are equal and, if the hyperplane intersects the simplex, subdivide the simplex accordingly. Then on each resulting polytope, $\bigwedge f$ is defined by one of the $\bigwedge f_i$ alone, which is a linear function on the simplex, and therefore on the polytope. Thus $\bigwedge f$ is piecewise linear.

  • 1
    @boumol: I don't know what you mean by "rationally triangulated". If the pieces of $f$ have rational coefficients and the points defining them have rational coordinates, then an argument analogous to the one I gave shows that the same will be true for $\bigwedge f$, since substituting a rational linear boundary into a rational linear function again yields a rational linear function.2011-07-03