Cardinals Question: Proving |D|=aleph-null using injectivity and surjectivity

[MathematicalPhysicist]

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 f(A)=2^{n_1}+2^{n_2}+...+2^{n_{m+1}}
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 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)
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).

 

[matt grime]

in 1. why do you need to show it is onto? All you need is injective: never attempt to do cardinality with explicit bijections unless you so happen to be able to do so. If X is infinite and f is an injection from X to N, then X has cardinality aleph_0.

 

[ecurbian]

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.

If this is really true for EVERY A,B in D, then for all A in D, |A^A|<=m,
that is |A|<=m. So D is not greater than Z^m (where ^ means power here) which is a countable set.

Should that be, for every DISTINCT A,B in D?

Sorry, just re-read the post, it was INFINITE subsets of naturals, so it must be intersections of distinct elements of D, but then the function f(A)=sum n in A of (exp(2,n)) does not converge to a natural.

 

[ecurbian]

Arithmetic approach

This is one approach.

Given a set of subsets of N with empty intersection, there can
be at most one subset for each n in N, so there is at most a
countable number of subsets. Given that the intersections are
finite, there is at most a countable number of intersections.
Looking at the set of subsets that has a given interesection,
the part of the subsets outside the intersection must have
empty intersection, and so there can only be a countable
number of them. Thus the total number of subsets is bounded
above by omega_0 times omega_0. Thus the set of subsets is
countable.

Maybe the sum pow(2,n) is supposed to be applied to the interesections
to prove that there is a countable number of them? Not to the elements
of the set of subsets?

 

[MathematicalPhysicist]

yes, i forgot about that, thanks matt.
what about my proof is it correct?
and what about my second question?

 

[ecurbian]

yes, i forgot about that, thanks matt.
what about my proof is it correct?
and what about my second question?

Loop,

I realize you spoke to matt direct, and in my rushing out of
the house this morning I did not properly read your posting,
but, I still feel I have something to say here.

The map f takes the set onto the sum of 2 to the powers of the
m+1 elements of the set. This is the standard binary trick to
map finite sets of naturals bijectively to naturals. So the
assertion that f(A)=f(B) means that the smallest m+1 elements
are equal, but since the intersection of distinct sets have
no more than m elements, the sets A and B cannot be distinct.

This is the core logic in your proof, that logic is fine.
But, you don't need induction at this point, and you have
not really used it either.

If you do need to prove that the binary expansion of a natural
number is unique, then consider subtracting two distinct
expansions for the same number. First, knock out all the
common powers. Of those powers left one must be the smallest.
Now we have ((2*A+1)-2*B)*C, where C is non zero. But,
2(A-B)+1 is an odd number, 0 is even, so without using
induction we have our proof.

But, now do it with |A^B| is finite, rather than at most m.
Does the theorem hold? or not, there is a very simple proof
along similar lines using a binary expansion.