Here's my question: Let A be a set. Define B to be the collection of all functions f : {1} → A. Prove that |A| = |B| by constructing a bijection F: A → B
In class, we just learned injections, surjections, bijections, cardinality, and power sets. I have a test next week and I feel like theres's going to be questions similar to this coming up.
I know that the cardinality is an attribute that describes the length of a set. I also know that a bijection by definition is injective and surjective, therefore mapping each element of the domain to exactly one element in the codomain.
In this question, since B is described as the collection of functions, does that mean that it only contains relations that have no more than one element in the codomain for any element in the domain? So, set B contains sets like {{1,a1},{1,a2},{1,a3}} and so on?
How do I show that the sets A and B have the same cardinality?
Can someone please give me advice as how to go about this question or possibly show me how to prove it?
How do I construct a bijection?
Can someone help me make sense of what this visually looks like in terms of mapping diagrams?
EDIT: How does constructing a bijection prove set A and B have the same cardinality? By definition for elements in the codomain, a bijection has exactly one element in the domain, meaning in terms of mapping diagrams that there's exactly one arrow pointing at each element in the codomain. So, an element in the domain is allowed to have more than one element in the codomain, right?
Best Answer
The deficulty is understanding concepts and using language. If you can do that this is trivial (almost literally).
Let me clearify with a few examples.
Ex: 1) Let $A=\{dog, cat, mouse\}$
Ex: 2) Let $A =\mathbb R$.
Then $B = \{f:\{1\}\to A\}= \{K\subset \{1\}\times A|$ for each $x \in \{1\}$ there is exactly one $(x,y) \in K\}=$
$\{K\subset \{1\}\times A|$ there is exactly one $(1,y) \in K\}=$
$\{K\subset \{1\}\times A| K = \{(1,y)\}$ for some $y \in A\}=$
$\color{blue}{\big\{}\{(1,y)\}| y\in A\color{blue}{\big\}}$.
In example 1: then $B = \color{blue}{\big\{}\{(1,dog)\}, \{(1,cat)\}, \{(1,mouse)\}\color{blue}{\big\}}$.
In example 2: then $B = \color{blue}{\big\{}\small\{(1, y)\small\}|y\in \mathbb R\color{blue}{\big\}}$
... Now try to do this on your own without reading further ...
Now it should be intuitively obvious that for every $a \in A$ there is exactly one function $f: \{1\}\to A$ so that $f(1) = a$.
And that's it. That's your bijection:
...... try to formally define the bijection, $j: B \to A$, before reading further ......
... Now try to prove that that is an injection without reading further...
To formally prove $j$ is a bijection.
Surjective: For each $a\in A$ then if we define $f:\{1\} \to A$ as $f(1) =a$ then $f \in B$ and $j(f) = a$. So $j$ is surjective.
Injective: If $j(f) = j(g)= y$ for some $y \in A$ then $f(1) = y$ and $g(1) = y$. but then (as $1$ is the only element of $\{1\}$) for all $x \in \{1\}$ then $f(x) = g(x)$. So $f = g$. So $j$ is one to one.