Let $\lambda\leq\kappa$ be infinite cardinals. Then $| \{X\subset \kappa | |X|=\lambda \} | = \kappa^{\lambda} $  $\leq$ part is trivial, but I don't know how to prove the other part. I used transfinite induction on $\lambda$ but it didn't work to me. Can I have any hint for this?  Thanks in advance
46950
Initially assume ZFC.  Let $\binom{\kappa}{\lambda}$ denotes $\left|[\kappa]^{\lambda}\right|$ where $[\kappa]^{\lambda}$ is the collection of all subsets of $\kappa$ with cardinality $\lambda$. That is, the number of subsets of $\kappa$ of size $\lambda$.  Let $\kappa$ be any infinite cardinal number. Then it is easy to see that   $\binom{\kappa}0=1$ $\binom{\kappa}n=\kappa$ for all positive natural number $n$.  $\binom{\aleph_0}{\aleph_0}=\beth_1$ $\binom{\kappa}{\lambda}\le \kappa^\lambda$ when $1\le \lambda \le \kappa$   3 is due to $\beth_1=\sum_{\lambda=0}^{\aleph_0}\binom{\aleph_0}{\lambda}$ and others besides $\binom{\aleph_0}{\aleph_0}$ sums $\aleph_0$(since countable infinite countable infinites sums to countable infinite)  $\left({}^{\kappa}_{\lambda}\right)\le \kappa^\lambda$ is due to an injection can be made from $[\kappa]^{\lambda}$ into $\kappa^{\lambda}$(maps $\{a_i|i&lt;\lambda\}$ to $\langle a_i\rangle_{i&lt;\lambda}$ where $a_j&lt;a_k$ iff $j&lt;k$)  I hypothesize that   $$\binom{\kappa}{\lambda}=\begin{cases} \kappa^\lambda,&amp;\lambda \le \kappa \\ 0,&amp; \lambda&gt;\kappa  \end{cases}$$  It holds when $\kappa=\aleph_0$, but hard to induct for larger cardinals without assuming GCH. So I need some helps.
97723
Let $|A|=\alpha, |B|=\beta, |C|= \gamma$ be cardinals and $\beta \leq \gamma$. Prove $\alpha ^{\beta}\le \alpha ^{\gamma}$.  So from the given we know that there's an injection $f:B\to C$ and some functions $h:B\to A, g: C\to A$. We want to prove there's an injection $l_1:A\to C$. It appears that $f$ doesn't help here.  Trying to take representatives from $A$ and show they're in $C$ and there's an injection doesn't work so maybe the function should be $l_2: h \to g$ but I don't know how to work with it.
51853
Why does the tree property hold for regular cardinals but not singular cardinals? (I.e. There exists a tree of height $\kappa$ with countable levels and no cofinal branch for $\kappa$ a singular cardinal)
23368
I need to show that for any countable ordinal $\alpha$ there is a set A $\subseteq \mathbb{Q}$ such that (A, &lt;) is isomorphic to ($\alpha, \in$).  To do it I am supposed to show the following stronger statement by induction on ordinals $\alpha$ &lt; $\omega_{1}$:  Let P($\alpha$) be the statement "For every interval (a, b) with rational endpoints, there is an A $\subseteq$ (a,b) such that (A, &lt;) is isomorphic to ($\alpha, \in$)."  I think that the purpose of breaking $\mathbb{Q}$ into intervals (a,b) is to make $\mathbb{Q}$ a countable set, but I don't see the significance of doing this or how it would make the proof easier.  I feel like I need to define a well-ordered set in (a,b) but I don't know how to do this since if a and b are both negative then there is no least element, so no well-ordering.  I believe that I am supposed to be using transfinite induction? But I don't know how P($\alpha$) implies P(S($\alpha$)) for S($\alpha$) successor of $\alpha$.  Any help would be greatly appreciated... thanks in advance.
106511
Is there any example that for cardinal numbers $\kappa &lt; \lambda$, we have $2^\kappa = 2^\lambda$?  My guess is that it only depends on whether GCH holds. Is it true?
75755
I need to show specifically using transfinite induction that given two well-ordered sets $\left(A,&lt;_{1}\right)$   and $\left(B,&lt;_{2}\right)$ there is only one isomorphism between them. To do this I want to show by induction that there is only one way to define the mapping and that is: $$\forall\, x\in A: \varphi\left(x\right)=\min\left(B\backslash\varphi\left(\left\{ a\in A\,:\, a&lt;_{1}x\right\} \right)\right)$$ Showing the base of the induction is no problem and the induction hypothesis would be that $$\forall\, y&lt;_{1}x\,:\,\varphi\left(y\right)=\min\left(B\backslash\varphi\left(\left\{ a\in A\,:\, a&lt;_{1}y\right\} \right)\right)$$ My problem is that I can't seem to manage to use the hypothesis in order to prove the step. I've found a couple of ways to show this definition of the mapping is indeed necessary but none of those used the induction hypothesis. My plan was to mark $$c_{0}=\min\left(B\backslash\varphi\left(\left\{ a\in A\,:\, a&lt;_{1}x\right\} \right)\right)$$ Using the fact $\varphi$ is surjective take $y\in A$ such that $\varphi\left(y\right)=c_{0}$ and show that it can't be that $y&lt;_{1}x$ or $x&lt;_{1}y$ and thus necessarily $y=x$. If someone could give me a way to show either one of these are false using the induction hypothesis it would solve my problem.  Thanks a lot!
50979
Theorem. Let $X$ denote an arbitrary set such that $|X|=n$. Then $|\mathcal P(X)|=2^n$.      Proof. The proof is by induction on the numbers of elements of $X$.      For the base case, suppose $|X|=0$. Clearly, $X=\emptyset$. But the empty set is the only subset of itself, so $|\mathcal P(X)|=1=2^0$.      Now the induction step. Suppose $|X|=n$; by the induction hypotesis, we know that $|\mathcal P(X)|=2^n$. Let $Y$ be a set with $n+1$ elements, namely $Y=X\cup\{a\}$. There are two kinds of subsets of $Y$: those that include $a$ and those that don't. The first are exactly the subsets of $X$, and there are $2^n$ of them. The latter are sets of the form $Z\cup\{a\}$, where $Z\in\mathcal P(X)$; since there are $2^n$ possible choices for $Z$, there must be exactly $2^n$ subsets of $Y$ of which $a$ is an element. Therefore $|\mathcal P(Y)|=2^n+2^n=2^{n+1}$. $\square$      From the above explanation, I don't understand why the set that contains $\{a\}$ will contain $2^{|n|}$ elements when it should clearly be $2^{|1|}$.  The construction of a new set $S$ is the union of the old set with cardinality $n$ and an new element $\{a\}$, therefore the set that do not contain $\{a\}$ still has cardinality $n$ and the set that contains $\{a\}$ is just $\{a\}$, one element...  Can someone please elucidate?
92975
This is a Lemma from N.L. Carothers Real Analysis.  Lemma. An infinite subset $A$ of $\mathbb{N}$ is countable.  Proof. Since $A\ne\emptyset$, there is a smallest element $x_1\in A$. Then $A\backslash\{x_1\}\ne\emptyset$, and there must be a smallest $x_2\in A\backslash\{x_1\}$. By induction we can find $x_1,x_2,\dotsc,x_n,\dotsc\in A$, where $x_n=\min(A\backslash\{x_1,\dotsc,x_{n-1}\})$. Now, suppose that $x\in A\backslash\{x_1,x_2,\dotsc\}\ne\emptyset$. Then the set $\{k:x_k&gt;x\}$ must be nonempty, and hence it has a least element. That is, there is some $n$ with $x_1&lt;x_2&lt;\cdots&lt;x_{n-1}&lt;x&lt;x_n$. But this contradicts the choice of $x_n$.  The part of the proof that I don't understand is that the set $\{k:x_k&gt;x\}$ must be nonempty. Carothers claims that otherwise we would have $x\in A$ and $x&lt;x_1=\min A$. I can't prove that if $\{k:x_k&gt;x\}=\emptyset$ then $x&lt;x_1$.  Help appreciated please.
84516
Prove: If $A$ is a finite set and $B$ is an infinite set, then $B \setminus A$ is an infinite set.   I've tried proving the contrapositive, that if $B \setminus A$ is a finite set then $A$ is infinite or $B$ is finite, but I don't think this is the way to go.
48667
A certain section of the chapter "The Axiom of Choice" on "Naive Set Theory" got me confused:     "[...] The assertion is that a set is infinite if and only if it is equivalent to a proper subset of itself. The "if" we already know; it says merely that a finite set cannot be equivalent to a proper subset. To prove the "only if," suppose that $X$ is infinite, and let $v$ be a one-to-one correspondence from $\omega$ into $X$. If $x$ is in the range of $v$, say $x=v(n)$, write $h(x)=v(n^{+})$; if $x$ is not in the range of $v$, write $h(x)=x$. It is easy to verify that $h$ is a one-to-one correspondence from $X$ into itself. Since the range of $h$ is a proper subset of $X$ (it does not contain $v(0)$), the proof of the corollary is complete. The assertion of the corollary was used by Dedekind as the very definition of infinity."   (The corollary would follow from "every infinite set has a subset equivalent to $\omega$".)  The question is: how can $h$ be a one-to-one correspondence from $X$ into itself if its range does not contain an element (namely, $v(0)$) that is in $X$?
25400
I need to find the cardinality of the set $S$ of all infinite subsets of $\mathbb{Q}$.   It's easy to prove $\operatorname{card} S=\mathfrak c$ if you first prove that the cardinality of the set of all finite subsets of $\mathbb{Q}$ is $\aleph_0$.   But is there some other proof for the statement without using the second one (about finite subsets)? Probably there is =)
73041
It is well-known that:     Given a set $X$ and a collection $\cal S$ of subsets of $X$, there exists a $\sigma$-algebra $\cal B$ containing $\cal S$, such that $\cal B$ is the smallest $\sigma$-algebra satisfying this condition.   Certain texts, Lieb and Loss, Analysis, for instance, state that the proof of this assertion requires transfinite induction. On the other hand, one can define $\mathcal B$ to be the intersection of all $\sigma$-algebras containing $\cal S$. Which statement is correct? Or, is there a hidden transfinite induction contained somewhere?  I must confess here that I have only vague ideaos of the rigorous set-theoretic foundations of mathematics.
102655
I'm working on exercises from Kunen and I'm stuck. I must proof that the following are equivalent:   There exists a sequence $\langle A_\alpha:\alpha&lt;\omega_1\rangle$ such that $\forall\alpha(A_\alpha\subset\alpha)$ and for all $A \subset \omega_1$ the set $\{\alpha \in \omega_1:A\cap\alpha=A_\alpha\}$ is stationary. ($\diamondsuit$-principle) There exists a sequence $\langle A_\alpha:\alpha&lt;\omega_1\rangle$ such that $\forall\alpha(A_\alpha\subset\alpha\times\alpha)$ and for all $A \subset \omega_1\times\omega_1$ the set $\{\alpha \in \omega_1:A\cap\alpha\times\alpha=A_\alpha\}$ is stationary. There exists a sequence $\langle f_\alpha:\alpha&lt;\omega_1\rangle$ such that $\forall\alpha(f_\alpha:\alpha\rightarrow\alpha)$ and for all $f : \omega_1\rightarrow\omega_1$ $\exists\alpha(f|\alpha=f_\alpha\wedge\alpha&gt;0)$ There exists a sequence $\langle f_\alpha:\alpha&lt;\omega_1\rangle$ such that $\forall\alpha(f_\alpha:\alpha\rightarrow\alpha)$ and for all $f : \omega_1\rightarrow\omega_1$ the set $\{\alpha \in \omega_1:f|\alpha=f_\alpha\}$ is stationary.   I have proved that $1\implies 2\implies 4\implies 3$ and that $4\implies 1,$ but I'm having problems on proving that $3\implies$ "something", because it only talks about one $\alpha$. Can someone help me?
88406
Is there any way to solve this problem using the diagonalization method? I know there's the proof that uses $\mathcal{P}(\mathbb{N})$ = set of all finite subsets $\cup$ set of all infinite subsets, but I'm trying to solve it using the diagonalization method specifically. I was thinking that we can assume the two have the same cardinality and arrive at a contradiction, but I don't know how to get there. How can we show there has to be some infinite set in the set of all infinite subsets that cannot match 1-1 with a natural number?
23510
How many subsets of $\mathbb{N}$ have the same cardinality as $\mathbb{N}$?   I realize that any of the class of functions $f:x\to (n\cdot x)$ gives a bijection between $\mathbb{N}$ and the subset of $\mathbb{N}$ whose members equal multiples of n.  So, we have at least a countable infinity of sets which have the same cardinality of $\mathbb{N}$.  But, we could remove a single element from any countably infinity subset of the natural numbers and we still will end up with a countably infinite subset of $\mathbb{N}$.  So (the reasoning here doesn't seem quite right to me), do there exist uncountably many infinite subsets of $\mathbb{N}$ with the same cardinality of $\mathbb{N}$?    Also, is the class of all bijections $f: \mathbb{N} \to \mathbb{N}$ and a given countably infinite subset uncountably infinite or countably infinite?
52144
Let $A$ be a set and $P(A)$ be the power set of $A$. Define $B(A)$ as   the set of all functions $F:A\rightarrow\{0,1\}$. For example,   $B(\mathbb{N})$ is the set of all binary sequences. Prove that $P(A)$   has the same cardinality as $B(A)$.   When $A$ is finite, this is easy to prove. I am interested in other cases; for instance when $A$ is countably infinite or uncountable. I am also a bit confused with the definition of $B(A)$. Could anyone help me with this one please?
19530
Let $X$ be an infinite set of cardinality $|X|$, and let $S$ be the set of all finite subests of $X$. How can we show that Card($S$)$=|X|$? Can anyone help, please?