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.

learn more… | top users | synonyms (1)

7
votes
1answer
139 views

$(\beth_{\omega})^\omega=\beth_{\omega+1}$

I'm trying to show that $(\beth_{\omega})^\omega=2^{\beth_\omega}$. This is an exercise in Kunen where he suggests to encode subsets of $\beth_\omega$ with functions from ...
7
votes
0answers
114 views

AC iff $P(\delta)$ can be well-ordered for all $\delta\in{\bf On}$ [duplicate]

I'm trying to do the following exercise: Exercise. Assume ZF. Then AC is equivalent to the statement that $P(\delta)$ can be well-ordered for all $\delta\in{\bf On}$. I'm struggling with the ...
6
votes
3answers
747 views

How do we prove the existence of uncountably many transcendental numbers?

I know how to prove the countability of sets using equivalence relations to other sets, but I'm not sure how to go about proving the uncountability of the transcendental numbers (i.e., numbers that ...
6
votes
5answers
343 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 ...
6
votes
4answers
1k views

What is the set of all functions from $\{0, 1\}$ to $\mathbb{N}$ equinumerous to?

What is the set of all functions from $\{0, 1\}$ to $\mathbb{N}$ equinumerous to? I have figured out the question when it's the other way around, but I am not making any progress here. The worst thing ...
6
votes
3answers
337 views

What is the first cardinal number which is grearter than continuum?

What is the first cardinal number which is grearter than continuum? We denote it by ? Thanks very much.
6
votes
3answers
584 views

Can we distinguish $\aleph_0$ from $\aleph_1$ in Nature?

Can we even find examples of infinity in nature?
6
votes
3answers
666 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?
6
votes
2answers
300 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
333 views

prove cardinality rule $|A-B|=|B-A|\rightarrow|A|=|B|$

I need to prove this $|A-B|=|B-A|\rightarrow|A|=|B|$ I managed to come up with this: let $f:A-B\to B-A$ while $f$ is bijective. then define $g\colon A\to B$ as follows: $$g(x)=\begin{cases} ...
6
votes
2answers
506 views

What is the Cardinality of the Nameable Numbers?

