Cantor's diagonal argument

  • Thread starter ahristov
  • Start date
  • #26
CRGreathouse
Science Advisor
Homework Helper
2,820
0
I don't quite follow this. By -1/9 I take it you are denoting the number that could also be represented as the recurring decimal -0.1111 ... But how can that be if the latter denotes a real number while ...111 doesn't denote anything at all in our usual number systems.
First, there's no reason that two different strings can't represent the same number. Certainly 3.999... and 4.000... are the same real number.

But in the 10-adics, there's no such thing as a decimal point or anything 'to the right' of it. Think about it this way:

....111 x 9 = ...999.
...999 + 1 = ...000.

So 0, minus 1, divided by 9, gives ...111 in the 10-adics.
 
  • #27
283
3
What about in the context of set theory. Could [tex]\infty[/tex] mean the size of the set of integers (= aleph-0)? I can see from previous discussion that it could not be an element of that set.
What you mean is cardinality. It isnt really a size of a set (by the way a set does not have to be one of integers), I would say its more closer to the number of elements in a set, but I dont like this wording either (I dont really have a satisfactory definition :shy:).

Aleph-null is the first cardinal, which is used to describe the set of natural numbers. Any non-finite set that you can inject into the naturals will also have cardinality aleph-null. However you cant do this with the real numbers which is why they have aleph-one cardinality. This you prove by using cantors diagonal argument via a proof by contradiction. Also it is worth noting that [tex] 2^{\aleph_0}=\aleph_1 [/tex] (I think you need the continuum hypothesis for this). Interestingly it is the transcendental numbers (i.e numbers that aren't a root of a polynomial with rational coefficients) like pi and e.

Sorry for the long post, hope this helps.
 
  • #28
6
0
But in the 10-adics, there's no such thing as a decimal point or anything 'to the right' of it.
Are you sure about that? The entry in Wikipedia (!) on p-adics (http://en.wikipedia.org/wiki/P-adic_number) indicates otherwise (see I've been doing my homework :wink:). It seems to me you are referring to 10-adic integers.
 
  • #29
6
0
What you mean is cardinality.
Well yes that is what I meant by size.

Aleph-null is the first cardinal, which is used to describe the set of natural numbers.
Should that be the first infinite cardinal? Surely finite sets also have cardinality, so the first cardinal would be 0, being the cardinality of the empty set.

Sorry for the long post, hope this helps.
Yes it all helps, and I appreciate all of the responses.
I have to do some work now :grumpy: so no more posts today.
 
  • #30
283
3
Should that be the first infinite cardinal? Surely finite sets also have cardinality, so the first cardinal would be 0, being the cardinality of the empty set.
Yeah true I blame it on the time (Im tired) :tongue2:

Yes it all helps, and I appreciate all of the responses.
I have to do some work now :grumpy: so no more posts today.
Well thats why I am browsing these forums, to not do work and not feel completely bad about it. I prey to God my supervisor is not on these forums.:rolleyes:
 
  • #31
CRGreathouse
Science Advisor
Homework Helper
2,820
0
Any non-finite set that you can inject into the naturals will also have cardinality aleph-null. However you cant do this with the real numbers which is why they have aleph-one cardinality.
Beth-one cardinality, not aleph-1. Unless you have the CH all you can say is that the reals have at least aleph-one cardinality.

Are you sure about that? The entry in Wikipedia (!) on p-adics (http://en.wikipedia.org/wiki/P-adic_number) indicates otherwise (see I've been doing my homework :wink:). It seems to me you are referring to 10-adic integers.
I've never read that article, but yes I'm talking about the 10-adic integers. I imagine that in both ...111 = -1/9, though.
 
  • #32
HallsofIvy
Science Advisor
Homework Helper
41,833
956
What you mean is cardinality. It isnt really a size of a set (by the way a set does not have to be one of integers), I would say its more closer to the number of elements in a set, but I dont like this wording either (I dont really have a satisfactory definition :shy:).

Aleph-null is the first cardinal, which is used to describe the set of natural numbers. Any non-finite set that you can inject into the naturals will also have cardinality aleph-null. However you cant do this with the real numbers which is why they have aleph-one cardinality. This you prove by using cantors diagonal argument via a proof by contradiction. Also it is worth noting that [tex] 2^{\aleph_0}=\aleph_1 [/tex] (I think you need the continuum hypothesis for this). Interestingly it is the transcendental numbers (i.e numbers that aren't a root of a polynomial with rational coefficients) like pi and e.

Sorry for the long post, hope this helps.
No, you don't need the continuum hypothesis to prove that [tex]2^{\aleph_0}= \aleph_1[/tex]. You need the continuum hypothesis to prove that [tex]2^{\aleph_0}= \aleph_1= c[/itex] where c is the cardinality of the real numbers.

But what does "it" in "Interestingly it is the transcendental numbers (i.e numbers that aren't a root of a polynomial with rational coefficients) like pi and e" refer to? Not, presumably [itex]\aleph_1= c[/itex](assuming continuum hypothesis) because that includes all real numbers, not just transcendental numbers.
 
  • #33
CRGreathouse
Science Advisor
Homework Helper
2,820
0
No, you don't need the continuum hypothesis to prove that [tex]2^{\aleph_0}= \aleph_1[/tex]. You need the continuum hypothesis to prove that [tex]2^{\aleph_0}= \aleph_1= c[/itex] where c is the cardinality of the real numbers.
I differ. [tex]2^{\aleph_0}= \mathfrak{c}[/tex] because there's a bijection from an infinite bitstring to the reals, but getting [tex]2^{\aleph_0}=\aleph_1[/tex] (or [tex]\mathfrak{c}=\aleph_1[/tex] which is the same) requires CH.
 
  • #34
283
3
No, you don't need the continuum hypothesis to prove that [tex]2^{\aleph_0}= \aleph_1[/tex]. You need the continuum hypothesis to prove that [tex]2^{\aleph_0}= \aleph_1= c[/itex] where c is the cardinality of the real numbers.
I am sorry but you do need CH to prove that identity. That is what the CH exactly states that [tex]2^{\aleph_{\alpha}}= \aleph_{\alpha +1}[/tex].
 
  • #35
CRGreathouse
Science Advisor
Homework Helper
2,820
0
That is what the CH exactly states that [tex]2^{\aleph_{\alpha}}= \aleph_{\alpha +1}[/tex].
More pedantry: that's the GCH. The CH says this only for [itex]\alpha=0.[/itex]
 
  • #36
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
I don't quite follow this. By -1/9 I take it you are denoting the number that could also be represented as the recurring decimal -0.1111 ...
No, I am not. As I said, - refers to additive inverse, and / refers to multiplication by the multiplicative inverse.

The additive inverse of 1 is ...999. (Because ...999 + 1 = 0)
The multiplicative inverse of 9 is ....8889. (Because ...8889 * 9 = 1)
Finally, ...999 * ...889 = ...111.

As I had said, the numbers in this number system are the left-infinite strings of decimal digits. -0.111... doesn't denote a number.


I'm also wondering what number the symbol oo (infinity) represents (if any). What does it mean when we say 'as x approaches oo' ?
The simplest is to define the phrase "The limit of ____ as __ approaches [itex]\infty[/itex]" as a whole; the individual symbols and words aren't given any meaning. This is something you'd probably see in an elementary calculus book.

A slightly more sophisticated treatment would define a new number system (such as the extended real numbers or the extended natural numbers) that contains an element called [itex]+\infty[/itex], and then you can just use the ordinary definition of the phrase "The limit of _____ as __ approaches __".
 
  • #37
6
0
No, I am not. As I said, - refers to additive inverse, and / refers to multiplication by the multiplicative inverse....
Yes, I see this now.
The simplest is to define the phrase "The limit of ____ as __ approaches [itex]\infty[/itex]" as a whole; ...
I guess I was trying to find the distinction in meaning between the symbols [tex]\infty[/tex] and [tex]\aleph_0[/tex]. Would I be right in thinking that while [tex]\aleph_0[/tex] is the cardinality of the set of integers (amongst others), [tex]\infty[/tex] is (potentially at least) an arbitrarily large member of that set? Is there any sensible way of comparing [tex]\aleph_0[/tex] and [tex]\infty[/tex]? After all the cardinality of {1, 2, 3} is also a member of the set.
 
Last edited:
  • #38
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
Yes, I see this now.

I guess I was trying to find the distinction in meaning between the symbols [tex]\infty[/tex] and [tex]\aleph_0[/tex]. Would I be right in thinking that while [tex]\aleph_0[/tex] is the cardinality of the set of integers (amongst others),
Essentially yes -- that is the most common intended meaning for that symbol.

[tex]\infty[/tex] is (potentially at least) an arbitrarily large member of that set?
No. Scratch that -- emphatically no. Can you even define what you mean by an "arbitrarily large member of a set"?

Again, it's just another symbol. But unlike [itex]\aleph[/itex], there are actually several different mathematical structures that make use of the symbol [itex]\infty[/itex] to denote an element. The most common structures you'd encounter are the projective real numbers and the extended real numbers (Look them up!) (In the latter, [itex]\infty[/itex] is really just shorthand for [itex]+\infty[/itex]).

Is there any sensible way of comparing [tex]\aleph_0[/tex] and [tex]\infty[/tex]? After all the cardinality of {1, 2, 3} is also a member of the set.
No and yes. The most common uses of those symbols lie in different structures, without any "default" conventional way to convert between them. But that said, it is occasionally useful to observe the fact that the closed interval [itex][0, \aleph_0][/itex] of cardinal numbers and the interval [itex][0, +\infty][/itex] of extended natural numbers are isomorphic as ordered sets. (Equivalently, as topological spaces, when given the order topology)
 
  • #39
350
0
Hoping I may be permitted to make a belated contribution here.

Summarising the key points from some of the other posts:
The key to the problem is that the new 'number' generated by the diagonal argument will have an infinite number of non-zero digits resulting from the infinite number of leading zeros in the original numbers. Such a number is not an integer since, although the set of integers has an infinite number of members, each individual member is finite and must have a finite number of non-zero digits.
i was actually having a ton of trouble figuring out what everyone was saying until i read this post. thanks alot!
 

Related Threads on Cantor's diagonal argument

  • Last Post
2
Replies
49
Views
9K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
1
Views
1K
Replies
43
Views
1K
Replies
55
Views
1K
  • Last Post
3
Replies
62
Views
5K
  • Last Post
Replies
17
Views
858
Top