Countability of functions

kindlychung

See the attached picture, please.

elimqiu

The cardinality of the set of all mappings from A to B is denoted by |B|^|A|
This can be verified in the cases of finite sets.
Now we want to show that ω^2 = ω while 2^ω > ω. That is to say, set of all functions from {0,1} to N has the same cardinality as N (|N| = ω)
While the set of all functions from N to {0,1} is not countable.
Proof. The set F1 of functions from {0,1} to N and N×N = {(m,n) | m,n ∈ N } has natural 1-1 correspondence  f ←→ (f(0),f(1)) thus  |F1| = |N×N| = |N| = ω
The set of F2 of functions from N to {0,1} is actually the set of characteristic functions of the subset of N thus the cardinality is the cardinality of the powere set of N, namely P(N). Thus it';s not countable by Cantor.

kindlychung

Thanks, great to have you here.

fleurly

下面引用由elimqiu在 2010/09/25 05:50am 发表的内容：
The cardinality of the set of all mappings from A to B is denoted by |B|^|A|
This can be verified in the cases of finite sets.
Now we want to show that ω^2 = ω while 2^ω > ω. That is to say ...

“That is to say, set of all functions from {0,1} to N has the same cardinality as N (|N| = ω)”
I think 2^|N| = c, the cardinality of real set.

elimqiu

Set of functions from A to B is B^A, not A^B.
Actually you can write the set explicitly and see your mistake on the post above

fleurly

下面引用由elimqiu在 2010/09/26 03:10am 发表的内容：
Set of functions from A to B is B^A, not A^B.
Actually you can write the set explicitly and see your mistake on the post above

对滴， 我搞错了

wangyangkee

为老外顶帖，为 elimqiu 顶帖，乐得赚积分，，，