Page 1 of 2 12 LastLast
Results 1 to 15 of 16

Math Help - Cardinality

  1. #1
    Super Member Showcase_22's Avatar
    Joined
    Sep 2006
    From
    The raggedy edge.
    Posts
    782

    Cardinality

    What's the cardinality of B=\{(x,X)| \ x\in A, \ X \subseteq A, \ x \in X \} where A is a set of n elements?

    |B|=|A|.|X| since it's the result of a binary operation.

    Therefore |B|=n.|X|.

    Can we say anything about |X|? At most, |X|=n, but can we say anything more definite?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Let '$' stand for the binary Cartesian product.
    Let 'P' stand for the power set operation.
    Let '*' stand for multiplication of natural numbers.
    Let '^' stand for exponentiation of natural numbers.

    So your notation is a roundabout way of saying:

    B = A $ PA

    So the cardinality of B is n*(2^n).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    Hi

    Quote Originally Posted by Showcase_22 View Post
    |B|=|A|.|X| since it's the result of a binary operation.
    Take care, X is not a fixed subset, it is a "variable" in the definition of B. What can help is dividing B into disjoint subsets whose cardinalities are easier to figure, for instance, define for any x\in A\ B_x to be \{(x,X)\ ;\ x\in X\} (here the only variable is X).

    We have B=\bigcup_{x\in A} B_x , and if x\neq y,\ B_x\cap B_y=\emptyset , therefore |B|=\sum_{x\in A}|B_x|

    Given x\in A, it is easy to see |B_x|=|\{X\subseteq A\ ;\ x\in X\}|; it gives you the cardinality of B_x (i.e. |\mathcal{P}(A-\{x\})|) and note it is independent from the choice of x, I mean any |B_x|=|B_y| for x,y\in A: conclude.


    @MoeBlee: It's a little (just a little) more subtle than that.
    Last edited by clic-clac; April 5th 2010 at 11:08 AM. Reason: typo
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    I believe I am correct.

    {<x X> | x in A & X subset of A & x in X} = A $ PA

    Proof:

    Suppose p in {<x X> | x in A & X subset of A & x in X}.
    So for some <x X>, we have p = <x X> with x in A and X in PA.
    So p in A $ PA.
    So B subset of A $ PA.
    Suppose p in A $ PA.
    So for some x in A and some z in PA, we have p = <x z>.
    But if x in A, then {x} in PA,
    So for some X in PA, we have x in X.
    So p in {<x X> | x in A & X subset of A & x in X}.
    So A $ PA subset of {<x X> | x in A & X subset of A & x in X}.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member Showcase_22's Avatar
    Joined
    Sep 2006
    From
    The raggedy edge.
    Posts
    782
    |B_x|=<br />
|\mathcal{P}(A-\{x\})|<br />

    I'm sorry, but I can't see why that's the case.

    Isn't <br /> <br />
x \in \{X\subseteq A\ ;\ x\in X\}=B_x<br />
? =S

    Is it to do with the fact that x is fixed?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,658
    Thanks
    1615
    Awards
    1
    Quote Originally Posted by MoeBlee View Post
    I believe I am correct.
    {<x X> | x in A & X subset of A & x in X} = A $ PA.
    Let A=\{1,2,3\} then \left(1,\{1,2\}\right)\in B~\&~\left(3,\{1,2\}\right)\notin B.
    Therefore B\ne A\times \mathcal{P}(A).

    BTW: Why not learn to post in symbols? You can use LaTeX tags.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,658
    Thanks
    1615
    Awards
    1
    Quote Originally Posted by Showcase_22 View Post
    |B_x|=<br />
