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)

6
votes
2answers
123 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
679 views

Cardinal Arithmetic versus Ordinal Arithmetic

I am reading Philosophy, not Set Theory, so please excuse the naivety of my question. My question concerns the wildly different character of ordinal arithmetic versus cardinal arithmetic. The ...
6
votes
2answers
208 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
3answers
937 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
366 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
2answers
2k 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 ...
6
votes
1answer
92 views

$ZFC^- + AFA$ and infinite cardinals

$ZFC^-+AFA$ is a non-well-founded set theory, where $ZFC^-=ZFC-FA$ is $ZFC$ without the axiom of foundation, and $AFA$ is an anti-foundational axiom With the axiom of foundation we have that every ...
6
votes
1answer
84 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
285 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
127 views

Why do $2^{\lt\kappa}=\kappa$ and $\kappa^{\lt\kappa}=\kappa$ when the Generalized Continuum Hypothesis holds?

I'm going to assume GCH here. If that holds, then why do we have the equalities $2^{\lt\kappa}=\kappa$ for every $\kappa$, and $\kappa^{\lt\kappa}=\kappa$ for all regular $\kappa$?
6
votes
1answer
179 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
2k views

What is known about the power set of the real number line?

Cantor's theorem states that the cardinality of a set's powerset is strictly greater than that of the set itself. This clearly applies to the reals also; if I'm not mistaken, the cardinality of the ...
6
votes
2answers
502 views

Let $X$ and $Y$ be countable sets. Then $X\cup Y$ is countable

Since $X$ and $Y$ are countable, we have two bijections: (1) $f: \mathbb{N} \rightarrow X$ ; (2) $g: \mathbb{N} \rightarrow Y$. So to prove that $X\cup Y$ is countable, I figure I need to define ...
6
votes
1answer
83 views

Why we use $\mathrm{Fn}(\kappa\times\lambda,2,\lambda)$ to force $2^\lambda\ge\kappa$ instead of $\mathrm{Fn}(\kappa\times \lambda,2)$

I am reading Kunen's Set Theory and I learn that, $\operatorname{Fn}(\kappa\times\omega,2)$ forces $2^{\aleph_0}\ge|\kappa|$, where $$\operatorname{Fn}(I,J,\lambda)=\{p:p\text{ ...
6
votes
1answer
96 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
418 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
147 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
143 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
207 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
202 views

Exercise on partially ordered sets from Kunen's *Set Theory*

This problem is Exercise (F4) from Chapter VII of Kunen's text. Apparently, it is a result of Tarski. It goes as follows: Let $ \mathbb{P} $ be a partial order. Define $ \text{c.c.}(\mathbb{P}) $ ...
6
votes
1answer
150 views

Dominating strategically $\omega_1$ reals

For a given $\kappa > \omega$, define the game $d(\kappa)$ that runs for $\omega$ stages as follows: At stage $n$, player I chooses a sequence of elements of $\omega$, $g_n$ of length $\kappa$, and ...
6
votes
1answer
417 views

List of explicit enumerations of rational numbers

A well-known mathematical fact is that the rational numbers are countable, i.e. there is a bijective function $$f:\mathbb{N}\rightarrow \mathbb{Q}$$ I am interesting in making a list of all explicit ...
6
votes
1answer
388 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
385 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
394 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 ...
6
votes
0answers
133 views

Is there an upper bound to the number of rings that can be obtained from a semigroup with zero by defining an additive operation?

