What's the cardinality of where A is a set of n elements?
since it's the result of a binary operation.
Therefore .
Can we say anything about ? At most, , but can we say anything more definite?
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).
Hi
Take care, is not a fixed subset, it is a "variable" in the definition of What can help is dividing into disjoint subsets whose cardinalities are easier to figure, for instance, define for any to be (here the only variable is X).
We have and if therefore
Given it is easy to see ; it gives you the cardinality of (i.e. ) and note it is independent from the choice of I mean any for : conclude.
@MoeBlee: It's a little (just a little) more subtle than that.
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}.
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.)
In certain contexts I don't like what is not perfectly portable to ASCII.
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.
@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.
Exactly; I have just seen I forgot in my definition to precise X was a subset of A, but I hope it was clearBut wait, is this what you mean?:
For x in A, let B_x = {<x X> | x in X & X subset of A}
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.
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)).