1. ## 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?

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

3. Hi

Originally Posted by Showcase_22
$|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.

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}. 5. $|B_x|= |\mathcal{P}(A-\{x\})| $ I'm sorry, but I can't see why that's the case. Isn't $ x \in \{X\subseteq A\ ;\ x\in X\}=B_x $ ? =S Is it to do with the fact that x is fixed? 6. Originally Posted by MoeBlee 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.

7. Originally Posted by Showcase_22
$|B_x|=
|\mathcal{P}(A-\{x\})|
$

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.$.

8. @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).

9. Originally Posted by Plato
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.)

Originally Posted by Plato
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.

10. Originally Posted by MoeBlee
In certain contexts I don't like what is not perfectly portable to ASCII.
Being portable rarely ever trumps being readable.

11. Originally Posted by clic-clac
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.

12. Originally Posted by Plato
Being portable rarely ever trumps being readable.
But I'm not playing bridge.

13. @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

14. Originally Posted by MoeBlee
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.

15. Originally Posted by clic-clac
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)).

Page 1 of 2 12 Last