From: M.Voorneveld@kub.nl (VOORNEVELD M.) Newsgroups: sci.math Subject: continuity of information summarizing function Date: Tue, 3 Oct 1995 08:54:38 GMT Suppose we are given a positive, finite number n of variables, each having possible values in [0,1] and real valued functions w^i:[0,1]^n ---> R (i = 1,...,n) assigning to each possible combination of these variables a number representing something attached to the i-th variable (i=1,...,n). These functions w^i are continuous. We are working in a laboratory environment where all these variables can change, but only one at a time (never 2 or more at the same time). This provides us with a lot of information, but we are only interested in the situations in which we cannot imcrease any of the w^i's under the permitted changes (i.e. one at a time). We have found functions containing the necessary information, real valued functions M:[0,1] --> R which is such that M(x_{-i}, x_{i}) - M(x_{-i}, y_{i}) > 0 iff w^i(x_{-i}, x_{i}) - w^i({x_{-i}, x_{i}) > 0 for each x_{-i} = (x_1,...,x_{i-1},x_{i+1},...,x_n) in [0,1]^(n-1) and x_{i} in [0,1]. In other words, this function M exactly represents what happens to w^i when any variable i is changed. What we are interested in, is whether or not there is a function M which is continuous, given that the w^i are continuous on [0,1]^n and M satisfies the property given above. We thought about proving this by induction. The result is trivial if n = 1, since P = w^i has the desired property. If we try to extend this result to higher n, the problem is that we only know of continuous M's for the 'smaller' experiments involving at most n-1 variables, but we have to extract from these functions a single function that is continuous. Any information, references to relevant literature, etc. would be greatly appreciated. Please e-mail to M.Voorneveld@kub.nl Thanks! Mark Voorneveld ============================================================================== From: rusin@washington.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: continuity of information summarizing function Date: 5 Oct 1995 15:02:42 GMT In article , VOORNEVELD M. wrote: >Suppose we are given a positive, finite number n of variables, each having >possible values in [0,1] and real valued functions w^i:[0,1]^n ---> R >(i = 1,...,n) assigning to each possible combination of these variables a >number representing something attached to the i-th variable (i=1,...,n). > ... >We have found functions containing the necessary information, real valued >functions M:[0,1] --> R which is such that > > M(x_{-i}, x_{i}) - M(x_{-i}, y_{i}) > 0 iff > w^i(x_{-i}, x_{i}) - w^i({x_{-i}, x_{i}) > 0 > >for each x_{-i} = (x_1,...,x_{i-1},x_{i+1},...,x_n) in [0,1]^(n-1) and x_{i} >in [0,1]. Let me see if I've got this straight, say for n=2. You've got two real-valuesd functions w1 and w2 defined on the square and you're looking for a third one M with the property that M(x1,x2) > M(y1,x2) iff w1(x1,x2) > w1(y1,x2) M(x1,x2) > M(x1,y2) iff w2(x1,x2) > w2(x1,y2) What happens if, say, w1(x,y)=(1/2-y)x and w2(x,y)=(x-1/2)y ? Then you want M(2/3,2/3) > M(2/3, 1/3) because w2(2/3, 2/3) > w2(2/3, 1/3), but also M(2/3,1/3) > M(1/3, 1/3) because w1(2/3, 1/3) > w1(1/3, 1/3); so your M must have M(2/3,2/3) > M(1/3,1/3). On the other hand you also want M(2/3,2/3) < M(1/3, 2/3) because w1(2/3, 2/3) < w1(1/3, 2/3), but also M(1/3,2/3) < M(1/3, 1/3) because w2(1/3, 2/3) < w2(1/3, 1/3); so your M must have M(2/3,2/3) < M(1/3,1/3). Now you're trapped in a contradiction. You can scale these examples to keep the outputs in any desired range. Continuity has nothing to do with it. Perhaps I've overlooked something obvious? dave ============================================================================== From: "M.Voorneveld" To: rusin@math.niu.edu (Dave Rusin) Date: Fri, 6 Oct 1995 11:15:54 MET Subject: Re: continuity of information summarizing function > In article , > VOORNEVELD M. wrote: > >Suppose we are given a positive, finite number n of variables, each having > >possible values in [0,1] and real valued functions w^i:[0,1]^n ---> R > >(i = 1,...,n) assigning to each possible combination of these variables a > >number representing something attached to the i-th variable (i=1,...,n). > > > ... > >We have found functions containing the necessary information, real valued > >functions M:[0,1]^n --> R which is such that > > > > M(x_{-i}, x_{i}) - M(x_{-i}, y_{i}) > 0 iff > > w^i(x_{-i}, x_{i}) - w^i({x_{-i}, x_{i}) > 0 > > > >for each x_{-i} = (x_1,...,x_{i-1},x_{i+1},...,x_n) in [0,1]^(n-1) and x_{i} > >in [0,1]. > > Let me see if I've got this straight, say for n=2. You've got two real-valuesd > functions w1 and w2 defined on the square and you're looking for a third one > M with the property that > M(x1,x2) > M(y1,x2) iff w1(x1,x2) > w1(y1,x2) > M(x1,x2) > M(x1,y2) iff w2(x1,x2) > w2(x1,y2) > No, we HAVE functions w1 and w2 such that a third function with the above property exists. When it exists, there is a whole convex cone of such functions (Easy: aM has the desired property for any a>0 and if M and M~ have the desired property, so does M+M~. Notice that this cone is typically not pointed, since the zero function usually does not satisfy the desired property.). But does this cone contain a continuous one? > What happens if, say, w1(x,y)=(1/2-y)x and w2(x,y)=(x-1/2)y ? Then you want > M(2/3,2/3) > M(2/3, 1/3) because w2(2/3, 2/3) > w2(2/3, 1/3), but also > M(2/3,1/3) > M(1/3, 1/3) because w1(2/3, 1/3) > w1(1/3, 1/3); so your > M must have M(2/3,2/3) > M(1/3,1/3). On the other hand you also want > M(2/3,2/3) < M(1/3, 2/3) because w1(2/3, 2/3) < w1(1/3, 2/3), but also > M(1/3,2/3) < M(1/3, 1/3) because w2(1/3, 2/3) < w2(1/3, 1/3); so your > M must have M(2/3,2/3) < M(1/3,1/3). Now you're trapped in a contradiction. > > Perhaps I've overlooked something obvious? Sorry for this misunderstanding! Mark. ============================================================================== From: M.Voorneveld@kub.nl (VOORNEVELD M.) Newsgroups: sci.math Subject: Re: continuity of information summarizing function Date: Fri, 6 Oct 1995 10:27:12 GMT In article <450s2i$g6j@muir.math.niu.edu> rusin@washington.math.niu.edu (Dave Rusin) writes: >In article , >VOORNEVELD M. wrote: >>Suppose we are given a positive, finite number n of variables, each having >>possible values in [0,1] and real valued functions w^i:[0,1]^n ---> R >>(i = 1,...,n) assigning to each possible combination of these variables a >>number representing something attached to the i-th variable (i=1,...,n). >> >... >>We have found functions containing the necessary information, real valued >>functions M:[0,1]^n --> R which is such that >> >> M(x_{-i}, x_{i}) - M(x_{-i}, y_{i}) > 0 iff >> w^i(x_{-i}, x_{i}) - w^i({x_{-i}, x_{i}) > 0 >> >>for each x_{-i} = (x_1,...,x_{i-1},x_{i+1},...,x_n) in [0,1]^(n-1) and x_{i} >>in [0,1]. >Let me see if I've got this straight, say for n=2. You've got two real-valuesd >functions w1 and w2 defined on the square and you're looking for a third one >M with the property that > M(x1,x2) > M(y1,x2) iff w1(x1,x2) > w1(y1,x2) > M(x1,x2) > M(x1,y2) iff w2(x1,x2) > w2(x1,y2) We assume that w1 and w2 are such that a function M with the desired property exists. When it exists there is a whole convex cone of such functions (Easy: if M has the desired property, then so does aM for any a>0 and if M and M~ both have the desired property, then so does M+M~. Notice that this cone is typically not pointed, since the zero function usually does not satisfy the desired property). The question is if this cone of functions with the desired property contains a CONTINUOUS one. Sorry for this misunderstanding! Mark M.Voorneveld@kub.nl ============================================================================== From: "M.Voorneveld" To: rusin@math.niu.edu (Dave Rusin) Date: Mon, 9 Oct 1995 14:46:44 MET Subject: Re: continuity of information summarizing function > got it now. let me think about it some more later today. > dave Okay, I hope you can figure it out. My knowledge of math is really not that phenomenal and even though I spent lots of time on it, I couldn't solve it. Intuitively, there should be such a continuous function, considering that the domain [0,1]^n and the functions w^i are so 'nice', but it wouldn't be the first time my intuition was wrong! Mark ============================================================================== From: rusin@washington.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Ordered topologies (Was Re: continuity of information summarizing function) Date: 9 Oct 1995 22:28:45 GMT I'm sort of tuckered out on this one, but I thought I'd re-cast the problem so that someone else can see what needs to be done. The following would resolve the original problem (attached below). Y is a topological space with a partial ordering "<", such that all the sets A_p = { q in Y : q < p } are open. The question then is, is there necessarily a _continuous_ embedding of Y into R? Jacobson's _Algebra_ notes that a finite partially ordered set embeds in a totally ordered set. Since he bothers attributing this result (to Szpilrajn-Marczewski (!) ) I assume there must be a broader context for this kind of thing. Of course you need to know something about Y (e.g. its cardinality). Here's the setup of the original poster. A (transitive!) partial order is established on the cube X = [0,1]^n . The ordering is specified by a set of n real-valued functions w_i: we say p < q iff p and q have all coordinates equal except the i-th, and w_i(p) < w_i(q). I believe the w_i were assumed to be smooth. Unless I've missed some nuance here, this leads to an equivalence relation on X such that Y = X/~ has the stated property. ("~" is generated by: p~q iff w_i(p)=w_i(q) and p and q have all but the i-th coordinates equal.) An excerpt of the original post is attached. dave In article , VOORNEVELD M. wrote: >Suppose we are given a positive, finite number n of variables, each having >possible values in [0,1] and real valued functions w^i:[0,1]^n ---> R >(i = 1,...,n) assigning to each possible combination of these variables a >number representing something attached to the i-th variable (i=1,...,n). > ... >We have found functions containing the necessary information, real valued >functions M:[0,1]^n --> R which is such that > > M(x_{-i}, x_{i}) - M(x_{-i}, y_{i}) > 0 iff > w^i(x_{-i}, x_{i}) - w^i({x_{-i}, x_{i}) > 0 > >for each x_{-i} = (x_1,...,x_{i-1},x_{i+1},...,x_n) in [0,1]^(n-1) and x_{i} >in [0,1]. ============================================================================== From: M.Voorneveld@kub.nl (VOORNEVELD M.) Newsgroups: sci.math Subject: Topology question Date: Wed, 21 Feb 1996 08:26:03 GMT Let X and Y be compact metrizable topological spaces (so that XxY, the product of X and Y, is compact in the product topology) and f = (f1,f2) : XxY --> R^2 a continuous function into two-dimensional Euclidean space. One is given that there exists a real-valued function g: XxY --> R such that for each a and b in X and each c and d in Y: g(a,c) > g(b,c) iff f1(a,c) > f1(b,c) and g(a,c) > g(a,d) iff f2(a,c) > f2(a,d) QUESTION: Is there a function h: XxY --> R with the same property as g which has a maximum on XxY? I tried this problem first by looking if I could show there is a function h which is continuous, but for the existence of a maximum it will suffice to show that there is a function h which is upper semi-continuous in the sense that {(x,y) in XxY | h(x,y) >= c} is closed for every c in R. But I can't show this, each time getting stuck because the only thing one knows about this function g (or h) is how it behaves in two 'directions' as dictated by the property of g: it increases iff the first (resp. second) coordinate changes and the first (resp. second) coordinate function increases. On the other hand, I couldn't find a counterexample either! Can someone maybe give some hints on how to solve this problem? Maybe looking at continuity properties is not the easiest way! Please mail to M.Voorneveld@kub.nl Thanks! Mark Voorneveld (M.Voorneveld@kub.nl) ============================================================================== From: rld@math.ohio-state.edu (Randall Dougherty) Newsgroups: sci.math Subject: Re: Topology question Date: 21 Feb 1996 19:46:11 -0500 In article , VOORNEVELD M. wrote: >Let X and Y be compact metrizable topological spaces (so that XxY, the >product of X and Y, is compact in the product topology) and >f = (f1,f2) : XxY --> R^2 a continuous function into two-dimensional >Euclidean space. > >One is given that there exists a real-valued function g: XxY --> R such that >for each a and b in X and each c and d in Y: >g(a,c) > g(b,c) iff f1(a,c) > f1(b,c) and >g(a,c) > g(a,d) iff f2(a,c) > f2(a,d) > >QUESTION: Is there a function h: XxY --> R with the same property as g which >has a maximum on XxY? Not necessarily. Let X = Y = [0,1]. Let f1(0,0) = f2(0,0) = g(0,0) = 0 and, for (x,y) different from (0,0), f1(x,y) = xy^6/(x^2+y^2)^3 f2(x,y) = yx^6/(x^2+y^2)^3 g(x,y) = xy/(x^2+y^2)^3. Then f1,f2,g have the stated properties. Now suppose h has the same property as g. Let Z be the zigzag path from (1,1) to (1/2,1) to (1/2,1/2) to (1/4,1/2) to (1/4,1/4) to ... . Then h(x,y) must strictly increase as (x,y) moves along Z toward (0,0). Also: h(x,0) = h(1,0) < h(1,1); h(0,y) = h(0,1) < h(1,1); if (x,y) lies to the right of Z, and (x',y) is on Z, then h(x,y) < h(x',y); if (x,y) lies above Z, and (x,y') is on Z, then h(x,y) < h(x,y'). Therefore, for any (x,y) we have h(x,y) < h(1/2^n,1/2^n) for some n. Since the numbers h(1/2^n,1/2^n) strictly increase as n increases, h has no maximum. Randall Dougherty rld@math.ohio-state.edu Department of Mathematics, Ohio State University, Columbus, OH 43210 USA "I have yet to see any problem, however complicated, that when looked at in the right way didn't become still more complicated." Poul Anderson, "Call Me Joe" ============================================================================== From: "M.Voorneveld" To: rusin@math.niu.edu (Dave Rusin) Date: Fri, 8 Mar 1996 14:00:43 MET Subject: Groebner bases and Info summary Admittedly, I had noticed the connection between linear algebra and game theory. The Groebner base idea sounds interesting. I don't know the concept, but will look in our library. Do you have any good references to it? Here's the counterexample of our correspondence on information summarizing functions. It was given by Randall Dougherty (Dept Mathematics, Ohio State University): Consider [0,1]^2 as domain, take w_1(x,y) = 0 if (x,y) = (0,0) xy^6/(x^2 + y^2)^3 otherwise w_2(x,y) = 0 if (x,y) = (0,0) yx^6/(x^2 + y^2)^3 otherwise M(x,y) = 0 if (x,y) = (0,0) xy/(x^2 + y^2)^3 otherwise Clearly, w = (w_1,w_2) is continuous, M satisfies the desired property. Consider any function M with the desired property and consider the zig zag path Z from (1,1) to (1/2,1) to (1/2,1/2) to (1/4,1/2) to (1/4,1/4) to ... M strictly increases along this path. Also M(x,0) = M(1,0) < M(1,1) M(0,y) = M(0,1) < M(1,1) If (x,y) lies to the right of Z and (x',y) is on Z, then M(x,y) < M(x',y). If (x,y) lies to the left of Z and (x,y') is on Z, then M(x,y) < M(x,y'). Therefore, for any (x,y) in [0,1]^2 we have M(x,y) < M(1/2^n, 1/2^n) for some n. Since the sequence {M(1/2^n, 1/2^n)}_{n = 0}^{\infty} strictly increases, M has no maximum. But then M cannot be continuous! Best, Mark =================== Mark Voorneveld M.Voorneveld@kub.nl =================== ============================================================================== From: "M.Voorneveld" Organization: Tilburg University To: rusin@math.niu.edu (Dave Rusin) Date: Mon, 11 Mar 1996 11:24:30 MET Subject: Re: Groebner bases and Info summary > There is a very readable introduction to Groebner bases in the Springer > Undergraduate Texts in Mathematics series. The authors are (I think) > Little, O'Shea, and one other whose name escapes me right now. Okay, I know which book you mean! As usual, it is not present at our library; the only study at our university which is closely related to mathematics is econometrics (I'm in the mathematical economics program of the econometrics department) and our supply of good books on mathematics is unfortunately rather limited. > Thanks for sending the example. I noticed in on sci.math. I should append > it to the file in which we discussed this problem. The zigzag path is essential since we only have data concerning the properties of the functions in the directions of the 'coordinate axes'; There may be simpler examples. I'll let you know if I find a particularly clear one! Mark =================== Mark Voorneveld M.Voorneveld@kub.nl ===================