Mr Example.

I enjoyed those two Monsieur Ejemplé threads so I thought I'd pose a maths question of my own, in fact I'll do two on countability. They're not that hard, but I think they're more enjoyable than calculus

1. Let f : R -> R be monotonic.
Is  the set { x | f is discontinous at x} countable?
where x is in R.


2. A function f : N -> N is increaing if f(n)>= f(n+1)   (if it's bigger than OR equal to) and a decreasing function is similarly defined.

is the set {f | f is increasing} countable?
is the set {f | f is decreasing} countable?

1: First, note that for a function to have uncountably many discontinuities, there must exist an interval on which it has uncountably many discontinuities. If it didn't, then each interval of the form [x,x+1] for integers x would have countably many discontinuities, and the total number of discontinuities would be countable.

Assume {x | f is discontinuous at x} is uncountable, and that f has uncountably many discontinuities on the interval [a,b]. For each discontinuity there is a jump, since it is a monotonic function. Hence the difference between f(a) and f(b) must be infinite, a contradiction.

2:
(a) Yes. There are uncountably many ways to choose an infinite subset of the natural numbers, and each can be turned into a function by pairing the nth natural number with the nth smallest number in the subset. (eg, {2, 3, 5, 7, 11, ...} would correspond to the function f(n) = 2 if n=1, 3 if n=2, 5 if n=3, etc..).
(b) No such thing as a decreasing function on the natural numbers. If you start the natural numbers at 1, f(f(1) + 1) cannot be a natural number; there are f(1) - 1 natural numbers less than f(1), so we have at most f(1), f(2), ... f(f(1)) able to exist if we simply take a decrementing sequence.