Having just finished "Meta Math!" (Chaitin), I came across an interesting observation on infinite sets that I hadn't seen before. If I'm correct (and please let me know if I'm not): 1] There are ...
6
votes
2answers
727 views

Cardinality of sets of subsets of $\mathbb{N}$

If we dont assume CH, is there a procedure to construct or define a set of subsets of $\mathbb{N}$ such that we cannot prove it to be of cardinality $\aleph_0$ or $\aleph_1$? Or if we assume not CH, ...
6
votes
1answer
247 views

is there a cardinality between the rational and the irrationals?

Was asked this question, and I have no idea about how to start proving it. Could someone give me some good reference material to start with.
6
votes
5answers
330 views

Are there more real numbers than we can actually imagine?

I mean, if we could imagine all the real numbers then we could assign each number a finite sentence (or a finite book). Since the set of the finite books is countable then the set of real numbers ...
6
votes
6answers
1k views

Proof that aleph null is the smallest transfinite number?

The wikipedia page on the cardinal numbers says that $\aleph_0$, the cardinality of the set of natural numbers, is the smallest transfinite number. It doesn't provide a proof. Similarly, this page ...
6
votes
3answers
501 views

Easiest way to prove that $2^{\aleph_0} = c$

$\aleph_0$ is the cardinality of the set of natural numbers, $\aleph_0 = |N|$. $c$ is the cardinality of the continuum, i.e. the set of real numbers $c = |R|$. I know that $|P(A)| = 2^{|A|}$. This ...
6
votes
1answer
277 views

What is the cardinality of the set of all sequences in $\mathbb{R}$ converging to a real number?

Let $a$ be an real number and let $S$ be the set of all sequences in $\mathbb{R}$ converging to $a$. What is the Cardinality of $S$? Thanks
6
votes
1answer
115 views

What is the cardinality of $\Bbb{R}^L$?

By $\Bbb{R}^L$, I mean the set that is interpreted as $\Bbb{R}$ in $L$, Godel's constructible universe. For concreteness, and to avoid definitional questions about $\Bbb{R}$, I'm looking at the set ...
6
votes
2answers
225 views

Confusion about cofinality

I'm confused about the notion of the cofinality of a cardinal. Since I think the source of the confusion is the Von Neumann cardinal assignment, my first question is: Question 0. Is there an article ...
6
votes
2answers
199 views

Is it viable to ask in an infinite set about the Cardinality?

Can you ask given an infinite set about its cardinality? Does an infinite set have a cardinality? So, for example, what would be the cardinality of $+\infty$?
6
votes
2answers
2k 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 ...
6
votes
2answers
151 views

What is the product of finitely indexed alephs?

I'm simply curious about why the following equality holds: $ \displaystyle\prod_{n\lt\omega}\aleph_n=\aleph_\omega^{\aleph_0}. $ Much thanks!
6
votes
2answers
333 views

Fodor's lemma on singular cardinals

Fodor's lemma asserts that if $\kappa$ is a regular and uncountable cardinal, then if $f(\alpha)<\alpha$ for a stationary subset of $\kappa$, then it is constant on stationary subset. Suppose ...
6
votes
1answer
854 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 ...
6
votes
2answers
134 views

Skolem's paradox and models in set theory

Say you have a model $M$ (of $\mathsf{ZF}$) containing a set $S$ that you know is countable outside the model but the enumeration is missing from the model so that $S$ appears to be uncountable in ...
6
votes
2answers
146 views

Sum of cardinals without AC

Let $A$ and $B$ be infinite sets. To show $|A\cup B|=\max\{|A|,|B|\}$ we need AC. Now let us assume $|A|<|B|$. Can we show $|A\cup B|=|B|$ without AC?
6
votes
3answers
148 views

Cardinality of a some linear ordering is at most that of a given cardinal?

This is an intuitive idea that I've used for a while, but don't know how to explain formally. Suppose $(A,\prec)$ is some linear ordering, and each initial segment of $A$ has cardinality strictly ...
6
votes
2answers
2k views

Cartesian Product of Two Countable Sets is Countable

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

In ZF, how would the structure of the cardinal numbers change by adopting this definition of cardinality?

In ZFC, a good way of ordering sets by cardinality is by leveraging the notion of an injection. We define: $$X \lesssim Y \leftrightarrow \mbox{ there exists an injection } X \rightarrow Y.$$ ...
6
votes
1answer
396 views

Can an infinite cardinal number be a sum of two smaller cardinal number?

Let $\kappa$ be an infinite cardinal number. My question is whether there are $\lambda$ and $\mu$ such that both $<\kappa$ but $\lambda+\mu=\kappa$? If AC holds, then the answer is definitely ...
6
votes
2answers
189 views

What is the product of all nonzero, finite cardinals?

To be specific, why does the following equality hold? $$ \prod_{0\lt n\lt\omega}n=2^{\aleph_0} $$
6
votes
2answers
320 views

mahlo and hyper-inaccessible cardinals

Wikipedia states that a Mahlo cardinal is hyper-inaccessible, hyper-hyper-inaccessible, etc. Is this a characterisation of Mahlo? If not what about "alpha = hyper^alpha-inaccessible" with the obvious ...
6
votes
2answers
113 views

Does $\sf GCH$ imply that every uncountable cardinal is of the form $2^\kappa$?

I think that this is a popular fallacy that GCH implies that every uncountable cardinal is of the form $2^\kappa$ for some $\kappa$. I think it does imply that for successor cardinals only. It cannot ...
6
votes
2answers
203 views

What happens after the cardinality $\mathfrak{c}$?

While having measure theory this year the following came in my mind: When we go from finite objects to infinite we "lose" a lot of properties. For example the summation isn't well defined ...
6
votes
2answers
217 views

Can proper classes also have cardinality?

In some set theories such as ZF+GAC, in which GAC is global axiom of choice, the Von Neumann universe $V$ bijects to $Ord$, the class of ordinals. It suggests us that proper classes may also have ...
6
votes
3answers
816 views

Number of countable subsets of $\mathbb{R}$

More generally, if a set $S$ has cardinality $\mathfrak{m}$, how many of its subsets have cardinality $\mathfrak{n}$? Clearly there are at least $2^\mathfrak{n}$ such subsets. I don't see how many ...
6
votes
1answer
336 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 ...
6
votes
1answer
70 views

How to show $\kappa^{cf(\kappa)}>\kappa$?

For $\kappa \geq \omega$, which is a cardinal, then how to show $\kappa^{cf(\kappa)}>\kappa$? My idea: When $\kappa=\aleph_\omega$, then $cf(\kappa)=\omega$, is $\kappa^\omega>\kappa$? It seems ...
6
votes
2answers
1k views

How do you prove the trichotomy law for cardinal numbers?

Law of trichotomy is that for any two cardinals $a$ and $b$, exactly one of the conditions $a<b$, $a=b$, or $a>b$ holds.
6
votes
1answer
252 views

Number of well-ordering relations on a well-orderable infinite set $A$?

Given a well-orderable infinite set $A$, can we always say that the set $$\left\{R\in A\times A:\langle A,R\rangle\, \text{is a well-ordering}\right\}$$ has cardinality $2^{|A|}$? How much Choice is ...
6
votes
1answer
166 views

Sequence of surjections imply choice

I am reading a paper where a side remark said that if a sequence $\langle g_\beta\colon\omega\to\beta\mid\beta<\omega_1\rangle$ is a sequence of surjections then $\omega_1$ is regular. I have ...
6
votes
1answer
161 views

How to prove that a regular cardinal cannot be expressed as a union of sets with less cardinality?

My question is about the following: Using the Axiom of Choice show that: If $\kappa\ge\omega$ is a regular cardinal, $\gamma\le\kappa$, and $\langle A_\alpha\mid\alpha\lt\gamma\rangle$ is a ...
6
votes
2answers
805 views

Non-existence of a surjection $\aleph_n \to \aleph_{n+1}$, without the axiom of choice

Firstly, let's establish what exactly I mean by these symbols. Let $\omega_0 = \{ 0, 1, 2, \ldots \}$, where $0, 1, 2, \ldots$ are the usual von Neumann representations of the natural numbers. Let $n$ ...
6
votes
1answer
93 views

$V=L[A]$ implies GCH for $A\subset \aleph_1$

On page 14 of the introduction to Vol. II of Gödel's collected works: By a slightly more difficult argument one can show that GCH continues to hold if $V=L[a]$ and $a\subseteq\aleph_1$. Does ...
6
votes
1answer
375 views

On cardinality of equivalence classes

Say $R$ is the set of all Riemann integrable functions $f:[a,b]\rightarrow \mathbb{R}$. We define an equivalence relation in $R$ as follows: $f$ and $g$ are said to be integrally equivalent iff they ...
6
votes
2answers
143 views

Effective cardinality

Consider $X,Y \subseteq \mathbb{N}$. We say that $X \equiv Y$ iff there exists a bijection between $X$ and $Y$. We say that $X \equiv_c Y$ iff there exist a bijective computable function between ...
6
votes
1answer
135 views

$\kappa <\operatorname{cf}(2^\kappa)$ without König's inequality

How can I prove $\kappa<\operatorname{cf}(2^\kappa)$ inequality without using König's inequality? We got this as a practice exercise, but I don't know how to approach this without König. Any hint ...
6
votes
1answer
129 views

Instance of Continuum Hypothesis implying cardinal inequality

I'm currently trying to solve Exercise 5.27 of Jech's Set Theory (3rd Millennium ed.), viz: If $2^{\aleph_1}=\aleph_2$, then $\aleph_{\omega}^{\aleph_0} \ne \aleph_{\omega_1}$. The presumption ...
6
votes
1answer
206 views

How to explain that $\Bbb{R}$ is not countable to a non-mathematician

What is the best way to explain that $\Bbb{R}$ is not countable assuming that the audience is formed of people who are not mathematicians? I ask this because these days I'm in a debate with someone ...
6
votes
1answer
372 views

Finding the cardinality of a set

I have to construct a few things before I get to my question: it's possible we don't need all of it, but I am stuck on the very last step so I should recap everything so far. Let $\kappa$ be a ...