Questions tagged [cardinals]

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

94
votes
1answer
6k 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 ...
72
votes
6answers
6k 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. ...
55
votes
5answers
5k views

Doesn't the unprovability of the continuum hypothesis prove the continuum hypothesis? [duplicate]

The Continuum Hypothesis say that there is no set with cardinality between that of the reals and the natural numbers. Apparently, the Continuum Hypothesis can't be proved or disproved using the ...
55
votes
7answers
11k 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 ...
54
votes
9answers
4k 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 ...
54
votes
7answers
23k views

Cardinality of set of real continuous functions

The set of all $\mathbb{R\to R}$ continuous functions is $\mathfrak c$. How to show that? Is there any bijection between $\mathbb R^n$ and the set of continuous functions?
54
votes
1answer
10k 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)?
39
votes
8answers
4k views

Is symmetric group on natural numbers countable?

I guess it is too difficult a question to ask about the cardinality of $S_{\mathbb{N}}$ so I would like to ask whether it is countable or not. I tried to prove it is uncountable somewhat mimicking ...
39
votes
4answers
15k 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)?
35
votes
2answers
4k 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 numbers....
33
votes
3answers
3k views

Is cardinality a well defined function?

I was wondering if the cardinality of a set is a well defined function, more specifically, does it have a well defined domain and range? One would say you could assign a number to every finite set, ...
32
votes
9answers
3k views

Why do we classify infinities in so many symbols and ideas?

I recently watched a video about different infinities. That there is $\aleph_0$, then $\omega, \omega+1, \ldots 2\omega, \ldots, \omega^2, \ldots, \omega^\omega, \varepsilon_0, \aleph_1, \omega_1, \...
31
votes
4answers
1k 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 ...
30
votes
3answers
1k views

What is the largest set for which its set of self bijections is countable?

I recently came across a problem which required some knowledge about the self bijections of $\mathbb{N}$, and after looking up how to construct some different bijections I came across the result that ...
28
votes
8answers
15k views

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

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

If the infinite cardinals aleph-null, aleph-two, etc. continue indefinitely, is there any meaning in the idea of aleph-aleph-null?

If the infinite cardinals aleph-null, aleph-two, etc. continue indefinitely, is there any meaning in the idea of aleph-aleph-null? Apologies if this isn't a sensible question, I really don't know too ...
26
votes
3answers
2k views

Do there Exist Proper Classes that aren't “Too Big”

Some proper classes are "too big" to be a set in the sense that they have a subclass that can be put in bijection with $\alpha$ for every cardinal $\alpha$. It is implied in this post that every ...
26
votes
4answers
12k 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 ...
25
votes
2answers
870 views

How many compact Hausdorff spaces are there of a given cardinality?

This is a question I found myself wondering about recently. I eventually figured out the answer myself, but as this doesn't seem to be written down anywhere easy to find on the Internet I decided to ...
25
votes
2answers
3k views

