Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Cardinals question.

  1. Feb 12, 2007 #1


    User Avatar
    Gold Member

    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).
  2. jcsd
  3. Feb 12, 2007 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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.
  4. Feb 12, 2007 #3
    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.
    Last edited: Feb 12, 2007
  5. Feb 12, 2007 #4
    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

    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?
  6. Feb 13, 2007 #5


    User Avatar
    Gold Member

    yes, i forgot about that, thanks matt.
    what about my proof is it correct?
    and what about my second question?
  7. Feb 13, 2007 #6

    I realise 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.
    Last edited: Feb 13, 2007
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook