| Author |
Message
|
| talanum1 |
 Posted: Fri May 09, 2008 7:51 am Post subject: Cardinality |
 |
|
Forum Freshman
Joined: 28 Jul 2007
Posts: 60
Location: South Africa
|
Does anyone know what the cardinality of the primes is equal to?
What about the density of primes in the Natural numbers?
_________________
Found cross product of two vectors in >3D. |
|
| Back to top |
|
 |
| river_rat |
| Posted: Fri May 09, 2008 8:06 am Post subject: |
|
|
Forum Ph.D.
Joined: 01 Jun 2006
Posts: 1002
Location: South Africa
|
Cardinality = Aleph0
Density = Prime Number Theorem
_________________
As is often the case with technical subjects we are presented with an unfortunate choice: an explanation that is accurate but incomprehensible, or comprehensible but wrong. |
|
| Back to top |
|
|
| JaneBennet |
| Posted: Fri May 09, 2008 8:54 am Post subject: |
|
|
Forum Junior
Joined: 06 Apr 2008
Posts: 257
Location: UK
|
Any infinite subset of the integers has cardinality ℵ0. This applies to the set prime numbers because – as Euclid proved a long time ago – there are infinitely many primes.
You can look up the prime-number theorem on Wikipedia. 
_________________
“A problem worthy of attack
Proves its worth by fighting back.” – Piet Hein
Why can’t a bull see red – literally can’t? Did You Know? |
|
| Back to top |
|
|
| thyristor |
| Posted: Sat May 10, 2008 11:55 am Post subject: |
|
|
Forum Freshman
Joined: 11 Feb 2008
Posts: 66
Location: Sweden
|
What do you mean? Aleph0 is the cardinality of the natural numbers and since these are many more than the prime numbers the cardinality of the prime numbers can't be Aleph0!
_________________
373 13213-mbm-13213 373 |
|
| Back to top |
|
|
| JaneBennet |
| Posted: Sat May 10, 2008 12:03 pm Post subject: |
|
|
Forum Junior
Joined: 06 Apr 2008
Posts: 257
Location: UK
|
| thyristor wrote: |
| What do you mean? Aleph0 is the cardinality of the natural numbers and since these are many more than the prime numbers the cardinality of the prime numbers can't be Aleph0! |
No, there are not many more natural numbers than prime numbers; there are exactly as many natural numbers as there are prime numbers. We are dealing with infinite sets here. It is possible for a proper subset of an infinite set to have the same cardinality as the set itself.
_________________
“A problem worthy of attack
Proves its worth by fighting back.” – Piet Hein
Why can’t a bull see red – literally can’t? Did You Know? |
|
| Back to top |
|
|
| serpicojr |
| Posted: Sat May 10, 2008 6:59 pm Post subject: |
|
|
Forum Ph.D.
Joined: 17 Jul 2007
Posts: 871
Location: JRZ
|
| We know there are infinitely many prime numbers. We can put them in a list, in increasing order, and this list has no end. It has a first member, 2, a second member, 3, and for any positive integer n, it has an n-th member, which is a prime number around n ln n. (If there were not an nth prime for some positive integer n, then there would only be finitely many primes.) You can thus put the prime numbers into a one-to-one correspondence with the positive integers, whence they have the same cardinality. |
|
| Back to top |
|
|
| river_rat |
| Posted: Sun May 11, 2008 9:38 am Post subject: |
|
|
Forum Ph.D.
Joined: 01 Jun 2006
Posts: 1002
Location: South Africa
|
Yep, the definition of an infinite set is actually one which has a subset of the same cardinality as itself (Exercise, prove the naturals are infinite )
_________________
As is often the case with technical subjects we are presented with an unfortunate choice: an explanation that is accurate but incomprehensible, or comprehensible but wrong. |
|
| Back to top |
|
|
| thyristor |
| Posted: Sun May 11, 2008 1:00 pm Post subject: |
|
|
Forum Freshman
Joined: 11 Feb 2008
Posts: 66
Location: Sweden
|
Well, the naturals are as a consequence of Peano's axioms infinite. They say that by adding one to a natural number you always get a new one to which you can add 1 and so forth.
_________________
373 13213-mbm-13213 373 |
|
| Back to top |
|
|
| river_rat |
| Posted: Sun May 11, 2008 10:00 pm Post subject: |
|
|
Forum Ph.D.
Joined: 01 Jun 2006
Posts: 1002
Location: South Africa
|
Hi thyristor
You have to use that property of the naturals to show that it satisfies the set theory definition (recall that Peano's axioms fall outside normal set theory in there standard form).
_________________
As is often the case with technical subjects we are presented with an unfortunate choice: an explanation that is accurate but incomprehensible, or comprehensible but wrong. |
|
| Back to top |
|
|
| JaneBennet |
| Posted: Mon May 12, 2008 4:23 am Post subject: |
|
|
Forum Junior
Joined: 06 Apr 2008
Posts: 257
Location: UK
|
If you use Zermelo–Fränkel set theory, you don’t need the Peano axioms at all: you can construct the natural numbers (with 0) directly from set theory itself. The axiom of infinity says that there exists a set N which contains the empty set Ř such that for any n ∊ N, n ∪ {n} ∊ N. The set of natural numbers with 0, ℕ0, is defined as the smallest such set (intersection of all the sets with this property). Then you just define
0 = Ř
1 = 0 ∪ {0} = {Ř}
2 = 1 ∪ {1} = {Ř, {Ř}}
3 = 2 ∪ {2} = {Ř, {Ř}, {Ř, {Ř}}}
4 = 3 ∪ {3} = {Ř, {Ř}, {Ř, {Ř}}, {Ř, {Ř}, {Ř, {Ř}}}}
etc
The natural numbers without 0 is ℕ = ℕ0\{0}. Neat, huh? 
_________________
“A problem worthy of attack
Proves its worth by fighting back.” – Piet Hein
Why can’t a bull see red – literally can’t? Did You Know? |
|
| Back to top |
|
|
|
|
