- #1
MathematicalPhysicist
Gold Member
- 4,699
- 371
i need to prove the next statement:
let D be infinite class of infinite subsets of natural numbers that satisfies the next condition:
there exists a natural number m such that for every A,B in D |A^B|<=m (where ^ is for intersection). then, |D|=aleph-null.
well I am given a hint, that for every A in D A={n1,n2,...} such that n1<n2<... and i should look on f:D->N which is given by [tex]f(A)=2^{n_1}+2^{n_2}+...+2^{n_{m+1}}[/tex]
well i need to show that it's injective and surjective.
well for the injective, let A,B be in D such that |A^B|<=m, and f(A)=f(B)
i feel that this proof should use induction here, we can write A^B={p1,p2,...,p_m} where p_m can be equal to another number, if |A^B|<m.
then [tex]f(A)=2^{p_1}+2^{p_2}+...+2^{p_m}+2^{p_{m+1}}=2^{p_1}+...+2^{p_m}+2^{q_{m+1}}=f(B)[/tex]
then 2^q_{m+1}=2^p_{m+1}, so q_m+1=p_m+1 and we have by induction that A=B, is this correct?
now i need to show it's onto, but each number can be wrriten in base 2, so that's also easy to do, am i correct here?
this was question one, my next question is:
2)let X be a set such that |X|=a>=2. prove that for every cardinal number b such that a>=b, |Z|=|{Y|Y a subset of X, |Y|<=b}|<=a^b (here ^ means power).
well what that i did is as follows (im not sure that it's correct):
let B be a set such that |B|=b, and we can assume without loss of generality that Y is a subset of B, and now we need to find an injective function from Z to X^B (here ^ is power again), f:B->X, then we can define the function g:Z->X^B by g(Y)=f|Y which is injective, is this correct?
your help is appreciated.
(as always).
let D be infinite class of infinite subsets of natural numbers that satisfies the next condition:
there exists a natural number m such that for every A,B in D |A^B|<=m (where ^ is for intersection). then, |D|=aleph-null.
well I am given a hint, that for every A in D A={n1,n2,...} such that n1<n2<... and i should look on f:D->N which is given by [tex]f(A)=2^{n_1}+2^{n_2}+...+2^{n_{m+1}}[/tex]
well i need to show that it's injective and surjective.
well for the injective, let A,B be in D such that |A^B|<=m, and f(A)=f(B)
i feel that this proof should use induction here, we can write A^B={p1,p2,...,p_m} where p_m can be equal to another number, if |A^B|<m.
then [tex]f(A)=2^{p_1}+2^{p_2}+...+2^{p_m}+2^{p_{m+1}}=2^{p_1}+...+2^{p_m}+2^{q_{m+1}}=f(B)[/tex]
then 2^q_{m+1}=2^p_{m+1}, so q_m+1=p_m+1 and we have by induction that A=B, is this correct?
now i need to show it's onto, but each number can be wrriten in base 2, so that's also easy to do, am i correct here?
this was question one, my next question is:
2)let X be a set such that |X|=a>=2. prove that for every cardinal number b such that a>=b, |Z|=|{Y|Y a subset of X, |Y|<=b}|<=a^b (here ^ means power).
well what that i did is as follows (im not sure that it's correct):
let B be a set such that |B|=b, and we can assume without loss of generality that Y is a subset of B, and now we need to find an injective function from Z to X^B (here ^ is power again), f:B->X, then we can define the function g:Z->X^B by g(Y)=f|Y which is injective, is this correct?
your help is appreciated.
(as always).