Intereting Posts

How to divide using addition or subtraction
Simplest Example of a Poset that is not a Lattice
How to classify one-dimensional F-algebras?
Repayments of a loan with compound interest
How do I get good at Math?
Prove for positive integers a,b,c and d (where b does not equal d), if gcd(a,b) = gcd(c,d) = 1, then a/b + c/d is not an integer
The logic behind partial fraction decomposition
Failure of excision for $\pi_2$
Show that $\omega\mapsto\int_a^bX_t(\omega)\;dt$ is measurable, for a real-valued and continuous stochastic process $X$
What is Cauchy Schwarz in 8th grade terms?
Real Analysis, Folland Theorem 3.5, absoulute continuity
Is $\exp:\overline{\mathbb{M}}_n\to\mathbb{M}_n$ injective?
Recurrence for $q$-analog for the Stirling numbers?
Euler, Grinberg,… who's next?
Calculate: $\lim\limits_{x \to \infty}\left(\frac{x^2+2x+3}{x^2+x+1} \right)^x$

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

- $(p \implies q) \wedge (q \implies r) \implies (p \implies r)$
- Straight-line embedding planar graph
- Distinguishing powers of finite functions
- What does the notation $\binom{n}{i}$ mean?
- Can anyone help me proving this with Mathematical induction?
- Show that if $c\mid a-b$ and $c\mid a'-b'$ then $c\mid aa'-bb'$

- Cardinality of cartesian product
- Factoring inequalities on Double Summation (Donald Knuth's Concrete Mathematics)
- Refuting the Anti-Cantor Cranks
- Intuitive explanation for how could there be “more” irrational numbers than rational?
- Proving a triangle with different edge colors exists in a graph.
- Infinite DeMorgan laws
- Proof that the irrational numbers are uncountable
- What is the probability of a randomly chosen bit string of length 8 does not contain 2 consecutive 0's?
- Prove by induction $3+3 \cdot 5+ \cdots +3 \cdot 5^n = \frac{3(5^{n+1} -1)}{4}$
- Semi-partition or pre-partition

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.

- Integral Definition of Exterior Derivative?
- Integral of bounded continuous function on $R$
- Intuition on the sum of first (n-1) numbers is equal to the number of ways of picking 2 items out of n.
- Critical values and critical points of the mapping $z\mapsto z^2 + \bar{z}$
- No closed form for the partial sum of ${n\choose k}$ for $k \le K$?
- Existence of $\{\omega, \omega+1,…\}$ via the axiom of replacement
- Limit of an integral question: $\lim \limits _{h \to \infty} h \int \limits _0 ^\infty e ^{-hx} f(x) \, d x = f(0)$
- Product of three consecutive positive integers is never a perfect power
- Show that $f(C)$ has Hausdorff dimension at most zero.
- General linear group and special linear group
- Derivation of soft thresholding operator
- Is a proposition about something which doesn't exist true or false?
- Can every torsion-free nilpotent group be ordered?
- The double cone is not a surface.
- Probability of a drawing a specific suit and a specific color