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.

Haha, is this the Trinity guy again? Fucking hell.

1: Each "interval" it jumps by at a discontinuity contains some point in Q. This is quite easy to prove, but tedious to write out.

2:
a) Assume increasing functions countable, list as f1, f2, f3... Go through and define a function so that it's not on the list (I'm in a hurry actually, I can do this more formally later tonight maybe). Hence uncountable.

3: Countable, and of course you can have a (not strictly) decreasing function on the natural numbers. The proof will involve there being a countable number of permutations of numbers below whatever f(1) is, then countable union of countable sets arguments.

>>3
>>2 here. Oops, didn't pay attention to his definition of decreasing.

They weren't hard, but countabilities just more fun than calculus :p

Ok, this one's slightly harder, but I think the solution's interesting.

Can an uncountably infinite collection of "figures of eight" be placed on RxR such that no two overlap?

>>5
Do you mean that the outlines of no two touch, or that the area enclosed by no two overlaps?

I believe the first can generate an uncountably infinite collection, the second only a countably infinite one.

>>6

The former, they are not plane shapes, only the outlines can't touch, but you are incorrect that the first can generate an uncountable set.

>>7

I see now... I'm assuming you mean that the figure-of-8 must be even, i.e. both parts of it the same shape and size?

>>8

Nope, they can be of any size you like, as long as it consists of two connected loops, topologically equivalent to a figure of eight.

>>5
What is that in English? Placing 8-shaped figures on a two-dimensional plane? Identical or varying in size? Or am I completely out of my depth?

>>9

In that case, my thinking leads me to presume there is some argument concerning the connection-point of the loops? I'll have to give it more thought.

>>11

I'll give you a slight nudge, the method I used was very similar to the method you use to show it's not possible to place an uncountable infinity of discs (That is like filled in circles) on the plane.

and it wasn't to do with the intersection point, although I suppose you might be able to use that.

Aw, c'mon, pretty please? You guys are excluding us plebeians here! Link to uncountable infinite disc proof, at least?

Oh, that ones not very interesting.

basic point is every disc has a radius, say r, which is a real number.

Now by the theorem of archimedes I think, which states there is no upper bound to the natural numbers, there is a natural number n such that 1/n < r for every r in the reals.

Now, you can use this fact to show there must be a rational point within any disk with a real radius.

Basically a disc at centre (a,b) with radius r.

There exists a rational number between a and a +r/2, call this c1, and there exists a rational number between b ad b+r/2, call this c2.

Now (c1,c2) lies in the disk of radius r centered at (a,b)

However QxQ is countable because Q is countable, and as there is a rational point in every disc, there exists an injection from the number of disks in the plane and QxQ, thus the number or disks in countable.


It's a pretty simple idea, the rigourous prood is kinda hard to write down.

>>14
Ah, I see. (Strictly speaking,  natural number n such that 1/n < r for every r in the positive reals.)

Then that works pretty much directly for filled 8-shapes, assuming they can't be infinitely thin, but doesn't work for outlines, since any rational point can be shared by (countably) infinitely many nested 8-shapes, right?
But if that is the case, you can place an uncountable infinite number of 8-shapes, so I must have misunderstood something.

>>15

The standard way to place an uncountable infinity of an shape on the plane is to "nest" slightly smaller copies of itself inside the original figure. Such that each copy corresponds to a shrinking or enlarging factor of a real number.

This works for the circle, and other shapes, because they have a certain property that I've heard referred to as "star shapes", but that's just a word we made up.

Basically a shape is a "Star shape" if there is a point inside a shape such that every point on the perimeter of the shape can be "seen" by that point. (ie. you can draw a straight line from this one point, to any point on the perimeter, without it having to cross another part of the perimeter)

It can easily be shown that being a star shape is sufficient to allow an uncountable infinity of them to be places on the plane, just shrink and enlarge w.r.t that point.

However I haven't seen a proof that it's necesary, but personally I think it is.

Now a figure of 8 isn't star shaped, the point inside has to be in one of the loops, and thus cannot "see" any of the perimeter points on the other loop.


This is not a proof that the figure of 8 can't be done. I'm merely trying to help >>15 understand why the converse of the proof in >>14 isn't true.

god this is a long post.

>>16
Yeah, sorry for making you type all that. :)

But I'm thinking like this; for every 8-shape, recursively put a smaller 8-shape in each of the loops. Let one of the sides be '1' and one be '0'.
Now you can follow the infinite shapes to form every binary string.

>>17

The set of all binary strings isn't uncountable.
Not sure how to show that, but it can't be :p

can't you just pretend the 8 is two circles.

>>19

And how exactly would that help?

>>18
The set of all infinite binary strings (which is what >>17 was referring to, as far as I can tell) is uncountable, and >>17's construction is a correct way of creating uncountably many non-intersecting figure-eights.

>>21

OP here, well then it looks like we have ourselves a contradiction.


By the same reasoning as the disk argument, each loop on a figure of eight contains a rational point.

Therefore you can assign each figure of eight a pair of rational points, one in each loop, that cannot also be assigned to any other loop.


Thus the number of figures of eight can be injected into (QxQ)x(QxQ), which is countable.


The other argument is interesting, but I'm not entirely sure if it's correct.

>>22

Sorry, that should read an ordered pair, although I don't even know if they need to be ordered, but that's still beside the point.

>>22
You're requiring that any 2 figure 8s share 0 area, which is clearly not what the few posters above you are requiring.

I'm still thinking about whether or not such a construction really is uncountably infinite.

>>22
It isn't, I'm wrong. It would be an infinite binary tree, and infinite binary trees has an uncountable infinite number of paths, but only a countable infinite number of nodes. Beginners' mistake, really.

>>24
No, he's only requiring that if an inlaid shape shares area with one of the two loop of an outer shape, it may not also share area with the other loop.

>>25
Somehow, that doesn't seem right.  If there are N = 2^n paths, then there are 2N-1 nodes (figure 8s).  Taking the infinite limit, both paths and nodes should have the same cardinality.

>>1-26
Give it up, it's NP-complete.

It only generates finite binary sequences.

I had a good think about it last night, and the binary sequences are represented by figures of eights.

An infinite sequence does not correspond to a figure of eight, because it's an infinite sequence.

The only sequences that can be represented are finite, I'm pretty certain.


Anyway my proof works because there are two seperate areas.

A figure of eight can share an area with another shape, but it must either fully enclose, or be fully enclosed within one of the loops.

Whereas I am assigning them a pair of points, on inside EACH loop. No two figures of eight can have the same pair and points, that fact it obvious.

>>22

Proof works.

>>28
Mm, I think that's right. You'd in theory have unreachable figures, which won't do, even if any infinite number could follow the figures all the way down. On the other hand, if you didn't have unreachable figures, it wouldn't be uncountable, would it? Meh. Infinity can be confusing that way.

On a similar vein, what if you just placed the figures adjacently on a line between 0 and 1, one on each number in the Cantor ternary set? I think it fails because some of the numbers would be infinitely close, which messes with the topology or something (makes them lines).