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)

3
votes
0answers
21 views

Proving that the Calkin-Wilf tree enumerates the rationals.

The Calkin-Wilf tree is an infinite undirected graph (tree) which is constructed as follows: starting from the root at $\frac{1}{1}$, each node $\frac{a}{b}$ has two children: a left child ...
2
votes
2answers
73 views

Proof of $\aleph_0^{\aleph_0} = \mathbb{c}$ without using Cantor's $2^{\aleph_0} = \mathbb{c}$

Prove that $\aleph_0^{\aleph_0} = \mathbb{c}$ without using Cantor's $2^{\aleph_0} = \mathbb{c}$ Card $\mathbb{N}^\mathbb{N} = \aleph_0^{\aleph_0}$ Card $(0, 1) = \mathbb{c}$ Define: $f: ...
0
votes
0answers
14 views

Family of infinite sets with finite intersections [duplicate]

I read somewhere that there exists a family of infinite sets $F \subset P_{inf}(\mathbb N)$, such that any two $X, Y \in F$ have a finite intersection and $\lvert F \rvert = \mathfrak c$. ...
1
vote
1answer
37 views

Where's the mistake in my reasoning?

Task: Find the cardinality of all such functions $f: P(\mathbb N) \rightarrow P(\mathbb N)$ that $f(\bigcup S) = \bigcup \lbrace f(Z) \mid Z \in S \rbrace$ The answer is: $\mathfrak c$ My ...
1
vote
2answers
46 views

Can you go from $\aleph_0$ to $\aleph_1$ with tetration or other higher order operators?

The paradox of Hilbert's Hotel shows us that you can not get past the cardinality of the natural numbers ($\aleph_0$) by adding a finite number (one new guest), adding an infinite quantity (infinitely ...
0
votes
1answer
31 views

Cardinal equality: $\;\left|\{0,1\}^{\Bbb N}\right|=\left|\{0,1,2,3\}^{\Bbb N}\right|$

I need to prove the above equality without Cantor-Bernstein Theorem or cardinals arithmetic (i.e., a bijection must be found). I know that for example $\;S\to 1_S=\;$ the indicator function, gives a ...
0
votes
1answer
55 views

Cardinality of the set of all bijections

Let $A$ be an infinite set and let $S$ be the set of all bijections $A \rightarrow A$. Then if $\mid A \mid = \kappa$, then $\mid S \mid = 2^\kappa$. I'm able to prove it for $A = \mathbb{N}$ by ...
4
votes
2answers
79 views

Why was $\aleph$ (aleph) chosen for infinities?

Why did Cantor choose a letter from the Hebrew alphabet to represent infinities, rather than using some Greek letter?
6
votes
1answer
90 views

Well-foundedness of cardinals and the axiom of choice

Without axiom of choice it is not generally true that the class of all cardinal (in this question we consider Scott cardinal rather than cardinals as ordinals) is not well-founded under the ordinary ...
0
votes
1answer
43 views

What result is $\left | \bigcup_{i \in I}A_i \right | =\sum_{i \in I} |A_i|$?

I'm reading a text that uses the following equality for disjoint sets $(A_i)_{i \in I}$: $$\left | \bigcup_{i \in I}A_i \right |=\sum_{i \in I} |A_i|$$ This has to do with disjoint unions, but I'd ...
2
votes
1answer
47 views

Cardinality of the set of functions $f: A \to B$ where where $|A|=\aleph_0$ and $|B|=2^{\aleph_0}$

Let $X$ be the set of all functions $f: A \to B$ where $|A|=\aleph_0$ and $|B|=2^{\aleph_0}$. Using some cardinal arithmetic, one can show that $|X|=2^{\aleph_0}$. However, I wanted to construct a ...
1
vote
3answers
34 views

Infinite-dimensional, countable, rational vector spaces.

Does such a thing exist? More explicitly, can I find a vector space $V$ over $\textbf{Q}$, such that $$\dim_\textbf{Q}V=+\infty$$ and $$\operatorname{card}V=\aleph_0$$?
3
votes
1answer
42 views

Countability of Collection of All Finite Subsets of a Countable Set

Let V be a countable set. Ok, first thing to say is that this isn't a question as to whether $S = \{ A \subseteq V \mid A \ \text{finite} \}$ is countable -- there are plenty of other duplicates on SE ...
1
vote
1answer
27 views

Multiplication Principle Proof

I am trying to prove the following; If $X$ and $Y$ are finite, then $|X \times Y| = |X||Y|$. Now, I'll define a bijection $g:\mathbb{N_{n}} \rightarrow X$ and a bijection $f: \mathbb{N_{m}} ...
0
votes
0answers
16 views

Is this Lindeloff theorem using AC? [duplicate]

Theorem: the following are equivalent: 1) The metric space $X$ is separable. 2) $X$ is second-countable (it has a countable basis) proof: $1 \Rightarrow 2: \lbrace B(d,r) : d\in D, r \in ...
2
votes
1answer
34 views

