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.
3,592
questions
2
votes
1
answer
38
views
Saturation of infinite complete Boolean algebra is a regular cardinal
Similar question existed here. However there are still many gaps for stupid persons like me.
A Boolean algebra $B$ is called $\kappa$-saturated if there is no antichain with supremum $1$ (also called ...
0
votes
0
answers
55
views
Finite cardinals raised to the power of an infinite cardinal
I am trying to prove the fact that if $a$ and $b$ are finite cardinals, and $c$ is an infinite cardinal, then $a^c = b^c$. I am able to prove this fact by using $d \cdot d = d$ for all infinite ...
0
votes
0
answers
41
views
Prove that an infinite well ordered set X has equal cardinality to the set X∪{a}, where 'a' does not belong to X.
Found this question in a book of analysis as a corollary. Before the question is introduced (as an exercise), the book introduced Theorem of Recursion on Wosets and Comparability Theorem. For ...
-1
votes
0
answers
42
views
The cardinality of a certain subset of the vertices of $[-1,1]^n$ [closed]
Let $A=\left\{(\alpha_1,\dots,\alpha_n)\mid \alpha_i\in\{-1,1\},~\forall i=1,\dots,n\right\}$. I.e., $A$ is the set of vertices of the hypercube $[-1,1]^n$. Let $B$ be a subset of $A$ such that any ...
1
vote
0
answers
36
views
What is the cardinality of the Diffeomorphism group $\text{Diff}(\mathbb{R})$ over the reals?
As a small set-up, we have $\aleph_0$ as the cardinality of $\mathbb{N}$, and then the cardinality of the reals $\mathbb{R}$ is $\beth_1 = 2^{\aleph_0}$. In particular, it turns out that this is also ...
0
votes
2
answers
59
views
Prove cardinality of R2 without creating a map to R1
I think we can prove $|\mathbb{R}^2|=\aleph_1$, by creating a bijection between $\mathbb{R}$ and $\mathbb{R}^2$. But this map is difficult to construct. Is there any easier way to show $|\mathbb{R}^2|=...
5
votes
2
answers
95
views
Why does countability misbehave in intuitionistic logic
On page 3 of this paper https://arxiv.org/pdf/2404.01256.pdf
I spotted the claim:
Definitions of countability in terms of injection into ℕ misbehave intuitionistically, because a subset of a ...
0
votes
1
answer
83
views
Is there a way to construct larger cardinals without choice axiom?
From Cantor's Theorem, we know that $|\mathcal{P}(X)| > |X|$. So, we can define inductively a set with cardinality $\aleph_n, \forall n \in \mathbb{N}$. Let $\lbrace A_i\rbrace_{i \in \mathbb{N}}$ ...
0
votes
0
answers
49
views
Is this Proof Involving Cardinal Arithmetic Correct?
Question
Show that for $n>0$,
$n.2^{2^{\aleph _0}}=\aleph _0.2^{2^{\aleph _0}}= 2^{\aleph _0}.2^{2^{\aleph _0}}= 2^{2^{\aleph _0}}.2^{2^{\aleph _0}}=(2^{2^{\aleph _0}})^n=(2^{2^{\aleph _0}})^{\...
3
votes
1
answer
96
views
Among 101 dalmatian dogs, each dog has a unique number of black spots, Addition property
Among 101 dalmatian dogs, each dog has a unique number of black spots from the set {1, 2, 3, . . . , 101}. We choose any 52 of the 101 dogs. We want to prove that any set of 52 dogs satisfies the ...
14
votes
1
answer
309
views
Combinatorial proof, without axiom of choice, that for any set $A$, there is no surjection from $A^2$ to $3^A$
The well known proof of Cantor's theorem (stating that $A<2^A$ for any set $A$) does not make any use of the axiom of choice. I have now spent some time wondering if the analogous result $A^2<3^...
13
votes
2
answers
812
views
Infinite wacky race
Dick Dastardly is taking part in an infinite wacky race. What is infinite about it, you ask? Well, just everything! There are infinitely many racers, every one of which can run infinitely fast and the ...
0
votes
1
answer
180
views
Fixing my gripe with the common proof for showing that $|\mathcal{P}(\mathbb{N})| = |\mathbb{R}|$
I am familiar with the proof that shows the powerset of the naturals is of the same cardinality as the reals using binary representation. Here's a quick rundown of the proof:
Showing that $f:(-1, 1) \...
2
votes
1
answer
71
views
How can I count the number of eventually constant functions $\kappa_1\to\kappa_2$?
Given two infinite cardinals $\kappa_1,\kappa_2$, what's the number $\tau$ of functions $f:\kappa_1\to\kappa_2$ that are eventually constant? I think that, if $\tau_0$ is the number of eventually zero ...
3
votes
1
answer
63
views
Is it consistent with ZC that a well-order of type $\omega_\omega$ does not exist?
Working in Zermelo's set theory (with choice for simplicity) - the construction in Hartogs' theorem shows that starting with a set $X$, there is a set $X'$ in at most $\mathcal{P}^4(X)$ (where $\...
2
votes
1
answer
112
views
$\{A_i\}, \{B_i\}$ are chain of sets indexed by the same linearly ordered set. If $|A_i|\le |B_i|$ for all $i$, does $|\cup A_i|\le |\cup B_i|$?
Let $I$ be a linearly ordered set and $\{A_i\}, \{B_i\}$ be two collection of sets indexed by $I$,
in an order-preserving way (i.e. $A_i\subsetneqq A_j\iff i<j$ and $B_i\subsetneqq B_j\iff i<j$)....
0
votes
0
answers
80
views
Show that $\mathcal{O}$ the set of all open sets in $\mathbb{R}$ has the same cardinality as $\mathbb{R}$
I've seen the post from here Prove that the family of open sets in $\mathbb{R}$
has cardinality equal to $2^{\aleph_0}$
This post is somewhat complex for me, and I turned it to the question as my ...
0
votes
0
answers
25
views
what is the probability of sampling a uniform distributed uncountable set and recieving a certain countable subset
I would assume that the chance would be $0%$ as $0=\lim\frac{1}{n}$ but since the equivalent would be something along the lines of $\frac{\aleph_0}{\aleph_1}$ I am not sure.
If $0=\frac{\aleph_0}{\...
0
votes
0
answers
82
views
Are there infinite sets whose aleph and beth numbers are both unknown?
Is there a set $S$ that is definable in ZFC and known to be infinite, but for which we know neither the aleph nor beth number?
For example, we do not know the aleph number of $|\mathbb R|$, but we ...
1
vote
1
answer
67
views
Using Surreal Numbers to measure function growth rate - Tetration?
In "The Book of Numbers" by John H. Conway, pg. 299, he discusses the application of surreal numbers to quantifying the growth rate of functions.
He gives the following correspondences:
$$\...
1
vote
1
answer
112
views
$\omega$-th or $(\omega + 1)$-th when putting odd numbers after even numbers?
The following clip is taken from Chapter 4 - Cantor: Detour through Infinity (Davis, 2018, p. 56)[2]. When putting odd numbers after even numbers, what should the index for the first odd number ($1$ ...
0
votes
1
answer
110
views
Set theory - functions: Given that $|A|=|B|$, how to prove that $|A^C|=|B^C|$?
Given that $|A|=|B|$ (the cardinality of set $A$ is equal to the cardinality of $B$).
How can I prove that $|A^C|=|B^C|$ (the cardinality of the set of all functions from $C \longrightarrow A$ is ...
0
votes
0
answers
60
views
Cofinality of $\beth_\lambda$ and increasing of beth sequence
Premise. I was given the following definition of beth-numbers:
$$ \beth_\alpha := \begin{cases}
\beth_0 = \aleph_0 \\
\beth_{\alpha + 1} = 2^{\beth_\alpha} \\
\beth_{\lambda} = \bigcup_{\alpha < \...
0
votes
1
answer
80
views
Cardinality of Schemes
I was thinking about set theoretic considerations of scheme theory and a question came to me.
I was wondering if there is a way to bound the cardinality of a scheme $S$ (the underlying set of the ...
0
votes
1
answer
42
views
Infinite Series of infinite cardinals in ZFC
$\sum_{n=0}^\omega 2^{\aleph_n}=2^{\aleph_\omega}$
Is this true?
And is there a way in ZFC to let $\infty$ range over ALL infinite ordinals (not a concrete one as in the example above) ?
$\sum_{n=0}^\...
7
votes
1
answer
167
views
Show the existence of family of sets
Show that there exists a family with cardinality of $c$, of subsets of $\mathbb{N}$, such that an intersection of any three elements of the family is an infinite (countable) set and the intersection ...
1
vote
0
answers
56
views
How is transifnite recursion applied?
I've been struggling to understand how ordinal addition, multiplication, and exponentiation, along with the Aleph function $\aleph$, are defined using Transfinite Recursion in Jech's Set Theory or ...
2
votes
0
answers
62
views
Correctness of Proof and Use of Axiom of Choice (Analysis I by Terence Tao)
I've skipped over some of the references in my proof for brevity. The following is an exercise from Terence Tao's Analysis I, specifically section 8.1. on countablity. ("countable" here ...
2
votes
1
answer
80
views
What is cardinality of ordinal exponentiation?
Using von Neumann definition of ordinals, is it true that for all cardinal numbers $a$ and $b$ the following equation holds:
$$
a^b = |a^{(b)}|
$$
where on the left side is the cardinal exponentiation ...
2
votes
1
answer
62
views
If $\kappa$ is weakly inaccessible, then it is the $\kappa$th element of $\{\alpha: \alpha =\aleph_\alpha\}$
This is an exercise from Kunen:
Exercise I.13.17 If $\kappa$ is weakly inaccessible, then it is the $\kappa$th element of $\{\alpha: \alpha =\aleph_\alpha\}$. If $\kappa$ is strongly inaccessible, ...
0
votes
0
answers
43
views
The cardinal number of a set from Cylindrical Sigma-algebra.
Let $\mathbb{R}^{[0,1]}$ be the set of all function on $[0,1]$, and $\mathcal{B}(\mathbb{R}^{[0,1]})$ be the sigma-algebra generated by all cylinder sets:
$$\{ x=x(t):(x(t_1),\ldots,x(t_n))\in B \}$$ ...
3
votes
0
answers
86
views
Basis for a $\sigma$-algebra of cardinality $\beth_1$. [duplicate]
Given a $\sigma$-algebra $\Sigma$ on a set $\Omega$, let's borrow language from topology, and call $B\subseteq\Sigma$ a basis for $\Sigma$ if $\Sigma$ is generated solely from countable unions of $B$, ...
0
votes
1
answer
110
views
Shouldn't ℵ₀ be the cardinality of the reals?
If in ZFC any set can be well ordered, and that $\aleph_0$ is the cardinality of every infinite set that can be well ordered, shouldn't $\aleph_0$ be the cardinality of the real numbers?
I know this ...
1
vote
0
answers
52
views
How does $2^{\aleph_2} \leqslant \aleph_{\omega}$ imply $\aleph_{\omega}^{\aleph_2} = \aleph_{\omega}^{\aleph_0}$? [duplicate]
I'm currently studying for my set theory exam and I got stuck trying to prove that if $2^{\aleph_2} \leqslant \aleph_{\omega}$ then $\aleph_{\omega}^{\aleph_2} = \aleph_{\omega}^{\aleph_0}$. Any help ...
2
votes
1
answer
79
views
Does a cardinal with uncountable cofinality imply that the cardinal is regular?
In our book we use for our classes, we often require cardinals to be uncountable regular cardinals (when proving stuff with cofinality/stationarity...). We often use that by creating some sort of ...
2
votes
1
answer
58
views
Does a separable, $US$, sequential space have cardinality at most the continuum?
Let $X$ be a separable sequential space with unique sequential limits ($US$). Can we prove that $X$ has cardinality at most $\mathfrak c=2^{\aleph_0}$?
Context.
If $X$ were Fréchet-Urysohn instead of ...
2
votes
1
answer
164
views
What ways are there to define $\aleph$?
I've seen some posts on this website that consist in providing and comparing different proofs of a theorem (e.g. for Taylor's Theorem or trigonometric identities). Currently I'm reading Holz's ...
2
votes
1
answer
58
views
Why does regularity of an ordinal $\gamma$ imply the existence of a sequence $(\delta_n)$ such that $\delta_n<\gamma$ for all $n$?
Source: Set Theory by Kenneth Kunen.
Lemma III.6.2: Let $\gamma$ be any limit ordinal, and assume that $\kappa:=cf(\gamma)>\omega$. Then the intersection of any family of fewer than $\kappa$ club ...
0
votes
0
answers
25
views
Ordering and dividing orders of infinity.
I read there are an infinite number of orders of infinity.
Can they all be ordered, or are there different orders we can identify where we do not know which has the greater cardinality?
Is the ratio ...
0
votes
1
answer
58
views
Proof of the Reflection Theorem in Kunen?
I'm reading Kunen's Set Theory and the last line of the proof of the Reflection theorem (page 131) is a bit puzzling to me. To those not in possession of Kunen at the moment, the book states verbatim:
...
0
votes
0
answers
27
views
Being unbounded in a limit ordinal implies order type is also a limit?
Whilst trying to follow a proof from my lecture notes, I stumbled upon the following:
$$\gamma \text{ limit, }A\subseteq \gamma, \sup A=\gamma\implies \text{type}(A)\text{ limit}$$ It sounds true, ...
1
vote
1
answer
59
views
Why do we define cardinality only for well-orderable sets?
I'm revising Kunen's Set Theory and he mentions that when we define the cardinality of a set, we should do it with well-orderable sets. Why is this the case? He points to a section which contains many ...
2
votes
1
answer
87
views
How the comparison of the cardinalities of sets affects the cardinalities of their powersets [duplicate]
In my question, I denote by $|\cdot|$ the cardinality of any set. Moreover, if $f: X \to Y$, we denote by $\mathcal{P}f$ its direct image, i.e. $\mathcal{P}f(A)=\{f(a) : a \in A\}$. Let $X,Y$ be two ...
1
vote
0
answers
44
views
How many homomorphisms are there from the graph Cycle 5 to the Peterson Graph?
I’m struggling to work out how many there are. Currently I know there’s 12 unique cycle 5s in the Peterson graph, so by rotation and flip rotation there’s 10 different possibilities. Does this mean ...
0
votes
0
answers
103
views
Paradox: Creating an uncountable set of natural numbers
Consider the following (contrived) way of enumerating and counting the natural numbers.
Step 1.
Enumerate the first numbers 0 and 1. These are all the numbers less than $2^1$. Collect these numbers ...
1
vote
0
answers
32
views
$\mu^\lambda = 2^\lambda$ for infinite $\mu$ and $\lambda$
The original question is (from Mathematical Logic, A course with Exercises):
Assume Axiom of Choice, let $a$ and $b$ be 2 infinite sets with $\text{card}(a)=\lambda$ and $\text{card}(b)=\mu$. Assume $\...
0
votes
1
answer
54
views
Cardinality of the set of bounded sequences in $\Bbb N$
This is from "Mathematical logic, A course with exercises" Chapter 7 question 7. The question is to determine the cardinality of
$\{f\in {\mathbb N}^{\mathbb N}: (\exists p\in \mathbb N)(\...
1
vote
2
answers
84
views
The set of all countable subsets of $X := \{0,1\}^\omega$ has the same cardinality as $X$. Does this generalize to larger sets?
Let $X$ be $\{0,1\}^\omega$, which can be thought of as the set of all sequences of $0$ and $1$s.
In Munkries Topology, an exercise in section 1-7 asks to show that the set of all countable susbsets ...
0
votes
1
answer
109
views
Group action & cardinality of a set.
You can find here more details and explanation on this question.
Question:
Let $n$ be a non-negative integer. For any family $ (i_1, \ldots, i_r) $ of non-negative integers such that $ i_1 + \ldots + ...
1
vote
1
answer
59
views
Cardinality of subset of the real numbers [closed]
In a response I read, someone stated that any uncountable subset if the real numbers had the cardinality of the real numbers. Is this true and if so where can I find a reference to that result?