Thread: Total relations between sets proof

1. Total relations between sets proof

Question: Suppose a set A has n elements and a set B has m elements. Prove that there are 2^m*n different relations from A to B

Now i see how this works with the product rule with AXB with m*n elements. and there are two sets so thats where 2 is involved. So i guess all the pieces are there but i don't know what to do with them.

2. Re: Total relations between sets proof

Question: Suppose a set A has n elements and a set B has m elements. Prove that there are 2^m*n different relations from A to B
I use $\displaystyle \|A\|$ as the notation for the number of elements is a set $\displaystyle A$.

Then $\displaystyle \|A\times B\|=\|A\|\cdot\|B\|$

Any subset of $\displaystyle A\times B$ is a relation $\displaystyle A\to B$.

So the answer to this question is $\displaystyle 2^{\|A\|\cdot\|B\|}$

3. Re: Total relations between sets proof

How do you get to the point where you come to the conclusion where you use '2' to get '2^||A||*||B||' ? I'm confused on that jump.

4. Re: Total relations between sets proof

How do you get to the point where you come to the conclusion where you use '2' to get '2^||A||*||B||' ? I'm confused on that jump.
If S is a set, the number of subsets of S is $\displaystyle 2^{\|S\|}$.

Here is a brief outline of a proof.
If we form the set of bit-strings, strings of 0's & 1's, of length n, then that set has $\displaystyle 2^n$ elements.
If $\displaystyle S=\{a,b,c,d\}$ then the string $\displaystyle 0,1,1,0$ represents the subset $\displaystyle \{b,c\}$. So every 4-bit-string represents a subset of $\displaystyle S$ so there are $\displaystyle 2^4$ subsets of $\displaystyle S$.

,

,

,

,

,

,

,

,

,

,

,

,

,

,

no of relations from a to b

Click on a term to search for related topics.