wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Continuous, Open, Injective
        
(Message started by: Eigenray on Dec 8^th, 2003, 11:29pm)

Title: Continuous, Open, Injective
Post by Eigenray on Dec 8^th, 2003, 11:29pm

I came up with this one myself years ago, and was surprised by the symmetry of the answer:

Let f : [bbr] [to] [bbr], and consider the following three statements:
1) f is Continuous (inverse image of open sets are open)
2) f is Open (image of open sets are open)
3) f is Injective (one-to-one; f(x)=f(y) [bigto] x=y)
Note: We require f to be defined on all of [bbr], but not necessarily onto.

Which combinations of truth values of 1,2,3 are possible? That is, for each of the 8 cases, either give an f which works, or prove no such f exists.

Most of the cases are easy. I'm pretty certain that precisely :[hide]5[/hide]: permit such an f.

Title: Re: Continuous, Open, Injective
Post by Icarus on Dec 9^th, 2003, 5:57pm

I'm not going to bother hiding this, so anyone who doesn't want to see a partial solution yet can stop reading.

4 cases are trivial:
Continuous, open, injective: y = x.
Continuous, not open, not injective: y = |x|.
Not continuous, not open, not injective: y = { 0 for x < 0; 1 for x [ge] 0 }.
Not continuous, not open, injective: y = { x for x < 0; x + 1 for x [ge] 0 }

2 more cases are quickly seen to be not possible:
Lemma: A continuous function f : [bbr] [to] [bbr] is open iff it is injective.

Proof: if f is not injective, then there exists a, b with f(a) = f(b) = F for some F [in] [bbr] and a < b. But since f is continuous f([a, b]) is compact and connected, and so must be an interval [c, d]. If c = d, then f((a, b)) = {c}. Otherwise,

[c, d] [supseteq] f((a, b)) [supseteq] f([a, b]) - {F} = [c, d] - {F}.
Both possibilities are not open, so f cannot be open.

Conversely, if f is injective, then f must be monotonic (strictly increasing or strictly decreasing). For if a < b < c, the intermediate value theorem says that every value between f(a) and f(b) is taken on by some x [in] [a, b], so none of them is f(c). Assume that f(a) < f(b). Then f(c) < f(a) or f(b) < f(c). But f(a) can not lie between f(b) and f(c) either, for some x [in] [b, c] would have f(x) = f(a) if it did. Hence f(a) < f(b) < f(c), and the function is increasing. The case for f(a) > f(b) can be shown by applying this case to -f.
Since an injective f is also monotone, f((a, b)) = (f(a), f(b)) or (f(b), f(a)). In either case, it is an open set. This is sufficient to show that f is an open function. QED

A corollary handles another case:

Corollary: An open injective function is continuous.

Proof: f^-1 is also an injective function, and is continuous since f is open. Hence f^-1 is open, and so f is continuous. QED

So the following 3 cases are impossible:
Continuous, open, not injective.
Continuous, not open, injective.
Not continuous, open, injective.

This leaves (not continuous, open, not injective) as the final case.

I believe that it is possible for a function to be open without being continuous or injective, but I have not found an example yet. I believe that there exist functions for which the image of every interval is [bbr]. Clearly if it exists, such a function is open (the image of every open set is [bbr], which is open), but not injective (every value must be taken on an infinite number of times) or continuous (no limits converge).

Title: Re: Continuous, Open, Injective
Post by Eigenray on Dec 9^th, 2003, 10:45pm

on 12/09/03 at 17:57:49, Icarus wrote:

Corollary: An open injective function is continuous.

Proof: f^-1 is also an injective function, and is continuous since f is open. Hence f^-1 is open, and so f is continuous. QED

It's important to note that f^-1:f([bbr])[to][bbr], so the lemma does not apply directly, but is easily extended.

Quote:

I believe that it is possible for a function to be open without being continuous or injective

Yes. Yes it is.

I think it's neat that any two properties imply the third, but all other combinations are possible.

Title: Re: Continuous, Open, Injective
Post by Icarus on Dec 10^th, 2003, 4:24am

Here is one function f for which the image of any interval is all of [bbr]:

Consider the trinary expression for x - using the terminating version when neccessary.

If it contains an infinite number of 2s, set f(x) = 0.
Otherwise throw away the all digits preceding the last 2, and the 2 as well.
Take off the first 2 digits remaining and place a decimal point before the remaining digits to get the BINARY expansion of a number y [in] [0, 1].
If y = 0, set f(x) = 0.
Otherwise, depending on the first 2 removed digits, f is defined by:
00 [bigto] f(x) = y
01 [bigto] f(x) = 1/y
10 [bigto] f(x) = -y
01 [bigto] f(x) = -1/y

In particular, f is open, but not continuous or injective.