Cantor Confusion
in [Math]
|
Prev: Pi berechnen: Ramanujan oder BBP
Next: Group Theory
From: David Marcus on 12 Jan 2007 20:12 Andy Smith wrote: > > > > Here is a question for you: Suppose you have a > > countably infinite > > ordered set X. So there is a bijection f:N -> X. Does > > it have to be true > > that m < n implies that f(m) < f(n)? > > At the risk of appearing an idiot, I would say yes. > > Because X is ordered such that x(n) > x(m) for all n > m. > > Am I missing something? Yes, you are missing something. But, I thought you were, so I asked the question. Now, I see why you are confused. Virgil gave an example, but let me give a simpler example: Consider the set X = {5,27,98}. I trust you will agree that X has three elements. However, mathematicians like to do weird things, so we can make the following definition: A set Y has cardinality n if there is a bijection between Y and {0,1,...,n-1}. We can now prove that X = {5,27,98} has cardinality 3 by exhibiting a bijection f:{0,1,2} -> X. Here is a suitable f: f(0) = 27 f(1) = 5 f(2) = 98 Notice that f(0) is not less than f(1). A mathematician would say that there is no requirement that a bijection preserves order. A bijection is simply a map that is one-to-one and onto. An order isomorphism is a bijection that also preserves order. The definition of "countably infinite" only requires a bijection, not an order isomorphism. So, countably infinite sets can have order types that are very different from the order type of the natural numbers. -- David Marcus
From: cbrown on 12 Jan 2007 20:28 Andy Smith wrote: > > > > Here is a question for you: Suppose you have a > > countably infinite > > ordered set X. So there is a bijection f:N -> X. Does > > it have to be true > > that m < n implies that f(m) < f(n)? > > > At the risk of appearing an idiot, I would say yes. > > Because X is ordered such that x(n) > x(m) for all n > m. > > Am I missing something? Two things: (Whoops! Actually three: it is /good/ that you snipped most of the irrelevant parts of the post you are responding to, and it is /good/ that you did not top post. However, it is useful if you include the name of the poster you are responding to - I /think/ it's David Marcus, but I'm not sure). First, there is no "x(n)"; I presume you mean f(n), which is a member of X. Secondly, when he said "X is a countably infinite ordered set", he meant that X /already has/ an ordering. For example suppose X is the set of integers. Surely if x and y are two integers, "x < y" has a very obvious meaning! Now we introduce a bijective function f: N -> X. (N being the naturals; {0, 1, 2, ...}). Suppose f(0) = z. Since f is a bijection, and z - 1 is an integer in X, there is some natural n such that f(n) = z - 1. But then z - 1 < z (as integers!), which is to say f(n) < f(0) (as integers!), even though it is not the case that n < 0 (as naturals!). Some of your confusion probably arises from the fact that "<" is being used "inconsistently" here: it is assumed by (most) mathematicians that the reader understands that "<" is a /particular/ relation on a /particular/ set. >From a physics standpoint, you are probably more used to understanding "<" as a /particular/ definite relation defined only for the real numbers; and that when "<" is restricted to, say, the naturals or the integers or the rationals, this is always taken to be its restriction if we /think/ of these sets /as subsets of the reals/. But in mathematics, we tend to work with mathematical objects which are /not/ neccessarily "subsets of the reals"; but for which it is still sensible to say "a < b, or a=b, or a > b". Sometimes it is still possible to "map" those objects to a subset of the reals, and then use the ordering of the reals to order those objects; but sometimes it is /not/ possible to do this. For example, there might not be "enough" reals; or not "enough" disjoint intervals of the reals. And so one becomes familiar with many different "flavors" of total order: the ordering of the naturals, integers, rationals, and reals being most familiar at the beginning; but later one meets all sorts of other types of ordering. And, confusingly perhaps, we signify them using one symbol: "<"; assuming that the reader understands that we mean a specific ordering on a specific set. Cheers - Chas
From: cbrown on 12 Jan 2007 20:45 Michael Press wrote: > In article > <1168516308.352303.113260(a)k58g2000hse.googlegroups.com> > , > cbrown(a)cbrownsystems.com wrote: > > > Now, "your" naturals may be different than "my" naturals because "my" > > naturals obey certain additional idiosyncratic (from "your", sadly, > > limited viewpoint) properties. E.g., that primes of the form 6*n + 1 > > are red, and primes of the form 6*n - 1 are green; and that therefore I > > have a theorem that no yellow primes exist. > > Hey! When did they repaint 2? > 2 is, and always will be, blue. It is, after all, the loneliest number since the number one! (Not sure what's up with 3... ecru, maybe?) Cheers - chas
From: David Marcus on 12 Jan 2007 22:16 cbrown(a)cbrownsystems.com wrote: > Andy Smith wrote: > > > > > > Here is a question for you: Suppose you have a > > > countably infinite > > > ordered set X. So there is a bijection f:N -> X. Does > > > it have to be true > > > that m < n implies that f(m) < f(n)? > > > > > At the risk of appearing an idiot, I would say yes. > > > > Because X is ordered such that x(n) > x(m) for all n > m. > > > > Am I missing something? > > Two things: > > (Whoops! Actually three: it is /good/ that you snipped most of the > irrelevant parts of the post you are responding to, and it is /good/ > that you did not top post. However, it is useful if you include the > name of the poster you are responding to - I /think/ it's David Marcus, > but I'm not sure). Yes, it's me. -- David Marcus
From: Dik T. Winter on 12 Jan 2007 22:20
In article <11087446.1168647563782.JavaMail.jakarta(a)nitrogen.mathforum.org> Andy Smith <andy(a)phoenixsystems.co.uk> writes: > > Here is a question for you: Suppose you have a > > countably infinite > > ordered set X. So there is a bijection f:N -> X. Does > > it have to be true > > that m < n implies that f(m) < f(n)? > > At the risk of appearing an idiot, I would say yes. > Because X is ordered such that x(n) > x(m) for all n > m. > Am I missing something? A few things. A bijection is not necessarily order preserving. One of the most beautiful bijections between the natural numbers and the positive rational numbers was shown quite some time ago by David R. Tribble. It states: S(1) = 1 S(2n) = S(n) + 1 S(2n + 1) = 1/S(2n) He also gives the inverse function, but that is a bit complicated. But whatever, the mapping from naturals to rationals starts with: 1, 2, 1/2, 3, 1/3, 3/2, 2/3, 4, ... And (to make Han de Bruijn happy) he found it based on Stern-Brocot sequences. Also it is closely tied to continued fractions: > But see: given a continued fraction > [a0, a1, ..., an+1] > (note the +1 in the last term; it can never be 0), we translate to: > 2^a0.(1 + 2^a1.(1 + ... (1 + 2^an)...) which maps positions of bits in the natural numbers to values in the coefficients of the continued fractions. And that is easily invertible. -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/ |