I am currently working through Abbott's analysis, and am asked to prove the following:     Denote the power set of $\mathbb{N}$ by $\mathcal{P}(\mathbb{N})$. Show that $\mathcal{P}(\mathbb{N})\sim\mathbb{R}$; that is, to show that there exists a bijection $F:\mathcal{P}(\mathbb{N})\rightarrow\mathbb{R}$.    I am quite sure that we have to use Schroder-Bernstein Theorem where we have to injections to show that there is a bijection, but I'm not sure how to find an injection in either direction.
31548
I have learnt that the cardinality of the power set of the natural numbers is equal to the cardinality of the real numbers. What is the function that gives the one-to-one correspondence between these two sets?  I have also learnt that there exists no set whose cardinality is strictly between the natural numbers and the real numbers. Is there a proof of this or at least some intuitiveness behind it?
71829
(1) Prove or disprove: For any sets $X,Y,Z$ and any maps $f:X \to Y$ and $g:Y \to Z$, if $f$ is injective and $g$ is surjective, then $g \circ f$ is surjective.  So i proved previously that $f$ is injective if $g \circ f$ is injective, but then i also proved that if $g \circ f$ is surjective then $g$ is surjective. then this question appears, so how do i prove it that it is true or false? I'm saying it's true, because $g \circ f$ is bijective, so how do i go around proving it? Or my idea is already wrong? I need some help thanks.  (2) Show that (it is true in general that) for any sets $A,B$, one has $P(A) \cup P(B) \subseteq P(A \cup B)$.  I know that power set has exactly all the subsets of $A$ for $P(A)$. but I dont know how to start.
60056
I'm trying to prove that, for a finite set $A$, if the map $f: A\rightarrow A$ is a surjection, then it's an injection.  I've looked at this post:  but the arguments there seem very round-about, proving that injectivity implies surjectivity first.  I think I've seen other proofs, too, but they all sound kind of flimsy.  They tend to go something like "If the function is surjective then no two arguments can go to the same image, since that would require some element of the range not being the image of any element."  While that's true and I see what the argument has in mind, it's no more convincing than the statement of the claim that we're trying to prove!  Without a more rigorous proof, both seem to rely on the intuition that everything has to go to one and only one thing, but we're supposed to be proving that.  But I've been trying to develop a more thorough and direct proof, and haven't been able to.  I've tried induction:     The theorem holds trivially if $|A|=0$.  Suppose the theorem holds up to $n=|X|$, and let $|A|=n+1$ and $f:A\rightarrow A$ be a surjection.  Then let $x\in A$ and $f^{-1}(x)$ be the set of all elements $y\in A$ such that $f(y)=x$...   But at this stage I want to restrict my function, but that has the disadvantage that if $f(y)$ has more than one element in it, when I pluck it out of $A$ as the domain and pluck $x$ out of $A$ as the range, then I may not be dealing with a function mapping from a set to itself and so I don't get to use the inductive hypothesis.  Any other proofs you know about?
120311
This proof seems odd to me. I have come to the conclusion that I will use induction. I would like to see a smoother way or just some improvements on my technique.     Let $f:A\rightarrow B$ be a function between two finite sets of equal cardinality. Show that $f$ is surjective if and only if it  is injective.   To start, I will show that a surjection implies an injection using induction. I will dismiss the cases that both sets are empty or contain one element as being trivial (essentially vacuously true).   Assume $|A| \geq 2$, $|B| \geq 2$, $|A| = n = |B|$, and $f:A \rightarrow B$ is a surjection. For the base case, let $n = 2$.   There are two elements in both $A$ and $B$. Due to surjection, every element $b \in B$ must be mapped to, through $f$, by at least one element $a \in A$. If each of the two elements in $B$ were mapped to by the same element in $A$, the definition of function would be violated. Therefore, they are mapped to by unique elements in $A$. Thus, for $f(p), f(q) \in B$, if $f(p) = f(q)$, it must be true that $p = q$ so $f$ is injective.  Now assume that the surjection implies an injection for $n \geq 2$. We must show this to be true for $|A| = n + 1 = |B|$. Since it is true for $|A| = n = |B|$, the $n + 1$ case represents the addition of one new element to both $A$ and $B$. The new element in $B$ cannot be mapped to any other element in $A$ except for the new one. If mapped to by an old one, the definition of function would be violated. It must be mapped to by something since $f$ is surjective, hence it must be the new element. Finally, the new element in $A$ cannot be mapped to an old element in $B$ because it is unique and the previous $B$ was shown to be injective.  $$\blacksquare$$  This is a very wordy and awkward proof in my opinion. I have been out of proofs for a long time. I would like to see one that is more clear or seek validation if there isn't. I know that I have only completed half of the proof and have yet to go the other way.
74678
About a bijection between $\mathbb R$ and $\mathbb R \cup \{\infty\}$  If we'll take a line $f(x)=\begin{cases} ax &amp;, x\in\mathbb R\\ 0 &amp;, x=\infty  \end{cases}$ then we'll have a bijection.   But about this function: $g(x)=\begin{cases} x &amp;, x\in\mathbb R\setminus \{0\}\\ 0 &amp;, x=\infty  \end{cases}$ ? it appears to be a bijection and it's even simpler.
100257
Let $A, B$ be sets. Show that $\mathcal P(A \cap B) = \mathcal P(A) \cap \mathcal P(B)$.   I understand what this question is asking. The power set of an intersection equals the intersection of two power sets. I just have no idea how to prove it.
69594
Is this statement true? i.e. If $f(n)$ is injective and $p_n \rightarrow L$, does $p_{f(n)} \rightarrow L$?? (I realize that it's technically only a rearrangement if $f(n)$ is bijective.)   My attempt at a proof:  Since $p_n \rightarrow L$, we have that, for all $n$ except $n \le N$, $d(p_n, L) &lt; \epsilon$.  Let $S = \{n \ | \ f(n)\le N\}$, let $n_0$ be the largest $n \in S$, we know there is such a largest $n$ because $f(n)$ is injective. Now we have that $\forall \ n &gt; n_0 \ f(n) &gt; N$ which implies that $p_{f(n)} \rightarrow L$, as required.  Is this correct? Does my proof work?
64952
Could you please give me a hint to prove that $\mathbb{R}^n$ with the 1-norm $\lvert x\rvert_1=\lvert x_1\rvert+\cdots+\lvert x_n\rvert$ is not isometric to $\mathbb{R}^n$ with the infinity-norm $\lvert x\rvert_\infty = \max_{i=1,\ldots,n}(\lvert x_i\rvert)$ for $n\gt2$.  I do not see how the critical case $n=2$ enters the picture.  Thank you!
71929
I've been banging my head on this problem for some time now, and could really use help. Bear in mind I'm not very good at this sort of thing and am struggling to get by in class.  Problem:     Given $ \alpha : A \to B       \;\;\;\;\;   |A|=p \;\;\;\;|B|=q $      Find:         Number of Injections: $A \to B$   Number of Surjections: $ A \to B$    Prove that ∃ a bijection $A \to B$       $\Rightarrow$ p = q   find number of bijections: $A \to B$         I apologize for dropping such a big problem on you all, but I just can't get anywhere with this. Help?  EDIT: These answers are really helpful and I believe I've got down the number of Injections, but  we haven't gone through permutations or combinatorics in class so my understanding of it is really hamstrung. I'm unclear on the Stirling theorem as discussed here: , specifically the part where inclusion-exclusion comes into play. I'm not sure how to apply that, since right now I'm letting p = 4 and q = 3, so I don't know where inclusion-exclusion would be used (if at all!) since I don't know how elements would be missing.
107141
Prove that $\mathcal{P}(A)$ of a finite set $A$ is finite.      I need to prove this without using the cardinality of $\mathcal{P}(A)$.  This is my attempt, which is by induction: $\newcommand{\lbrac}[1]{\left(#1\right)}$ $\newcommand{\sett}[1]{\left\{#1\right\}}$ $\newcommand{\pset}[1]{\mathcal{P}\lbrac{#1}}$ Proof by induction over cardinality.  If $A = \varnothing$, then $\pset{A} = \sett{\varnothing}$, which is finite.  Suppose that for a set $A$ of cardinality $n$, $\pset{A}$ is finite.  Let $A$ be a set of cardinality $n+1$. $A$ is not empty, since it is of cardinality $n+1 &gt; 0$, and therefore pick some $x\in A$. It follows that $A = \lbrac{A-\sett{x}}\cup\sett{x}$. We claim that $$ \pset{A} = \pset{\lbrac{A - \sett{x}}\cup\sett{x}} = \pset{A - \sett{x}}\cup\sett{C | C\in\pset{A}\wedge x\in C} $$ Suppose $B\in\pset{A} = \pset{\lbrac{A-\sett{x}}\cup{x}}$. Then either $x\in B$ or $x\not\in B$. If $x\in B$, then $x\in B \wedge B\in\pset{A}\Rightarrow B\in C$. If $x\not\in B$ then $B\subseteq A - \sett{x}$.  \newline Either way, $B\in \pset{A - \sett{x}}\cup\sett{C | C\in\pset{A}\wedge x\in C}\Rightarrow \pset{A}\subseteq\pset{A - \sett{x}}\cup\sett{C | C\in\pset{A}\wedge x\in C}$.  Suppose $B\in\pset{A - \sett{x}}\cup\sett{C | C\in\pset{A}\wedge x\in C}$. Then either $B\in\pset{A-\sett{x}}$ or $B\in\sett{C | C\in\pset{A}\wedge x\in C}$ (or both).  If $B\in\pset{A-\sett{x}}$, then $B\subseteq(A-\sett{x})\cup\sett{x} = A$, and if $B\in\sett{C | C\in\pset{A}\wedge x\in C}$, then by definition, $B\subseteq A$. Either way, we get that $B\in\pset{A} \Rightarrow \pset{A - \sett{x}}\cup\sett{C | C\in\pset{A}\wedge x\in C} \subseteq \pset{A}$.  Since we have shown both sets are contained in each other, they are equal.  My goal is to now prove that $\sett{C|C\in\pset{A} \wedge x\in C}$ is finite. I didn't manage to do so without non rigorous claims that could also "prove" the main question.  If this set is finite, and by induction hypothesis $\pset{A - \sett{x}}$ is finite, I'll be done.  Any ideas on how to prove $\sett{C|C\in\pset{A} \wedge x\in C}$ is finite?
24054
Trying to solve a problem, I got stuck on the following question.     If $P\in\mathbb R[X]$ is an irreducible polynomial and $\operatorname {deg} P=2$, then is it true that $$\mathbb{R}[X]/(P)\cong\mathbb C?$$   I believe it must be true from the bits I've been hearing throughout my studies, but of which I haven't seen proofs. I've been unable to find anything on the internet other than . It tells me that there is something called Weierstrass' theorem which should be relevant, but can't find even the precise statement of the theorem, let alone the proof.  Here's what I have tried.   First of all, I can assume that $P$ is monic, because for any polynomial of degree $2$ there's a monic polynomial generating the same ideal in $\mathbb R[X].$ So I have  $$P(x)=x^2+bx+c$$  for some real numbers $b,c$ such that $b^2&lt;4c$.   I want to assume there is an isomorphism $\phi:\mathbb R[X]/(P)\to\mathbb C$ and work out what it should look like. I will denote by $[S]$ the coset of $S\in \mathbb R[X]$ in $\mathbb R[X]/(P).$ I'd like to find $S$ such that $\phi([S])=i.$  I have   $$ [x^2+bx+c-1]\mapsto -1, $$  So the coset that is mapped to $-1$ has to be a square root of $[x^2+bx+c-1]$ in $\mathbb R[X]/(P).$ Such a coset must be represented by a linear polynomial $kx+l$. Thus $$(kx+l)^2-(x^2+bx+c-1)\in (P),$$  that is $$ (kx+l)^2-(x^2+bx+c-1)\equiv a(x^2+bx+c) $$  for some real number $a$, and further  $$ (k^2-1-a)x^2+(2kl-b-ab)x+l^2-c-ac+1\equiv 0. $$  This gives   $$ \begin{cases} k^2=1+a\\ l^2=(1+a)c+1\\ 2kl=(1+a)b \end{cases} $$  The problem is that solving this gives formulas that are very difficult to handle. And I need to handle them if I want to prove that what I'm constructing is indeed an isomorphism. Is there a better way of doing it?
2650
Theorem. Let $X$ and $Y$ be sets with $X$ nonempty. Then (P) there exists an injection $f:X\rightarrow Y$ if and only if (Q) there exists a surjection $g:Y\rightarrow X$.  For the P $\implies$ Q part, I know you can get a surjection $Y\to X$ by mapping $y$ to $x$ if $y=f(x)$ for some $x\in X$ and mapping $y$ to some arbitrary $\alpha\in X$ if $y\in Y\setminus f(X)$. But I don't know about the Q $\implies$ P part.  Could someone give an elementary proof of the theorem?
114859
My book on set theory says     Prove that is a set $A$ is transitive, then $\mathcal{P}(A)$ is also transitive, where $\mathcal{P}(A)$ is the power set of $A$.   I don't know understand how. Let $A=\{a,b\}$. Clearly it is transitive. Now $\mathcal{P}(A)=\{\{a\},\{b\},\{a,b\},\emptyset\}$. This is clearly not transitive.
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).
69916
I need to find if set $I$ of all injective functions $\mathbb{N} \rightarrow \mathbb{N}$ is equinumerous to $\mathbb{R}$. Still, I have no idea how to work with set of functions, it's something new to me since I have only encountered sets of numbers before.
41946
I'm getting hung up on a proof that I remember being fairly easy... Showing that the power set of $\mathbb N$ is uncountable. Supposing it's countable, say $A=\{A_1,...\}$, we choose a set $B$ composed of elements $b_i$, where $b_i\notin  A$. How to we guarantee that $B$ isn't the naturals itself, an element of its own power set? Thanks!
105317
Theorem:  No set is equinumerous with its power set.  Proof:  Let $A$ be a set. We want to show that if $f: A \to \mathcal{P}A$ (a random function) then $f$ is not surjective.  We define the set $D=\{ x \in A: x \notin f(x)\}$ and obviously $D \in \mathcal{P}A$.  We assume that there is an $a \in A$ such that $f(a)=D$.  Then we have:  $$a \notin D \leftrightarrow a \notin f(a) \leftrightarrow a \in D, \text{ contradiction}$$  Therefore for each $x \in A, f(x) \notin D$, i.e. $f$ is not surjective.  Could you explain me the proof from the point where we assume that there is an $a \in A$ such that $f(a)=D$?  We have show that $D \in \mathcal{P}A$ and we want to show that $D \notin f(A)$ in order to show that $\mathcal{P}A$ isn't the image of $f$. Why do we do it like that? Why do we assume an $a \in A$ such that $f(a)=D$?