Cardinality

**Showcase_22** · April 5th 2010, 10:01 AM

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?

**MoeBlee** · April 5th 2010, 10:32 AM

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

**clic-clac** · April 5th 2010, 11:05 AM

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.

**MoeBlee** · April 5th 2010, 11:34 AM

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

**Showcase_22** · April 5th 2010, 11:38 AM

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

**Plato** · April 5th 2010, 11:45 AM

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.

**Plato** · April 5th 2010, 11:54 AM

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

**clic-clac** · April 5th 2010, 11:55 AM

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

**MoeBlee** · April 5th 2010, 12:12 PM

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.

**Plato** · April 5th 2010, 12:22 PM

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.

**MoeBlee** · April 5th 2010, 12:22 PM

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.

**MoeBlee** · April 5th 2010, 12:29 PM

Originally Posted by Plato

Being portable rarely ever trumps being readable.

But I'm not playing bridge.

**clic-clac** · April 5th 2010, 12:40 PM

@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

**MoeBlee** · April 5th 2010, 01:49 PM

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.

**MoeBlee** · April 5th 2010, 01:55 PM

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

Thread: Cardinality

LinkBack

Thread Tools

Display

Cardinality

Similar Math Help Forum Discussions

Cardinality

Cardinality of R, [0,1], R^2, [0,1] x [0,1]

Cardinality

Cardinality

Cardinality

Search Tags