Alternate definitions of width (of a partial order) without Choice?

Say an antichain of a poset $P$ is a set of pairwise incomparable elements of $P.$ Typically, the width of a partial order is defined to be the supremum of the cardinalities of antichains of $P.$ When ...
1
vote
1answer
21 views

Cardinality of collection of subfields of $\mathbb C$

The question is just curiosity on my part. The title says it all. I can see that the cardinality is at least $\aleph_1$ (take simple extensions by an uncountable family of transcendental numbers). But ...
1
vote
3answers
40 views

Disprove bijection between reals and naturals

Coming across diagonalization, I was thinking of other methods to disprove the existence of a bijection between reals and naturals. Can any method that shows that a completely new number is created ...
1
vote
1answer
33 views

$A$ countable, $f :A \rightarrow B$ surjective. Prove $B$ is at most countable

My question is: can this be proven without using the almighty Axiom of Choice? Here's the idea of my proof using the axiom: We need an injective function from $B$ in $A$. Let $e$ be the choice ...
0
votes
0answers
49 views

Cardinality of the union and product of two sets without AC

We have the following results Let $A$ and $B$ be infinite sets s.t. $|A|=|B|$, then $|A\cup B|=|A|$. I was wondering if we can prove that without the Axiom of Choice or without using cardinal ...
0
votes
2answers
43 views

Cardinal of an infinite set

In our course about combinatorics, our maths teacher recently introduced to us the notion of cardinality with the following definition: Let $E$ be a set. If there exists an integer $n$ and a ...
3
votes
0answers
77 views

Minimal Possible Ordinal for a Cardinal

For a given $\aleph_\alpha$, what is the minimal ordinal possible such that $|\beta| = \aleph_\alpha$? More precisely, assume we have a model $N$ of ZFC. $N$ could be an extension of many different ...
2
votes
2answers
86 views

More numbers between $2$ and $4$ than between $2$ and $3$? (I am not a mathematician.) [duplicate]

Between $2$ and $3$ there are infinite numbers and between $2$ and $4$ there are infinite numbers. So which "infinity" is greater?
0
votes
1answer
46 views

Need a formal proof?

If A and B are two equipotent sets (they have 1-1 correspondence). Prove that if A is denumerable then B is also denumerable. It is easy to understand by intuition. But I can't understand how to ...
3
votes
1answer
58 views

What do you call a cardinal $\kappa$ that is a limit of $\kappa$-many cardinals?

For instance, $\omega$ is the limit of $\omega$-many cardinals. But of course $\omega_1$ is not the limit of $\omega_1$-many cardinals. 1) Are there cardinals other than $\omega$ with this property? ...
1
vote
3answers
167 views

Ordinal with given cardinality (without AC)

Is it possible to show that every cardinality has an ordinal with this cardinality (without the axiom of choice)? If so, how?
4
votes
2answers
170 views

Can every set be expressed as the union of a chain of sets of lesser cardinality?

If a set $S$ has countably many elements $\{x_n\}$, it can be expressed as a union of a chain of finite sets $$ \{x_1\} \subset \{x_1,x_2\} \subset $$ But what about a set of arbitrary cardinality ...
1
vote
1answer
56 views

Is this function one to one? Why? [closed]

Is the function $f:P(\mathbb{N})\to\mathbb{R}$ defined by $$f(A)=\sum_{n\in A}\dfrac{2}{3^{n+1}},\quad\forall\,\,A\in P (\mathbb{N}),$$ an one to one function? Please help understand why. For me, ...
0
votes
2answers
40 views

Cardinal of a difference of power sets

How can the following be calculated? Given the sets $X = \{1, 2, \dots, 10\}$ and $Y = \{1, 2, \dots, 12\}$, compute $| \mathcal P (Y) \setminus \mathcal P (X) |$, where $\mathcal P (X) = \{ A \mid A ...
2
votes
2answers
270 views

Where is the flaw in my Continuum Hypothesis Proof?

I am not a mathematician, but rather a computer engineer with a curious mind. The continuum hypothesis (CH) has gripped my attention today, and I even asked a question about it earlier today. ...
2
votes
1answer
83 views

Is this interpretation of the continuum hypothesis correct?

I am not a mathematician, but rather a computer engineer with a curious mind. The continuum hypothesis states (I believe) that there does not exist a set $S$ such that $\aleph_0 < |S| < ...
1
vote
2answers
68 views

Why are Aleph numbers by definition of the form $2^x$?

The first Aleph number is $\aleph_0$, and my question is this: why is the second Aleph number defined to be $\aleph_1 = 2^{\aleph_0}$? If I remember correctly, it had something to do with power sets ...
2
votes
2answers
53 views

Cardinality of the set of all real functions which have a countable set of discontinuities

I'm having a trouble calculating the cardinality of the set of all functions $f:\mathbb{R} \longrightarrow \mathbb{R}$ which have at most $\aleph_0$ discontinuities (let's call the set $M$). A hint ...
2
votes
1answer
44 views

