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,538
questions
1
vote
1
answer
26
views
How to define the sum of cardinals in the definition of an inaccessible cardinal?
I'm reading the Wikipedia definition of an inaccessible cardinal and I'm trying to understand it.
On Wikipedia, a (strongly) inaccessible cardinal $\kappa$ is defined in the following way:
$\kappa$ ...
- 10.2k
0
votes
0
answers
47
views
An infinite linear system of equations with an uncountable number $A$ of equations
I will start with an example to make things clear and avoid confusion :
Take all $x>0$ and
$$\exp(x) = \sum_{-1<n} a_n x^n$$
Now finding $a_n$ can be described as an infinite linear system of ...
- 15.3k
0
votes
1
answer
62
views
$H_\kappa = \{A: |TC(A)|<\kappa \} = \{A: (\forall x \in TC(\{A\})) (|x|<\kappa)\}$ for singular cardinal $\kappa$
$TC(A)$ is the transitive closure of $A$, $|x|$ is the cardinality of $x$, $\kappa$ is a cardinal number greater than $\aleph_0$ and $H_\kappa$ is the set of sets hereditarily of cardinality less than ...
- 100
1
vote
1
answer
46
views
How do I prove that my piecewise function is bijective
Question
Prove that the set $$\mathbb{N} \text{ and } S = {x\in \mathbb{R}|x^{2} \in \mathbb{N}}$$ have the same cardinality.
I drew an arrow diagram, and got this equation:
$$ f: \mathbb{N} \...
- 33
7
votes
1
answer
93
views
Is the dominating number of this continuum graph a small cardinal?
Define the relation $\sim$ over $\mathcal C := \{0, 1\}^{\mathbb N}$ given by $(x_n)_n\sim (y_n)_n$ iff $\exists^\infty k: a_{k+i} = b_{k+i},~i=0, 1, \dots, k-1$.
What is the least size of a subset $\...
- 2,239
1
vote
2
answers
55
views
Show that $\{\alpha<\omega_1 : L_\alpha \prec L_{\omega_1}\}$ is closed unbounded in $\omega_1$.
I was doing this exercise and there is a hint to consider the Skolem functions for $L_{\omega_1}$. However, I did not find any general definition of what a Skolem function may be in Kunen (1980), and ...
- 87
2
votes
0
answers
52
views
Cardinality of set of all rectangles on a plane
The set of rectangles in $\mathbb{R}^2$ with sides parallel to axes and bottom-left corner in origin can be described as:$$\mathcal{R}=\{[0,a]\times[0,b]:a,b\in\mathbb{R}\}$$
There is bijection $\...
1
vote
1
answer
80
views
Questions about the Infinite Monkey Theorem
(Context: the Infinite Monkey Theorem stipulates that given infinite time, a monkey can type out the complete works of Shakespeare, or any other text of finite length, just by randomly pressing keys.)
...
- 467
7
votes
1
answer
98
views
What does the cardinality alone of a totally ordered set say about the ordinals that can be mapped strictly monotonically to it?
For any cardinal $\kappa$ and any totally ordered set $(S,\le)$ such that $|S| > 2^\kappa$, does $S$ necessarily have at least one subset $T$ such that either $\le$ or its opposite order $\ge$ well-...
2
votes
0
answers
48
views
How to force character of ultrafilter be equal to $2^k$?
Let $k$ be an infinite cardinal. We already know there are exactly $2^{2^k}$ distinct non-principal ultrafilter on $k$.
Here The set of ultrafilters on an infinite set is uncountable. And proof uses ...
- 103
-1
votes
2
answers
74
views
When we say "cardinality of first order language L" and "cardinality of a structure or model" what we are meaning? [closed]
I ask about for what set we are referring for these cardinalities?
- 11
-1
votes
1
answer
45
views
Ordinal vs. Cardinal $0$ [closed]
From my files ...
$1, 2, 3, ...$ are cardinals, they count as in $9$ trucks, $12$ voles, etc.
First ($1^{st}$), Second ($2^{nd}$), etc. are ordinals, they're used to order stuff.
Now, I've heard of ...
- 725
1
vote
0
answers
55
views
What is the cardinality of the set of $x$-th roots of unity?
Consider the set of $x$-th roots of unity. What is its cardinality?
Formally, consider $x \in \mathbb{C}$, and let
$S_x = \{y \in \mathbb{C} \; : \;$ there exist $k, m \in \mathbb{Z}$ such that
$ x(\...
- 1
3
votes
1
answer
525
views
Is there really no family of humongous sets?
I've previously tried to define a meaningful notion of size for sets with this question. It turns out that the notion I tried to define was more then related to the one of measurable cardinals, which ...
- 2,239
1
vote
1
answer
119
views
Is there a family of humongous sets?
I'm once again trying to define a meaningful notion of size for sets.
Let $R$ be a set of size $\mathfrak c=2^{\aleph_0}$ and say $\mathcal F\subset \mathcal P(R)$ is a family of humongous sets if it ...
- 2,239
1
vote
1
answer
130
views
Why isnt $|\mathbb{R}| = |\mathbb{N}|$?
Question: To show that 2 sets have the same cardinality, there needs to be atleast one bijective mapping between them. So given the below proof of a bijective mapping below, why can't we say that $\...
4
votes
0
answers
90
views
Does $\dim \mathcal{L}(V,W) = \dim V \dim W$ hold for infinite dimensional vector spaces? If not when does it not hold? [duplicate]
I’m currently reading Alexer’s linear algebra done right. He proved in the book that $\dim \mathcal{L}(V,W) = \dim V \dim W$ holds if both $V$ and $W$ have finite dimension. I’m wondering if this ...
- 141
0
votes
1
answer
51
views
What is the cardinality of union countably infinite set, infinite time?
Here is the question from Master entry exam of computer science called KONKUR in IRAN:
What is cardinality of this:
$$\bigcup\limits_{i=1}^{\infty} N^i$$
As far as I concerned the right answer is ...
- 1
0
votes
0
answers
61
views
Cardinality with primes
My friend asked me this question. I would appreciate your understanding even if my English is not perfect.
For any prime number ${p}$, let's define a set ${P}$ that consists of all multiples of ${p}$. ...
- 1
4
votes
1
answer
97
views
Jech's proof of canonical well-ordering of $\alpha\times\alpha$.
I'm reading Jech's Set Theory. The canonical well-ordering of $\mathrm{Ord}\times\mathrm{Ord}$ is defined as
$$( \alpha ,\beta ) < ( \gamma ,\theta ) :\begin{cases}
\max\{\alpha ,\beta \} < \max\...
- 89
2
votes
0
answers
98
views
Does worldly cardinal exist if $\mathsf{ZFC}$ is consistent?
A worldly cardinal is a cardinal $\kappa$ such that $V_\kappa$ is a model of $\mathsf{ZFC}$. Please forgive me if this is very silly, but if $\mathsf{ZFC}$ is consistent (so there exists a model of $\...
- 1,318
2
votes
1
answer
85
views
Compact Hausdorff space, hereditarily Lindelöf but non-metrizable?
Is there a compact Hausdorff space that is hereditarily Lindelöf but non-metrizable? Under the continuum Hypothesis, such space exists (see the abstract of A compact L-space under CH by Kunen). I ...
- 1,216
0
votes
0
answers
169
views
The Axioms of 'Fictional Googology'
There have been questions on whether proper classes have cardinality (some say yes). However, I have my own axioms about it.
Firstly, we define the 'cardinality' of a proper class as the conglomerate ...
- 127
2
votes
1
answer
89
views
would diagonalization work in this scenario?
consider a countably infinite list of infinite strings.. such that each string has an ordinal of $ \ \bf ɷ.2 \ $, and the entire list also has an ordinal of $ \ \bf ɷ.2 \ $. Can we use cantor's ...
- 31
0
votes
0
answers
39
views
How is the following theorem the princple of *complete* induction?
The following is from page $19$ of Holz' Introduction to Cardinal Arithmetic.
As I understand it (see here), ordinary and complete induction (on $\omega$) work as follows:
Ordinary Induction: if $P(...
- 4,760
1
vote
0
answers
28
views
The existence of a function on $\kappa$
Let $\kappa>\omega$ be a regular cardinal. Let $C\subseteq\kappa$ be a club. Prove that there exists a function $f:\kappa\rightarrow\kappa$ such that $C_f=\{0<\alpha<\kappa:\forall\xi<\...
- 87
0
votes
0
answers
37
views
Prove that these sets are stationary.
Define Lim($\omega_1$)={$\delta<\omega_1\ :\ \delta$ is a limit ordinal}. Assume that $\left<A_\alpha:\alpha\in\text{Lim}(\omega_1)\right>$ is a sequence satisfying the following:
(1) $\...
- 87
1
vote
1
answer
77
views
Can this statement be proved without the Continuum hypothesis?
I was just learning about set theory and came across this exercise. It does not specify whether we work with CH as an axiom. The statement is easy to prove if CH is assumed, but I'm not sure where to ...
- 87
1
vote
1
answer
73
views
Cardinality of bijection of $\mathbb{N} \rightarrow \mathbb{N}$ using finite sets [duplicate]
I was solving the following exercise : Is $\mathfrak{S}(\mathbb{N})$ countable ? Here $\mathfrak{S}$ stands for the set of bijections from $\mathbb{N}$ to itself. A proof could be to build an ...
- 11
1
vote
1
answer
54
views
Dimension of function space $X \to \mathbb F$
Let $X$ be an arbitrary set, and let $\mathbb F$ be an arbitrary field. Functions $X \to \mathbb F$ form a vector space over $\mathbb F$, with pointwise addition and scalar multiplication. What is its ...
- 4,451
-1
votes
1
answer
71
views
Infinite recursion of function defined with respect to "every $n$" [closed]
I have very little formal mathematical training, so I apologize in advance for what may seem like basic issues in this question's phrasing.
I am trying to determine whether I can make a certain ...
- 101
0
votes
0
answers
46
views
Category Theory and Cardinality
This is a very basic question from Rotman's Homological Algebra text. I think the issue is that I don't know how to rigorously talk about cardinality.
Problem
If $\mathcal A$ is a small category (...
- 617
-2
votes
3
answers
64
views
Why is the cardinality of irrationals greater than of rationals?
If the rationals are dense in the rationals, meaning there is a rational between every 2 irrationals, then there is essentially a rational number for every irrational.
If there is aleph irrationals, ...
1
vote
2
answers
160
views
How to describe a function that depends on the cardinality of a vector with mathematical notation
I have to describe a code I have written using formal mathematical notation, but I don't know how to define an operation that depends on the number of elements.
Here's an example pseudocode:
...
2
votes
3
answers
111
views
Necessary and sufficient condition for $\left \lvert \mathbb{R} \big / \! \! \equiv \right \rvert = |\mathbb N|$
I was thinking about the following:
Let $\equiv$ be an equivalence relation on $\mathbb R$. What is the necessary and sufficient condition that $\equiv$ must satisfy in order for $\left \lvert \mathbb{...
- 4,443
0
votes
1
answer
52
views
Bound for the cardinality of the model of a set of formulas
I don't know if the proof of the theorem below is correct. The goal is to do the proof from the beginning, without using compactness or Löwenheim-Skolem. Only the Tarski-Vaught test (maybe).
We are ...
- 394
0
votes
0
answers
63
views
Does the proof that "a proper ascending chain of subsets of the naturals is countable" necessitate axiom of choice?
Let $(A_x)_{x\in X}$ be a collection of disjoint subsets of $\mathbb{N}$. Using the Axiom of Choice, i.e. assuming there exists a function $f:\{A_x\}_{x\in X}\to \bigcup_{x\in X} A_x$, with $f(A_x)\in ...
4
votes
1
answer
114
views
There is no surjective function from a set in the Hartogs number of its power set
I'm trying to prove an equivalent state of the Axiom of Choice :
Given two non-empty sets, there is a surjective function from one of them into the other one.
If we prove that for any non-empty set $X$...
- 169
2
votes
1
answer
63
views
Reference request for different definitions of finite
I understand that there are different definitions of finite. They are all equivalent over ZFC, and some of them are even equivalent over ZF, but not over weaker theories than ZF(C). I would like some ...
- 19.2k
0
votes
1
answer
68
views
Cardinality of union of sets of a given cardinality
I know that:
finite union of finite sets is a finite set
countable union of countable sets is a countable set
It is possible to characterize the sets $C$ of cardinals satisfying the following ...
- 15.9k
0
votes
0
answers
29
views
To show the cardinality of $\mathbb{R}$ and $\mathbb{R}^\mathbb{N}$ are same [duplicate]
I want to show that the cardinality of the countable infinite product of the set of real numbers $\mathbb{R}$ is same as the cardinality of $\mathbb{R}$. I am trying to find a bijection from $\mathbb{...
- 97
2
votes
0
answers
93
views
Cardinality of $[X]^\kappa$
In ZF, what do we know about the cardinality of the set
$$[X]^\kappa = \{ Y \subseteq X : |Y| = \kappa\},$$
where $X$ is a set and $\kappa$ is a cardinal?
- 769
1
vote
2
answers
97
views
Inequality Regarding Subtraction of Transfinite Cardinals. Is this correct? $\aleph_0 - \aleph_0 \le \aleph_0$
I've been learning about transfinite cardinals and examining the expression $\aleph_0 - \aleph_0$. I've read online that subtraction in this case is not defined because it can result in any finite ...
2
votes
2
answers
96
views
Torsion-free commutative groups of a given cardinality
If an abelian group $G$ is torsion-free, it has at least one subgroup isomorphic to $\Bbb{Z}$, given by $⟨g⟩ := \{ g^n | n \in \Bbb{Z} \}$, for any non-identity element $g$. This subgroup is obviously ...
- 5,598
-1
votes
2
answers
85
views
The rationals and their initial segments [closed]
My question was inspired by an Alon Amit post on Quora recently. The Quora problem posed to
AA was something like, only slightly more confused: how can the set of initial segments of the
rational ...
- 23
1
vote
1
answer
42
views
Is the cardinality of $L^1[0,1]$ greater than $\frak c$?
I am looking for a normed space whose completion has strictly larger cardinality. I have settled on the space $I^1[0,1]$ of simple functions on $[0,1]$ with completion $L^1[0,1]$ the space of ...
- 10.2k
0
votes
1
answer
55
views
VC dimension and Cardinality of real numbers
Is it true that the cardinality of a hypothesis class with finite VC dimension is less than the cardinality of real numbers?
My intuition is that the number of functions in a hypothesis class with ...
- 979
2
votes
1
answer
74
views
Is there a set-theoretic construction of tetration and even higher-order Ackermann functions?
Cardinal addition, multiplication, and exponentiation have set-theoretic constructions, namely disjoint union, cartesian product, and the set of all functions from $S$ to $T$, respectively. Are there ...
- 19.2k
0
votes
2
answers
50
views
Proving proper inequality of cardinality of sets is transitive
I need to prove the following:
If $A,B,C$ are sets (finite or infinite), such that $|A|< |B|$, and $|B| < |C|$ then $|A| < |C|$.
My proof:
Let $f:A \to B$ be in injective, since $|A| \le |B|$,...
- 23
-1
votes
1
answer
54
views
Given |A\B| = |B\A|, prove |A|=|B| and provide 2 sets (A and B) such that |A| = |B| but |A\B| is not the same as |B\A|
Part A : Given |A\B| = |B\A|, prove |A|=|B|
Part B : Provide 2 sets (A and B) such that |A| = |B| but |A\B| is not the same as |B\A|
Part A:
Let A,B be sets. Given that |A\B| = |B\A| then |A|=|B|
Hint ...
- 137