1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Apparent paradox in cardinalities
  1. Same cardinality (Replies: 1)

  2. Bijection Cardinality (Replies: 2)

  3. Cardinal arithmetic (Replies: 39)

Loading...