It looks like you're new here. If you want to get involved, click one of these buttons!

- All Categories 2.3K
- Chat 499
- Study Groups 17
- Petri Nets 8
- Epidemiology 3
- Leaf Modeling 1
- Review Sections 9
- MIT 2020: Programming with Categories 51
- MIT 2020: Lectures 20
- MIT 2020: Exercises 25
- MIT 2019: Applied Category Theory 339
- MIT 2019: Lectures 79
- MIT 2019: Exercises 149
- MIT 2019: Chat 50
- UCR ACT Seminar 4
- General 67
- Azimuth Code Project 110
- Statistical methods 3
- Drafts 2
- Math Syntax Demos 15
- Wiki - Latest Changes 3
- Strategy 113
- Azimuth Project 1.1K
- - Spam 1
- News and Information 147
- Azimuth Blog 149
- - Conventions and Policies 21
- - Questions 43
- Azimuth Wiki 707

Options

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

*order-preserving*if \(x\leq y\) implies \(f(x)\leq f(y)\), for all \(x,y\in\mathbb{R}\);*metric-preserving*if \(|x-y|=|f(x)-f(y)|\);*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

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.

`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.`

`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.`

\( f(x)=x\) is order-preserving, \(f(x)=-x\) is not.

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

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

`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.`

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

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

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

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

`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.`

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).

`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).`

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

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

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.

`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.`

Yes,

order-preservingmeans the same asmonotonically increasing, and the book usesmonotoneas a shorter synonym. So, in the book, amonotone 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-reversingormonotonically decreasingfunctions, 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

oppositeposet \(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\).`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\\).`

William wrote:

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\).

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

continuousaddition-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!`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!`

Here is my solution.

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

`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.`

\(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)\)

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

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

`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.`

`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.`

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?

`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?`

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?

`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?`

Keith: I said the proof that

not alladdition-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.

`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.`

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.

`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).`

My answers after playing around a bit.

`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}\\)`

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.`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.`

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

order-preserving, whereas \(f(x)=|x|\) is not.metric-preserving, whereas \(f(x)=2x\) is not.addition-preserving, whereas \(f(x)=x^2\) is not.intuitively, I'm thinking of

order-preservingfunctions as ones which don't fold thedomaininto thecodomain, in a sense.metricandaddition-preservingfunctions I think of as ones which don't stretch thedomaininto thecodomain. 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.`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.`

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

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

`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`

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.)

`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.)`

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.`

`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.``

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.

`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.`

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.

`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.`

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

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

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

`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.`

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

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