Online since 2002. Over 3300 puzzles, 2600 worldwide members, and 270,000 messages.

TwistyPuzzles.com Forum
 It is currently Mon Apr 21, 2014 12:27 am

 All times are UTC - 5 hours

 Page 1 of 1 [ 12 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Cardinality and other mathematical musingsPosted: Sat Aug 10, 2013 12:16 am

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
First a brief introduction. My background is in physics and even though math is the language of science rarely did my schooling take me into areas where we simply did math for math's sake. I can think of a few exceptions. But typically it was rather closely tied to something physical. That said I have a very good friend from my grad school days that was so good at physics that he found it boring and he went off and got his math Ph.D. and I've long since lost count of the number of conversations we've had on topics ranging from Cardinality to the proof of Fermat's Last Theorem (almost none of which I understood by the way). However most of the Cardinality discussion I could follow and I found facinating and some of this stuff strikes me as very counter intuitive.

Anyways this is a sort of spin off thread from the Gizmo Gears Jumbling discussion which I didn't want to take too far off topic. And where this next quote comes from.
bhearn wrote:
More obviously, the set of irrational reals is uncountable, but between any two irrationals are some rationals.
Yes... I know this is true but it seems very counter intuitive. The set of irrationals is uncountable. So the set of all possible pairings of irrationals is also uncountable. Yet inside EACH of these parings are rational numbers. But the rationals are countable... how is it possible that there are enough to distribute them across all these uncountable regions? If there are irrationals between any two rationals and vice versa it implies to me that the density of the two are the same. See... me being in physics makes me want to apply terms like density which I don't even really know have any meaning in this line of reasoning but none the less its how my mind works. So if the density is the same how is it that we have more of one then the other. If the density isn't the same and we have more irrationals (which I know we do) then my physical mind tells me we should have pairs of irrationals without any rationals in between. Anyways I've sort of learned to live with these counter intuitive situations. If there are any good answers to share here please do but its not required to participate.

So lets move on to questions about Jumbling Gizmo Gears...
(1) Its believed that the set of orbits for some points becomes infinite at some critical R. I think I could almost say its been proven... just not formally so at the moment. Anyways its also believed that these infinite orbits may be uncountable. My question is... if these orbits become uncountable is it possible that there is one value of R where the orbits become infinite but countable and yet another value of R where they become uncountable?

(2) If we call N0 the cardinality of the rationals and N1 the cardinality of the reals, is it ever possible for an orbit to reach N2 (the next higher cardinality) number of elements in a problem like this? If the answer is yes... what would that mean? Both sets are considered uncountable. As I believe the entire plane only has N1 elements I think that is impossible but that's me applying physics to a math problem again.

And now on to a general cardinality question which has been in my head for some time which I don't believe I've ever asked. Back in school on one of those rare exceptions were we were playing with math for the sake of math I was introduced to something called at the time The One Third Function. I've googled it and I can't find it now so it may be known by another name. Anyways we were looking for a function which was continuous between 0 and 1 which had a slope of 0 everywhere it was differentiable yet F(0)=0 and F(1)=1. Its very counter intuitive that there could even exist such a function as how does it obtain a value of 1 if it must start at 0 and be continuous while the slope remaines 0 everywhere it was defined. As I recall one of the conclusions was that there were uncountably many such functions and The One Third Function was but one of them. It went something like this.

At the ends of the interval the values are defined... in this case F(0)=0 and F(1)=1.

Now take this interval and cut it into thirds and for the middle third give the function the value of the average of the end points so we now have:

F(x) = 0 if x=0
= 0.5 if x between 1/3 and 2/3
= 1 if x=1

Now repeat and you get

F(x) = 0 if x=0
= 0.25 if x between 1/9 and 2/9
= 0.5 if x between 1/3 and 2/3
= 0.75 if x between 7/9 and 8/9
= 1 if x=1

And you continue to repeat this process until all the points are defined.

This being a continuous function allows one to ask rather interesting questions. For example at what value of x does the function take on the value of 1/pi? Basically any value that the function takes on which isn't of the form N/(2^M) where N and M are integers can only happen where x is of the form P/(3^Q) where P and Q are integers.

If I think about this too long that seems to tell me all the irrationals plus many of the rationals between 0 and 1 must be mapped to this very specific subset of the rationals also between 0 and 1 using this function. How is that possible? If I can map all the irrationals to a subset of the rationals and have room left over for most of the rationals too. How can the set of irrationals be bigger then the rationals?

Anyways... that should be enough to get us started,
Carl

_________________
-

Top

 Post subject: Re: Cardinality and other mathematical musingsPosted: Sat Aug 10, 2013 12:57 am

Joined: Fri Feb 08, 2008 1:47 am
Location: near Utrecht, Netherlands
I don't think an orbit could ever be uncountable. If x is a point on the puzzle, then the only reasonable definition of its orbit is the set of all points obtained as the image of x under a finite move sequence ("infinite move sequence" does not make any sense). This means the orbit is as most as big as the set of all finite move sequences which is countable (you can enumerate the finite move sequences by first enumerating the (finitely many) sequences of length 1, then of length 2, etc...).
So the answer to both questions is no.

The one thirds function reminds me of the cantor set. I don't think the one-thirds function actually exists, since the example function you gave is undefined on uncountably many points!

_________________
Tom's Shapeways Puzzle Shop - your order from my shop includes free stickers!
Tom's Puzzle Website

Buy my mass produced puzzles at Mefferts:

Top

 Post subject: Re: Cardinality and other mathematical musingsPosted: Sat Aug 10, 2013 1:45 am

Joined: Tue Aug 11, 2009 2:44 pm
Fun stuff!!

wwwmwww wrote:
First a brief introduction.

OK, let me do a brief introduction as well then... my background is in computer science, but my Ph.D. was on the theoretical side (computational complexity of games and puzzles), really more of a mathy thesis. I have always loved logic, set theory, and the foundations of mathematics, at least since I read Gödel, Escher, Bach in 1980, possibly earlier, I don't recall. Anyway it has never been more than a hobby, though my bookshelf does hold maybe a couple dozen books in this area. There is, in fact, a deep connection between these areas and the theory of computation, and there I have more of a legitimate academic background.

Quote:
The set of irrationals is uncountable. So the set of all possible pairings of irrationals is also uncountable. Yet inside EACH of these parings are rational numbers. But the rationals are countable... how is it possible that there are enough to distribute them across all these uncountable regions? If there are irrationals between any two rationals and vice versa it implies to me that the density of the two are the same. See... me being in physics makes me want to apply terms like density which I don't even really know have any meaning in this line of reasoning but none the less its how my mind works. So if the density is the same how is it that we have more of one then the other. If the density isn't the same and we have more irrationals (which I know we do) then my physical mind tells me we should have pairs of irrationals without any rationals in between. Anyways I've sort of learned to live with these counter intuitive situations. If there are any good answers to share here please do but its not required to participate.

I don't think I can offer much insight here, except to say that, well, that's the way it has to work. Naive concepts of "more" don't really work for transfinite numbers; we get into trouble right away if we think there are more integers than even integers.

Quote:
So lets move on to questions about Jumbling Gizmo Gears...
(1) Its believed that the set of orbits for some points becomes infinite at some critical R. I think I could almost say its been proven... just not formally so at the moment. Anyways its also believed that these infinite orbits may be uncountable. My question is... if these orbits become uncountable is it possible that there is one value of R where the orbits become infinite but countable and yet another value of R where they become uncountable?

Good question! One we might hope to answer, but I don't have an answer yet.

Quote:
(2) If we call N0 the cardinality of the rationals and N1 the cardinality of the reals, is it ever possible for an orbit to reach N2 (the next higher cardinality) number of elements in a problem like this? If the answer is yes... what would that mean? Both sets are considered uncountable. As I believe the entire plane only has N1 elements I think that is impossible but that's me applying physics to a math problem again.

I wondered at first why you used "N", then realized that the Hebrew letter aleph does look like an N. But usually when it's written in Latin letters it's just spelled out, "aleph". Aleph-0 (or aleph-null) is indeed the cardinality of the set of natural numbers (also rationals), but your statement that aleph-1 is the cardinality of the reals is actually equivalent to the celebrated continuum hypothesis. That's a statement that can neither be proven nor disproven within the standard axioms of mathematics.

But taking your question more generally... if an orbit can contain a countably infinite set of points, or a set of points with the cardinality of the reals, can it also contain a higher cardinality set of points? Here I would think the answer would be no. The image of an orbit is the set of points that can be reached under some sequence of moves, and if we allow (countably!) infinite sequences, then we are left with at most (2^aleph-null = cardinality of the reals) points. Why is it reasonable to allow countably infinite sequences of moves? Well... actually, maybe it's not. The motivation here is unbandaging a disk puzzle. A puzzle is unbandaged if, in any reachable configuration, no moves are blocked. But it's reasonable for "reachable" to mean a position reached by some finite sequence of moves. I guess we could go either way here. But if we adopt this latter perspective, then we can't get orbits with uncountably many points either. I don't see how one could get a higher cardinality than that of the reals, in any case.

Quote:
And now on to a general cardinality question which has been in my head for some time which I don't believe I've ever asked. Back in school on one of those rare exceptions were we were playing with math for the sake of math I was introduced to something called at the time The One Third Function. I've googled it and I can't find it now so it may be known by another name. Anyways we were looking for a function which was continuous between 0 and 1 which had a slope of 0 everywhere it was differentiable yet F(0)=0 and F(1)=1. Its very counter intuitive that there could even exist such a function as how does it obtain a value of 1 if it must start at 0 and be continuous while the slope remaines 0 everywhere it was defined.

Well I don't see any problem here... if the function is discontinuous, then why does it seem odd for F(0) = 0, F(1) = 1, even if the slope of 0 everywhere it's differentiable? That's just a step function. It's not differentiable at the step. Maybe I am not understanding.

Quote:
And you continue to repeat this process until all the points are defined.

Oh, but that can't happen... e.g., F(1/3) will never be defined.

Quote:
This being a continuous function allows one to ask rather interesting questions. For example at what value of x does the function take on the value of 1/pi? Basically any value that the function takes on which isn't of the form N/(2^M) where N and M are integers can only happen where x is of the form P/(3^Q) where P and Q are integers.

That's only true if you look at the values assigned after a finite number of steps. Also, I don't think this function is continuous, even if you iterate your subdivision steps a (countably!) infinite number of times (actually, this is a reasonable thing to do, and is in fact one way to define the reals). It looks to me like it's been infinitely chopped, and is in fact discontinuous everywhere (and not differentiable) now.

Quote:
If I think about this too long that seems to tell me all the irrationals plus many of the rationals between 0 and 1 must be mapped to this very specific subset of the rationals also between 0 and 1 using this function.

Based on the pairing with a specific P and Q? Yeah, I'm pretty sure that the answer there is that P and Q don't exist. Certainly, you can't exhibit natural numbers P and Q such that P/(3^Q) = 1/pi.

If you find questions like this interesting, I'd highly recommend "Surreal Numbers", by Knuth, and "Inifinity and the Mind", by Rucker, if you haven't already read them.

Top

 Post subject: Re: Cardinality and other mathematical musingsPosted: Sat Aug 10, 2013 2:01 am

Joined: Tue Aug 11, 2009 2:44 pm
TomZ wrote:
I don't think an orbit could ever be uncountable. If x is a point on the puzzle, then the only reasonable definition of its orbit is the set of all points obtained as the image of x under a finite move sequence ("infinite move sequence" does not make any sense).

That may be the most reasonable definition, but I would disagree that "infinite move sequence" does not make any sense. One could just as well say that infinite decimals don't make any sense. It is true that many infinite move sequences applied to a point x do not converge to a fixed point (as infinite decimals do), and then we could say that there is no image of x under those sequences. Hmm, in the context of the disk puzzles we are talking about, I guess it does seem to be the case that *no* sequences can converge to a fixed point, other than trivial cases (e.g. a point sits at the center of one disk, and only that disk moves in the sequence).

But if this is true, it's only because of the particular transformations that make up our sequences. It's not that there's anything wrong with the concept of an infinite sequence of moves. An in fact, it could well be the case, even for these disk puzzles, that a certain amount of sense could be made of infinite move sequences. We might have two sequences A and B, with the property that some infinite sequences of As and Bs do converge to fixed points.

Top

 Post subject: Re: Cardinality and other mathematical musingsPosted: Sat Aug 10, 2013 3:44 am

Joined: Fri Nov 05, 2010 2:20 am
Location: Wherever
I have no idea if what I am going to ask is related, but oh well...

My teacher mentioned that there are an infinite number of infinities. I can comprehend that, but which infinity is the number of infinities?

_________________
A budding puzzle designer!

Check out my Shapeways shop!

Top

 Post subject: Re: Cardinality and other mathematical musingsPosted: Sat Aug 10, 2013 8:14 am

Joined: Sun Nov 23, 2008 2:18 am
It is my understanding that Cardinaily only distinguishes two sizes of infinities, namely countable(or as a video on numberphile stated, listable) and uncountable. Yet even within these categories, their seem to be infinities of vastly different sizes.

For example:
The primes are countably infinit, as are the composites, together, these two mutually exclusive sets form the positive integers, also countably infinite, which is itself a ubset of the countably infinite integers. which is in turn a subset of the rational numbers, also countable.

While all of the above listed sets are countable infinities, intuition says their sizes very quite drastically. For example:
-The vast majority of positive integers are composite, if not nearly all as all evens are multiples of two, a third of all odds are multiples of three, roughly a fifth of all number not divisible by 2 or 3 are multiples of 5, etc. This suggests that composites are a much larger set than the primes, yet both are countably infinite.
-Despite both being countably infinite, the positive integers are only about half of the integers(with zero being an integer, but neither positive or negative).
-Primes, Composites, Positive Integers, and Integers all share the property that within any two members, there are finitely many other members of the set. while all are subsets of the countably infinite Rationals, the rationals break this property, with their being infinitely many rationals between even consecutive members of the integers.
-In other words, the Rationals can be divided into a countably infinite number of mutually exclusive subsets all of which are countably infinite, something which cannot be done with the integers.
-I have heard is said that the rationals are dense whereas the other countable infinites mentioned thus far are non-dense(is their a more proper term for htis?).

Continueing on, we have the rationals as a subset of the Algebraic Numbers(which, just off hand, I don't know if they are countable or uncountable), which are in teurn a subset of the reals. We also have the transcentals, which are also a subset of the reals and mutally exclusive to the albegraic numbers. The transcendentals are also a subset of the irrationals(uncountable) and their is an area of intersection between the irrationals and the Albebraic numbers.

If the Algebebraic numbers are uncountable, they are still a "small" subset of the reals as nearly all reals are transcendtal.

Intuition tells me that all uncountable sets should be dense for some segment of their range, but need not be dense everywhere(for example, if you remove the range 0< x < 1 from the reals, you still have an uncountably infinite set, yet there is no member between 0 and 1, so its not dense in the range 0-1), but I don't know enough to confirm this intuition.

I guess my main question is whether their is a branch of mathematics that discusses the comparative sizes of infinities within the two infinite cardinalities?

For the record, my background is limited to Undergrad Computer science stuff, and even then, I didn't du to well in my first attempt at Linear Algebra, Statistics for Engineers or Discrete Mathematics for Computer Scientists.

_________________
Just so you know, I am blind.

I pledge allegiance to the whole of humanity, and to the world in which we live: one people under the heavens, indivisible, with Liberty and Equality for all.

My Shapeways Shop

Top

 Post subject: Re: Cardinality and other mathematical musingsPosted: Sat Aug 10, 2013 8:29 am

Joined: Fri Feb 08, 2008 1:47 am
Location: near Utrecht, Netherlands
Jeffery Mewtamer wrote:
It is my understanding that Cardinaily only distinguishes two sizes of infinities, namely countable(or as a video on numberphile stated, listable) and uncountable. Yet even within these categories, their seem to be infinities of vastly different sizes.

There is more than just that. Even though the real numbers are uncountable there are sets which have a strictly greater cardinality than the real numbers. For instance, the set of all subsets of the set of real numbers.

Jeffery Mewtamer wrote:
Intuition tells me that all uncountable sets should be dense for some segment of their range, but need not be dense everywhere(for example, if you remove the range 0< x < 1 from the reals, you still have an uncountably infinite set, yet there is no member between 0 and 1, so its not dense in the range 0-1), but I don't know enough to confirm this intuition.
The cantor set is uncountable but it is not dense anywhere.

Jeffery Mewtamer wrote:
I guess my main question is whether their is a branch of mathematics that discusses the comparative sizes of infinities within the two infinite cardinalities?
Perhaps measure theory but it doesn't give an answer like "there are half as many positive numbers as there are real ones" since that is arbitrary. Your intuition that there are half as many positive numbers seems to be based off the fact that for every positive number x there's a unique negative number -x, but in the same way I can argue that there are twice as many positive numbers as there are negative ones: for any negative number -x I can list two unique positive numbers, 2x and 2x+1.

_________________
Tom's Shapeways Puzzle Shop - your order from my shop includes free stickers!
Tom's Puzzle Website

Buy my mass produced puzzles at Mefferts:

Top

 Post subject: Re: Cardinality and other mathematical musingsPosted: Sun Aug 11, 2013 11:05 pm

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
bhearn wrote:
I wondered at first why you used "N"
I looked it up on Wikipedia and saw this thing and thought N looked close enough. Granted I've never done anything very formal with this stuff.
bhearn wrote:
Well I don't see any problem here... if the function is discontinuous, then why does it seem odd for F(0) = 0, F(1) = 1, even if the slope of 0 everywhere it's differentiable? That's just a step function. It's not differentiable at the step. Maybe I am not understanding.
Well I'm just remember fuzzy details from a class that was over 20 years ago so I may have some details wrong. But as I recall the class was asked to find a CONTINUOUS function which went from F(0)=0 to F(1)=1 while having slope 0 everywhere its defined. So the One Third Function was sold as being continuous. I wish I could find a web site on this function as I may have left out some details. Either that or the teacher himself was just simply wrong. Not sure which at the moment. So unless anyone else if familiar with the function I'm trying to describe I may just be leading us down the wrong path.
bhearn wrote:
And you continue to repeat this process until all the points are defined. Oh, but that can't happen... e.g., F(1/3) will never be defined.
Off the top of my head I can't recall if the function was built using "< or =" or just "<". If the earlier than F(1/3) = 1/2. If the later then I believe F(1/3) was to be defined by taking a limit as b approached 0 using something like the average of F(1/3-b) and F(1/3+b). But we are getting into very foggy 20 year old memories at this point and its a topic I didn't even fully understand then.
bhearn wrote:
If you find questions like this interesting, I'd highly recommend "Surreal Numbers", by Knuth, and "Inifinity and the Mind", by Rucker, if you haven't already read them.
I think I've read parts of them years ago. Both titles sound familiar. I'll have to track them down. Thanks...

Carl

_________________
-

Top

 Post subject: Re: Cardinality and other mathematical musingsPosted: Sun Aug 11, 2013 11:33 pm

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
rubikcollector123 wrote:
I have no idea if what I am going to ask is related, but oh well...

My teacher mentioned that there are an infinite number of infinities. I can comprehend that, but which infinity is the number of infinities?
Oh I raised this question of my friend years ago. Having seen things like aleph-0, aleph-1, aleph-2, etc. I asked him about the set of all cardinalities. And I thought his reply was via email but it would seem it may have been several email address ago as I can't find it now. My guess was that the cardinalities were countable as a list of them appears to have been started. But as I recall the answer he gave me was much much more complicated then that and I certainly can't do it justice. As I recall he had things which look like polynomials and discussed the difficulty of expressing the cardinalities of VERY VERY large sets. I think he even stated there were cardinalites which can't be expressed and part of the reason for that is there are only a finite number of ways you can string a set of characters together. Most of that conversation was well over my head so I've probably butchered some of it already.

Having just googled the question I have found this:
Quote:
The collection of all cardinals is not a set, it is a proper class. Therefore it does not have a cardinality. Informally speaking, there are SO MANY cardinals that the class of cardinals does not have a "size".
And this is supposed to be a paper which answers that question: (but just looking at it most of its well over my head)
http://math.uga.edu/~pete/settheorypart1.pdf

http://math.stackexchange.com/questions/3069/number-of-infinite-sets-with-different-cardinalities

Carl

_________________
-

Top

 Post subject: Re: Cardinality and other mathematical musingsPosted: Sun Aug 11, 2013 11:41 pm

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
Jeffery Mewtamer wrote:
It is my understanding that Cardinaily only distinguishes two sizes of infinities, namely countable(or as a video on numberphile stated, listable) and uncountable. Yet even within these categories, their seem to be infinities of vastly different sizes.
I don't think you are using the term size correctly. Sure the positive integers are a subset of the integers but these two sets I believe are typically stated to be the SAME size. You can easily create a 1 to 1 mapping between the elements of the two sets which you couldn't do if their sizes were different.
TomZ wrote:
Jeffery Mewtamer wrote:
It is my understanding that Cardinaily only distinguishes two sizes of infinities, namely countable(or as a video on numberphile stated, listable) and uncountable. Yet even within these categories, their seem to be infinities of vastly different sizes.

There is more than just that.
Many many more. More then uncountably many more if the link in my last post is correct.

Having fun yet?
Carl

_________________
-

Top

 Post subject: Re: Cardinality and other mathematical musingsPosted: Mon Aug 12, 2013 4:26 am

Joined: Sat Jan 01, 2011 12:54 pm
Location: Copenhagen, Denmark
I believe the "One Third" function mentioned previously is what's also known as the Cantor Function.

As bhearn points out, it's easy to get a function on the unit interval such that F(0)=0 and F(1)=1 with derivative 0 everywhere the derivative is defined. The surprising thing is that this can be done with a function that is continuous.

\Taus

Top

 Post subject: Re: Cardinality and other mathematical musingsPosted: Tue Aug 13, 2013 1:48 pm

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
Taus wrote:
I believe the "One Third" function mentioned previously is what's also known as the Cantor Function.
Yes, that is it. And having seen that, the name Devil's staircase also sounds familiar so I may I heard it by that name too 20+ years ago.
Taus wrote:
As bhearn points out, it's easy to get a function on the unit interval such that F(0)=0 and F(1)=1 with derivative 0 everywhere the derivative is defined. The surprising thing is that this can be done with a function that is continuous.
Agreed. As I reacall the class where this subject came up also pointed out that there were uncountably many such functions... though this is the only example of a function with this property that I have seen. Though having seen this one it should be hard to create others.

I also like both of the definitions on that page much better then my own. Using either of their definitions its easier to see that the value of F(x) is defined everywhere. To to be honest I wasn't aware there were so many different definitions of continuous. (uniformly continuous, Hölder continuous, absolutely continuous...)

Carl

_________________
-

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 12 posts ]

 All times are UTC - 5 hours

#### Who is online

Users browsing this forum: No registered users and 2 guests

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

Search for:
 Jump to:  Select a forum ------------------ Announcements General Puzzle Topics New Puzzles Puzzle Building and Modding Puzzle Collecting Solving Puzzles Marketplace Non-Twisty Puzzles Site Comments, Suggestions & Questions Content Moderators Off Topic