Re: Counting taxicabs...

On Sep 11, 12:33 pm, Simon Tatham <ana...@xxxxxxxxx> wrote:
mensana...@xxxxxxx <mensana...@xxxxxxx> wrote:
Isn't 2^oo called the power set and defined to be Aleph_1?

No. Aleph_1 is the name given to the second smallest infinite
cardinal, not the power set of 2^oo.

Ok, that must be the part I dreamed. Thanks.


Isn't it unproved that the continuum has cardinality of Aleph_1?

Hasn't it been shown that taking continuum=Aleph_1 and
continuum!=Aleph_1 both result in consistent systems, much
like taking the number of parallel lines to be either
0, 1 or oo all lead to consistent geometries?

This is all true, but it's best viewed as an uncertainty about the
nature of _aleph_1_, rather than the nature of the continuum. The
continuum is very clearly defined: it's the cardinality of the real
numbers, and also the cardinality of the power set of the natural
numbers, and those are easily shown to be identical. The only
question is whether there exists a size of infinity _between_
aleph_0 and C, and that's the undecidable Continuum Hypothesis.

If there is such an infinty, would it necessarily be Aleph_1,
or something else? Would nothing between Aleph_0 and C mean that
C=Aleph_1 or that C=Aleph_1 remains undecided even if it's proved
that there is nothing between Aleph_0 and C?


You can construct a formal definition of a set of cardinality
aleph_1 if you really try: as the cardinality of the first
uncountable ordinal, it must be the cardinality of the set of all
countable ordinals. Countable ordinals are equivalence classes of
well-orderings of N under order-isomorphism, so we arrive at a
construction along the lines of:

- Consider the set R of all relations on N (that is, subsets of NxN).
- Consider the subset S = { r in R: r defines a well-ordering of N }.
- Consider the equivalence relation on S in which the relations s,t
are equivalent iff they are order-isomorphic (that is, there is a
bijection f: N -> N such that for any i,j in N, i < j in s iff
f(i) < f(j) in t). This partitions S into equivalence classes (as
does any equivalence relation).
- Consider the set T of equivalence classes of S.
- This set T has cardinality aleph_1.

So another way of stating the Continuum Hypothesis is `There exists
a bijection between T and the real numbers'.

(Note that R has cardinality C, and in fact so does S. It's only
taking the quotient of S by order-isomorphism which potentially
reduces its cardinality.)
--
Simon Tatham "infinite loop _see_ loop, infinite"
<ana...@xxxxxxxxx> - Index, Borland Pascal Language Guide


.

Relevant Pages

  • Re: P does not equal NP - a logical approach
    ... I am putting teeth in it by connecting it to the power set ... problem is essentially the problem of the cardinality of ... the problem of the continuum hypothesis, i.e. oracles ...
    (comp.theory)
  • Re: Cardinality of equivalence classes and measure
    ... What is the cardinality of set of equivalence classes of all sets? ... Construct a family of c pairwise disjoint nonmeasurable sets, ... unions, no two equivalent. ...
    (sci.math)
  • Re: Size of equivalence class of Cauchy sequences
    ... What is the cardinality of the Lebesgue ... are these equivalence classes, although you can also ... and not leave the equivalence class it belongs to. ... of the other ways are right now (besides separability). ...
    (sci.math)
  • Re: TIME STARTS NOW
    ... >which is the cardinality of the power set of the set defining aleph_1, ... Whether that is aleph_1, as claimed by the continuum hypothesis, is ...
    (sci.math)
  • Re: TIME STARTS NOW
    ... >which is the cardinality of the power set of the set defining aleph_1, ... Whether that is aleph_1, as claimed by the continuum hypothesis, is ...
    (sci.logic)
Loading