Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Apparent paradox in cardinalities

  1. Nov 20, 2012 #1
    I'm strictly amateur at number theory (Not even studying it, just playing around for fun), so forgive me if I'm being foolish here. I've found a "proof" of something that is clearly wrong, and I can't find my mistake, so I'd appreciate anybody's help in figuring out what I did wrong. Also please forgive me for changing the template provided, but the existing one didn't make any sense for this question.

    1. Definitions

    First, I define a "sturdy" number as any natural number that is not divisible by any perfect square other than 1. To put it another way, if you were to decompose a sturdy number into its prime factors, each prime factor would be raised to the first (or zeroth) power. Let S be the set of all sturdy numbers, {1, 2, 3, 5, 6, 7, 10,...}.

    Let P be the set of all prime numbers, {2,3,5,7,...}.

    Let Q denote the power set of P: {∅,{2},{3},{2,3},{5},{2,5},{3,5},{2,3,5},...}.

    2. Relevant theorems

    Cantor's theorem (for any set A, the power set of A has greater cardinality than A).
    Euclid's proof of the infinitude of primes

    3. My reasoning

    For any sturdy number s, multiplying s by a prime that does not divide s yields another sturdy number. Since there are infinite primes, there are also infinite sturdy numbers.

    Since the sturdy numbers are a subset of the natural numbers, S must be countable. Since S is countable and infinite, it has the same cardinality as the set of natural numbers, [itex]\aleph_{0}[/itex].

    Since the primes are a subset of the natural numbers, P is countable. Since there are infinite primes, P is countably infinite, so it has the same cardinality as the set of natural numbers.

    Therefore, P and S have the same cardinality, [itex]\aleph_{0}[/itex].

    By Cantor's theorem, Q must have greater cardinality than P. Since P and S have the same cardinality, Q must have greater cardinality than S. However, there exists a one-to-one mapping from Q to S. Map the empty set to 1, and map each other set in Q to the product of its members. Therefore, Q and S must have the same cardinality. However, I've already shown that Q must have greater cardinality than S! How do I resolve this paradox?
     
  2. jcsd
  3. Nov 20, 2012 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    So far you haven't listed any infinite sets in Q. The power set of P certainly contains a LOT of them. If you mean Q to be the set of all finite subsets of P (which is NOT the power set), then that is countable and has the same cardinality as P.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook