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
154 views

What is the product of finitely indexed alephs?

I'm simply curious about why the following equality holds: $ \displaystyle\prod_{n\lt\omega}\aleph_n=\aleph_\omega^{\aleph_0}. $ Much thanks!
5
votes
1answer
135 views

Filter completeness question

I have a question about filters which I suspect has a very simple answer (hence my asking it here as opposed to MO): Let $F$ be a filter on an infinite set $X$. Then $F$ is "countably closed" if for ...
6
votes
2answers
200 views

What is the product of all nonzero, finite cardinals?

To be specific, why does the following equality hold? $$ \prod_{0\lt n\lt\omega}n=2^{\aleph_0} $$
6
votes
3answers
168 views

Cardinality of a some linear ordering is at most that of a given cardinal?

This is an intuitive idea that I've used for a while, but don't know how to explain formally. Suppose $(A,\prec)$ is some linear ordering, and each initial segment of $A$ has cardinality strictly ...
5
votes
1answer
419 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 ...
2
votes
2answers
2k views

How to Understand the Definition of Cardinal Exponentiation

I'm having trouble understanding the definition of cardinal exponentiation. Let's start with the definitions / claims I've been given: For any finite sets $A,B$, such that if $|A|=a$ and $|B|=b\neq ...
9
votes
2answers
556 views

axiom of choice: cardinality of general disjoint union

I have this exercise involving the axiom of choice, but I don't understand where it's needed: Let $(X_i)_{i \in I}$ and $(Y_i)_{i \in I}$ be pairwise disjoint sets with $|X_i| = |Y_i|$. Prove, using ...
3
votes
2answers
2k views

Union of Uncountably Many Uncountable Sets

I know that the union of countably many countable sets is countable. Is there an equivalent statement for uncountable sets, such as the union of uncountably many uncountable sets is uncountable? ...
0
votes
1answer
154 views

Cardinality of Set of Simple Closed Curves

What is the cardinality of the set of all simple closed curves in $R^2$? Furthermore, what resources are there which present a proof, if any, of said cardinality?
5
votes
4answers
705 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 ...
1
vote
1answer
137 views

Cardinality of set of normal functions $f \colon \omega_{\alpha} \to \omega_{\alpha}$

What is the cardinality of the set of all normal functions $f \colon \omega_{\alpha} \to \omega_{\alpha}$, where $\omega_{\alpha}$ is the initial ordinal of $\aleph_{\alpha}$?
8
votes
1answer
432 views

For every $n < \omega$, $\aleph_n^{\aleph_0} = \max(\aleph_n,\aleph_0^{\aleph_0})$

I have proved that if $\aleph_n \leq \aleph_0^{\aleph_0}$, then $\aleph_n^{\aleph_0} \leq \max(\aleph_n,\aleph_0^{\aleph_0})$. Clearly $\aleph_n \leq \aleph_n^{\aleph_0}$ and $\aleph_0^{\aleph_0} \leq ...
5
votes
3answers
475 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 ...
4
votes
4answers
575 views

What is the cardinality of the group of bijections from $\Omega$ to $\Omega$ with finite support?

These questions cropped up in the discussion in this question, What is the cardinality of the group of bijections from $\Omega$ to $\Omega$ with finite support, where $\Omega=\mathbb{N}$? ...
4
votes
3answers
2k views

Cardinality and infinite sets: naturals, integers, rationals, bijections

I have alot of questions. Do Infinite sets have the same cardinality when there is a bijection between them? Are $\mathbb{N}$ and $\mathbb{Z}$ infinite sets? I assume they are, but why? Why does ...
7
votes
2answers
395 views

Implications of continuum hypothesis and consistency of ZFC

I've been a bit confused whilst doing some reading. I think the confusion arises because I am trying to read Wikipedia on topics without being able to work along. Anyway, I have read that, of course, ...
4
votes
1answer
74 views

$|S_X|=|S_Y| \Leftrightarrow |X|=|Y|$

Reading this problem I remembered trying to solve the following problem. For a set $A$, denote by $S_A=\{ f : A \to A | f \text{ is bijective }\}$. Denote by $|X|$ the cardinal number of $|X|$. ...
7
votes
4answers
598 views

Fractional cardinalities of sets

Is there any extension of the usual notion of cardinalities of sets such that there is some sets with fractional cardinalities such as 5/2, ie a set with 2.5 elements, what would be an example of such ...
4
votes
4answers
2k views

