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.

Filter by
Sorted by
Tagged with
1
vote
1answer
18 views

Cardinality of a nested set

What is the cardinality of {a,{b,{c,d,e},{f,{g}}}}? I think it's 2 because the set length of the broadest {} is 2, but I am not sure if the set being nested will affect the cardinality.
1
vote
0answers
21 views

Addition of infinite cardinal numbers

Recently while trying to prove the Schröder–Bernstein theorem, I stumbled upon a fact that, if $m$ and $n$ are two cardinal numbers such that atleast one of them is infinite, then $m+n= \max\{m,n\}$. ...
1
vote
1answer
36 views

Let $X,Y$ be the collections of all finite subsets of $A$ and $B$ respectively. Assume $|X| \le |Y|$. Is it true that $|A| \le |B|$?

In proving the dimension of infinite-dimensional vector space is well-defined, I come across below question. Let $A,B$ be sets. Let $X,Y$ be the collections of all finite subsets of $A$ and $B$ ...
0
votes
0answers
14 views

Selection function for all non-empty subsets of $\mathrm{R}$ [duplicate]

Task is to find a function, which for any non-empty subset of the reals, gives an element of this subset. For this easy looking problem, something none of the ideas worked, what my IT-accustomed mind ...
1
vote
1answer
42 views

Cardinality of tail transformation

I am reading this article, "A non-measurable tail set" by Blackwell and Diaconis. In this article we don't have axiom of choice, we just suppose that there exists a free ultrafilter on $\...
0
votes
0answers
31 views

A problem about decomposition of infinite set?

I am using lee larson's lecture note on introductory real analysis for self learning. And I am stucking in one problem which is like this: If $S$ is an infinite set, then there is a countably ...
1
vote
1answer
39 views

Cardinality of the image of injection

Claim: Let $f: S \to T$ be an injection and $A$ be a finite subset of $S$. Then, $$ |f[A]| = |A| $$ that is, there is a bijection from $f[A]$ onto $A$. ProofWiki proves this fact using mathematical ...
1
vote
0answers
45 views

Does $|\mathcal{P}(X)| = |\mathcal{P}(Y)|$ imply $|X| = |Y|$? [duplicate]

