- #1

MathematicalPhysicist

Gold Member

- 4,223

- 174

## Main Question or Discussion Point

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 im 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 im 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).