|\mathcal{P}(A-\{x\})|<br />
    I'm sorry, but I can't see why that's the case.
    For each x\in A,~~x is in 2^{n-1} subsets of A..
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    @Showcase_22: The equality " " is just a cardinality equality.

    There is a bijection between B_x and \mathcal{P}(A-\{x\}), given by X\leftrightarrow X-\{x\}. I just specified because \mathcal{P}(A-\{x\}) is known: since |A-\{x\}|=n-1, it is 2^{n-1}.

    Take care, x does not belong to B_x ! The elements of B_x are some ordered pairs (element of A ,subset of A).
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by Plato View Post
    Let A=\{1,2,3\} then \left(1,\{1,2\}\right)\in B~\&~\left(3,\{1,2\}\right)\notin B.
    Therefore B\ne A\times \mathcal{P}(A).
    You're right. I must have made a quantifier mistake in my argument.

    So let's look at B more carefully:

    Let 'E' stand for the existential quantifier.

    B = {<x X> | x in A & & x in X & X subset of A }
    = {p | ExX(x in A & x in X & X subset of A & p = <x X>)}.

    Certainly, B subset of A $ PA.

    But, right, it doesn't follow that A $ PA is a subset of B.

    (I'm going to look back at clic-clac's argument now.)

    Quote Originally Posted by Plato View Post
    BTW: Why not learn to post in symbols? You can use LaTeX tags.
    In certain contexts I don't like what is not perfectly portable to ASCII.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,658
    Thanks
    1615
    Awards
    1
    Quote Originally Posted by MoeBlee View Post
    In certain contexts I don't like what is not perfectly portable to ASCII.
    Being portable rarely ever trumps being readable.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by clic-clac View Post
    Take care, X is not a fixed subset, it is a "variable" in the definition of B. What can help is dividing B into disjoint subsets whose cardinalities are easier to figure, for instance, define for any x\in A\ B_x to be \{(x,X)\ ;\ x\in X\} (here the only variable is X).
    I don't understand your approach. There are two different variables , 'x' and 'X', both of them existentially quantified:

    B = {p | ExX(x in A & x in X & X subset of A & p = <x X>)}.

    But x is in too many X's for your B_x even to be a set per how I (somewhat) glean what you mean by B_x.

    But wait, is this what you mean?:

    For x in A, let B_x = {<x X> | x in X & X subset of A}.

    Okay, if that's what you mean, then I'll study the rest of your argument.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by Plato View Post
    Being portable rarely ever trumps being readable.
    But I'm not playing bridge.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    @MoeBlee: Yes in the definition of B x and X are "variables", in your quote I just mentioned X because I was refering to something written before.

    The idea is: since we have a set of ordered pairs, we look its subsets whose elements have all the same first coordinate.
    But wait, is this what you mean?:

    For x in A, let B_x = {<x X> | x in X & X subset of A}
    Exactly; I have just seen I forgot in my definition to precise X was a subset of A, but I hope it was clear
    Last edited by clic-clac; April 5th 2010 at 12:41 PM. Reason: typ
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by MoeBlee View Post
    But I'm not playing bridge.
    Sorry, that was flippant. What I should say is that I don't expect that ASCII would be clearer than tags. But I think my ASCII is pretty clear anyway (the only odd thing I've used is "$" for Cartesian, and only because 'x' and 'X' were already being used in the discussion), and I'm willing to sacrifice the difference in clarity for certain portability.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by clic-clac View Post
    X was a subset of A
    Okay, and then that led me to see your method too. Nice reasoning. So, if I'm not mistaken, the answer is n*(2^(n-1)) as follows:

    The B_x's form a partition of B. And the cardinality of each B_x is 2^(n-1) (easily verified by induction on n). And so, since there are n number of B_x's, we have that the cardinality of B is n*(2^(n-1)).
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Cardinality
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 11th 2010, 07:08 AM
  2. Cardinality of R, [0,1], R^2, [0,1] x [0,1]
    Posted in the Differential Geometry Forum
    Replies: 11
    Last Post: March 18th 2010, 02:20 PM
  3. Cardinality
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 31st 2009, 03:56 PM
  4. Cardinality
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 11th 2009, 05:36 PM
  5. Cardinality
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 8th 2009, 02:23 PM

Search Tags


/mathhelpforum @mathhelpforum