We have the set $A=\{1,2,3,4,5\}$. what is the number of functions from $A$ to $A$? I think the domain of the function should contain all the elements of $A$ but range of the function may have any elements of $A$ or not having them. so for each of the numbers from $1$ to $5$ we have two possibilities $(1)$ existing in the range of function. $(2)$ not existing in the range. so the number of functions from $A$ to $A$ is $2^5=32$. is my justification right?
121741
Let $X$ and $Y$ be finite sets. Then the set $Y^X$ is finite and $\#(Y^X) = (\#Y)^{\#X}$.  I can see how to do it combinatorially. Let $y \in Y$. There are $\#(X)$ choices for such y to come from x, therefore we have $\#Y^{\#X}$ choices. I am not sure how to do it bijectively.
101305
I am having trouble getting started with this particular problem.  Let $A$ be a nonempty set, and let $\mathcal{B}$ be the set of all functions $f:A\to\{0,1\}$. Show that $\mathcal{B}\sim\mathcal{P}(A)$; that is, construct a bijection $\phi: \mathcal{B} \rightarrow \mathcal{P}(A)$.   Faced with this problem, I know that the power set contains all subsets of $A$. Now, does that mean all possible combinations of the functions which map to $\{0,1\}$? Also, does the fact that the characteristic function is associated with the power set have anything to do with the problem? Thanks.
5263
Let $ D = 2^\mathbb{N} $, i.e., D is the set of all sets of natural numbers.   What's the meaning of this definition? Intuitively, I would suggest that $ D = \{1,2,4,...\} $ but the explanation "set of all sets" leads me to the guess that this is wrong.
41826
If I have the function $f(x)$ and I want to apply it $n$ times, what is the notation to use?  For example, would $f(f(x))$ be $f_2(x)$, $f^2(x)$, or anything less cumbersome than $f(f(x))$? This is important especially since I am trying to couple this with a limit toward infinity.
51157
Find all functions $f$ such that $f:\mathbb{N}\rightarrow\  \mathbb{N}$ and $f(f(n))+f(n+1)=n+2$   Let us plug in $n=1$  $f(f(1))+f(2)=3$  Since the function is from $\mathbb{N}$ to $\mathbb{N}$, $f(2)$ can only take the values $1,2$. Now we divide the problem into cases.  Case-1: $f(f(1))=2,f(2)=1$  We can assume that $f(1)=c$ for the time being. Then plugging in $n=3$ and using $f(2)=1$ gives $$f(3)=4-c$$ and again since the range of the function is positive integers,then $4-c$ has to be positive and hence $c$ belongs to  {$1,2,3$}. Now, $$f(1)=c$$$$\implies f(f(1))=f(c)$$$$\implies 2=f(c)$$ by the assumption that $f(f(1))=2$ . Now,since $c$ can only take the values $1,2,3$,we start treating cases. If $c=1$,$$f(c)=2$$$$\implies f(1)=2$$ but we know from the deinition of $c$ that $f(1)=c=1$,a contradiction.If $c=2$,then $2=f(c)=f(2)$ but $f(2)=1$ by assumption. Finally,if $c=3$ $$2=f(c)=f(3)$$ but $$f(3)=4-c=4-3=1$$ which is once again a contradiction. Therefore there are no such functions in this case.  Case-2: $f(f(1))=1,f(2)=2$  Again assuming $f(1)=c$ and using $f(n)\le n$ along with plugging $n=c-1$ will give us that $f(1)=1$ and then it is easy to prove that such a function exists by recursion. I can only give a "sort of recursive" way to define the function. Here it goes $$f:\mathbb{N}\rightarrow \mathbb{N}$$$$f(1)=1$$$$f(n)=n+1-f(f(n-1))$$  But this case is harder to deal with.Some help will be appreciated.
69087
Give:  $fn(S)=\prod_{x\in S}x$  what is:  $fn(\emptyset)$  I can see reason that it would be defined as 1 or 0.    Note: I thought about restricting the domain of $S$ but that would make the problem less general. If there is no general answer then answers for restricted domains would be valid.
81180
I am trying to prove the following statement but have trouble  comprehending/going forward with some parts! Here is the statement:     If $A$ is any set, then  $|A|$ $&lt;$ $|P(A)|$   Here is what I have so far:  We need to show that there is an injection from $A$ to $P(A)$ but not a surjection.   A natural choice for an injection is the function $ f(x)$ $=$ $\{x \}$, which in plain English, takes any element $x$ (that is in $A$) and sends it to the one-element set $\{x \}$. Thus $f(x)$ is injective!  To show that there is no surjection, for the sake of contradiction, assume there is a surjection. Here is where I start to have trouble. Surjectivity means that every element of the co-domain is mapped to an element of the domain, correct? Consequently, in this particular case, we are "matching" sets (from $P(A)$) to elements (from $A$) right?  If the above is correct, my problem arises here. I am not sure how to prove that $f$ is not surjective. Unfortunately, I am easily confused by notation so please explain in English.  Thank you in advance!! :)
75254
Let $n$ be a natural number and $X$ = {$1,2,...,n$}. For subsets $A$ and $B$ of $X$ we deﬁne $A\Delta B$ to be the set of all those elements of $X$ which belong to exactly one of $A$ and $B$. Let $F$ be a collection of subsets of $X$ such that for any two distinct elements $A$ and $B$ in $F$ the set $A∆B$ has at least two elements. Show that $F$ has at most $2^{n-1}$ elements. Find all such collections $F$ with $2^{n−1}$ elements.  I have no clue on how and where to start. Please help.
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?
72209
I'm working on this problem already, the domain and co-domain are the set of Rational Numbers. we see that setting $x = 1$ and $y = n$, we obtain $f(n + 1) = f(n) + 1$  But I'm trying to prove that $f(n) = n + 1$ for all $n$, the case when $n = 1, 2$ is obviously true, how do I approach this via induction?
53683
I don't understand why a set with n elements has 2^n subsets. How is this calculated? I realize that {123} has empty set - 1-2-3-1,2-1,3-2,3-1,2,3 but how is the formula derived?
117621
a. Prove that the interval $A = [1,3]$ has the same cardinality as $B = [1,5]$ by writing down a bijection from $A \to B$. Don't prove it is a bijection.  b. Consider the following infinite set: $A = {1, \frac{1}{2},  \frac{1}{3},  \frac{1}{4},..., \frac{1}{n}}$,     Prove the set $A$ has the same cardinality as the integers by writing down a     .  bijection from $A$ onto $Z$.  I don't know how to find a function that is a bijection from one set to another. Can anyone help by explaining the thought process behind it, I've been having trouble with these types of problems? Thanks.
6443
My motivation for asking this question is that a classmate of mine asked me some kind of question that made me think of this one. I can't recall his exact question because he is kind of messy (both when talking about math and when thinking about math).   I'm kind of stuck though. I feel like the set $A^{\mathbb{N}} = \{f: \mathbb{N} \rightarrow A, f \text{ is a function} \}$ should have the same cardinality as the power set of A, if A is infinite. On the other hand, in this , it is stated that the sequences with real coefficients have the same cardinality as the reals.   It's easy to see that $A^{\mathbb{N}} \subseteq P(A)$, but (obviously) I got stuck on the other inclusion. Is there any general result that says anything else? References would be appreciated.  EDIT To clarify the intetion of this question: I want to know if there are any general results on the cardinality of $A^{\mathbb{N}}$ other that it is strictly less than that of the power set of A.   Also, I was aware that the other inclusion isn't true in general (as the post on here I linked to gave a counterexample), but thanks for pointing out why too. :)
39523
If $A=\left\{1,2,3,4,5\right\}$ Then     Find Number of functions $f : A \to A$ such that $f(f(x))=f(x)$   Case $1.$ if $f$ is injective then $f(f(x))=f(x)$ $\implies$ $f(x)=x$, hence there is only one injective function which is an identity function.  Case $2.$ When $f$ is many to one function  Let us assume that $f(1)=f(2)=f(3)=f(4)=f(5)=k$ Then clearly for any $k$ from the set $A$, $f(f(x))=f(x)$  hence there are five such functions.  Are there any other possibilities?
59905
If $F$ is a function and $U$ is a set, then what does $F|U$ mean?   In , the Inverse Function Theorem, the notation is used  Also, the file in stating the Lemma 2.14 states that $A \in U$, what does this mean? A set is an element of another set? What is $A$?  EDIT: Could someone kindly explain to me what is going on in Lemma 2.16. How does $\delta$ come into play? I dont see the role in the lemma. I also don't see why this proves one-to-one
76683
How can I prove that the set of all functions from $\mathbb{N} \to \{0, 1\}$ is uncountable?  Edit:  This answer came to mind.  Is it correct?  This answer just came to mind.  By contradiction suppose the set is $\{f_n\}_{n \in \mathbb{N}}$.  Define the function $f: \mathbb{N} \to \{0,1\}$ by $f(n) \ne f_n(n)$.  Then $f \notin\{f_n\}_{n \in \mathbb{N}}$.
70457
I need help in prooving that the cardinal number of the following set is $C_{n}$:  The set of all sequences   $a_{1}, a_{2}, .., a_{n} \in \mathbb{Z} \\ s.t \\ a_{1}+a_{2}+....+a_{n} = 0$  and for every $1 \leqslant i \leqslant n$ , $ a_{i}\geq -1$ and $a_{1}+a_{2}+....+a_{i}\geq 0$  For example, if $n =3$:  the series in the set will be: $(0, 0, 0),(0, 1, −1),(1, 0, −1),(1, −1, 0),(2, −1, −1)$  EDIT: I thought of presenting the problem using parenthesis. Every sequence as a total equal number of "(" and ")". Every sub-sequence has more "(" than ")".  $0$ is presented by "$\color{blue}(\color{blue})$",   $1$ by "$\color{red}($"   $-1$ by "$\color{green})$"  The problem is that the number of parentheses isn't fixed for a given $n$. For example when $n=2$ the series could be $\color{blue}(\color{blue})\color{blue}(\color{blue})$ or $\color{red}(\color{green})$   Also, I don't know how to "translate" the term $ a_{i}\geq -1$  And for $n=3$ the representation of the sequences $(0,1,-1)$ and $(1,-1,0)$ is the same - "$()()$"