Intereting Posts

Why is the Auslander Reiten theory not working in this example?
Verify that R(p,2) = R(2,p) = p, where R is the Ramsey number
Comaximal ideals in a commutative ring
Does there exist a prime that is only consecutive digits starting from 1?
Every minimal Hausdorff space is H-closed
What is the probability that when you place 8 towers on a chess-board, none of them can beat the other.
The Practical Implication of P vs NP Problem
Small time behavior of Lévy processes
Why is the absence of zero divisors not sufficient for a field of fractions to exist?
Show that the value of a definite integral is unity
Evaluate $\int_{0}^{\infty} \mathrm{e}^{-x^2-x^{-2}}\, dx$
If $\langle a,b \rangle=0$, then $a,b$ are perpendicular?
Does algorithmic unsolvability imply unsolvability in general?
Find all the values of $(1+i)^{(1-i)}$
If $f$ is holomorphic and $\,f'' = f$, then $f(z) = A \cosh z + B \sinh z$

The question is that we have to prove that if $A$ has $m$ elements and $B$ has $n$ elements, then there are $2^{mn}$ different relations from A to B.

Now I know that a relation $R$ from $A$ to $B$ is a subset of $A \times B$. And as the maximum number of subsets (Elements in the powerset) is $2^{mn}$ so the answer is also the same.

But I don’t get how would I prove this. Should I prove that there are $2^{mn}$ in a powerset and give the definition of a relation and hence conclude that the answer is $2^{mn}$. (If this is the case can you help me with it.)

- What is the history of this theorem about the finite sum of a polynomial?
- Make up a reasonable definition for the bipartite complement of a bipartite graph
- Proving the sum of the first $n$ natural numbers by induction
- Recurrence with varying coefficient
- Ballot counting when ties occurs exactly $r$ times
- Can a collection of points be recovered from its multiset of distances?

- Why isn't this a well ordering of $\{A\subseteq\mathbb N\mid A\text{ is infinite}\}$?
- Prove that if an average of a thousand numbers is less than 7, then at least one of the numbers being averaged is less than 7
- Monotonic subsequences and convergence
- Count Exclusive Partitionings of Points in Circle, Closing Double Recurrence?
- Arranging books on the shelf.
- Prove that if a|b and b|c then a|c using a column proof that has steps in the first column and the reason for the step in the second column.
- Combinatorics: Number of subsets with cardinality k with 1 element.
- Countable/uncountable basis of vector space
- Definition of the Infinite Cartesian Product
- Distributing 6 oranges, 1 apple, 1 banana and 1 pineapple among 3 children

You should prove two statements:

1) If $A$ has $m$ elements and $B$ has $n$ elements, then $A \times B$ has $mn$ elements.

2) If $C$ is a set of $k$ elements, then the power set $P(C)$ has $2^k$ elements.

Regarding 2): Let $C = \{c_1,\ldots,c_k\}$ and consider the mapping

$$f : P(C) \to \{ (a_1,\ldots, a_k) ~ | ~ a_i \in \{0,1\}\}$$

defined in the following way: For $D\subseteq C$ let $f(D) := (d_1,\ldots, d_k)$ where $d_i = 1$ if $c_i \in D$ and $d_i =0$ if $c_i \notin D$. For example $f(\emptyset) = (0,\ldots, 0)$, $f(\{c_2\}) = (0,1,0,\ldots, 0)$ and so on.

This way we associate every subset $D$ of $C$ with a $k$-tuple that has a $1$ at the $i$-th position, if $c_i$ is in $D$ and a $0$ otherwise.

Now one can see that $f$ is a bijection: If $f(D) = f(D’)$, then $D = D’$ and for every sequence $(a_1,\ldots, a_k)$ consisting of $0$’s and $1$’s we can find a matching subset $D \subseteq C$ such that $f(D) = (a_1,\ldots, a_n)$. That $f$ is a bijection means that $P(C)$ and the set of all possible $k$-tuples containing only $0$’s and $1$’s have the same cardinality (number of elements).

Another hint to finish the proof of 2):

$$\{ (a_1,\ldots, a_k) ~ | ~ a_i \in \{0,1\}\} = \underbrace{\{0,1\} \times \ldots \times \{0,1\}}_{k \text{ times}}$$

Can you use 1) now?

I hope this isn’t too confusing. If you have further questions, just leave a comment below.

$R\subset A\times B$.

Let $A=\{a_1,a_2,…,a_m\}$ and $B=\{b_1,b_2,…,b_n\}$. Recall that $A\times B=\{(a_i,b_j):1\leq i\leq m, 1\leq j\leq n\}$ so $|A\times B|=mn$. Also we have $|2^{A\times B}|=2^{mn}$ Since $R\in 2^{A\times B}$ then there are $2^{mn}$ relations.

- Integrate $\sin(101x)\cdot \sin^{99}x$
- Quotient rings of Gaussian integers
- The differential equation $xu_{x}+yu_{y}=2u$ satisfying the initial condition $y=xg(x),u=f(x)$
- Does the frontier of an open set have measure zero (in $\mathbb{R}^n$)?
- How to prove that if each element of group is inverse to itself then group commutative?
- The Rapidity of the Exponential Function Towards Infinity
- Prove by contradiction that every integer greater than 11 is a sum of two composite numbers
- Number of pairs of strings satisfying the given condition
- partitions with even number of even parts – partitions with odd number of even parts
- “weird” ring with 4 elements – how does it arise?
- What is the history of this theorem about the finite sum of a polynomial?
- Solving a semilinear partial differential equation
- Combination Problem Understanding
- When do the multiples of two primes span all large enough natural numbers?
- What's the arc length of an implicit function?