Show that the union of two sets of the same cardinality has again the same cardinality.

Greetings great wise ones. Continuing my set-theoretic adventures, I have again stumbled upon a problem and need guidance. The original problem goes like this: Let $k_0 = \aleph_0$ and for any $n ...
0
votes
2answers
51 views

Unique infinite subsets of the integers

Edit: Great points on the comments. There is no unique set of unique infinite subsets of the integers. Is this a better question? What is the largest possible cardinality of a set which is a set of ...
27
votes
3answers
850 views

What is the largest set for which its set of self bijections is countable?

I recently came across a problem which required some knowledge about the self bijections of $\mathbb{N}$, and after looking up how to construct some different bijections I came across the result that ...
1
vote
0answers
31 views

Cardinality of Binary sets

Two questions I encountered in my last Set Theory HW. 1) Let T be a set of all Binary sequences that do not contain 2 consecutive zeros (ex. $100111010\notin T$). Let B be a set that contains all ...
4
votes
3answers
89 views

The cardinality of Indra's net?

This question has been asked before, but the title of the post was so general that it received no sufficient answer. What is the cardinality of the set of jewels and reflected jewels in Indra's Net? ...
7
votes
1answer
167 views

Can all Power Sets be Limit Cardinals?

Is it possible to create a model of ZFC, so that the cardinality of each power set is a limit cardinal (as opposed to GCH where they are always successor cardinals)? Take for example the following ...
10
votes
1answer
171 views

Cardinality of power sets decides all of cardinal arithmetic?

Assuming ZFC, is it possible to have two models which agree on the cardinality of all the power sets, but disagree on the cardinality of some other cardinal exponentiation (meaning that they agree on ...
0
votes
1answer
32 views

Defining a function that maps two sets

I am new to the topic of cardinality and I am trying to prove the following statement: "If $a$ is a natural number then $\mathbb{N} \setminus \{ a \}$ is denumerable. Here, $\mathbb{N} \setminus ...
0
votes
2answers
39 views

Applying power set finite times

Is every infinite set $A$ smaller than a set of the form $\mathcal P (\mathcal P(\dots \mathcal P(\mathbb N)))$?
2
votes
1answer
29 views

cardinal arithmetic: prove that $k_2^m>=k_1^m$ if $k_2>=k_1$

I could use some help on this problem: Suppose $k_1$, $k_2$, $m$ are cardinals. Given that $ k_2 \geq k_1$ prove that $ k_2^m\geq k_1^m$ . I know that I need to find a one to one function $f$ from ...
2
votes
3answers
79 views

Is there a set $A$ such that $|\mathbb Z|<|A|<|\mathbb R|$ is undecidable?

CH guarantees that the statement $|\mathbb Z|<|A|<|\mathbb R|$ is false for all $A$, but since $\sf CH$ is undecidable it might still be possible that there exist a set $A$ for which the ...
2
votes
2answers
71 views

Can I assume the continum hypothesis in a proof

I am showing that the cantor ternary set has the same cardinality as $\mathbb{R}$ I want to use the fact that it is uncountably infinite and a subset of $\mathbb{R}$. ($|N| < |C| \leq \mathbb{R}$) ...
4
votes
4answers
34 views

A surjective map $S \to T$ implies $|S| \geq |T|$

Problem: Suppose that there is a function mapping $S$ onto $T$. Show that $\operatorname{Card}(S)\ge\operatorname{Card}(T)$ Issue: I can't seem to find a reason why this follows. If $S$ maps ...
1
vote
1answer
19 views

Possible cardinalities of the equivalence partitioning

Let $\sim$ denote a relation in $\mathbb{R}$ as follows: $x \sim y \iff d(x,y) \in \mathbb{Q} $ ($d(x,y)$ is the distance between $x$ and $y$) Determine the possible cardinalities of the equivalence ...
2
votes
0answers
25 views

Cardinality of this equivalence class

I'm looking at the following equivalence relation on $\mathbb{Z}$: $a \sim b$ if and only if there exist $n,m \in \mathbb{N}_{>0}$ so that $a^n = b^m$ I'm trying to determine what the cardinality ...
1
vote
2answers
58 views

Cardinality of all rational points in $R^3$

Question: Find the cardinality of the set of all points in $R^3$ all of whose coordinates are rational, and justify the answer. Idea: Call the set of all points in $R^3$ all of whose coordinates are ...
2
votes
1answer
37 views

cardinality of the set of points with one irrational coordinate, and one rational.

Find the cardinality of the set of all points in the plane which have one rational and one irrational coordinate. Justify you answer. My thoughts so far. We know that $\mathbb Q$, the set of all ...