For any sets $X$ and $Y$, does $|\mathcal{P}(X)| = |\mathcal{P}(Y)|$ imply $|X| = |Y|$? It is well-known that the converse true; for a bijection $f: X \to Y$, we can define the bijection $g: \mathcal{...
0
votes
3answers
109 views

Is $2^{\aleph_0}$ well-defined?

Ok so I was thinking about power sets and mathematics that utilize infinity, and I ended up thinking about power sets for $\aleph_0$. Knowing that to get a power set you take $2$ and raise it to the $...
0
votes
0answers
67 views

How to prove if sets A and B satisfy $|A\cup B|=|\mathbb R|$, then $|A|=|\mathbb R|$ or $|B|=|\mathbb R|$?

I saw this problem when I'm learning set theory and real analysis. This problem can easily be solved if we acknowledge The continuum hypothesis(CH), because if the cardinality of A or B is not bigger ...
4
votes
1answer
90 views

An informal debate on the cardinality of infinite sets

A friend and I have been engaged in a lively discussion on prime numbers. I'll cut to the chase right away. They ask: If you were to write out all of the even numbers and then all of the pairs of ...
-5
votes
0answers
26 views
0
votes
0answers
34 views

how is cardinality of free ultrafilters to be understood

Let $X$ be an infinite set, $F$ the set of filters and $U$ the set of free ultrafilters on $X$. Then for the cardinalities we have $|U| \leq |F| \leq 2^{2^{|X|}}$. I have found several proofs that we ...
1
vote
0answers
41 views

Trying to understand the proof that the bounding number $\mathfrak{b}$ is uncountable

Background For two functions, $f,g \in {}^\omega\omega$ we say that $g$ dominates $f$, denoted $f<^*g$, if for all but finitely many integers $k\in\omega$, $f(k)<g(k)$. A family $\mathscr{B}\...
-1
votes
0answers
20 views

the set of nonrecursive sequences of pos. int. is uncountable

A sequence $a_{n}$ of positive integers is called recursive if there is a positive integer k such that $a_{n} = x_{1}a_{n−1} + ... + x_{k}a_{n−k}$ holds for all $n > k$, where $x_{1}, ..., x_{k}$ ...
-1
votes
0answers
44 views

Numbers/cardinal numbers [closed]

so i had two classes this semester abstract algebra and philosophy of math. I enjoyed them both but there is one thing that i have been trying to understand all the semester and just can't get ...
2
votes
1answer
46 views

Necessary and sufficient condition on the cardinal number of quotient set

I'm studying for an exam, and I have found question that I'm not sure about how to solve it. The question is: Let A be finite set. Let R be equivalence relation on A. 1.Write necessary and sufficient ...
0
votes
1answer
34 views

is the cardinality function sigma-additive?

I am confused by how these facts are consistent: i. If $A$ and $B$ are disjoint sets, then $|A| + |B| = |A \cup B|$ [1] ii. If $S = \{x : x \in [0,1] \} $, then $|S| \neq 0$, $|\mathbb{R} - S| = |\...
0
votes
1answer
36 views

Proof of set cardinality equation $|2^S|=|S×2^S|$

Let $S$ be a non-empty set, such that $|S|=|S+S|$. Prove that $|2^S|=|S×2^{S}|$. I found an answer for $\mathbb{N}$. It is possible to just construct two injective functions and finish the proof by ...
10
votes
1answer
216 views

Which ordinals can be "mistaken for" $\aleph_1$?

I've just finished working my way through Weaver's proof of the consistency of the negation of the Continuum Hypothesis in his book Forcing for Mathematicians. One of the key points in this proof is ...
0
votes
0answers
11 views

Cofinality of a limit ordinal equal to cofinality of normal operation - Clarification

I'm a bit confused by the solution sketch in this post: Cofinality of a limit ordinal is equal to the cofinality of a given normal operation - Proof. For reference, the question answered is the ...
0
votes
1answer
37 views

Cardinality of a language $L_\Sigma$ over a decidable signature $\Sigma$

In the middle of a proof of a theorem I was studying, in order to prove a cardinality argument, there was the following statement: Note that $|L_\Sigma|=|\Sigma|+ \aleph_0$ Where $L_\Sigma$ is a ...
1
vote
1answer
75 views

Is $\alpha < \beta \to 2^\alpha < 2^\beta$ provable in ZF+V=HOD?

Is the following a theorem of ZF + V=HOD? $\kappa < \lambda \to 2^\kappa < 2^\lambda$ Where $<$ is cardinal strictly smaller than. I know that this is not a theorem of ZFC. Of course, it is a ...
2
votes
2answers
39 views

Is the number of 3-dimensional slices slices of a 5-dimensional space less than the number of 3-dimensional slices of a 4-dimensional space?

I’m only in high school, so I’m not certain whether I could have used better terminology to describe this. I’m initially thinking of it using dimensional analogy. I think, tentatively, that the ...
1
vote
0answers
40 views

Show that there exists a bijection between $\mathbb{N^N}$ and $2^\mathbb N$.

I have see somewhere that ${\aleph_0}^{\aleph_0}=2^{\aleph_0}$.That means that $|\mathbb{N^N}|=|2^\mathbb N|$.I want to show explicitly that there exists a bijection between $\mathbb {N^N}$ and $2^\...
2
votes
1answer
89 views

Several forcing axioms imply $2^{\aleph_0 }= \aleph_2$. What about $2^{\aleph_1}$?

On the one hand, it seems intuitive that $2^{\aleph_1 }> 2^{\aleph_0}$, because $\aleph_1 > \aleph_0$. However, I also know that, like many things involving the continnum function, that's ...
0
votes
1answer
39 views

What is the cardinality of the set of untyped $\lambda$-calculus functions? I know it’s an infinity, but is it countable or uncountable?

What is the cardinality of the set of untyped $\lambda$-calculus functions? I know it’s an infinity, but is it countable or uncountable? Let $\Lambda$ be the set of untyped $\lambda$-calculus ...
3
votes
1answer
62 views

Concerning $\kappa+\kappa=\kappa$ for any infinite cardinal $\kappa$

In Introduction to Set Theory by Hrbacek and Jech, on page 94, the authors state that $\aleph_0+\aleph_0=\aleph_0$, and the Axiom of Choice implies that $\kappa+\kappa=\kappa$ for any infinite ...
1
vote
0answers
70 views

When does proof by contradiction occur in Cantor's diagonalization proof?

Cantor's diagonalization argument says that given a list of the reals, one can choose a unique digit position from each of those reals, and can construct a new real that was not previously listed by ...
0
votes
1answer
97 views

What is the cardinality of countable union of infinite sets?

Let $X=\underset{n\in\mathbb{N}}{\bigcup} X_n$ and each $X_n$ has infinite cardinality $\alpha$. What is the cardinality of $X$ ? Is this $\aleph_0\alpha$ ?
1
vote
2answers
126 views

Cardinality Of $n^{\aleph_0}$ for cardinals $n$ up to $\aleph_0$?

Considering The Continuum Hypothesis in it's most simplified form States that $|\mathbb{R}| = 2^{\aleph_0} = \aleph_1$. Is $3^{\aleph_0} = |\mathbb{R}| = 2^{\aleph_0} = \aleph_1$? what about other $n\...
0
votes
1answer
73 views

Confusion over the definition of cardinality

In Abbott's Understanding Analysis, he defines cardinality as follows: The set $A$ has the same cardinality as $B$ if there exists $f : A → B$ that is 1–1 and onto. In this case, we write $A ∼ B$. Do ...
4
votes
1answer
212 views

Can you "undo" a powerset of an infinite set?

So for instance, if you take the Beth numbers as a sequence of infinite cardinal numbers: $\beth_0=\aleph_0$, $\beth_1=\mathcal{P}(\beth_0)$, $\beth_2=\mathcal{P}(\beth_1)$, etc., where $\beth_{\alpha+...
0
votes
1answer
63 views

Bijection between $\{0,1\}^\omega$ and the set of positive integers

I have studied the first sections of "Munkres, J.R., Topology". In section 7 I find a theorem (7.7) that states that the set $\{0,1\}^\omega$ ($=\{0,1\}\times\{0,1\}\times\cdots$), i.e., the ...
5
votes
1answer
85 views

Showing a Set is Uncountable (Using Cantor's Diagonalization)

Good day! Found this tricky exercise in an elementary set theory course: Given the set: $L = \mathcal{P}(\mathbb{N} \times \mathbb{N}) \setminus {}^\mathbb{N}\mathbb{N}$ (where ${}^\mathbb{N}\mathbb{...
2
votes
1answer
89 views

Why are Aleph Cardinal Numbers "strictly increasing"?

perhaps my title isn't very clear, I'll try to be more precise: The definition I'm using is that (for the "successor" step of the recursion) $\aleph_{\alpha+1}$ is the smallest cardinal ...
1
vote
1answer
73 views

Is it possible to construct a function $f: \mathbb{R} \rightarrow \mathbb{Z}$ such that $f$ is injective?

this was a true and false question which I mistakenly thought was false. My reasoning was thus: Let the function $f: \mathbb{R} \rightarrow \mathbb{Z}$ be injective. It follows that for every element $...
0
votes
1answer
67 views

Proof that the cardinality of an uncountably infinite set $S$ is equal to the cardinality of $S\setminus \{x\} $, $ x $ being an element of $S$.

I have to prove that for some uncountably infinite set $ S$ and $x \in S$ the cardinality of $S$ is equal to the cardinality of $S \setminus \{x\}$. I have proven that this is the case for countably ...
0
votes
0answers
26 views

Separating weight of discrete space.

Recall that a cover $\mathscr{A}$ of a set $E$ is separating if for each pair of distinct points $p,q\in E$ there is $A\in \mathscr{A}$ such that $p\in A$ and $q\not\in A$. The separating weight of a $...
1
vote
0answers
24 views

An upper bound for the continuum hypothesis [duplicate]

The ZFC set theory cannot prove (nor disprove) the continuum hypothesis. However, is this theory powerful enough to give an upper bound ? What I mean by this is a result like : $$ 2^{\aleph_0} \leq \...
0
votes
1answer
12 views

What is the lower ordinal bound for the smallest fixed point of derivations with infinitary rules

Assume $J$ is a set (of judgments). A rule is a pair $(P,c)$ with $P\subseteq J$ and $c\in J$ with the reading that $P$ is a set of preconditions and $c$ is the conclusion. A system of rules is a set $...
2
votes
2answers
80 views

Do hypercontinuous fields exist?

"Hypercontinuity" is a cardinality of a continuous set's power set (set of all subsets). When talking about fields, I mean the cardinality of field's set. At first glance there is nothing ...
0
votes
0answers
39 views

How to prove and define amount of countably infinite set in the naturals numbers

I have the following question Picture of the question What is the cardinality of $D=\{A \subseteq \Bbb N \mid \vert A \vert = \aleph_0 \land \vert \Bbb N \setminus A \vert = \aleph_0 \}$? I do ...
0
votes
1answer
61 views

Quick question about inaccessible cardinals

I am trying to find a source that states, it is consistent with ZFC that weakly inaccessible cardinal does not exist. Can I please get some sources? It was quite hard for me to find such. Indeed, I ...
0
votes
2answers
56 views

Let A = $\left\{1,\:2,\:\left\{1,\:2\right\}\right\}$, how many elements are in the set $P(A)\setminus A$?

My thinking: A = $\left\{1,\:2,\:\left\{1,\:2\right\}\right\} $ (which contains three elements) The power set of $A$, $P(A)$ then contains $2^3 = 8$ elements which are: $P(A) = \left\{\right\},\:\left\...
0
votes
2answers
55 views

Prove that a field of a set has $2^r$ elements if it has finite cardinality.

Prove that a field of a set $A$ has $2^r$ elements if it has finite cardinality. The definition of algebra is given here "https://en.wikipedia.org/wiki/Field_of_sets" My try: I was trying to ...
3
votes
3answers
71 views

Compact cardinal cannot be successor?

This is a follow-up question to $\kappa$ is compact $\implies$ $\kappa$ is regular. The definition I'm using for "compact" is the same as there. I am trying to show if $\kappa$ is compact, ...
1
vote
2answers
110 views

Bijection between $3^{\mathbb N}$ and $\mathcal P(\mathbb N)$?

Since $\mathcal P(\mathbb N)$ is the set of all subsets of $\mathbb N$, For each element $a \in \mathbb N$ and every subset $S\subset N$, we can define a function $f$: $f(a) = 0$ if $a \notin S$ $f(a) ...
0
votes
1answer
21 views

$ (1*...*1)(n) =\# \{(m_1,...,m_k)\in (\mathbb{N}\setminus \{0\})^k : m_1...m_k = n\} $

We call an arithmetic function any element of $\mathcal{F} (\mathbb{N}\setminus \{0\} , \mathbb{C})$. We endow $\mathcal{F} (\mathbb{N} \setminus \{0\}, \mathbb{C})$ binary operation convolution and ...
0
votes
0answers
55 views

How to construct a one-to-one function from $\mathbb{R}$ to a perfect set $P$?

Let, $ P$ be a non empty perfect subset of $\mathbb{R}$ . Then, as an application of Baire Catagory theorem, I can show that the set $P$ is uncountable. As we know any uncountable subset of $\mathbb{R}...

1
2 3 4 5
65