Re: P does not equal NP - a logical approach

In article
<31f6dc07-63b1-4343-aec7-6efab18deb37@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
jeffrubard@xxxxxxxxx wrote:

At my level of computer science knowledge, I'm excited about
coming up with "well-known informal justifications", rather
than incoherent garbage (although you graciously tried that
tack first). What is different about what I am saying is that
I am putting teeth in it by connecting it to the power set
via the set of truth-functions, and conjecturing that the
problem is essentially the problem of the cardinality of
the power set (and the oracle solution or non-solution
the problem of the continuum hypothesis, i.e. oracles
that work assume the continuum hypothesis in that
2^(n-1) has the same cardinality as n, and oracles that
do not work deny it by having the largest cardinality
before 2^n be different from n).

What you have written above is either so profound that I fail to grasp
it or a confusion of terminology.

You write that "2^(n-1) has the same cardinality as n".

"Same cardinality as" is an equivalence relation on sets. If we are to
view numbers as sets and speak of the cardinality of numbers, I assume
that we are talking about ordinals.

In our setting, which is that of computational complexity, it only makes
sense to speak of finite ordinals.

Firstly, if we let n denote the finite ordinal number n and view it as a
transitive set, then it is obvious from our standard definition of
ordinal arithmetic that there cannot be a bijection between the finite
ordinal 2^{n-1} and the ordinal n. A simple counterexample is the
ordinal 3.

Secondly, the continuum hypothesis talks about infinite ordinals, or
rather their associated cardinals. The continuum hypothesis states that
there is no infinite cardinal between Aleph_0 and Aleph_1.



Or am I missing something?

Hans Hüttel
Department of Computer Science
Aalborg University
Denmark
.

Relevant Pages

  • Re: Proper classes
    ... > Even in set theories with an anti-foundation axiom. ... I disagree that "by definition" cardinal numbers are ordinals. ... By definition, cardinal numbers are equivalence classes of sets, ... is not the cardinality of all cardinals, ...
    (sci.math)
  • Re: RAF: Rational numbers, irrational numbers: each dense in real numbers
    ... There's no such thing as an inconsistent theorem. ... example the class of Ordinals, ... the cardinality of the irrationals and thus there exists uncountably ... many irrationals left from which to select, or it is greater than the ...
    (sci.math)
  • Re: RAF: Rational numbers, irrational numbers: each dense in real numbers
    ... RAF assumed there existed an uncountable ... equal to the cardinality of the irrationals, where for higher ordinals ...
    (sci.math)
  • Re: Cardinals as Equivalence class?
    ... from this Moe Blee deduces that Uc is the set of all sets. ... I don't know whether if we assume that c is a proper class will also ... Similar thing applies to the definition of ordinals as equivalence ... Then you can define the cardinality of a set to be the set ...
    (sci.math)
  • Re: Cardinals as Equivalence class?
    ... ie c itself can replace z in x and thus can be a member of x, ... I don't know whether if we assume that c is a proper class will also ... Similar thing applies to the definition of ordinals as equivalence ... Then you can define the cardinality of a set to be the set ...
    (sci.math)