This might do your head in
Imagine that you have a square of paper and a black pen which draws lines with no width. Is it possible to draw a curve on the paper which leaves it entirely black?
I've recently asked this question to several people - who had differing degrees of mathematical aptitude - and each of them has told me that it is impossible. Perhaps you would too; and indeed quite recently I tried to prove something assuming such a task to be impossible, only to be told that it can be done.
Here's how
Formally speaking we're looking to construct a
surjective mapping from [ 0,1 ] to [ 0,1 ]
2 (a curve is really just a function from a subinterval of
R to some space, and surjectivity requires that its
track should fill up all of that space). I'll define the curve as the limit of an infinite sequence of curves; the first one looks like this:
.;------------;------;;;;;;;;;;;;;;,,,,,,,,,,,,,,,...,.....,.................,,...... .....
+xXxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxXXXXXXXXXXXXXXXXxXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXxXXXX#####Xxx+==-
.X#+===+x+xxxxxxxxxxx+x+xxxxxxxxxxxxxxxxxxxxxxxxx+xxx+x+xxxxxx++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++====++xX.
+=-==-;---------------------------------===---==-=-======================================================+++++++++++++++++++++++++++++++-+=-=-=+.
x=-=- x=---=+.
#=-==. x=---=+.
x=-==. .#=---=+.
#=-==. ,#----=+
#====. ;#----=+.
X====. #=--=+=
#-===. #=--==;
-,===. x=--==,
#-===. ;#+=-==,
#====. x#=--==,
x=-==. X=--==,
X=-==. #x--==,
x+-==. X--==,
-+-==. X--==,
;x==+. +#=-==,
;x-=+ x--==,
;x-=x -#====,
-x-=x X=-==,
;x-== -+-==,
=x-== ++-==,
-x-=x =x-=+,
.+==+ -x-=x;
.x==+. .x==+.
.x==x. +==+=
.x==X, +=-=#
.x==+. x=-=#
.+=== x=-=#
.+==x- x=-=x
.==-+= x=-++
.==-++ +=-+=
.==-++ ==-=X
.==-+- =+-=#
.==-++ =+-=#
.==-++ =+--#
,==-+= ==--#
,==-+= +=-=#
,==-=x x=-=#
,==-=# x=-=X
,==-=X x=-=#
,==-=X x=-=#
,==-=x .x--+=
,==--x+ =x--+=
,==--+X -##= =x--x,
.==-=xX ####+ ++--x,
,==-=+ =##### X+--x,
,==-=X ##### #=--x,
,==-=x X#### x=--+.
,==-=xx . ;##########x-;,... #=-=+.
,==-=x= .-############################################, X=-=+,
,==--x. -+###############+-. -x#####; . x++###########; x+-=+.
.==-=# ;############- ;#####= +#########= x+--x,
,==-=- ,x############x; .###### -######### ++-=x,
.==-=x. ;###########xX ###### #######x X=-=x,
,==-=+# .######X ##### ;######- #=-=x.
;++--=+ =####X #### =#####x #=-=x;
-+==== ##### +###### X=--+.
,=-=X =####- ###### x=--x-
,===X ,#####. -###### X=--x-
,+==+ #####x .###### .#=--x,
;+=--,####X. ###### X=--x;
,+=;+###x ;#####. =+--+-
,+=-##= =##### .+--+x
;+=;,;;-X###################x==+x+==,... . .. ..... . ..,.... x-.,.. . . . -x###-=--=+
;x+==-==+=====-----------==+xxxxxxxxX##############################X###X#XXX####XxxXXX###XX##X#XXXXXXXXXXXXXxxxxxxxxxxxxxxxxxxxxx+-,..,;----=x
.=xxXXXxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxXXXXXXxXxxxxXXXXxXXXXXXX#XXX#XXXXXXxX##X#X#XX##XXX####X####X##XXxxxxxx+++++++++++++++++++++++=========+#,
I've drawn a curved line here between the bottom left and bottom right hand corners: its should really be a straight line, but I've drawn it curved for reasons that will become clear when I've drawn the next picture. The second curve looks like this:
=x+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++=++++++=======================++-
-=====++=++++++++++++=--========--=======-=======+++xxxxxxxxxxxx+=---==+++xxxxx+xxxxx+++++++xxxxx+=----+xXXX#XXXxX##XXXXXXxxxxXxx+=--=--====
;==++x+xXX++++===+x++x#######+###################++=---;,;-;;;;;,#=-=x-==+=;;;+===;;==++=x#x,-=, .X=--=+ .,,,,,,,.,,+;x+==,=-===
-==X -+-+- X+--=# +,=-==+
-==# ;x-+, +x--=# =,---=+
.===# -X-++ =#--+= --=-=+
;===# -x-+# #=-+= ### ;;=-=+
.-===- -X-== , #+-+- ##### ===-=+
;====X #-== #####+ X+-+X ,###+ ---=+
===--#, #-=#; ,#####; xx-=X =;-+#####x =-=-=+
===--# #=-# =; X##### -x--X- =################ ----=+
-==--# x=-X .###################, x--X- ##### ########- -----+
===--# x=-=;=######; =##########X- ,=--x. ####x ####X x#### =---=+
;-==-# #=.;####x +#### =######-.;+ #### ###X ,###x;---===
;==-X +;,### #### x####= ###- ### ###+,.;==-
.-=--X# #,### .. . x########+X######= X###=,-=-
.-==-x; #,########XXxxx+=-=xXXxX#X##xxxx=. ,X##=.,-=+=++++=+xX##########+,=###;-==
.-==-x- #;.+#####x--x#############X#####XXx=. ;=+++XXX++X#########x+; ;-####+,-=+
.-==-X- #-=. +###+ ;=-=X ;X######=--=-
.-==-X #-=- #### =+-=# ####. +--==
.-==-x #-+- ###+ =x-=#+ ##### x-==-
.-==-+# #-=# ### ,x-=# ####x .x-==-
.-==-=# #-=x ### x--# ###= # =x-==-
.-==-=x x=++ ###; #--# ##. ### ### X+-==-
.-=--xX +####. ++=+ ########+ #--#X ####- ##. ### +=-==-
.-==-+ ,#######. ;x+= ###############, #--# x##########, +=-==-
.-==-+# .x###### .x=- ##### ##+ ,X#######. #--# +#######. +=-==-
.-=--=#. ..,;x######=;. .X=x- X####, ### ,-- +X--# .###X .--==-
.-==-=# ;x###########################- .x-x ###x ;##. -#--#. ###. X=-==-
.-==-=# .x##############X= #####X###############x; .X-X+ X### #--#. ###= x--==-
.-===-# ###########x, ####X ,###########x. x-x ####= #--X+ -###- x--==-
.-==;=+. -########- #####= . -########## =-+ ####- #--x. +#### +=-==-
.-=-;;,-#######, ####; -###### X#####= -#--x- ####++,--==-
.-=--+######= .+#########= , .,;; =x=-+-..# ,.x+,xxxxx,,, +#####;;==.
.-==--###x.. .-+xxxxxxxxxXXXX####Xxx+++=-==+x##############XXxx+-. .;x+; ;+x########################Xx+--=xXxX####XXXXxxxxxXXXXx=, ;##+;=-
.-==,;X##=.x###############xxxX##x- .=######- .X#####X############Xx+=-.,-+X#################X####XXXXXX####X###XXXXxx##XXXX#####X=..=###x--;
.-==-;-### -#####=.#### ;,==x--+= ####x=--==,
.-==;=--###, ####+ ####. ,= ####X #--x= ###- =-=+=
.-==;-+- x####- ###X x####=;-+; ;#### #=-x+ ###= X+-==-
.-==;=x ######+,=#####. ;##### -=-x; ###x X=-x= ###; #=-==-
.-==-=x, ,################X ++-x; ### #=-X= #### #=-==-
.-==;=+#+ =######, +x-x- ### ==-X ###= #+-==-
.-==,=+# . .###; X-+. ####+ #+-# ### -x--=-
.-==,==#= X###X .#-+- x########= ==-# ###X ,X--+-
.-==;=+#= ###x -#-+# ####### -####. #=-X, +### ,X--+=
.-==;==x- +==X ### ### ### #--X, ###+ -#--++
.-==;==X= ++=+ ## ### #--x. =### X=-=-
.-==;==#= +==+ x### #=-+x ###x ## x+-+-
.-==-==X X+=# ### #=-=# ### ### #### ,+-=+
.-==;==x# -+-x .###, x=-=X ####X ### ##### =+-=#.
.-==--++# x+-x #### #=-=X ####=##x ####X =+-=+
.===---=# ==-==##### .X--=# ;#####+ ####. -+==x
,++----=+xx#######################X##+--;####-,x###################Xx++---# ######## ;+-=x.
,++==----=+xxXX###############XXX###x+=-.-##X -+XXXXX##XX##XXXXX###Xx=---## ###### -x--X=
.===--=+x++;; ;,- ,-+--X####=; . ;. ;, ,,,,, ..,X=-=X ####X -+--x=
.==-==x, +--- -#### #--=x ;### -+--x=
,==--=X= .x==# .###; #=-+x ###+ -+-=x=
,==-,=+# x=-#; #### #=-+; #### ;+--=
,==--=x# +=-X# #### #--++ ### -+--+X
,==--=+- +=-x ###- #=-++ #### -+--=#
,==-,=++ +=-x# ### #=-+= #### -+--=#
;==-,=x# ==-x# x####= #--+= x###. -+--=#
,==-;=+# =+=X= ########. #=-=# #### -==-=#.
,==-;=+# ###X =+=+ x########### ,#=-=# x#### -+=-=#.
,==-;=+# #### =+=x ### X##+#####= .#=-=X #### -+--=#
,==-,=+# #### =+=x x### ### -x#x #--++ #### -+=-=#;
,==-,=x# =X###; =+-x ## ###+ #=-+- #### -+--=#
;==-;==# .##############X ;=-X+ ###- #=-=# ##### ;+--=X
,==--=+# ######## -X############=,;x- =### +#=--# ##### .+--=#;
,==--=+++x###### x####; =####,.+, ####x .x=--#. x### =--=#
,==--==###### ### X### ; +####-== ..==##X--=#####Xx+==x=;-===+=x###x##################xX###+=====-x############x+X###x=--=#-
,==---;,+x; ,=x++=. .xXXXXx-.x##########= ,-+xXXx++=+xx++===------==+xxxxx++==++===-=============+++==++xxxxxx+=============;..,;-----;
;==----;..,;-===+++x+xX###Xx+++++=-, -xXXX+;.,-==========================================================================================+xX=
;+x+=+-==xX########XXxxxxXxxxxxxxxxxx+xx++==++xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx+=;
The lines are drawn cruved here so as you can tell which boxes they belong to.
Note that the second curve is made up of ten smaller copies of the first (and it's three times longer). So, to construct the third curve, just replace each of these copies of the first curve with suitably scaled down and rotated copies of the second. Thus the third curve is composed of one hundred copies of the first curve...
To complete the rest of the sequence, just keep repeating this process (it is called
fractal iteration). I claim that this sequence of curves (name them, say, f
n: [ 0,1 ] -> [ 0,1 ]
2)converges to a fractal curve (say, f: [ 0,1 ] -> [ 0,1 ]
2) which passes through every point in the square. Such a curve is known as a
Peano (monster) curve.
In terms of justification, I could launch into some dreadful epsilon/delta argument that would send you all to sleep, but there is a nicer way for this particular curve.
Here's why
Suppose you have some number in the interval [ 0,1 ] - it can be written in the form of a decimal expansion of the form 0.d
1d
2d
3... (n.b.
1=0.999...) where each d
i is one of 0,1,...,9. Now have a look at the following picture:
#################
# # 6 # 7 #
# 4 #########
# # 5 # 8 #
#################
# 3 # 2 # #
######### 9 #
# 0 # 1 # #
#################
Note that this picture numbers the boxes in the same order as the curve passes through them in the second picture. Ah ha! This then allows you to work out approximately where any given number in the interval [ 0,1 ] gets sent to one the second curve - it gets sent to the box labeled by d
1, the first digit. You can then more accurately determine where the number gets sent to one the third curve by subdividing box d
1 into ten parts again, and of these you know that the image point must lie in box d
2. If you keep repeating this process, you can determine where a given number get sent to one sucessively finer iterations of the curve to a greater degree of accuracy;
because as each time the process is repeated, the boxes get at least four times smaller.
I'm afraid I couldn't make that last sentence any shorter. How about a quick example: suppose the number in question is
pi/10 = 0.31415... Dissect you square into ten parts as prescribed above, and you know that pi/10 must be mapped into box 3. So, subdivide box 3 into ten parts, and you then know that pi/10 belongs in sub-box 1. Subsubdivide sub box 1, etc.
Now to prove the convergence of the curves. By the above algorithm, we know that from some 0 <= a <= 1:
- we can place f2(a) inside some box of size at most one quarter
- we can place f3(a) inside some box of size at most one sixteenth
- we can place f4(a) inside some box of size at most one sixty-fourth
and so forth. In general, f
n(a) is bounded by some box of area (1/4)
n-1, so for any value of a, (f
n) is a
Cauchy sequence. Because [ 0,1 ]
2 is
complete, all the series converge and so the limiting monster curve f exists.
Finally, it should now be clear that f is surjective as claimed: by using the repeated subdivision process described above, you can produce a decimal series corresponding to any point in the square.
As a techincality, consider the subdivided boxes as open sets ie. not inculding their boundaries. If you want to find the decimal series for a point on a boundary between two boxes, just take numbers corresponding to boxes on either side of the boundary as you 'zoom' closer in; the resultant decimal series must then converge to the boundary.
m-m-m-MONSTER KILL kill kill*
You might not believe this argument at first, as it seems to go against your previous conceptions on what the real numbers were. Initially you might wish to dismiss this as a pathological example of no relevence to the world as described by real numbers, but
Mandelbrot would argue otherwise. In his book on the fractal geometry of nature, he writes "[ when ]
Peano curves are observed attentively, letting one's thoughts wander about, it becomes very difficult not
to associate them with the diverse aspects of Nature.", citing the drainage basin of river as an example.
The madness doe eventually stop, you'll be pleased to hear, as for a!=b
Ra is not homeomorphic to
Rb, so toplogically speaking at least there are no more surprises.
Proof: Ra - some point and Ra - some point have different homology groups.
Remarks
- The fractal dimension of this curve is 2, which seem fairly sensible given that it fills an area; indeed the existence of such curves is a motivation for the definition of the fractal dimension of a curve. Fractal curves which behave in a similar way but don't manage to fill and area (such as the Koch curve) can then be sensibly expected to have fractal dimensions between 1 and 2.
- The generator for the curve I describe above is more complicated that in needs to be - I devised this one because it lends itself nicely to decimal expansions. Here's a simpler one:
XxX#XXXXX############X############XXXX##XX####X#####X##X###########XXXXXXXXXXXXXXXXX#X#X#X##X###X###XXXXXXXXXXXx#X;
#x==+xXXXX#XXXXXXXXXXXXXXXXXXXXXX#XXX#X###X##XXXXXXXXXXXXXXXXXXXXX##X#########X#X##X##X###XXXXXXXXX#XXXxxx++-,.,=x;
.+-=- x#--+,
,x=+; ##+;+,
.x=+= ###;;x,
.+==- =###-,-x,
,+=== =##### ---x,
,+=== #####- x=-+,
,+==- ##### #+-x,
,+=== =#### =+-x-
,+=== .##### ;x-x;
,+=== -####- .x-+-
,+=== X####. .x-+-
,+=-= #####; .x=+=
,+=== #####+ x=+-
,+=== -#####; x=+=
,+==+ #####, x=+-
,+==- ####; .x=+-
,+==, #### +=++
,+=== -###X .x=+x
,+=== ;###x .x=+=
,+=== +###= .x=+-
,+=== X###= .X=x-
,+=== #### .x=+-
,+=== =#### .x=x-
,+=== X#### .x=x;
,+==- -X######. .x=x,
,+=== x#X############- .x=x,
,+=== +######x###### ,x-x;
,+=== ###=## =x-x,
,+=== #### ,## ;x-x,
,+=== #### ### ;x-x;
,+=== ,####. ### ;x-x,
,+=== -###+ ### -x-x,
,+=== ####x ###, .x-x,
,+=== +####. ,x-x,
,+==x ####x ;x=+,
,+==# ####+ =+=+,
.+==# =###- -+=x,
,+==x x###X ;+=+,
,+=++ ####+ ++=x,
.+=+- ####; ,+=+,
,+=+= ####. =+=+,
.x=+= #### x+=+,
.x-+= #### ++=+,
,x-x; -#### ++=+,
,x-x, ;#### ++=+,
;x-x, =###x x+=+,
;x=+. =####; ++=+,
-x=x, x#### ++=+,
=+=+, =### ;x=+,
x+=+. .####- -+=+,
X=-;. ####= x+=+,
#=-=####. x+=+,
.X--;X- ;+=+,
,x----. .,;-;-Xx+xXX+xX+=xxx#####################X+XXx+++-;;,..... .,, ..,. . ,+=+;
.#x==++X#######XXXxxxxXXXXXXxxxxxxx+++++++++++++xxxxXxXXXX###########################XXXXXxxxxxxxxxxxxxxxxxxxxxx++xX;
-#xxx+---==================================================+++===+++++++++++xxxXXxX########################XXXXX+,
is the first curve of the sequence, and
.. ...
;#XXX###########################x+=-;;;,,,;=x########################XXXX###########################Xxxxx+=+xX#x,
-x==+=+++++++++++++++++++++++- ,+########= -+++++++++++++++++++++==+===++++++++++++++++++++++++; ,;;;.+##-=++.
;+==x #####x ;+x##; x== =#######;;===.
;+=-X =####; ;-= ### . X=x x###### X-,===.
;+==# ;#### =+x ### ;### .X=x x##### #+.;+=
;+==X ####- x+#. #### ## .X=x ####. #+-;+=
;+=-# .#### ++x +##. ##+ .X=x #### #X=-==
;+==# #####+ #### =+X. X####= .X=x ####+, x###x =X=-==
;+-=X ##########X =+X, ########### .X=x .-#######; +X=-==
;x-=+ =#### =+X, +x#=;. X##= .x=x +#### +#=-==
;+-+= +### ## -+x, ### .X+x =####### x#=-==
;+-+= ###x ## -+x; X### X++ =#### ### xx--==
;+-+- #### ##; =+x; ###x X+= -####x .## #X--==
-x-+x .###= ### -+x- ### X++ -####, ## xx=-==
-x-x, #### ,+xx ####. X+= ####; #X--==
;x-+. #### ,++= .### =+; =### #x--==
;+==-.###+ ,++- ####;= ### #x=-==
;+=-;##=.=+X###########################x+=x+x+##+=----====--==--- .=##==- ### ........................ .x+=-==
;+=;-##. =+xxxxx+++x++++++xxxxx+++x++==+++x###################X=;.,###.-++###-+###########################+=--==
;+=-,### ++ ,+#### -=+ ###= ,,,,.====+++==--...... =#=-==
;+=-,####. ,+X. ###- -+=+ X###. #=-==
;+==-.####- .+X. #### +++x #### #=-==
;+=== #### ,+X, .- #### ++++ ##### =#--==
;+==X ###x .+X. ### .#### ++++ x###- .#--==
;+==x; =### ,+X, .## x### ++++ ############+ #=-==
;+==x- ### .+x, ######; ++++ =###; +X. #+-==
;+==x, ###= .+X- =### ++++ ##### xx-==
;+==x ;###; +x- ;### X####= ++++ ### ###, #x-+-
;+==x+ ############x .+x; ;########x+ ++++ ### #### #+-+-
;+-=x+ ######, =; .xX; #### ++++ ### ###+ #+-+-
;+-=x ### ####x +X; -#### x=++ -# -##x #=-+-
;+-=x. ### ;##### +X; ### +=++ ,### #+-+-
;+==+X ### -#### ++ #### x=++ ###, #=-+-
;+-==# ####. x=+##X x=+= ### #=-+=
;+--=# ####. +-=## x=++ =##- #=-=+.
;+--=#. x### +;=#x +=+- =###=x##+-==.
;+--=X ###. =-;## ===+;;+###x+###################-;+##-+x=-==
;+--=+-,;,;;;---=++xx+=---==--=+#= =##.== ##=X#######################+=+##x=X+=-=-+;+,,,,;,,.,.,.,,,,X#x ,x+-==
;+====X##########################X- ###==+ ### +==. ### .#+-==.
;+--xx- -###- ++ ### x=+; ###- #+-==.
;+-;xx ####. .xx =### X=x- ### #+-==.
;+=-+# ####x ;xx ### #=x; ,### Xx-==.
;+--+X #### ;xx ;### =## X=x; ,### ##-==.
;+--xX +###+ -xx -##-x##- X=+; #### -#-==
;+--xX .####= ;xx ###### X=+; -### -#-=+
;+--+X +###X ;xx #### X=+x .###x .#-==
-+--xX +####- ;xx. x##- X==; -#=;. .#### .#-==
.x=--+X ########### ,xx. ##########= X=+# ############ #-==
.+=--+X ##, ###### ;xx #### x=+= -##### #-=+.
.+=--+X ### ### ,xx. ####- #=+; x###;## .#-==
.+=--xX -### ### .xx. #### #=+; -###x ## #-==
.+=--x, x####x ### .xx. .###, #=x; x#### .## #-==
.+=--x, #####- .xx. x### x=+; ###. ### #-=+
.+=--x +###, ,+X. ### ,;=. ####= ## #==+.
,+=--+x =##. .+X, ,##x +#####, #===.
.x=---+x#### =+ ######### #+==,
=+--+####=;,x##X##################X+===+++x####xX###+++++;.,.. ,+X= .+==.
-x++-;..,-=+++++++=+===========++++xXxx++=+===++++++xxxxXX###########x=;,.;=+X####XXXX#XXXXxxxxxxxxxxxxxxxx+==-==
,-==++xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxXxxXX##############################XXx++++++xxxxxxXXXX##-
.,.,,--+#####Xxx++++= -,..
is the second.
- Considering this simpler example, can you generalise it to a monster curve that fills up a volume?