Cardinality of the Irrationals [duplicate]

Possible Duplicate: Proof that the irrational numbers are uncountable We previously proved that $\mathbb{Q}$, the set of rational numbers, is countable and $\mathbb{R}$, the set of real ...
3
votes
2answers
225 views

How can I show that the set of reals and the set of pairs of reals have the same cardinality?

How can I show that the set of reals and the set of pairs of reals have the same cardinality? I know that since reals are uncountable infinite, I can't create a list of reals and talk about the ...
9
votes
2answers
2k views

Cartesian Product of Two Countable Sets is Countable

How can I prove that the Cartesian product of two countable sets is also countable?
8
votes
1answer
582 views

What is the cardinality of a set of all monotonic functions on a segment $[0,1]$?

What is the cardinality of a set of all real monotonic functions on a segment $[0,1]$? Does it really matter that functions are monotonic?
4
votes
1answer
152 views

CH for tilings of the plane

Given any set of jordan curves that can tile the plane, how to prove that the number of possible tilings using tiles from this set is either in bijection with the real numbers or a (possibly infinite) ...
2
votes
1answer
977 views

Cardinality of an infinite union of finite sets

This follows Arturo's answer of this question. Let $I$ an infinite set and $\{E_i\}_{i\in I}$ a family of finite sets. It is said that there exists an injection $$\bigcup_{i\in I} \ ...
10
votes
3answers
1k views

Is the class of cardinals totally ordered?

In a Wikipedia article http://en.wikipedia.org/wiki/Aleph_number#Aleph-one I encountered the following sentence: "If the axiom of choice (AC) is used, it can be proved that the class of cardinal ...
0
votes
1answer
40 views

Cardinals arising from random walks in the limit

A random walk $X$ is a sequence of elements of the set $\{-1, 0, 1\}$ and $X_i$ denotes the $i^{th}$ element of $X$. Consider the set $C_n$ of all random walks of length $n$ and the set $C_\infty = ...
4
votes
1answer
160 views

Prove that: $\aleph_0 \cdot \frak{c} = \frak{c} \cdot \frak{c}$

I've been fiddling with this enough. Found an answer here but didn't quite understand it. How do I prove that: $$\aleph_0 \cdot \frak{c} \leq \frak{c} \cdot \frak{c}$$ $$\frak{c} \cdot \frak{c} \leq ...
6
votes
2answers
507 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
2answers
371 views

prove cardinality rule $|A-B|=|B-A|\rightarrow|A|=|B|$

I need to prove this $|A-B|=|B-A|\rightarrow|A|=|B|$ I managed to come up with this: let $f:A-B\to B-A$ while $f$ is bijective. then define $g\colon A\to B$ as follows: $$g(x)=\begin{cases} ...
17
votes
2answers
1k views

How to show $(a^b)^c=a^{bc}$ for arbitrary cardinal numbers?

One of the basic (and frequently used) properties of cardinal exponentiation is that $(a^b)^c=a^{bc}$. What is the proof of this fact? As Arturo pointed out in his comment, in computer science this ...
6
votes
3answers
744 views

How to prove cardinality equality ($\mathfrak c^\mathfrak c=2^\mathfrak c$)

How do I prove this cardinality equality:$\mathfrak c^\mathfrak c=2^\mathfrak c$ I have failed to prove this after lots of trail - but I am certain it's true How can I prove this?
1
vote
2answers
350 views

Proof of cardinality inequality

I have this homework question I am struggling with: Let k1,k2,m1,m2 be cardinalities. prove that if $${{m}_{1}}\le {{m}_{2}},{{k}_{1}}\le {{k}_{2}}$$ then $${{k}_{1}}{{m}_{1}}\le {{k}_{2}}{{m}_{2}}$$ ...
3
votes
2answers
1k views

Cardinality of union of ${{\aleph }_{0}}$ disjoint sets of cardinality $\mathfrak{c}$

I have a home work question which is: " what is the cardinality of the union of ${{\aleph }_{0}}$ disjoint sets of cardinality $\mathfrak{c}$?" I believe somehow we can get to: cardinality = ...
6
votes
2answers
381 views

Fodor's lemma on singular cardinals

