Let $A$ be the set of subsets of $[n]$ that have even size, and let $B$ be the set of subsets of $[n]$ that have odd size.  Establish a bijection from $A$ to $B$.  The following bijection is suggested for $n=3$:  $$\matrix{A: &amp; \{1,2\} &amp; \{1,3\} &amp; \{2,3\} &amp; \varnothing\\  B: &amp; \{1,2,3\} &amp; \{1\} &amp; \{2\} &amp; \{3\}}$$  I know that first we have to establish a function that is both surjective and injective so that it is bijective. I don't know where to take a step from here in the right direction. So I need a bit of guidance.   Something suggested is let f be the piecewise function:  $$f(x) = x \setminus \{n\}\text{ if }n \in x\text{ and }f(x) = x\cup\{n\}\text{ if }n \notin x$$
3921
Let $A$ be a non-empty set and $n$ be the number of elements in $A$, i.e. $n:=|A|$.  I know that the number of elements of the power set of $A$ is $2^n$, i.e.  $|\mathcal{P}(A)|=2^n$.  I came across the fact that exactly half of the elements of $\mathcal{P}(A)$ contain an odd number of elements, and half of them an even number of elements.  Can someone prove this? Or hint at a proof?
81800
For which $a,b,c,d \in \Bbb R$ does $f(x) = \frac {ax+b}{cx+d}$ define a bijection $f: \Bbb R \to \Bbb R$?  I'm guessing I need a system of equations and I know that $cx + d \ne 0$.  Thanks!
52246
We define $A$ to be a finite set if there is a bijection between $A$ and a set of the form $\{0,\ldots,n-1\}$ for some $n\in\mathbb N$.  How can we prove that a subset of a finite set is finite? It is of course sufficient to show that for a subset of $\{0,\ldots,n-1\}$. But how do I do that?
29331
Find the number of three element subsets $A$ of $\{1,2,...,10\}$ such that $A$ contains at least one even and one odd integer.  I think in this way: First we distribute one even and one odd number to 3 sets.Then there are 4 digits left of which 2 are even and 2 are odd.But how to distribute this 4 digits into 3 sets?
16175
Is it true that if $X$ and $Y$ are sets and there is a bijection between $\mathcal{P}(X)$ and $\mathcal{P}(Y)$ then there is a bijection from $X$ to $Y$ ?. I believe this should be obvious, but I can't see why this is so. A proof or a counter example would be highly appreciated.   Thanks.
43188
I originally stumbled upon this beast whilst trying to find the number of surjective functions from $[n]=\{ 1,...,n\}$ to $[k]$. Here is my idea, denote this number $a(n,k)$ hence $a(n,k) =k^n- \#\{{f:[n]\to [k]\; | \; f \; isn't \; surjective}\}$. For every $1\leq m\leq k-1$ we have ${m\choose k}$ ways of choosing a set of $m$ elements from $[k]$ and $a(n,m)$ functions in $\{{f:[n]\to [k]\; | \; f \; isn't \; surjective}\}$ with $|im(f)|=m$ and so: $a(n,k+1)=(k+1)^n-\sum_{m=1}^k {k+1\choose m}a(n,m)$ From here I tried to use induction to get $a(n,k+1)$ to the form of a polynomial in $a(n,1)$ which is clearly $1$, but had no luck as to finding the polynomial itself. Solutions to the original problem or to the recurrence relation would by much appreciated. EDIT: from the inclusion-exclusion prinicple I got the follwing expression for $a(n,k)$ which is: $a(n,k) = \sum_{m=0}^k (-1)^m{k\choose m}(k-m)^n$ and plugging it into $a(n,k+1)=(k+1)^n-\sum_{m=1}^k {k+1\choose m}a(n,m)$ yeilds: $a(n,k+1)=(k+1)^n-\sum_{m=1}^k{\sum_{i=0}^m {k+1 \choose k+1-m,i,m-i}(m-i)^n}$ which, to be honest, looks terrible. My original question still stands, what is the closed-form expression (if there even is one) for this monster double sum?
46477
Is there a continuous bijection from $[0,1]$ onto $[0,1] \times [0,1]$? That is with $I=[0,1]$ and $S=[0,1] \times [0,1]$, is there a continuous bijection $$ f: I \to S? $$  I know there is a continuous bijection $g:C \to I$ from the Cantor set $C$ to $[0,1]$. The square $S$ is compact so there is a continuous function  $$ h: C \to S. $$ But this leads nowhere. Is there a way to construct such an $f$?  I ask because I have a continuous functional $F:S \to \mathbb R$. For numerical reason, I would like to convert it into the functional $$ G: I \to \mathbb R, \\ G = F \circ f , $$ so that $G$ is continuous.
20757
It is quite easy to calculate the total number of functions from a set $X$ with $m$ elements to a set $Y$ with $n$ elements ($n^{m}$), and also the total number of injective functions ($n^{\underline{m}}$, denoting the falling factorial). But I am thinking about how to calculate the total number of surjective functions $f\colon X \twoheadrightarrow Y $.  The way I thought of doing this is as follows: firstly, since all $n$ elements of the codomain $Y$ need to be mapped to, you choose any $n$ elements from the $m$ elements of the set $X$ to be mapped one-to-one with the $n$ elements of $Y$. This results in $n!$ possible pairings. But the number of ways of choosing $n$ elements from $m$ elements is $\frac{m!}{(m-n)!\,n!}$, so the total number of ways of matching $n$ elements in $X$ to be one-to-one with the $n$ elements of $Y$ is $\frac{m!}{(m-n)!\,n!} \times n! = \frac{m!}{(m-n)!}$.  Now we have 'covered' the codomain $Y$ with $n$ elements from $X$, the remaining unpaired $m-n$ elements from $X$ can be mapped to any of the elements of $Y$, so there are $n^{m-n}$ ways of doing this. Therefore I think that the total number of surjective functions should be $\frac{m!}{(m-n)!} \, n^{m-n}$.  Is this anything like correct or have I made a major mistake here?
7674
(a) $S_k=\{A\subset\mathbb{N}: |A|=k\}$ for $k\in\mathbb{N}$  (b) $S = \bigcup_{k=1}^\infty S_k$   Work: For (a), I am not too sure about what approach I should use. I think finding a bijective function between the $S_k$ and $\mathbb{N}$ is hard to do . I also thought about using the Schroeder-Bernstein theorem and find injective functions $f:\mathbb{N}\rightarrow S_k$and $g:S_k\rightarrow\mathbb{N}$ in order to prove that $S_k$ and $\mathbb{N}$ are numerically equivalent. However, I have a hard time finding and proving these injective functions. I haven't really looked at (b) as I have yet to complete (a).
45862
Prove that the function $f: R\to R$ given $f(x)=x\cdot |x|$ is a bijection  Proof 1: f is injective  Suppose $$f(a) = f(b) \implies a\cdot |a| = b\cdot |b|$$ $$\implies (a\cdot |a|)^2 = (b\cdot |b|)^2$$ $$\implies a^4 =b^4$$ $$a=b$$ Thus, f is injective  Proof 2: f is surjective  Pick $n\in R$, we want to show $n=f(x)$ for some $x\in R$  $$\implies n= a\cdot |a|$$ for some $a\in R$  I dont know how to complete the surjective proof
55489
$A$ and $B$ two sets. $|A|=k, |B|=n.$ I need to prove in a combinatoric way that the number of partial function from $A$ to $B$ is $(n+1)^k.$ I thing the number is $Σ(n^i),$ for $i=0$ to $k.$ but I have no idea how to show equality, and how to prove it in a combinatoric way.  If someone can show me the way or guide me that will be great!  thanks for helpers.
45650
Is there a simple geometric proof that there exists a continuous bijective function between a square and its side?    And is there some explicit continuous function or formula $f^1(z)\mapsto (x,y)$ and $f(x,y)\mapsto z$, with $(x,y) \in [0,1]\times[0,1]$ and $z \in [0,1]$?  And is there a constructive proof that two sets of the same cardinality have a bijective function?
65235
I am stuck on this problem:  Define $f: N\times N \rightarrow N$ by   $f(i,j)=\frac{(i+j-1)(i+j-2)}{2}+i$.   How do you prove that $f$ is a bijection thus $N\times N$ and $N$ are numerically equivalent?  Work: First I tried to prove that $f$ is injective by setting $f(i,j)=f(x,y)$. However, from here I am stuck and I cannot reduce it properly. My work really does not get anywhere significant and its really messy.
41015
How many subsets of $\{1,2,...,n\}$ have no two consecutive numbers ?  Here is the solution :  The subsets are interpreted as $n$-words from the alphabet $\{0,1\}$. Let $a_n$ be the number of words with no consecutive ones. Then, a word can start from $0$ and proceed in $a_{n-1}$ ways or start with $10$ and proceed in $a_{n-2}$ ways. Therefore, $a_{n} = a_{n-1} + a_{n-2}$. $a_1 = 2, a_2 = 3$. So, $a_n = F_{n+2}$.  I have no trouble understanding the part of the argument linking $a_n$ with the Fibonacci numbers. But, I have trouble understanding the bijective argument.  What is a $n$ word ? And, how is the bijective constructed here ? How is $a_n$ linked to the question ?
23040
I'm looking for a 'simple' bijection $$ \pi \colon \mathbb N_0 \times \mathbb N_0 \to \mathbb N_0, $$  where 'simple' in this context means that it should be as easy as possible to define and it should be self-evident that said function is in fact a bijection. It's a quest for convenience - not minimal complexity in any rigorous sense.  Here are a couple of examples I came up with - none of which satisfy both requirements:   Let $\pi(m,n) = c(2^m3^{n+1})$, where $c \colon \{2^m3^{n+1} \mid m,n \in \mathbb N_0 \}\to \mathbb N_0$ is the order isomorphism (or in fact Mostowski collapse) of its domain under the natural ordering, Let $\pi(m,n) = \langle n,m \rangle$ - Gödel's pairing function, Let $\pi(m,n) = m \oplus n$ - the number resulting from '' $m,n$ (where we imagine both $m$ and $n$ as in infinite decks of cards whose $i$th element is labeled with its respective $i$th digit). ...
111795
I've looked at a few examples on here of how cardinality works and I'm still struggling. This is the problem that I'm currently struggling with. I know there needs to be a bijection function. I'm just stuck on how to actually do it.
109540
Here are two sets which I need to define a bijection function in order to show they are equivalent: $$ (A^B)^C \triangleq \{f:C\rightarrow \{g:B\rightarrow A\} \} $$ $$ (A^{B \times C}) \triangleq \{ h:B \times C \rightarrow A\} $$ where $A, B, C$ are sets, and $f, g, h$ represent functions.  I am trying to define a function $F : C \rightarrow A$ , but still struggling with its formal description, and how to use functions like $g$ above.  What is the right way of showing that such bijection $F$ exists?