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

6
votes
5answers
336 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
334 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
575 views

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

Can we even find examples of infinity in nature?
6
votes
3answers
661 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
290 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

How to understand the regular cardinal?

How to understand the regular cardinal? Could someone give me some examples?
6
votes
2answers
327 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
501 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
724 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
326 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
483 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
273 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
112 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
213 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
197 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
150 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
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
144 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
144 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
321 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
2answers
155 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
387 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
188 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
319 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
110 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
200 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
212 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
799 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
326 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
69 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
249 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
163 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
155 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
1answer
202 views

Question about the order of a Stationary subset of $ \kappa$

Greets I'm trying to prove one part of exercise 8.14 of Jech's "Set Theory", namely that if $o(k)\geq k$, then $k$ is weakly inaccessible, where $\kappa$ is regular; $o(\kappa)$ is defined as ...
6
votes
2answers
795 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
361 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
141 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
133 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
127 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
202 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
85 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
367 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 ...
6
votes
1answer
366 views

cardinality of infinite sets

prove or disprove: If two infinite sets $A$,$B$ have the same cardinality, then $A\cup B$ and $A$ have the same cardinality. I even cannot make a judgement. P.S: Can this be done without using ...
6
votes
1answer
372 views

What is the standard proof that $\dim(k^{\mathbb N})$ is uncountable?

This is my (silly) proof to a claim on top of p. 54 of Rotman's "Homological algebra". For $k$ an infinite field (the finite case is trivial) prove that $k^\mathbb{N}$, the $k$-space of functions ...