Options

Exercise 1 - Chapter 1

A function \(f\colon \mathbb{R}\to\mathbb{R}\) is

  1. order-preserving if \(x\leq y\) implies \(f(x)\leq f(y)\), for all \(x,y\in\mathbb{R}\);
  2. metric-preserving if \(|x-y|=|f(x)-f(y)|\);
  3. addition-preserving if \(f(x+y)=f(x)+f(y)\).

In each of the three cases above, find an \(f\) that is foo-preserving and an example of an \(f\) that is not foo-preserving.

Comments

  • 1.
    edited April 1

    Feel free to post answers and discuss!

    I'm hoping that I can get some of you folks to some of the work: post one new discussion for each exercise, labeled "Exercise \(n\) - Chapter \(m\)". The discussion should start with a comment containing just the problem; then people can add comments containing solutions.

    Comment Source:Feel free to post answers and discuss! I'm hoping that I can get some of you folks to some of the work: post one new discussion for each exercise, labeled "Exercise \\(n\\) - Chapter \\(m\\)". The discussion should start with a comment containing just the problem; then people can add comments containing solutions.
  • 2.
    1. \(f(x)=2x\) is order-preserving, \(f(x)=x^2\) is not (e.g., \(-1<0\), but \(f(-1)=1>0=f(0)\)).
    2. \(f(x)=x+2\) is metric-preserving, \(f(x)=x/2\) is not.
    3. we can reuse the same functions as in point 1.
    Comment Source:1. \\(f(x)=2x\\) is order-preserving, \\(f(x)=x^2\\) is not (e.g., \\(-1<0\\), but \\(f(-1)=1>0=f(0)\\)). 2. \\(f(x)=x+2\\) is metric-preserving, \\(f(x)=x/2\\) is not. 3. we can reuse the same functions as in point 1.
  • 3.
    edited April 1
    1. \( f(x)=x\) is order-preserving, \(f(x)=-x\) is not.

    2. \( f(x)=|x|\) is metric-preserving, \(f(x)=x^2\) is not.

    3. \( f(x)=n*x\) is addition preserving. \(f(x)=-x^2\) is not.

    Comment Source:1. \\( f(x)=x\\) is order-preserving, \\(f(x)=-x\\) is not. 2. \\( f(x)=|x|\\) is metric-preserving, \\(f(x)=x^2\\) is not. 3. \\( f(x)=n*x\\) is addition preserving. \\(f(x)=-x^2\\) is not.
  • 4.

    I'm suspicious of one of Keith's answers. But don't change anything, Keith! This makes a nice extra puzzle.

    Comment Source:I'm suspicious of one of Keith's answers. But don't change anything, Keith! This makes a nice extra puzzle.
  • 5.
    edited April 1

    Keith, \( f(x)=|x|\) isn't metric-preserving for \(x = 1, y = -1\): \(|1-(-1)| = 2 \neq ||1|-|-1|| = 0\)

    Comment Source:Keith, \\( f(x)=|x|\\) isn't metric-preserving for \\(x = 1, y = -1\\): \\(|1-(-1)| = 2 \neq ||1|-|-1|| = 0\\)
  • 6.
    edited April 1
    1. \( f(x) = x^5 \) is order-preserving, but \( f(x) = |x| \) is not;
    2. \( f(x) = -x \) is metric-preserving, but \( f(x) = 1 \) is not;
    3. \( f(x) = \frac{x}{2} \) is addition-preserving, but \( f(x) = |x| \) is not.
    Comment Source:1. \\( f(x) = x^5 \\) is order-preserving, but \\( f(x) = |x| \\) is not; 2. \\( f(x) = -x \\) is metric-preserving, but \\( f(x) = 1 \\) is not; 3. \\( f(x) = \frac{x}{2} \\) is addition-preserving, but \\( f(x) = |x| \\) is not.
  • 7.

    I notice: The identity function f(x) = x is order-preserving in all three cases. I think this is unique.

    Multiplication by a positive constant f(x) = c*x is addition-preserving and order-preserving, but not metric preserving. Annihilation f(x) = 0 is addition-preserving and order-preserving, but not metric preserving.

    Rotation through 180° f(x) = -x is metric preserving and addition-preserving, but not order-preserving.

    Also, it looks like the addition-preserving endomorphisms are fully determined by the value of f(1).

    Comment Source:I notice: The identity function f(x) = x is order-preserving in all three cases. I think this is unique. Multiplication by a positive constant f(x) = c*x is addition-preserving and order-preserving, but not metric preserving. Annihilation f(x) = 0 is addition-preserving and order-preserving, but not metric preserving. Rotation through 180° f(x) = -x is metric preserving and addition-preserving, but not order-preserving. Also, it looks like the addition-preserving endomorphisms are fully determined by the value of f(1).
  • 8.

    I believe order-preserving is another way of saying monotonically-increasing.

    Comment Source:I believe order-preserving is another way of saying monotonically-increasing.
  • 9.

    What constitutes metric-preserving depends on the metric chosen and the associated function, in this case, the absolute value and addition, I.e. |x + (+inv(x))| are chosen. The metric-preserving functions form a preorder, the identity function being the join.

    Comment Source:What constitutes metric-preserving depends on the metric chosen and the associated function, in this case, the absolute value and addition, I.e. |x + (+inv(x))| are chosen. The metric-preserving functions form a preorder, the identity function being the join.
  • 10.
    edited April 1

    Yes, order-preserving means the same as monotonically increasing, and the book uses monotone as a shorter synonym. So, in the book, a monotone function \(f : A \to B\) between preorders \(A\) and \(B\) has

    $$ a \le a' \textrm{ implies } f(a) \le f(a') $$ for all \(a,a' \in A\). Other people also talk about order-reversing or monotonically decreasing functions, that obey

    $$ a \le a' \textrm{ implies } f(a') \le f(a) $$ I forget how Fong and Spivak describe these, but every poset \(A\) has an opposite poset \(A^{\mathrm{op}}\) , in which the order relation is reversed, and a monotonically decreasing function from \(A\) to \(B\) is the same as a monotonically increasing function from \(A^{\mathrm{op}}\) to \(B\).

    Comment Source:Yes, **order-preserving** means the same as **monotonically increasing**, and the book uses **monotone** as a shorter synonym. So, in the book, a **monotone function** \\(f : A \to B\\) between preorders \\(A\\) and \\(B\\) has $$ a \le a' \textrm{ implies } f(a) \le f(a') $$ for all \\(a,a' \in A\\). Other people also talk about **order-reversing** or **monotonically decreasing** functions, that obey $$ a \le a' \textrm{ implies } f(a') \le f(a) $$ I forget how Fong and Spivak describe these, but every poset \\(A\\) has an **opposite** poset \\(A^{\mathrm{op}}\\) , in which the order relation is reversed, and a monotonically decreasing function from \\(A\\) to \\(B\\) is the same as a monotonically increasing function from \\(A^{\mathrm{op}}\\) to \\(B\\).
  • 11.
    edited April 1

    William wrote:

    I notice: The identity function f(x) = x is order-preserving in all three cases. I think this is unique.

    Nice! You mean it's the only one that's order-preserving, addition-preserving and metric-preserving. It's neat how you got examples of functions that preserve two but not all three of these structures.

    It takes some work, but one can show that the only order-preserving and addition-preserving functions

    $$ f: \mathbb{R} \to \mathbb{R} $$ are of the form

    $$ f(x) = c x $$ for some \(c \ge 0\). The only one of these functions that's also metric-preserving is the one with \(c = 1\).

    Also, it looks like the addition-preserving endomorphisms are fully determined by the value of \(f(1)\).

    That's very plausible. Surprisingly, it's not true if you believe in the Axiom of Choice, the way most mathematicians do!

    It's pretty easy to show that if \(f\) is addition-preserving, \(f(1) = c\) implies

    $$f(x) = c x $$ when \(x\) is rational. In theory you could cleverly choose \(f\) to behave in some other way when \(x\) is irrational. And using the Axiom of Choice, you can. But if you require \(f\) to be continuous or even just "measurable", the only option is to take \(f(x) = c x\) for all \(x \in \mathbb{R}\). An order-preserving function must be measurable, so the the only order-preserving and addition-preserving functions

    $$ f: \mathbb{R} \to \mathbb{R} $$ are of the form

    $$ f(x) = c x $$ for some \(a \ge 0\).

    For more on this, see:

    In 1821 Cauchy proved that any continuous addition-preserving function \(f: \mathbb{R} \to \mathbb{R} \) is of the form \(f(x) = a x \). The trick is to show that \(f\) must be like this when \(x\) is rational. But this was just the start of a long and interesting story!

    Comment Source:William wrote: > I notice: The identity function f(x) = x is order-preserving in all three cases. I think this is unique. Nice! You mean it's the only one that's order-preserving, addition-preserving and metric-preserving. It's neat how you got examples of functions that preserve two but not all three of these structures. It takes some work, but one can show that the only order-preserving and addition-preserving functions $$ f: \mathbb{R} \to \mathbb{R} $$ are of the form $$ f(x) = c x $$ for some \\(c \ge 0\\). The only one of these functions that's also metric-preserving is the one with \\(c = 1\\). > Also, it looks like the addition-preserving endomorphisms are fully determined by the value of \\(f(1)\\). That's very plausible. Surprisingly, it's not true if you believe in the Axiom of Choice, the way most mathematicians do! It's pretty easy to show that if \\(f\\) is addition-preserving, \\(f(1) = c\\) implies $$f(x) = c x $$ when \\(x\\) is _rational_. In theory you could cleverly choose \\(f\\) to behave in some other way when \\(x\\) is irrational. And using the Axiom of Choice, you can. But if you require \\(f\\) to be continuous or even just "measurable", the only option is to take \\(f(x) = c x\\) for all \\(x \in \mathbb{R}\\). An order-preserving function must be measurable, so the the only order-preserving and addition-preserving functions $$ f: \mathbb{R} \to \mathbb{R} $$ are of the form $$ f(x) = c x $$ for some \\(a \ge 0\\). For more on this, see: * Wikipedia, [Cauchy's functional equation](https://en.wikipedia.org/wiki/Cauchy%27s_functional_equation). In 1821 Cauchy proved that any _continuous_ addition-preserving function \\(f: \mathbb{R} \to \mathbb{R} \\) is of the form \\(f(x) = a x \\). The trick is to show that \\(f\\) must be like this when \\(x\\) is rational. But this was just the start of a long and interesting story!
  • 12.
    edited April 1

    Here is my solution.

    As William Godwin mentioned, the identity function \(x \mapsto x\) is order-, metric-, and addition-preserving.

    1. \(x \mapsto x+1\) is order-preserving, but \(x \mapsto x^2\) is not.
    2. \(x \mapsto x-1\) is metric-preserving, but \(x \mapsto |x|\) is not.
    3. \(x \mapsto 2x\) is addition-preserving, but \(x \mapsto x^3\) is not.
    Comment Source:Here is my solution. As William Godwin mentioned, the identity function \\(x \mapsto x\\) is order-, metric-, and addition-preserving. 1. \\(x \mapsto x+1\\) is order-preserving, but \\(x \mapsto x^2\\) is not. 2. \\(x \mapsto x-1\\) is metric-preserving, but \\(x \mapsto |x|\\) is not. 3. \\(x \mapsto 2x\\) is addition-preserving, but \\(x \mapsto x^3\\) is not.
  • 13.
    edited April 2
    1. \(f(x)=e^x\) is order-preserving, \(f(x)=e^{x^2}\) is not. \(f(x)=e^x\) also has the nice property that makes using a slide rule possible: \(f(x+y)=f(x)*f(y)\)

    2. \(f(x)=-x\) is metric-preserving, as Dan and William mentioned.

    3. I am not feeling up to the challenge of Cauchy right now.

    Comment Source:1. \\(f(x)=e^x\\) is order-preserving, \\(f(x)=e^{x^2}\\) is not. \\(f(x)=e^x\\) also has the nice property that makes using a slide rule possible: \\(f(x+y)=f(x)*f(y)\\) 2. \\(f(x)=-x\\) is metric-preserving, as Dan and William mentioned. 3. I am not feeling up to the challenge of Cauchy right now.
  • 14.
    1. \(f(x) = e^x\) is order-preserving, but \(f(x) = e^{-x}\) is not.
    2. \(f(x) = -x - 1\) is metric-preserving, but \(f(x) = 0\) is not.
    3. \(f(x) = x|I_Q(x) - 1|\) where \(I_Q(x)\) is the Dirichlet function is addition-preserving; it is metric and order-preserving almost everywhere, in the pathological sense noted in comment 11, being the identity function everywhere apart from the rationals where it is zero.
    Comment Source:1. \\(f(x) = e^x\\) is order-preserving, but \\(f(x) = e^{-x}\\) is not. 2. \\(f(x) = -x - 1\\) is metric-preserving, but \\(f(x) = 0\\) is not. 3. \\(f(x) = x\|I_Q(x) - 1\|\\) where \\(I_Q(x)\\) is the [Dirichlet function](https://en.wikipedia.org/wiki/Nowhere_continuous_function#Dirichlet_function) is addition-preserving; it is metric and order-preserving almost everywhere, in the pathological sense noted in comment 11, being the identity function everywhere apart from the rationals where it is zero.
  • 15.
    edited April 3

    Allan - I doubt \( f(x) = x|I_Q(x) - 1|\) is an addition-preserving function from the reals to the reals, because the only such functions for which an explicit formula is possible are the functions \(f(x) = c x \). The rest require the Axiom of Choice, as mentioned in an earlier comment.

    What happens with \(f(x+y) = f(x) + f(y)\) when \(x,y\) are irrationals that sum to a rational?

    Comment Source:Allan - I doubt \\( f(x) = x\|I_Q(x) - 1\|\\) is an addition-preserving function from the reals to the reals, because the only such functions for which an explicit formula is possible are the functions \\(f(x) = c x \\). The rest require the Axiom of Choice, as mentioned in an earlier comment. What happens with \\(f(x+y) = f(x) + f(y)\\) when \\(x,y\\) are irrationals that sum to a rational?
  • 16.

    Does the proof that \(f(x)=n*x\) are the only functions of the reals that are addition-preserving strictly need to use the full axiom of choice?

    Does the condition hold in constructive varients of math?

    Comment Source:Does the proof that \\(f(x)=n*x\\) are the only functions of the reals that are addition-preserving strictly need to use the full axiom of choice? Does the condition hold in constructive varients of math?
  • 17.
    edited April 3

    Keith: I said the proof that not all addition-preserving functions from the reals to the reals uses the axiom of choice. See this:

    In some constructive variants of math all functions from the reals to the reals are continuous. All continuous addition-preserving functions from the reals to the reals are of the form \(f(x) = c x\) for some \(c \in \mathbb{R}\); that's pretty easy to see.

    Comment Source:Keith: I said the proof that _not all_ addition-preserving functions from the reals to the reals uses the axiom of choice. See this: * Wikipedia, [Cauchy's functional equation](https://en.wikipedia.org/wiki/Cauchy%27s_functional_equation). In some constructive variants of math all functions from the reals to the reals are continuous. All continuous addition-preserving functions from the reals to the reals are of the form \\(f(x) = c x\\) for some \\(c \in \mathbb{R}\\); that's pretty easy to see.
  • 18.

    Derp -- perhaps I could have read John's comment 11, or also the Wikipedia article: measurable functions are most definitely out. I was hoping to come up with something almost, but not quite, like the identity function...but it seems it is too special for that.

    For anyone still interested in a pathological additive function, there is an article on 'monster' functions linked to at the bottom of the Wikipedia article on Cauchy's functional equation.

    Comment Source:Derp -- perhaps I could have read John's comment 11, or also the Wikipedia article: measurable functions are most definitely out. I was hoping to come up with something almost, but not quite, like the identity function...but it seems it is too special for that. For anyone still interested in a pathological additive function, there is an [article on 'monster' functions](http://www.cofault.com/2010/01/hunt-for-addictive-monster.html) linked to at the bottom of the Wikipedia article on [Cauchy's functional equation](https://en.wikipedia.org/wiki/Cauchy%27s_functional_equation).
  • 19.

    My answers after playing around a bit.

    1. order preserving, \(f(x) = 2x\). non order preserving \(f(x) = \frac{1}{x}\)
    2. metric preserving, \(f(x) = x + 2\). non metric preserving \(f(x) = \frac{1}{x}\)
    3. addition preserving, \(f(x) = 2x\). non addition preserving \(f(x) = \frac{1}{x}\)
    Comment Source:My answers after playing around a bit. 1. order preserving, \\(f(x) = 2x\\). non order preserving \\(f(x) = \frac{1}{x}\\) 2. metric preserving, \\(f(x) = x + 2\\). non metric preserving \\(f(x) = \frac{1}{x}\\) 3. addition preserving, \\(f(x) = 2x\\). non addition preserving \\(f(x) = \frac{1}{x}\\)
  • 20.
    edited April 8

    Eric - yes, \(1/x\) doesn't preserve any of those three things. But the puzzle asked for a function from \(\mathbb{R}\) to \(\mathbb{R}\), and \(1/x\) isn't that. It's a function from \(\mathbb{R}- \{0\} \) to \(\mathbb{R}- \{0\}\).

    On the other hand, \(1/x\) is nice because it preserves multiplication!

    Puzzle: find a function from \(\mathbb{R}\) to \(\mathbb{R}\) that doesn't preserve the order, metric or addition, but preserves multiplication.

    Comment Source:Eric - yes, \\(1/x\\) doesn't preserve any of those three things. But the puzzle asked for a function from \\(\mathbb{R}\\) to \\(\mathbb{R}\\), and \\(1/x\\) isn't that. It's a function from \\(\mathbb{R}- \\{0\\} \\) to \\(\mathbb{R}- \\{0\\}\\). On the other hand, \\(1/x\\) is nice because it preserves _multiplication!_ **Puzzle:** find a function from \\(\mathbb{R}\\) to \\(\mathbb{R}\\) that doesn't preserve the order, metric or addition, but preserves multiplication.
  • 21.

    Still getting used to MathJax, we'll see if this renders correctly!

    1. \(f(x)=x\) is order-preserving, whereas \(f(x)=|x|\) is not.
    2. \(f(x)=x\) is metric-preserving, whereas \(f(x)=2x\) is not.
    3. \(f(x)=2x\) is addition-preserving, whereas \(f(x)=x^2\) is not.

    intuitively, I'm thinking of order-preserving functions as ones which don't fold the domain into the codomain, in a sense. metric and addition-preserving functions I think of as ones which don't stretch the domain into the codomain. I'm sure there are other examples, and I'm not sure the intuition holds up exactly, but those are the ones that come intuitively to mind for me.

    Comment Source:Still getting used to MathJax, we'll see if this renders correctly! 1. \\(f(x)=x\\) is _order-preserving_, whereas \\(f(x)=|x|\\) is not. 2. \\(f(x)=x\\) is _metric-preserving_, whereas \\(f(x)=2x\\) is not. 3. \\(f(x)=2x\\) is _addition-preserving_, whereas \\(f(x)=x^2\\) is not. intuitively, I'm thinking of _order-preserving_ functions as ones which don't fold the _domain_ into the _codomain_, in a sense. _metric_ and _addition-preserving_ functions I think of as ones which don't stretch the _domain_ into the _codomain_. I'm sure there are other examples, and I'm not sure the intuition holds up exactly, but those are the ones that come intuitively to mind for me.
  • 22.

    Sean - all those answers are right, so your intuition must have some merit.

    Comment Source:Sean - all those answers are right, so your intuition must have some merit.
  • 23.
    1. \(f(x) = log_{0.1}(x)\) is not order-preserving \(f(x) = log_{10}(x)\) is
    2. \(f(x) = log_{0.1}(x)\) is not metric-preserving \(f(x) = (x)\) is
    3. \(f(x) = log_{0.1}(x)\) is not addition-preserving \(f(x) = 10x\) is
    Comment Source:1. \\(f(x) = log_{0.1}(x)\\) is not order-preserving \\(f(x) = log_{10}(x)\\) is 2. \\(f(x) = log_{0.1}(x)\\) is not metric-preserving \\(f(x) = (x)\\) is 3. \\(f(x) = log_{0.1}(x)\\) is not addition-preserving \\(f(x) = 10x\\) is
  • 24.

    Sean -- I too am thinking of metric- and addition-preserving functions as ones that don't stretch the domain into the codomain. But I don't understand what you mean by folding the domain into the codomain. (I haven't taken the leap into MathJax yet.)

    Comment Source:Sean -- I too am thinking of metric- and addition-preserving functions as ones that don't stretch the domain into the codomain. But I don't understand what you mean by folding the domain into the codomain. (I haven't taken the leap into MathJax yet.)
  • 25.
    edited April 13

    Charles - an order-preserving map from \(\mathbb{R}\) to itself cannot decrease, so it can't map the real line to itself in a manner like folding a strip of paper. The function \(f(x) = |x|\), thought of as a map from the line to itself, folds the line over.

    But notice that \(f(x) = -x\) is not order-preserving and does not fold the line.

    If you want to learn MathJax just click on the little gear that will appear when you mouse over someone's comment, and click on "View Source". Then you'll see what they did. For example, in my first paragraph I wrote this:

    Charles - an order-preserving map from \\(\mathbb{R}\\) to itself cannot decrease, so it can't map the real line to itself in a manner like folding a strip of paper. The function \\(f(x) = |x|\\), thought of as a map from the line to itself, folds the line over.

    Comment Source:Charles - an order-preserving map from \\(\mathbb{R}\\) to itself cannot decrease, so it can't map the real line to itself in a manner like folding a strip of paper. The function \\(f(x) = |x|\\), thought of as a map from the line to itself, folds the line over. But notice that \\(f(x) = -x\\) is not order-preserving and does not fold the line. If you want to learn MathJax just click on the little gear that will appear when you mouse over someone's comment, and click on "View Source". Then you'll see what they did. For example, in my first paragraph I wrote this: `Charles - an order-preserving map from \\(\mathbb{R}\\) to itself cannot decrease,` `so it can't map the real line to itself in a manner like folding a strip of paper. The` `function \\(f(x) = |x|\\), thought of as a map from the line to itself, folds the line` `over.`
  • 26.

    The first two are surprisingly boring (Ok, the members for the first one form monoid, the second non commutative group. )

    Ouf, the third one leads to nice monstrosities.

    Comment Source:The first two are surprisingly boring (Ok, the members for the first one form monoid, the second non commutative group. ) Ouf, the third one leads to nice monstrosities.
  • 27.

    John - Thank you for the nice description of folding and the examples of non-order-preserving functions. And thank you for the help with MathJax ... I'm tempted to take the plunge.

    Comment Source:John - Thank you for the nice description of folding and the examples of non-order-preserving functions. And thank you for the help with MathJax ... I'm tempted to take the plunge.
  • 28.
    1. \( f(x)=2x\) is order-preserving, \(f(x)=-x\) is not.

    2. \( f(x)=x+2\) is metric-preserving, \(f(x)=2x\) is not.

    3. \( f(x)=-x\) is addition preserving, \(f(x)=x+2\) is not.

    Comment Source:1. \\( f(x)=2x\\) is order-preserving, \\(f(x)=-x\\) is not. 2. \\( f(x)=x+2\\) is metric-preserving, \\(f(x)=2x\\) is not. 3. \\( f(x)=-x\\) is addition preserving, \\(f(x)=x+2\\) is not.
  • 29.

    \( f(x)=x \) satisfies all three properties and \( f(x) = x^2 \) violates all three properties.

    Comment Source:\\( f(x)=x \\) satisfies all three properties and \\( f(x) = x^2 \\) violates all three properties.
Sign In or Register to comment.