Re: How many finite subsets are there?

Hello David!

On 13 Apr., 15:15, David C. Ullrich <dullr...@xxxxxxxxxxx> wrote:
On Sun, 13 Apr 2008 04:22:04 -0700 (PDT), m_schnei <schn...@xxxxxx>
wrote:

Hi!

If I have a set M of cardinality aleph_n, what is the cardinality of
FPot(M), where "FPot(M)" means the set of all *finite* subsets of M?

aleph_n.

Intersting, I did not expect this. Is there a proof?

I know that Pot(M) has cardinality aleph_{n+1}

No, you don't know this. This is the Generalized Continuum
Hypothesis,

No!

The continuum hypothesis only states that there is no further
cardinality between aleph_n and aleph_{n+1}, for n >= 0. So this only
relates to this problem here in that it would be possible, in
principle, that the cardinality of the set of finite sets
card(FPot(M)) falls somewhere between the two cardinalities card(M)
and card(Pot(M)). When accepting the continuum hypothesis, this /
cannot/ be the case.

However, coming back to my statement above: aleph_{n+1} is *defined*
to be the cardinality of the power sets Pot(M) for all those sets M,
which have cardinality aleph_n. The induction starts at aleph_0 for
the set of natural numbers. So aleph_{n+1} is properly defined, and my
original claim is trivially true by definition.

which is known to be independent of the usual
axioms for set theory. (Which means there's no way to prove
it and no way to disprove it.)

This is right, but I thought that the continuum hypothesis is
generally accepted as just another axiom of mathematics. Just like,
for example, the axiom of choice, or the extentionality axiom, which
both have also always been pretty arguable in the history of logic.

(BTW: It is, of course, in the very nature of "real" axioms that (a)
neither they nor their negation are entailed by the rest of the
respective logic language, and (b) either they or their negation can
be added to the language without making the language unsatisfiable.)

(Cantor's Theorem).

Really? How did he prove this?

The idea is to show that Pot(M) has not the same cardinality than M
(which then means that Pot(M) must have a larger cardinality, because
I can 1:1-correspond M to the set of singletons of M-members).

This is shown by assuming that M and Pot(M) have same cardinality,
i.e. that there exists some bijection f which maps M to Pot(M). Then
the class

C_d := {x in M | x notin f(x)}

is a subset of M, and therefore an instance of Pot(M). This means that
there has to be some unique instance w in M such that

f(w) = C_d

But from this we learn about w that

w in C_d <==> w notin f(w) <==> w notin C_d

which is a contradiction. Hence, there is no such bijection f between
M and Pot(M), and thus the cardinalities of M and Pot(M) differ.

Note that I did not make any assumption about the concrete cardinality
of M, i.e. this proof is, in particular, valid for all aleph's.

I
expect this result to hold even for FPot(M), but wasn't able to proof
this yet.

Any ideas?

Cheers,
Michael

David C. Ullrich

Regards,
Michael
.

Relevant Pages

  • Re: non-Archimedean models of Euclidean geometry?
    ... The axiom basically says that if every point in A is to the ... isomorphism exactly one model for each infinite cardinal. ... example where the non isomorphic models have then same language. ... has non-isomorphic models of the same cardinality. ...
    (sci.logic)
  • Re: Null Sets and Product Measures.
    ... Using the continuum hypothesis, Sierpinski has constructed a set B ... necessary for Sierpinski to use an assumption that went beyond ZFC ... of the interval with cardinality less than the continuum have Lebesgue ... smallest union of measure-0 sets which covers the interval". ...
    (sci.math.research)
  • Re: How many finite subsets are there?
    ... This is the Generalized Continuum ... to be the cardinality of the power sets Potfor all those sets M, ... generally accepted as just another axiom of mathematics. ... respective logic language, and either they or their negation can ...
    (sci.math)
  • Re: Why float is called as float, not real?
    ... establishment by proving that the Continuum Hypothesis could not be decided. ... continuum hypothesis to be independent of the axiom of choice. ... rest of set theory; probably a wise choice. ... cardinality of the reals then the continuum hypotheis is that C = X_1. ...
    (comp.lang.fortran)
  • Re: P does not equal NP - a logical approach
    ... problem is essentially the problem of the cardinality of ... the problem of the continuum hypothesis, ... that we are talking about ordinals. ... sense to speak of finite ordinals. ...
    (comp.theory)
Quantcast