Fodor's lemma asserts that if $\kappa$ is a regular and uncountable cardinal, then if $f(\alpha)<\alpha$ for a stationary subset of $\kappa$, then it is constant on stationary subset. Suppose ...
19
votes
2answers
1k views

For every infinite $S$, $|S|=|S\times S|$ implies the Axiom of choice

How to prove the following conclusion: [For any infinite set $S$,there exists a bijection $f:S\to S \times S$] implies the Axiom of choice. Can you give a proof without the theory of ordinal ...
3
votes
3answers
758 views

Help with an elementary proof regarding cardinalities of finite sets.

I was relatively confused trying to produce a proof of this theorem, however, I have provided my attempt. I would greatly appreciate it if people can help steer me to the correct proof, or provide a ...
3
votes
1answer
104 views

Can the cofinality of a $\operatorname{cf}(A)$-directed partially ordered set $A$ be singular?

The cofinality of a totally ordered set is always a regular cardinal. On the other hand for any cardinal (regular or singular) $\kappa$ there is a partially ordered set $(A,\leq)$ with ...
16
votes
1answer
815 views

Medial Limit of Mokobodzki (case of Banach Limit)

A classical Banach limit is very usefull concept for me, but there is a problem with the integration and even with the measurability, this means for a sequence $(f_n)_{n\in \mathbb{N}}$ of measurable ...
13
votes
3answers
1k views

The cartesian product $\mathbb{N} \times \mathbb{N}$ is countable

I'm examining a proof I have read that claims to show that the Cartesian product $\mathbb{N} \times \mathbb{N}$ is countable, and as part of this proof, I am looking to show that the given map is ...
2
votes
1answer
836 views

Cardinality of the set of hyperreal numbers

What is the cardinality of the set of hyperreal numbers?
17
votes
3answers
1k views

Defining cardinality in the absence of choice

Under ZFC we can define cardinality $|A|$ for any set $A$ as $$ |A|=\min\{\alpha\in \operatorname{Ord}: \exists\text{ bijection } A \to \alpha\}. $$ This is because the axiom of choice allows any ...
11
votes
1answer
528 views

There's non-Aleph transfinite cardinals without the axiom of choice?

I can't find anything on this anywhere. The book I'm largely using at the moment is based around ZFC, so it makes no mention of anything other than the Aleph numbers, but according to Wikipedia on the ...
6
votes
2answers
554 views

What is the Cardinality of the Nameable Numbers?

Having just finished "Meta Math!" (Chaitin), I came across an interesting observation on infinite sets that I hadn't seen before. If I'm correct (and please let me know if I'm not): 1] There are ...
7
votes
7answers
2k views

Partition of N into infinite number of infinite disjoint sets?

Is it possible to have a countable infinite number of countable infinite sets such that no two sets share an element and their union is the positive integers?
6
votes
4answers
2k views

What is the set of all functions from $\{0, 1\}$ to $\mathbb{N}$ equinumerous to?

What is the set of all functions from $\{0, 1\}$ to $\mathbb{N}$ equinumerous to? I have figured out the question when it's the other way around, but I am not making any progress here. The worst thing ...
12
votes
0answers
437 views

Formulations of Singular Cardinals Hypothesis

I have stumbled on a few different formulations of the Singular Cardinals Hypothesis. The most common are: SCH1: $\quad 2^{cf(\kappa)}<\kappa \ \Longrightarrow \ \kappa^{cf(\kappa)}=\kappa^+$ for ...
11
votes
3answers
612 views

How to prove that from “Every infinite cardinal satisfies $a^2=a$” we can prove that $b+c=bc$ for any two infinite cardinals $b,c$?

Prove that if $a^2=a$ for each infinite cardinal $a$ then $b + c = bc$ for any two infinite cardinals $b,c$. I tried $b+c=(b+c)^2=b^2+2bc+c^2=b+2bc+c$, but then I'm stuck there.
6
votes
2answers
738 views

Cardinality of sets of subsets of $\mathbb{N}$

If we dont assume CH, is there a procedure to construct or define a set of subsets of $\mathbb{N}$ such that we cannot prove it to be of cardinality $\aleph_0$ or $\aleph_1$? Or if we assume not CH, ...
65
votes
1answer
4k views

How do we know an $ \aleph_1 $ exists at all?

I have two questions, actually. The first is as the title says: how do we know there exists an infinite cardinal such that there exists no other cardinals between it and $ \aleph_0 $? (We would have ...
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 ...