Howdy, Stranger!

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

Options

Exercise 1 - Chapter 1

edited April 2018

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.

• Options
1.
edited April 2018

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.
• Options
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.
• Options
3.
edited April 2018
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.
• Options
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.
• Options
5.
edited April 2018

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\$$
• Options
6.
edited April 2018
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. 
• Options
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). 
• Options
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.
• Options
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.
• Options
10.
edited April 2018

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\$$. 
• Options
11.
edited April 2018

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!
• Options
12.
edited April 2018

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. 
• Options
13.
edited April 2018
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.
• Options
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.
• Options
15.
edited April 2018

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?
• Options
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? 
• Options
17.
edited April 2018

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. 
• Options
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).
• Options
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}\$$ 
• Options
20.
edited April 2018

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.
• Options
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.
• Options
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.
• Options
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
• Options
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.)
• Options
25.
edited April 2018

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.
• Options
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.
• Options
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.
• Options
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.
• Options
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.