Is there a way of proving that if $|X|=2^{\aleph_0}$ and $Y\subseteq X$ such that $|Y|=\aleph_0$ then $|X-Y|=2^{\aleph_0}$ without using axiom of choice or continuum hypothesis. Most of the proofs I've seen for this rely on the fact that if $X-Y$ does not have the cardinality of $\mathbb{R}$, then it must be countable (because it is clearly infinite). I was wondering if there is any way around this.
4934
I'm currently reading a little deeper into the Axiom of Choice, and I'm pleasantly surprised to find it makes the arithmetic of infinite cardinals seem easy. With AC follows the Absorption Law of Cardinal Arithmetic, which states that for $\kappa$ and $\lambda$ cardinal numbers, the larger infinite and the smaller nonzero, then $\kappa+\lambda=\kappa\cdot\lambda=\max(\kappa,\lambda)$.  I was playing around with the equation $k+\aleph_0=\mathfrak{c}$ for some cardinal $k$. From the above, it follows that $\mathfrak{c}=k+\aleph_0=\max(k,\aleph_0)$, which implies $k=\mathfrak{c}$.  I'm curious, can we still show $k=\mathfrak{c}$ without the Axiom of Choice? Is it maybe possible to bound $\mathfrak{c}-\aleph_0$ above and below by $\mathfrak{c}$? But then I'm not quite sure such algebraic manipulations even mean anything, or work like that here. Certainly normal arithmetic does not! Thanks.
123292
I have this problem:     Prove that $\mathbb{|Q| = |Q\times Q|}$   I know that $\mathbb Q$ is countably infinite.  But then how can I prove that $\mathbb{|Q\times Q|}$ is countably infinite?  Thanks you!
59894
Note that $\mathcal{P}(x)$,$\mathcal{P}(y)$ are power sets.  My proof.$\left( \Rightarrow \right)$ Let $t\in x$. Then, $t\in y$. So, since $t\in x$, $t\in \mathcal{P}(x)$. Also, since $t\in \mathcal{P}(x)$, $t\in\mathcal{P}(y)$. Thus, $x\subseteq y \Rightarrow  \mathcal{P}(x)\subseteq\mathcal{P}(y)$.  $(\Leftarrow )$. Similar.  Can you check my proof?
51180
From what I understood, cardinal numbers are defined as:  $\aleph_0$ = the cardinality of $\mathbb{N}$ $\aleph_{n+1}$ = is the least cardinal number greater than $\aleph_n$  The continuum hypothesis states that the cardinality of $\mathbb{R}$ is  $\aleph_1$. I more or less understand this cannot be proven (does not follow from ZFC).  However, can it be proven dat there in fact is a 'least cardinal number' greater than $\aleph_0$?  Is it possible that there are sets with cardinality $\aleph_{1/2}$, $\aleph_{1/3}$, et cetera, so to speak?  Or expressed differently: is it possible that for every set A with cardinality CA > $\aleph_0$, there exists another set B with cardinality CB where CA > CB > $\aleph_0$?
93120
This is a homework problem for class credit and I would appreciate a hint.  Let $A$ be an infinite set and suppose $x, y$ and $z$ are points in $A$. Show that $A$ has the same cardinality as $A\setminus\{x,y,z\}$.  So far I am trying to solve this for the more general case, let $A$ be an infinite set and $B$ be a finite subset of $A$, show that $A$ has the same cardinality as $A\setminus B$.  If $B$ is finite and $A$ is infinite, then $A\setminus B$ is infinite because if $A\setminus B$ were finite then $A = A\setminus B \cup B$, the union of two finite sets and hence $A$ would be finite.  Using Cantor-Bernstein we know that if there is a one-to-one function from $A$ to $A\setminus B$ and a one-to-one function from $A\setminus B$ to $A$, then $A$ and $A\setminus B$ are equivalent.  It is easy to define a function $f:A\setminus B \to A$ that is one-to-one, $f(x) = x$.  Now I need to define a function $g:A \to A\setminus B$ that is one-to-one.  I have a feeling that this involves using the axiom of choice.  Is this the right strategy?  Have I made any errors?  And can anyone give me a hint on how to define a one to one function from $A$ to $A\setminus B$?
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. :)
15818
Set theory (Jech) $\text{p.}\;27:$     It is an open problem whether one can prove without the axiom of choice that there exists a regular uncountable $\aleph_{\alpha}\;($the informed guess is that one cannot$)$.   My question is on the remark in brackets, in particular the use of the word informed: could someone briefly expand on the reasons for believing that this is likely to be impossible?
46163
$A$ and $B$ are sets. $|A \cup B| = \mathfrak{c}$, prove that $A$ or $B$ has cardinality $\mathfrak{c}$.  This is an exercise problem from my textbook. It's easy if I assume CH to be true. But how can I prove this without it? I don't know how to eliminate the case of $A$ and $B$ both has cardinality larger than that of natural numbers and strictly smaller than that of reals.
79740
This means: if $V\models{\sf ZFC}$ in such a way that $2^{\aleph_0}=\aleph_2$, can $2^{\aleph_1}$ be anything it ought to be? By the way, can $2^{\aleph_0}=\aleph_2$ be considered the 'simplest' case of $\lnot{\sf CH}$ in some sense?
25823
Is the cardinality of the Cartesian product of two equinumerous infinite sets the same as the cardinality of any one of the sets? I couldn't find this explicitly stated in any handout or text. This certainly seems to be true from the examples I have seen:  The Cartesian product of two infinitely countable sets is again infinitely countable. The Cartesian product of two sets with cardinality of continuum again has cardinality of continuum.
12731
I asked a similar question yesterday about well ordered sets, now I am having troubles with equivalence relations.   Could someone suggest an injection from a well known set of cardinality $2^{\aleph_{0}}$ to the set of all equivalence relations of $\mathbb{N}$?  Many thanks in advance!
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?
112884
I want to prove that the set of all real functions $\mathbb{R}^\mathbb{R}$ has a higher cardinality than the real numbers $\mathbb R$, by Cantor's diagonal argument.  I'm having difficulties with approaching this problem.  What I'm looking for is a hint in the right direction.  I've seen an example where it is shown that the power set $2^S$ of a countable set $S$ is uncountable, by the diagonal argument.
68953
I am comfortable with the different sizes of infinities and Cantor's "diagonal argument" to prove that the set of all subsets of an infinite set has cardinality strictly greater than the set itself. So if we have a set $\Omega$ and $|\Omega| = \aleph_i$, then (assuming continuum hypothesis) the cardinality of $2^{\Omega}$ is $|2^{\Omega}| = \aleph_{i+1} &gt; \aleph_i$ and we have $\aleph_{i+1} = 2^{\aleph_i}$.  I am fine with these argument.  What I don't understand is why should there be a smallest $\infty$? Is there a proof (or) an axiom that there exists a smallest $\infty$ and that this is what we address as "countably infinite"? or to rephrase the question "why can't I find a set whose power set gives us $\mathbb{N}$"?  The reason why I am asking this question is in "some sense" $\aleph_i = \log_2(\aleph_{i+1})$. I do not completely understand why this process should stop when $\aleph_i = \aleph_0$.  (Though coming to think about it I can feel that if I take an infinite set with $\log_2 \aleph_0$ elements I can still put it in one-to-one correspondence with the Natural number set. So Is $\log_2 \aleph_0 = \aleph_0$ (or) am I just confused? If $n \rightarrow \infty$, then $2^n \rightarrow \infty$ faster while $\log (n) \rightarrow \infty$ slower and $\log (\log (n)) \rightarrow \infty$ even slower and $\log(\log(\log (n))) \rightarrow \infty$ even "more" slower and so on).  Is there a clean (and relatively elementary) way to explain this to me?  (I am totally fine if you direct me to some paper (or) webpage. I tried googling but could not find an answer to my question)
100786
Show that the logic $ \ \forall x \exists y \ P(x,y) \ $ is not logically equivalent to $ \ \exists x \forall y \ P(x,y) \ $  in the domain $ \ \{-1,0,1 \} \ $ by giving a counter example .  Answer:  Let   $ x=\{0,1 \} \\ y=\{-1,0 ,1 \} \ $  Let $ P(x,y) \ $ be the property such that $ \ x \geq y \ $   Then , $ \forall x \exists y \ P(x,y) \ $ is true.   But, $ \ \exists x \forall y \ P(x,y) \ $ is False. Because for $ x=0 \ $ , we have $ \ 0 \ngeqslant y=1 \ $.  I need confirmation of my work.
22520
I came to point where I suppose for case 1 that $A\subseteq B$ and conclusion is trivial. For case 2 I suppose that $A\not\subseteq B$ and try to prove $B\subseteq A$, but that gets me nowhere. Any pointers here are most welcome.
38308
So basically I want to show:  $\aleph_{\alpha}^{\aleph_{1}} = \aleph_{\alpha}^{\aleph_{0}}\cdot2^{\aleph_1}$ , Where $\omega\leq\alpha&lt;\omega_1$  There is a proof that I found;    But I don't understand his proof for the limit case of $\alpha$.  To be more specific, I dont understand why $ \left( \sup_{\omega \le \beta &lt; \alpha} \aleph_{\beta}\right)^{\aleph_1} \le \left( \prod_{\omega \le \beta &lt; \alpha} \aleph_{\beta}\right)^{\aleph_1}$  Any insights or help is deeply appreciated.  Cheers