Cardinality of a Hamel basis of $\ell_1(\mathbb{R})$

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 2^{\...
24
votes
3answers
2k 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 ...
23
votes
6answers
5k views

Proof that the number of proofs is countably infinite

I think that the number of mathematical statements is countably infinite, since each statement is a finite string of finitely many symbols, but i am not sure how to prove it. Once i prove that, i can ...
23
votes
4answers
6k 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?
22
votes
3answers
2k views

Is there a set whose power set is countably infinite? [duplicate]

Does there exist a set whose power set is countably infinite? I know for sure that if a set has a finite number of elements, then its power set must have a finite number of elements, and if a set has ...
22
votes
2answers
3k 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 ...
21
votes
2answers
2k views

Are there number systems corresponding to higher cardinalities than the real numbers?

As most of you know, the set $\omega$ with cardinality $\aleph_0$ corresponds to what we normally know as the natural numbers $\mathbb{N}$, and the set $\mathcal{P}(\omega)$ with cardinality $\aleph_1$...
21
votes
1answer
1k 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 (...
21
votes
1answer
4k views

The cardinality of a countable union of countable sets, without the axiom of choice

One of my homework questions was to prove, from the axioms of ZF only, that a countable union of countable sets does not have cardinality $\aleph_2$. My solution shows that it does not have ...
20
votes
3answers
1k 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, what ...
20
votes
2answers
433 views

Does $\mathfrak{(p<q)\land(r<s)}$ imply $\mathfrak{p^r<q^s}$?

Does $\mathfrak{(p<q)\land(r<s)}$ imply $\mathfrak{p^r<q^s}$, where $\mathfrak{ p,q,r,s}$ are cardinal numbers? Is it possible to prove in $\mathsf{ZFC}$ that there is a counterexample?
20
votes
2answers
485 views

Covering $\mathbb R^2$ with function graphs

Suppose we have a countable family of function graphs (each function is $\mathbb R\to\mathbb R$, not necessary continuous). Obviously, they cannot cover the whole plane $\mathbb R^2$, because they ...
19
votes
5answers
1k views

Why study cardinals, ordinals and the like?

Why is the study of infinite cardinals, ordinals and the like so prevalent in set theory and logic? What's so interesting about infinite cardinals beyond $\aleph _0 $ and $\mathfrak{c} $? It seems ...
19
votes
3answers
3k 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 ...
19
votes
1answer
2k views

Do you need the Axiom of Choice to accept Cantor's Diagonal Proof?

Math people: It is my understanding that set theorists/logicians compare cardinalities of sets using injections rather than surjections. Wikipedia defines countable sets in terms of injections. ...
19
votes
4answers
1k views

What do the cosets of $\mathbb{R} / \mathbb{Q}$ look like?

$\newcommand{\R}{\Bbb R}\newcommand{\Q}{\Bbb Q}$ Looking at the group of real numbers under addition $(\R, +)$ it contains the (normal) subgroup of rational numbers $(\Q, +)$. I am wondering how to ...
18
votes
2answers
3k views

How many non-differentiable functions exist?

The size of the set of functions that map $\mathbb{R}\to \mathbb{R}$ equals $(\#\mathbb{R})^{\#\mathbb{R}}$. How many non-differentiable functions are there in this set?
18
votes
6answers
1k views

Why hasn't GCH become a standard axiom of ZFC?

I've never seen a text that includes GCH in the ZFC axioms. I presume this means that GCH has not achieved widespread acceptance. This seems surprising to me, given that: The cardinal numbers ...
18
votes
4answers
19k 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 ...
17
votes
2answers
3k views

Is aleph-$0$ a natural number?

Would I be right in saying that $\aleph_0 \in \mathbb N$? Or would it be a wrong thing to do?
17
votes
2answers
1k 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}< ...
17
votes
1answer
1k views

Bijection between power sets of sets implies bijection between sets?

Is it true that if $X$ and $Y$ are sets and there is a bijection between $\mathcal{P}(X)$ and $\mathcal{P}(Y)$ then there is a bijection from $X$ to $Y$ ?. I believe this should be obvious, but I can'...
17
votes
1answer
699 views

Cardinality of a locally compact Hausdorff space without isolated points

I am interested in the following result: Theorem. A locally compact Hausdorff topological space $X$ without isolated points has at least cardinality $\mathfrak{c}$. To prove it, one can find two ...
16
votes
5answers
7k views

cardinality of all real sequences

I was wondering what the cardinality of the set of all real sequences is. A random search through this site says that it is equal to the cardinality of the real numbers. This is very surprising to me, ...
16
votes
1answer
1k views

Medial Limit of Mokobodzki (case of Banach Limit)

A classical Banach limit is very usefull concept for me, but there is a problem with the integration and even with the measurability, this means for a sequence $(f_n)_{n\in \mathbb{N}}$ of measurable (...
16
votes
1answer
2k views

bound on the cardinality of the continuum? I hope not

Suppose we don't believe the continuum hypothesis. Using Von Neumann cardinal assignment (so I guess we believe well-ordering?), is there any "familiar" ordinal number $\alpha$ such that, for non-...
16
votes
3answers
1k views

Can sets of cardinality $\aleph_1$ have nonzero measure?

$\aleph_1$ is the cardinality of the countable ordinals. It is the least cardinal number greater than $\aleph_0$, and assuming the continuum hypothesis it's equal to $\mathfrak{c}$, the cardinality of ...
16
votes
1answer
479 views

How to reach $\aleph_1$ without power sets?

At the end of Set Theory and the Continuum Hypothesis, Paul Cohen wrote: A point of view which the author feels may eventually come to be accepted is that CH is obviously false. The main reason one ...
16
votes
1answer
243 views

There's no cardinal $\kappa$ such that $2^\kappa = \aleph_0$

I am trying to prove that there is no cardinal $\kappa$ such that $2^\kappa = \aleph_0$ . My attempt: We suppose it exists. Since $\kappa<2^\kappa$, in particular, $\kappa<\aleph_0$. But ...
16
votes
0answers
667 views

Formulations of Singular Cardinals Hypothesis

I have stumbled on a few different formulations of the Singular Cardinals Hypothesis. The most common are: SCH1: $\quad 2^{cf(\kappa)}<\kappa \ \Longrightarrow \ \kappa^{cf(\kappa)}=\kappa^+$ for ...
15
votes
5answers
1k views

Non-isomorphic structures of the same cardinality which are elementary equivalent

We usually give examples (es. ultrapowers) of elementary equivalent structures which are not isomorphic because they have different cardinalities? Can someone help me to find an example of two such ...