Let $\mathscr S$ be the class of all semigroups with zero. For $(S,\times,0)\in\mathscr S,$ I want to count additive operations $+$ on $S$ such that $(S,+,\times,0)$ is a ring (possibly without ...
5
votes
3answers
896 views

Prove that transcendental numbers exist: Are there less paniful ways of doing it?

I've found this exercise on Boolos' Logic and Computability: A real number $x$ is called algebraic if it is a solution to some equation of the form: $$c_{\small d}x^{\small ...
5
votes
2answers
662 views

Why are infinite cardinals limit ordinals?

My book states this as obvious, but it isn't so trivial to me. thanks
5
votes
2answers
2k views

How to understand the regular cardinal? [closed]

How to understand the regular cardinal? Could someone give me some examples?
5
votes
3answers
128 views

$|\mathbb{R}^\mathbb{R}|$ vs $|P(\mathbb{R})|$ Which is bigger?

$|\mathbb{R}^\mathbb{R}|$ vs $|P(\mathbb{R})|$ where $\mathbb{R}^\mathbb{R} =\{f | f:\mathbb{R} \rightarrow \mathbb{R}\}$ Are they equal? Which is bigger? How can I prove it?
5
votes
3answers
311 views

Question about Generalized Continuum Hypothesis

I wonder how the Generalized Continuum Hypothesis reveal that $A\times A$ is equivalent to $A$? $A$ is any infinite set.
5
votes
3answers
469 views

How many $p$-adic numbers are there?

Let $\mathbb Q_p$ be $p$-adic numbers field. I know that the cardinal of $\mathbb Z_p$ (interger $p$-adic numbers) is continuum, and every $p$-adic number $x$ can be in form $x=p^nx^\prime$, where ...
5
votes
2answers
506 views

In set theory, what does the symbol $\mathfrak d$ mean?

What's meaning of this symbol in set theory as following, which seems like $b$? I know the symbol such as $\omega$, $\omega_1$, and so on, however, what does it denote in the lemma? Thanks ...
5
votes
2answers
2k 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 ...
5
votes
1answer
671 views

Cofinality of cardinals

I have read some of the related questions (cofinality and its consequences, for example) about cofinality, but I still have no idea how to calculate the cofinality of an aleph. So, let's say I have ...
5
votes
3answers
225 views

Question on a proof from Jech's Set Theory of: If $X$ is a set of cardinals, then $\sup X$ is a cardinal.

The proof: Let $\alpha= \sup X$. If $f$ is a bijective mapping of $\alpha$ onto some $\beta < \alpha$, let $\kappa \in X$ be such that $\beta < \kappa \le \alpha$. Then $|\kappa|=|\{f(\xi): \xi ...
5
votes
3answers
339 views

What does $H(\kappa)$ mean?

As the typical references (Wikipedia, Mathworld, etc.) don't seem to address this satisfactorily, I figured this would be a good place to put a nice formal definition. Hence: I've heard that if ...
5
votes
1answer
123 views

Is $\alpha^{\beta}=2^{\beta}$ for all infinite cardinalities $\alpha, \beta$?

Is $\alpha^{\beta}=2^{\beta}$ for all infinite cardinalities $\alpha, \beta$? I was wondering about this since I've encountered examples of times where this holds, but I can't seem to prove it myself ...
5
votes
2answers
2k 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 ...
5
votes
1answer
159 views

What is the value of $\aleph_1^{\aleph_0}$?

Is there any neat way to calculate the value of $\aleph_1^{\aleph_0}$?
5
votes
3answers
347 views

The cardinality of a countable union of sets with less than continuum cardiality

Can continuum be a countable union of sets with cardinality, less than continuum? I can prove it for a finite union by mathematical induction from this: $\mathbb R = A_1 + A_2 => |\mathbb R| = ...
5
votes
1answer
414 views

Intuition about the size of $\aleph_k$ with $k>1$

Assuming CH for simplicity, I know of some more or less intuitive way to think about difference in sizes of $\aleph_0$ and $\aleph_1$. The most straightforward is the distinction of natural/rational ...
5
votes
4answers
701 views

Problems about Countability related to Function Spaces

Suppose we have the following sets, and determine whether they are countably infinite or uncountable . The set of all functions from $\mathbb{N}$ to $\mathbb{N}$. The set of all non-increasing ...
5
votes
4answers
686 views

Cardinality of Irrational Numbers

I know and I have proved more than once that the set of irrational numbers ($\mathbb{I}$) is uncountable, but now I'm given to solve this problem: Show that $|\mathbb{I}|=|\mathbb{R}|$, How can I ...
5
votes
2answers
718 views

some elementary questions about cardinality

I know little about set theory and while reading some Algebra proof I had difficulty on some details. So my questions are : If $X$ is an infinite set and $Y$ is the set of all finite subsets of $X$, ...
5
votes
2answers
153 views

What is the value of $\beth_{\omega_1}^{\aleph_0}$?

It is well known that $\beth_\omega^{\aleph_0} = \beth_{\omega+1}$. This follows since for strong limit $\kappa$, we have $\kappa^\kappa = \kappa^{\mathrm{cf}(\kappa)}.$ Question. To the extent that ...
5
votes
3answers
260 views

Uncountable Cardinals without AC

I am doing an exercise, proving that without AC or Replacement that there are uncountable cardinals. As a point of reference I looked at the proof in Kunen's "The Foundations of Mathematics" that ...
5
votes
5answers
173 views

$\mathrm{card} ( \mathbb{Q})=\mathrm{card}( \mathbb{Q^c})$: Overcoming Wrong Intuition

This is a widespread intuitive argument, asserting that $\mathrm{card} ( \mathbb{Q})=\mathrm{card}( \mathbb{Q^c})$: Between any two rational numbers there's an irrational one and vice versa. So ...
5
votes
2answers
104 views

Question about proof of Hessenberg: $\kappa \cdot \lambda = \lambda$

The following is a theorem: (Hessenberg) Let $1 \le \kappa \le \lambda$ where $\lambda$ is an infinite cardinal. Then $\kappa \cdot \lambda = \lambda$. The proof in the book proceeds by transfinite ...