Re: Cardinality of P

In article <399778db-a61a-4da2-86f2-755ee99967fb@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
the.theorist <the.theorist@xxxxxxxxx> wrote:
Does anybody know what the cardinality of the set P is?
what about the cardinality of NP?

As someone else explained, all the usual complexity classes are countable.

Are P (or NP) even considered sets in ZFC or 1st order Peano
Arithmetic?

P and NP are certainly considered sets in ZFC. In ZFC, strictly speaking,
all you can talk about are sets, so *everything* is a set.

As for first-order Peano arithmetic, it's worth pointing out that the term
"first-order Peano arithmetic" is not just a proper name for a particular
system---the word "first-order" actually means something. It means that
you can only talk directly about the natural numbers. In particular, you
can't talk about sets directly. Finite sets can be "faked" by identifying
them with natural numbers, but there is no general method for talking about
infinite sets.

On the other hand, it is possible to take a statement like "P = NP" which
ostensibly says that two infinite sets are equal and translate it into a
statement about finite sets, which can then be expressed in first-order
Peano arithmetic.

If anyone out there has links (or names) to papers (or people) that
have worked on these questions it would be very helpful.

The above facts are so basic that there are no names or papers associated
with them. You're best off learning some basic logic and set theory from a
class or from an introductory textbook. Then you'll be able to answer
questions like this yourself.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
.

Relevant Pages

  • Re: the need for relevance
    ... to make them look a great deal like the already well known finite sets. ... there is more than _one_ set theory for infinite sets. ... *solved* by ZFC. ... IS a correct abstraction of what sets really are. ...
    (sci.math)
  • Re: Cantor and the binary tree
    ... mathematicians are using it to mean "having a higher ... Of finite sets (which are the only thing we meet directly in the Real ... sizes can be extended in a natural way to infinite sets. ...
    (sci.math)
  • Re: Why? [was Re: Cantor`s powerset theorem is false?]
    ... In what sense is that fact the outcome of a computational experiment? ... Set theory defines 'natural number' and gives precise mathematical ... For finite sets, it should be clear what the computational meaning of ... For infinite sets, we would need to define a ...
    (sci.logic)
  • Re: Herc and Russells Paradox
    ... make any difference between finite and/or infinite sets at that level). ... the axioms holds for ANY sets, ... it SHOWs (at least in ZFC ... It doesn't exist because it is not a valid construction, ...
    (sci.logic)
  • Re: Cantors proof that #(Evens) = #(Naturals) is inconsistent
    ... constructions are different. ... >> correspondence, then demonstrate this by giving an answer to one of the ... finite sets uses the fact that A and B are finite, ... which has been proven for finite sets, and extended it to infinite sets, ...
    (sci.math)