1

Ok, So I know this proof is wrong, but I can't find the error.

  1. The fundamental theorem of arithmetic says that every natural number can be uniquely expressed as a product of primes. I usually see this explained with multistep. (Definition)
  2. So the naturals are bijective to the set of multisets of primes (Right? [This is the wrong step]) (From Step 1)
  3. Primes are countable and thus bijective to naturals (Definition)
  4. The set of multisets of primes is bijective to the set of multisets of naturals (This seems like the error, but I don't see why) (From step 3)
  5. So the naturals are bijective to the set of multisets of naturals (At this point I know I'm wrong) (From steps 2 and 4)
  6. The powerset of naturals is a proper subset of the set of multisets of naturals (Definition)
  7. The reals are bijective to the powerset of naturals (outside theorem)
  8. The reals are a proper subset of the naturals (from steps 5,6,7)
  9. 22/7 is real and not natural (Definition)
  10. The reals are not a proper subset of the naturals (From Step 9)
  11. Contradiction. (From steps 8, 10)

What am I doing wrong here?

Donneaux
  • 57
  • 7
    The naturals are the same as finite multisets of primes. That finite is the key here. – lulu Feb 03 '23 at 15:00
  • 1
    I also suggest avoiding the term "isomorphic" unless you specify what category you are working in. Here, I think you just mean "isomorphic as sets" so you can just say that your sets are in $1:1$ correspondence with each other, or that there is a bijection between them. – lulu Feb 03 '23 at 15:04
  • There's also an issue with around steps 8 and 9 -- that sort of argument would also give a contradiction from the rational numbers being in bijection with the natural numbers, even though it's true. You have to remember that infinite sets don't behave the same as finite sets do: this example shows that a strict subset of an infinite set can still be in bijection with the full set (obligatory reference to Hilbert's hotel here...). – Daniel Schepler Feb 03 '23 at 17:56
  • Thanks for the answer @lulu. It's just a shame I had to pay reputation to get an answer. Besides figuring out the answer myself, I'm not sure how much more research I could have done here or how I could make the question clearer. – Donneaux Feb 04 '23 at 19:18
  • Step 6 is wrong since the power set of the naturals has elements which are infinite sets, and those sets are not finite multisets of naturals. – quasi Feb 04 '23 at 22:37

0 Answers0