question about sets and subsets using the definition

95 Views Asked by At

Assume $A$ and $B$ are two sets such that: $Card(A)=n$ and $Card(B)=m$, also $B⊆A$,Clearly $n\ge m$. define: $$\mathscr{P}(A:B)=\left\{X∈\mathscr{P}(A):B⊆X\right\}$$ find the number of elements of $\mathscr{P}(A:B)$

I just know $Card\left(B\right)\le Card\left(X\right)$ how I can answer the question? does there exist any general formula?

3

There are 3 best solutions below

2
On

Hint: Try to find a bijection $\mathscr P(A:B)\to \mathscr P(A\setminus B)$.

5
On

Below, a reasoning ( probably not a proof properly speaking) trying to answer the question : in how many ways can one " build" a set X belonging to P(A:B). The number of possible ways to build a member of P(A:B) is the same as the number of members of P(A:B).

enter image description here

3
On

If we assume $Card(A)=n$ and $Card(B)=m$ then $$\mathscr{P}(A:B)=\sum_{k=m}^{n}{{n}\choose{k}}{{k}\choose{m}}$$ For example if $A=\left\{1,2,3\right\}$, clearly $Card(A)=3$,and take $Card(B)=2$ then: $\mathscr{P}(A)=\left\{\left\{\right\},\left\{1\right\},\left\{2\right\},\left\{3\right\},\left\{1,2\right\},\left \{1,3\right\},\left\{2,3\right\},\left\{1,2,3\right\}\right\}$ Since $X∈\mathscr{P}(A)$ and $B⊆X$ we have: There are ${{3}\choose{2}}$ sets of $\mathscr{P}(A)$ and ${{2}\choose{2}}$ set of $X$ with cardinality $2$ There are ${{3}\choose{3}}$ set of $\mathscr{P}(A)$ and ${{3}\choose{2}}$ sets of $X$ with cardinality $2$ Summing gives the desired result, also using the formula we have: $$\mathscr{P}(A:B)=\sum_{k=2}^{3}{{3}\choose{k}}{{k}\choose{2}}$$$$={{3}\choose{2}}{{2}\choose{2}}+ {{3}\choose{3}}{{3}\choose{2}}$$ which is the same as the previous result.