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)

7
votes
4answers
588 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
222 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
575 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
968 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
505 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
369 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
738 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
347 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
379 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 ...
18
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
752 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
103 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
805 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
823 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
527 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
548 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
435 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
607 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
735 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, ...
64
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 ...
4
votes
0answers
178 views

Property of Galvin-Hajnal rank

In what follows, $\|\Phi\|_I$ means the Galvin-Hajnal rank of a function $\Phi:\kappa \to Ord$ with respect to a $\omega_1$-complete ideal $I$ of $\kappa$. Lemma 2.2.5 of Introduction to Cardinal ...
3
votes
2answers
304 views

About Cardinality in Hausdorff Spaces

I have two problems: 1.- Let $X$ be a compact Hausdorff space, then $X$ has a basis with cardinality less than or equal to $|X|$. 2.- Let $X$ be a Hausdorff space and $D$ a dense subset in $X$, ...
4
votes
1answer
326 views

Regressive function on an ordinal

I'm trying to prove the following statement. Let $0<\overline{\alpha}\leq\alpha$ be two ordinals such that $\omega_{\overline{\alpha}}$ is the cofinality of $\omega_\alpha$. Let $f$ be a mapping ...
5
votes
1answer
672 views

Cofinality of cardinals

I have read some of the related questions (cofinality and its consequences, for example) about cofinality, but I still have no idea how to calculate the cofinality of an aleph. So, let's say I have ...
4
votes
4answers
715 views

What infinity is greater than the continuum? Show with an example

The diagonal argument establishes that the continuum is greater than countable infinity. What is an example of the next infinity (or any greater infinity) and how can it be shown that there is no 1:1 ...
14
votes
2answers
702 views

Relationship between Continuum Hypothesis and Special Aleph Hypothesis under ZF

Special Aleph Hypothesis AH(0) is the claim $2^{\aleph_0}=\aleph_1$, i.e. there is a bijection from $2^{\aleph_0}$ to $\aleph_1$. Continuum Hypothesis CH is the claim $\aleph_0 \leq \mathfrak{a}< ...
9
votes
2answers
2k views

Cardinality of the infinite sets

Consider the following problem: Which of the following sets has the greatest cardinality? A. ${\mathbb R}$ B. The set of all functions from ${\mathbb Z}$ to ${\mathbb Z}$ C. The ...
7
votes
1answer
171 views

Sequence of surjections imply choice

I am reading a paper where a side remark said that if a sequence $\langle g_\beta\colon\omega\to\beta\mid\beta<\omega_1\rangle$ is a sequence of surjections then $\omega_1$ is regular. I have ...
3
votes
2answers
260 views

How to prove that if $\kappa>\omega$ then $|H(\kappa)|>2^{<\kappa}$

I could not see $|H(\kappa)| > 2^{<\kappa}$. It is a question in Kunen book. The other part is answered, this part may be clear but I could not see. Also, $2^{<\kappa}$ is not clear for ...
6
votes
3answers
621 views

Cardinality != Density?

I was in a discussion where I argued that the density of two sets of the same cardinality could be different in respect to the infinite range of non-negative integers. Does cardinality imply that any ...
7
votes
1answer
322 views

powers of singular cardinals

I am trying to solve the following two problems: 1) if $\beta <\omega_1$, $2^{\aleph_1}<\aleph_{\omega_1}$, and $\aleph_\alpha^{\aleph_0} \leq \aleph_{\alpha +\beta}$ for a stationary set of ...
8
votes
3answers
1k views

The largest number system

If my number set construction memory doesn't fail me (I'll edit if errors are pointed out), we start out with Peano's axioms to get to $\mathbb{N}$, and in the need of an additive inverse for its ...
3
votes
1answer
193 views

If $\kappa<\aleph_\alpha$, then $\kappa\leq\alpha$?

I'm having a hard time following this proof. Here $\aleph(\alpha)$ is the cardinality of $Z(\alpha)$, the set of all ordinals $\gamma$ such that $|\gamma|\leq\alpha$. Also, $\aleph_1=\aleph(\aleph_0)$ ...
6
votes
3answers
846 views

How do we prove the existence of uncountably many transcendental numbers?

I know how to prove the countability of sets using equivalence relations to other sets, but I'm not sure how to go about proving the uncountability of the transcendental numbers (i.e., numbers that ...
1
vote
3answers
439 views

Comparing infinite sets (of real numbers)

If $A$ is the set of all real numbers in $(0,1)$ with no $5$ in their decimal representation, and $B$ is the set with no $34$ and no $76446$. Then the set $B$ is in some sense larger then $A$, how can ...
4
votes
2answers
232 views

If $|X|=|Y|=|X-Y|=\kappa$, can we find a bijection on $X$ that fixes $Y$ only?

in a previous question, I mistakenly attempted to subtract one cardinal number from another. Anyway, this got me to thinking, suppose I have two sets $X$ and $Y$, with $Y\subseteq X$. Suppose also ...
21
votes
4answers
778 views

Does $k+\aleph_0=\mathfrak{c}$ imply $k=\mathfrak{c}$ without the Axiom of Choice?

I'm currently reading a little deeper into the Axiom of Choice, and I'm pleasantly surprised to find it makes the arithmetic of infinite cardinals seem easy. With AC follows the Absorption Law of ...