Joined: 4/20/2005
Posts: 2161
Location: Norrköping, Sweden
Warp wrote:
Is the set of points inside a unit square larger than the set of points on a unit line?
This is not the case if we can fill the unit square by mapping points from the unit line. Let x be a number on the unit line and let [X,Y] be a point inside the unit square. Let r(x) be the rational part of x and i(x) the irrational part of x. Consider the mapping:
[X,Y]=[2*r(x),2*i(x)]. This maps the unit line to a right angled triangle with corners at [0,0],[2,0] and [0,2]. This triangle covers the unit square, and we can fill the entire triangle since both the rational and irrational numbers are dense on [0,1]. Only the rational numbers are filled on the x-axis, and only irrational on the y-axis, but since both these sets are dense, we have filled (more than) the unit square mapping only points from the unit line. This means that the unit square does not have more points than the unit line.
I'm not sure I'm allowed to do what I just did, but it was worth a try!
Is the set of points inside a unit square larger than the set of points on a unit line?
(Before someone instinctively answers "of course", remember that eg. the set of rational numbers is actually exactly as large as the set of integers. Adding a dimension doesn't necessarily increase the size of an infinite set.)
By your phrasing, I think you're asking whether the cardinality of [0,1] x [0,1] is larger than [0,1]. The answer is no. Dimensionality (or more strictly, the cartesian product of two sets) doesn't increase the cardinality of a set. There are some pathological curves in differential geometry that manage to fill the whole plane, and some fractals that induce, as the name suggests, "fractional" dimensions, while fractional cardinality numbers don't exist.
One bijection between R and R2 is to get the decimal representation of x and y in a point (x,y) and map them to something like 0,x1 y1 x2 y2 x3 y3 ...
If you make a consistent choice between choosing 1 or 0,9999999.. you can get only one real number for every two x and y.
In real analysis though, the "size" of a set, depending on the context, can mean its measure, and in this case, you can say a square is larger than a line, in the sense that a line (or any enumerable set of lines) has null measure in R^2. One example of this is that, if the discontinuity points of a function in a domain in R^2 is a line (or more generally, has null measure), the function will still be Riemann integrable in that domain, because the places where discontinuity happens are "too small" or "negligible".
This is not the case if we can fill the unit square by mapping points from the unit line. Let x be a number on the unit line and let [X,Y] be a point inside the unit square. Let r(x) be the rational part of x and i(x) the irrational part of x. Consider the mapping:
[X,Y]=[2*r(x),2*i(x)]. This maps the unit line to a right angled triangle with corners at [0,0],[2,0] and [0,2]. This triangle covers the unit square, and we can fill the entire triangle since both the rational and irrational numbers are dense on [0,1]. Only the rational numbers are filled on the x-axis, and only irrational on the y-axis, but since both these sets are dense, we have filled (more than) the unit square mapping only points from the unit line. This means that the unit square does not have more points than the unit line.
I'm not sure I'm allowed to do what I just did, but it was worth a try!
This is not really my field of expertise, but it sounds to me like you are attempting to enumerate all the vertical coordinates of the square with rational numbers. Since rational numbers are countable, it would mean that the vertical coordinates (which are expressed with reals) would be countable, but that's not possible because the amount of coordinates is uncountable.
p4wn3r wrote:
By your phrasing, I think you're asking whether the cardinality of [0,1] x [0,1] is larger than [0,1]. The answer is no. Dimensionality (or more strictly, the cartesian product of two sets) doesn't increase the cardinality of a set.
I assume from this that the set of points inside a unit cube would also be the same as those on a unit line, and likewise for a 4-dimensional unit hypercube, and so on. Is there any amount of dimensions that would make the set larger?
By your phrasing, I think you're asking whether the cardinality of [0,1] x [0,1] is larger than [0,1]. The answer is no. Dimensionality (or more strictly, the cartesian product of two sets) doesn't increase the cardinality of a set.
I assume from this that the set of points inside a unit cube would also be the same as those on a unit line, and likewise for a 4-dimensional unit hypercube, and so on. Is there any amount of dimensions that would make the set larger?
I made a mistake in my reply. The cartesian product of two sets A x B can have a greater cardinality than A and B, if both their cardinalities are finite. However, if they're infinite, card(A x B) = max {card(A),card(B)}.
So, if you consider that an n-dimensional space is the cartesian product of R n times, you can prove that the cardinality won't change by induction.
If you have an infinite dimensional space, there are two cases: the first one is if the base of your space is countable. This set will have the same cardinality as the set of all sequences of real numbers R^N (N denoting the set of natural numbers). And this set, being the set of all countable subsets of R, has the same cardinality as R.
The other case is when the base is uncountable. The cardinality will be the same as the set of all real functions from R to R (R^R) . Using the same diagonal argument Cantor used to prove R is not enumerable, we can prove that the cardinality of R^R is 2^card(R), bigger than card(R). The generalized continuum hypothesis states that this cardinality is aleph-2, but it's unprovable in the most common axiomatization of mathematics. If you reject these axioms, a lot of things I wrote will no longer hold.
The other case is when the base is uncountable. The cardinality will be the same as the set of all real functions from R to R (R^R) . Using the same diagonal argument Cantor used to prove R is not enumerable, we can prove that the cardinality of R^R is 2^card(R), bigger than card(R). The generalized continuum hypothesis states that this cardinality is aleph-2, but it's unprovable in the most common axiomatization of mathematics. If you reject these axioms, a lot of things I wrote will no longer hold.
Do I understand correctly from what you are saying (and from what I have read at wikipedia about the continuum hypothesis) that whether there exists a one-to-one mapping between the set of reals in the range [0,1] (or, for that matter, the entire set of reals, it doesn't really make a difference AFAIK) and the set of points inside a unit hypercube of uncountably infinite dimensions or not cannot be either proven or disproven with "regular" set theory mathematics (for a definition of "regular" that goes well beyond my understanding of set theory)?
(Wow, that was one big sentence. I tried to split it up, but couldn't figure out a natural way of doing it without it becoming even more contrived...)
The other case is when the base is uncountable. The cardinality will be the same as the set of all real functions from R to R (R^R) . Using the same diagonal argument Cantor used to prove R is not enumerable, we can prove that the cardinality of R^R is 2^card(R), bigger than card(R). The generalized continuum hypothesis states that this cardinality is aleph-2, but it's unprovable in the most common axiomatization of mathematics. If you reject these axioms, a lot of things I wrote will no longer hold.
Do I understand correctly from what you are saying (and from what I have read at wikipedia about the continuum hypothesis) that whether there exists a one-to-one mapping between the set of reals in the range [0,1] (or, for that matter, the entire set of reals, it doesn't really make a difference AFAIK) and the set of points inside a unit hypercube of uncountably infinite dimensions or not cannot be either proven or disproven with "regular" set theory mathematics (for a definition of "regular" that goes well beyond my understanding of set theory)?
(Wow, that was one big sentence. I tried to split it up, but couldn't figure out a natural way of doing it without it becoming even more contrived...)
No, that's not what I was talking about. Perhaps my explanation was too fast.
Cardinal numbers are defined like this. Aleph-0 is the cardinality of N. A set has cardinality aleph-k if there's no bijection between it and any other set with cardinality aleph-i, i<k.
We can prove that the cardinality of R is 2^aleph-0 . The continuum hypothesis says that 2^aleph-0 = aleph-1 , implying that no set can have a cardinality between the natural numbers and the real numbers. With Zermelo-Fraenkel + axiom of choice set theory (the most common set theory), we can assume this proposition is true or false, and no contradictions will arise in the theory both ways. Thus, it's unprovable.
In the case of R^R, it's certainly true that its cardinality is larger than R (2^aleph-1 is larger than aleph-1), the (generalized) continuum hypothesis will only say if there's a set whose cardinality is between them or not.
Btw, thinking about it, how could we have an uncountably infinite amount of dimensions? Dimensionality, at least in cartesian coordinates, seems to be a purely integral concept because each dimension is represented by its own number, and there can obviously be only an integral amount of numbers: You can have one number (representing coordinates in one-dimensional space), two numbers (representing coordinates in two-dimensional space) and so on. By this logic you can only have countably infinite dimensions (ie. the set of natural numbers). How could one even pose the possibility of having uncountably infinite dimensions? It's not like we could have a rational, much less an irrational amount of dimensions. (What would it even mean to have a "pi-dimensional cube"?)
On a different note: Thinking about the question of "is the set of reals in the range [0,1] the same size as the set of reals in the range [0,2]?", the answer is trivial: Yes, because we can formulate a simple one-to-one mapping between them: Just take a number in the former set, multiply it by 2, and you have unambiguously mapped each value in the former with the latter. Likewise for any set of reals in the range [0,x]: Simply multiply by x and you have a simple one-to-one mapping.
However, what happens if x is infinite? How do you create a one-to-one mapping then? It's not like you can multiply by infinity. (This is, basically, the case with the unit square: We have an uncountably infinite amount of different one-dimensional ranges of size 1, and we have to come up with a one-to-one mapping between the reals [0,1] and the points inside the unit square.)
That's the hard part to understand.
(If that became clear, then it would be trivial to understand why the same applies to a cube, a hypercube, and a cube in any amount of dimensions, because each is just an infinite expansion of [0,1] ranges.)
To define the dimension of a space, you need to determine a base. A base is a set that, for any element in your space, you can write it uniquely as a linear combination of the base elements. The space of all polynomials of degree 3, for example, has dimension 4, because:
P(t) = a + b t + c t2 + d t3
This is a linear combination of the base {1, t, t2, t3}, it has four elements, so dimension four. However, if you consider the space of all polynomials, its base is {1, t, t2, t3... }, because for spaces that aren't finitely generated, the definition of a base is a little different. A set B is a base of a space V iff B is linearly independent and every element in V can be written as a linear combination of a subset of B. This is the case for the polynomials of any degree, its base is infinite and it has infinite dimensions. If the set also happens to be uncountable, then you have uncountably many dimensions, but this case is not very useful in practice.
We have a little trouble to think of a bijection from [0,1] to [0,infinity[ because we normally tend to think of continuous functions, and such mapping doesn't exist, because the image of a continuous function on a closed and bounded interval is always a closed and bounded interval too.
Consider this:
S = {1 , 1/2, 1/3, ... }
f(x) = {0, if x=0 ; -ln (1/(1/x + 1)), if x is in S ; -ln x, if x>0 is not in S}
This function is basically -ln x with a "shift" along the enumerable set {0,1,1/2,1/3 ... } to fix the problem of the point 0, where ln is not defined. This shift maps 0 to -ln 1 , 1/1 to - ln 1/2 , 1/2 to -ln 1/3 and so on.
However, what happens if x is infinite? How do you create a one-to-one mapping then?
As you noted, it's not going to work by "evenly stretching" the interval. You might intuitively expect that you need an even mapping to preserve densitiy, but since both sets are infinitely dense, that's not required.
A simple bijection from ]0;1] to [1;\infty[ is given by f(x) = 1/x. Add a few shift tricks (similar to p4wn3r's) to get a bijection from [0;1] to [0;\infty[.
For easy to understand mappings from the unit line to the unit square, see Space filling curves. These are pretty useful in databases when working with multi-dimensional data. For example, you can map your data to the unit line and insert them into a B+-tree - when choosing a good curve, this will preserve most of your data locality. Area queries can thus be answered efficiently by answering a small number of range queries.
For a specific example, tan((pi/2)*x) maps [0,1) to [0,Inf). Since tan is an invertible function on this domain, that means [0,1) and [0,Inf) have equal cardinality.
Here's a fun question. Prove that there is no infinite set smaller than the integers.
Here's a fun question. Prove that there is no infinite set smaller than the integers.
The proof follows immediately from the axiom of choice. Let S be an infinite set, according to the axiom of choice, I can select an element from S. Call it x1. Since S is infinite, S - {x1} is infinite too, and again I can pick an x2 from it . Through analogous recursive reasoning, I can pick an xn from S - {x1,x2,...,x_n-1}.
I have then defined an injection from N to S, thus card(S)>=card(N), which proves the statement, and, I'm not really a fan of this part of mathematics and don't find it fun. =P
Warp wrote:
(What would it even mean to have a "pi-dimensional cube"?)
I missed this part before. I don't remember very well non-integer dimensions, they're defined differently from integer ones. I think it had something to do with balls (sets of all elements x such that d(x,a)<r for a given element a), and how fast the amount of balls needed to cover the figure diverges as r gets smaller. I may be saying stupid stuff though...
What I do remember is that there isn't only one formal definition and they're adopted depending on the mathematical interest.
Joined: 4/20/2005
Posts: 2161
Location: Norrköping, Sweden
When it comes to non-integer dimensions, you enter the field of Hausdorff dimension and fractal dimensions. An example of a set of non-integer dimension is the cantor set C - in terms of cardinality, C is as large as R, but in terms of length, C is just a single point. Therefor the dimension of C falls between 0 and 1, in this case 0.631. So I guess a pi-dimensional cube would be an object with 3-dimensional length (where in this case "length" is defined by some metric) but with some cardinality-properties of a 4-dimensional object.
When it comes to non-integer dimensions, you enter the field of Hausdorff dimension and fractal dimensions. An example of a set of non-integer dimension is the cantor set C - in terms of cardinality, C is as large as R, but in terms of length, C is just a single point. Therefor the dimension of C falls between 0 and 1, in this case 0.631. So I guess a pi-dimensional cube would be an object with 3-dimensional length (where in this case "length" is defined by some metric) but with some cardinality-properties of a 4-dimensional object.
Interesting...
With the idea of fractal dimensions and the Cantor set, I could create a set with pi-dimension. First, let's see why the Cantor set has that dimension. Let's try to find the minimum amount of balls and their "radius" to cover the figure at each iteration. The only ball in R is an interval, and it needs to have the length of the sub-intervals f the Cantor set at the n-th iteration. We have:
Now, its dimension will be given by , which matches the number.
It follows from intuition that since pi>3, we can't construct a set with pi dimension starting from a 3-dimensional space, so we have to go to the fourth dimension, where geometric interpretations will no longer help us. Let S^4 denote S x S x S x S. Let's construct a more general Cantor set, which partitions the interval in more general quantities and extends it to the fourth dimension by cartesian products. The first iteration looks like this:
I'll consider the balls to cover this interval to be boxes, the same result would be achieved with the Euclidean metric, but there would be more calculations. This way, we can get:
We want to pick a t so that the dimension of this set is pi, in order to do this, we evaluate its dimension:
So, by constructing this set using , it'll have a dimension of pi.
arflech wrote:
Is the consistency of the definitions still an open mathematical question?
Even arithmetic has trouble being totally reduced to logic, let alone the more advanced concepts. Gödel's incompleteness theorems struck a heavy blow to the program of finding a consistent theory for arithmetic. There's still hope to do it though, by proving its consistency with a theory that doesn't satisfy the conditions of Gödel's theorems, so it's still open.
With the idea of fractal dimensions and the Cantor set, I could create a set with pi-dimension.
Even if a non-integral dimension can be defined mathematically, it still leaves open the question if a non-integral-dimensional unit cube is possible, given how a cube can be defined. One can specify a definition of "unit cube" such that it will define any such shape in any amount of dimensions from 2 upwards. (In 2 dimensions it would be a unit square, in 2 dimensions a unit cube, in 4 dimensions a unit hypercube, and so on.) The definition would be a combination of the shape having 1 unit of "n-dimensional volume", 2*n faces (in parallel pairs which are orthogonal to all the others), right angles, etc.
However, could a definition of "unit cube" be given that gives a sensible meaning to one in non-integral dimensions?
I don't think so, because there is no sensible generalization of "vector space" or "orthonormal basis" to dimensions other than whole numbers; more generally, IMO a set of non-integral dimension cannot even be a manifold.
Joined: 11/30/2008
Posts: 650
Location: a little city in the middle of nowhere
Well, to find the highest common factor of two numbers, you just repeatedly subtract the smaller from the larger. (the Euclidean algorithm). If the HCF of 21n+4 and 14n+3 is one, then the fraction is irreducible.
Define f(a,b) as the HCF of a and b.
f(21n + 4, 14n + 3)
= f(7n + 1 , 14n + 3)
= f(7n + 1 , 7n + 2)
= f(7n + 1 , 1)
and the HCF of any number and 1 is 1, therefore the fraction is irreducible.
Yeah, that's totally right. I wish I could solve the present IMO problems as easily as I can solve the archaic ones... Things have come a long way.
Another way is to use Bézout's identity.
Since -2*(21n+4) + 3(14n + 3) = 1, therefore, 1 is the gcd of the two numbers, so the fraction is irreducible.
Completely equivalent, but only uses one line =P. Anyone in the mood for harder number theory problems?
1) Show that, if p is a prime larger than 3, then p^2 - 1 is divisible by 24.
2) p4wn3r writes 3^2011 consecutive 7's in a blackboard. Is this number divisible by 3^2011?
3) The number 1/89 is written in decimal form. Determine the length of the period of the digits.
4) Let S = 1! * 1 + 2! * 11 + ... + k! * (k^2 + 3k + 1) + ... + 200! * (200^2 + 3*200 + 1)
Find the remainder of S when divided by 2004.
5) Prove that 1^2011 + 2^2011 + 3^2011 + ... + 2011^2011 is divisible by 1 + 2 + 3 + ... + 2011
Good luck!
Joined: 11/30/2008
Posts: 650
Location: a little city in the middle of nowhere
1) p is a prime greater than 4, which means it's odd. (of the form 2n + 1 for a natural n)
p^2 - 1
=(2n + 1)^2 -1
=4(n)(n+1)
(n)(n+1) is divisible by 2, since they are consecutive, so 4(n)(n+1) is divisible by 8, and so is p^2 - 1.
p is greater than 3, so it is not divisible by 3. It is either of the form 3n + 1, or 3n + 2 for a natural n. If p = 3n+1, then p^2 - 1 = 3(3n^2 + 2n), which is divisible by 3. If p = 3n + 2, then p^2 - 1 = 3(3n^2 + 4n + 1), which is also divisible by 3.
since p^2 - 1 is divisible by 8 and 3, and they are both coprime, p^2 - 1 is divisible by 24.
2)Yes we can. firstly, divide the number by 7 to get rid of it. You now have 3^2011 1's written on an enourmous blackboard. 111 is divisible by 3, but not by 9 (add the digits together). 111000 is also divisible by 3. 111000000 is also divisible by 3. basically we split the number into three digit chunks, and divide each one by 3.
we get a number m = 111/3 which is not divisible by 3, since 111 is not divisible by 9. After we divide the number by 3, the remaining number is m*1 + m*1000 + m*1000000 ect. since m is not divisible by 3, we can safely divide by m to get 100100100...001001001. but now 1001001 is divisible by 3 and not by 9, and 1001001000000000 is divisible by 3 and not by 9. we now divide by 3 and m again, but this time, m is 1001001/3. basically, every time we divide by 3, we also divide the number of 1's in the number by 3 as well. We start off with 3^2011 1's and we need to divide by 3 2011 times. eventually we get to a point where we have 3^1 ones and we need to divide by 3 once. basically the number has exactly that many factors of 3.
3) 45. When 999...999/89 is a whole number, then the period of the digits is the number of 9's. if you have n 9's and the remainder is r, then the remainder for n+1 9's will be 10r + 9 mod 89. It just so happens that the remainder is 0 when you're on the 45th digit.
I think you should revise your calculations for 3), because the reasoning is correct, but the answer should be 44.
We basically want to find the smallest m that satisfies 10^m = 1 (mod 89). By Fermat's little theorem, since 89 is a prime, we have a^(p-1) = 1 (mod p) -> 10^88 = 1 (mod 89). So, the smallest integer is a divisor of 88 (1,2,4,8,11,22,44,88).
10 = 10 mod 89
10^2 = 100 = 11 mod 89
10^4 = 11^2 = 121 = 32 mod 89
10^8 = 32^2 = 1024 = 44 mod 89
None of these worked.
10^11 = 10^8 * 10^2 * 10 = 44 * 11 * 10 = 55 mod 89
10^22 = 55^2 = 3025 = 88 = -1 mod 89
10^44 = (-1)^2 = 1 mod 89 <- Hit!
So, 10^44 - 1 is divisible by 89, and is a number with 44 nines.
Any ideas for 4) and 5)?
Joined: 11/30/2008
Posts: 650
Location: a little city in the middle of nowhere
My knowledge of math ends at high school level, but you mentioned Fermat's little theorem which gives me an idea for 5)
2011 is prime, and fermat's little theorem states that a^p = a mod p. I'm thinking this is because there are only p values that a^n can be mod p, and a^n will cycle through them all as long as p is prime.
basically if 1^2011 +2^2011 + 3^2011 ... = 1+2+3... mod 2011 and 1+2+3... 2010+2011 = 2011*2012/2 mod 2011 and since 2011 = 0 mod 2011, then 1^2011 + 2^2011 + ... + 2010^2011 + 2011^2011 = 0 mod 2011.
now we know it's divisible by 2011, but we need the number to be divisible by 2011*2012/2 which is 2011*1006, so we also need the number to be divisible by 1006, or 2*503. lucky for us we can use fermat's little theorem again, but in the form a^p-1 = 1 mod p, because 2011 = 502 mod 503. so now we have 1^502 + 2^502 + ... 501^502 + 502^502 + 0^502 + 1^502 + ... + 501^502 + 502^502 mod 503. which equals 502*4 mod 503. this is where I get something wrong, because 502*4 mod 503 = 499, not 0.
Now, its dimension will be given by 
, which matches the number.
It follows from intuition that since pi>3, we can't construct a set with pi dimension starting from a 3-dimensional space, so we have to go to the fourth dimension, where geometric interpretations will no longer help us. Let S^4 denote S x S x S x S. Let's construct a more general Cantor set, which partitions the interval in more general quantities and extends it to the fourth dimension by cartesian products. The first iteration looks like this:
I'll consider the balls to cover this interval to be boxes, the same result would be achieved with the Euclidean metric, but there would be more calculations. This way, we can get:
We want to pick a t so that the dimension of this set is pi, in order to do this, we evaluate its dimension:
So, by constructing this set using 
, it'll have a dimension of pi.
