This tag is for questions about cardinals and related topics such as cardinal arithmetics, clubs, stationary sets, cofinality, and principles such as $\lozenge$. Do not confuse with [large-cardinals] which is a technical concept about strong axioms of infinity.

learn more… | top users | synonyms

53
votes
1answer
3k views

How do we know an $ \aleph_1 $ exists at all?

I have two questions, actually. The first is as the title says: how do we know there exists an infinite cardinal such that there exists no other cardinals between it and $ \aleph_0 $? (We would have ...
12
votes
3answers
856 views

The cartesian product $\mathbb{N} \times \mathbb{N}$ is countable

I'm examining a proof I have read that claims to show that the Cartesian product $\mathbb{N} \times \mathbb{N}$ is countable, and as part of this proof, I am looking to show that the given map is ...
4
votes
2answers
1k views

Cartesian Product of Two Countable Sets is Countable

How can I prove that the Cartesian product of two countable sets is also countable?
15
votes
2answers
756 views

Defining cardinality in the absence of choice

Under ZFC we can define cardinality $|A|$ for any set $A$ as $$ |A|=\min\{\alpha\in \operatorname{Ord}: \exists\text{ bijection } A \to \alpha\}. $$ This is because the axiom of choice allows any ...
17
votes
2answers
959 views

For every infinite $S$, $|S|=|S\times S|$ implies the Axiom of choice

how to prove the following conclusion: [for any infinite set $S$,there exists a bijection $f:S\to S \times S$] implies the Axiom of choice. Can you give a proof without the theory of ordinal ...
18
votes
2answers
3k views

Cardinality of set of real continuous functions

The set of all ℝ → ℝ continuous functions is c. How to show that? Is there are bijection between ℝn and the set of continuous functions?
14
votes
3answers
1k views

The Aleph numbers and infinity in calculus.

I have a fairly fundamental question. What is the difference between infinity as shown by the aleph numbers and the infinity we see in algebra and calculus? Are they interchangeable/transposable in ...
13
votes
2answers
609 views

Relationship between Continuum Hypothesis and Special Aleph Hypothesis under ZF

Special Aleph Hypothesis AH(0) is the claim $2^{\aleph_0}=\aleph_1$, i.e. there is a bijection from $2^{\aleph_0}$ to $\aleph_1$. Continuum Hypothesis CH is the claim $\aleph_0 \leq \mathfrak{a}< ...
30
votes
6answers
1k views

Why is the Continuum Hypothesis (not) true?

I'm making my way through Thomas W Hungerfords's seminal text "Abstract Algebra 2nd Edition w/ Sets, Logics and Categories" where he makes the statement that the Continuum Hypothesis (There does not ...
18
votes
2answers
670 views

How to show $(a^b)^c=a^{bc}$ for arbitrary cardinal numbers?

One of the basic (and frequently used) properties of cardinal exponentiation is that $(a^b)^c=a^{bc}$. What is the proof of this fact? As Arturo pointed out in his comment, in computer science this ...
8
votes
4answers
673 views

What's the cardinality of all sequences with coefficients in an infinite set?

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 ...
5
votes
2answers
1k views

Cantor-Bernstein-like theorem: If $f\colon A\to B$ is injection and $g\colon A\to B$ is surjective, can we prove there is a bijection as well?

I've been trying to find this proof: If there exists $f \colon A\to B$ injective and $g \colon A \to B$ surjective, prove there exists $h \colon A \to B$ bijective. I thought of using ...
15
votes
1answer
739 views

Cardinality of a Hamel basis

What is the cardinality of a Hamel basis of $\ell_1(\mathbb{R})$? Is it deducible in ZFC that it is seemingly continuum? Does it follow from this that each Banach space of density $\leqslant ...
7
votes
1answer
1k views

A simple bijection between $\mathbb{R}$ and $\mathbb{R}^4$ or $\mathbb{R}^n$?

How to form a bijection from $(0,1]$ to $\mathbb{R}$: $$f(x) = \left\{\begin{array}{ll} 2-\frac{1}{x}&\text{if }x\in(0, .5]\\ \frac{2x-1}{1-x}&\text{if }x\in(.5, 1]. \end{array}\right.$$ ...
19
votes
4answers
665 views

Does $k+\aleph_0=\mathfrak{c}$ imply $k=\mathfrak{c}$ without the Axiom of Choice?

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 ...
2
votes
2answers
518 views

Do $\omega^\omega=2^{\aleph_0}=\aleph_1$?

As we know, $2^{\aleph_0}$ is a cardinal number, so it is a limit ordinal number. However, it must not be $2^\omega$, since ...
11
votes
1answer
439 views

There's non-Aleph transfinite cardinals without the axiom of choice?

I can't find anything on this anywhere. The book I'm largely using at the moment is based around ZFC, so it makes no mention of anything other than the Aleph numbers, but according to Wikipedia on the ...
4
votes
2answers
1k views

Proving the Cantor Pairing Function Bijective

How would you prove the Cantor Pairing Function bijective? I only know how to prove a bijection by showing (1) If $f(x) = f(y)$, then $x=y$ and (2) There exists an $x$ such that $f(x) = y$ How would ...
4
votes
2answers
941 views

An infinite subset of a countable set is countable

In my book, it proves that an infinite subset of a coutnable set is countable. But not all the details are filled in, and I've tried to fill in all the details below. Could someone tell me if what I ...
6
votes
1answer
278 views

Is there a way to define the “size” of an infinite set that takes into account “intuitive” differences between sets?

The usual way to define the "size" of an infinite set is through cardinality, so that e.g. the sets $\{1, 2, 3, 4, \ldots\}$ and $\{0, 1, 2, 3, 4, \ldots\}$ have the same cardinality. However, is this ...
55
votes
6answers
3k views

Why is $\omega$ the smallest $\infty$?

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. ...
6
votes
4answers
2k views

Cardinality of all cardinalities

Let $C = \{0, 1, 2, \ldots, \aleph_0, \aleph_1, \aleph_2, \ldots\}$. What is $\left|C\right|$? Or is it even well-defined?
8
votes
3answers
699 views

Is the class of cardinals totally ordered?

In a Wikipedia article http://en.wikipedia.org/wiki/Aleph_number#Aleph-one I encountered the following sentence: "If the axiom of choice (AC) is used, it can be proved that the class of cardinal ...
3
votes
3answers
311 views

Proving that for infinite $\kappa$, $|[\kappa]^\lambda|=\kappa^\lambda$

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 ...
12
votes
10answers
1k views

Intuitive explanation for how could there be “more” irrational numbers than rational?

I've been told that the rational numbers from zero to one for a countable infinity, while the irrational ones form an uncountable infinity, which is in some sense "larger". But how could that be? ...
8
votes
4answers
1k views

Do the real numbers and the complex numbers have the same cardinality?

So it's easy to show that the rationals and the integers have the same size, using everyone's favorite spiral-around-the-grid. Can the approach be extended to say that the set of complex numbers has ...
6
votes
3answers
532 views

How to prove cardinality equality ($\mathfrak c^\mathfrak c=2^\mathfrak c$)

How do I prove this cardinality equality:$\mathfrak c^\mathfrak c=2^\mathfrak c$ I have failed to prove this after lots of trail - but I am certain it's true How can I prove this?
5
votes
3answers
478 views

Cardinality != Density?

I was in a discussion where I argued that the density of two sets of the same cardinality could be different in respect to the infinite range of non-negative integers. Does cardinality imply that any ...
5
votes
2answers
1k views

Cardinality of $\mathbb{R}$ and $\mathbb{R}^2$

I am working on this exercise for an introductory Real Analysis course: Show that |$\mathbb{R}$| = |$\mathbb{R}^2$|. I know that $\mathbb{R}$ is uncountable. I also know that two sets $A$ and ...
14
votes
1answer
1k views

Overview of basic results on cardinal arithmetic

Are there some good overviews of basic formulas about addition, multiplication and exponentiation of cardinals (preferably available online)?
14
votes
4answers
3k views

Cardinality of the set of all real functions of real variable

How does one compute the cardinality of the set of functions $f:\mathbb{R} \to \mathbb{R}$ (not necessarily continuous)?
6
votes
1answer
241 views

What is $\aleph_0$ powered to $\aleph_0$?

By definition $\aleph_1 = 2 ^{\aleph_0}$. And since $2 < \aleph_0$, then $2^{\aleph_0} = {\aleph_1} \le \aleph_0 ^ {\aleph_0}$. However, I do not know what exactly $\aleph_0 ^ {\aleph_0}$ is or how ...
3
votes
3answers
194 views

Why the principle of counting does not match with our common sense

Principle of counting says that "the number of odd integers, which is the same as the number of even integers, is also the same as the number of integers overall." This does not match with my ...
-3
votes
1answer
268 views

Question about Cantors Diagonal Argument [closed]

Lets be honnest I don't understand cantors diagonal argument. http://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument While I can understand that this proof proves that you cannot make the list of ...
2
votes
2answers
267 views

Cardinal number subtraction

We all know that $|\mathbb{N}| = \aleph_0$. Since $|\{-1\} \cup \mathbb{N}| = \aleph_0$ as well, I guess you could say that $\aleph_0 + 1 = \aleph_0$. You can go on to derive that $\aleph_0 + ...
1
vote
2answers
281 views

Non-aleph infinite cardinals

I'm now confused with a concept of $\aleph$. 1.$\aleph$ is a cardinal number that is well-ordered in ZF.(Defined as an initial ordinal that is equipotent with). Does that mean $\aleph_x$ in ZF may ...
8
votes
1answer
327 views

Is the axiom of choice needed to show that $a^2=a$?

A comment on this answer states that choice is needed for the statement that $a^2=a$ for all infinite cardinals $a$. In Thomas Jech's Set Theory (3rd edition), his theorem 3.5 proves this statement ...
15
votes
3answers
561 views

For any two sets $A,B$ , $|A|\leq|B|$ or $|B|\leq|A|$

Let $A,B$ be any two sets. I really think that the statement $|A|\leq|B|$ or $|B|\leq|A|$ is true. Formally: $$\forall A\forall B[\,|A|\leq|B| \lor\ |B|\leq|A|\,]$$ If this statement is true, ...
7
votes
2answers
322 views

Implications of continuum hypothesis and consistency of ZFC

I've been a bit confused whilst doing some reading. I think the confusion arises because I am trying to read Wikipedia on topics without being able to work along. Anyway, I have read that, of course, ...
7
votes
1answer
260 views

Cardinal equality question

The question contains 2 stages: 1. Prove that ${\aleph_n} ^ {\aleph_1} = {2}^{\aleph_1}\cdot\aleph_n$ This one is pretty clear by induction and by applying Hausdorf's formula. 2. Prove ...
6
votes
5answers
242 views

cardinality of the set of $ \varphi: \mathbb N \to \mathbb N$ such that $\varphi$ is an increasing sequence

I know that the set of functions $ f:\mathbb N \to \mathbb N$ is uncountable, but what if we consider only $f$ such that $f$ is increasing? I want to know if this set is countable D: and also the case ...
5
votes
1answer
598 views

Cardinality of a set that consists of all existing cardinalities

I have taken a look at the following topics: number of infinite sets with different cardinalities Cardinality of all cardinalities Are there uncountably infinite orders of infinity? Types of ...
7
votes
2answers
411 views

axiom of choice: cardinality of general disjoint union

I have this exercise involving the axiom of choice, but I don't understand where it's needed: Let $(X_i)_{i \in I}$ and $(Y_i)_{i \in I}$ be pairwise disjoint sets with $|X_i| = |Y_i|$. Prove, using ...
6
votes
2answers
252 views

Proving existence of a surjection $2^{\aleph_0} \to \aleph_1$ without AC

I'm quite sure I'm missing something obvious, but I can't seem to work out the following problem (web search indicates that it has a solution, but I didn't manage to locate one -- hence the ...
6
votes
2answers
1k views

Why do the rationals, integers and naturals all have the same cardinality?

So I answered this question: Are all infinities equal? I believe my answer is correct, however one thing I couldn't explain fully, and which is bugging me, is why the rationals $\mathbb Q$, integers ...
4
votes
4answers
1k views

Cardinality of the Irrationals [duplicate]

Possible Duplicate: Proof that the irrational numbers are uncountable We previously proved that $\mathbb{Q}$, the set of rational numbers, is countable and $\mathbb{R}$, the set of real ...
1
vote
4answers
845 views

Proving $\mathbb{N}^k$ is countable

Prove that $\mathbb{N}^k$ is countable for every $k \in \mathbb{N}$. I am told that we can go about this inductively. Let $P(n)$ be the statement: “$\mathbb{N}^n$ is countable” $\forall n \in ...
-2
votes
2answers
442 views

Comparing the sizes of countable infinite sets [duplicate]

Possible Duplicate: Cardinality != Density? The theory: For the infinite set of natural numbers Aleph-naught indicates it's cardinality, and therefor any other set that is countable (using ...
30
votes
7answers
1k views

Refuting the Anti-Cantor Cranks

I occasionally have the opportunity to argue with anti-Cantor cranks, people who for some reason or the other attack the validity of Cantor's diagonalization proof of the uncountability of the real ...
15
votes
1answer
281 views

How to formulate continuum hypothesis without the axiom of choice?

Please correct me if I'm wrong but here is what I understand from the theory of cardinal numbers : 1) The definition of $\aleph_1$ makes sense even without choice as $\aleph_1$ is an ordinal number ...