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)

11
votes
1answer
176 views

Sets of Cardinals without choice

I have a theory that the axiom of choice is equivalent to the statement that sets of distinct cardinals are well ordered by cardinality. I can prove that the axiom of choice implies this. However I am ...
10
votes
9answers
5k views

Is the sum of all natural numbers countable?

I do not even know if the question makes sense. The point is rather simply. If I have the sum of all natural numbers, $$\sum_{n\in \mathbb{N}}n$$ this is clearly "equal to infinity". But since ...
10
votes
4answers
444 views

Looking for a problem where one could use a cardinality argument to find a solution.

I would like to find an exercise of the type: Find some $x$ in $A\setminus B$. Solution: since $A$ is uncountable and $B$ is countable such $x$ exists...
10
votes
2answers
2k views

What's “the catch” in this question?

I am solving old exam questions and I came across this question: Let $\langle A_n \mid n < \omega\rangle$ disjoint sets such that $\bigcup_{n < \omega}A_n = \mathbb{R}$. Prove that there ...
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 ...
10
votes
4answers
4k views

Do the real numbers and the complex numbers have the same cardinality?

So it's easy to show that the rationals and the integers have the same size, using everyone's favorite spiral-around-the-grid. Can the approach be extended to say that the set of complex numbers has ...
10
votes
1answer
535 views

Tightness and countable intersection of neighborhoods

The following is a problem a colleague has encountered. He would like to know whether the following conjecture is right, wrong, or neither: Let $X$ be a topological space of countable tightness ...
9
votes
3answers
251 views

Existence of a sequence that has every element of $\mathbb N$ infinite number of times

I was wondering if a sequence that has every element of $\mathbb N$ infinite number of times exists ($\mathbb N$ includes $0$). It feels like it should, but I just have a few doubts. Like, assume ...
9
votes
4answers
334 views

Infinite sets and their Cardinality

(I am a 13 year old so when you answer please don't use things that are TOO hard even though I actually can understand quite complex stuff) I was studying Infinite sets and their cardinality (not in ...
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 ...
9
votes
2answers
560 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 ...
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?
9
votes
2answers
189 views

Is it possible that $2^n=3^n$ for some Dedekind-finite cardinal $n\gt0$?

Is it possible that $2^n=3^n$ for some Dedekind-finite cardinal $n\gt0$? I think the question speaks for itself, but let me try and satisfy the "quality standards" algorithm by padding it. Yes, I ...
9
votes
1answer
316 views

A “reverse” diagonal argument?

Cantor's diagonal argument can be used to show that a set $S$ is always smaller than its power set $\wp(S)$. The proof works by showing that no function $f : S \rightarrow \wp(S)$ can be surjective ...
9
votes
2answers
245 views

Why does $\omega$ have the same cardinality in every (transitive) model of ZF?

As in the title: Why does $\omega$ have the same cardinality in every (transitive) model of ZF? I've been thinking about this for some time now. Can someone show me how to show this by showing me a ...
9
votes
2answers
296 views

Does $\mathcal P ( \mathbb R ) \otimes \mathcal P ( \mathbb R ) = \mathcal P ( \mathbb R \times \mathbb R )$?

Obviously the answer's yes if I replace $\mathbb R$ by a countable set. If $\mathbb R$ is replaced by a set $X$ having a greater cardinality, then the diagonal $\{ (x,x) , \ x\in X\}$ is not in the ...
9
votes
1answer
314 views

Is there an easy proof for ${\aleph_\omega} ^ {\aleph_1} = {2}^{\aleph_1}\cdot{\aleph_\omega}^{\aleph_0}$?

The question contains 2 stages: Prove that ${\aleph_n} ^ {\aleph_1} = {2}^{\aleph_1}\cdot\aleph_n$ This one is pretty clear by induction and by applying Hausdorff's formula. Prove ...
9
votes
1answer
202 views

Is the cardinality of uncountable $G_{\delta}$ set of $\mathbb{R}$ equals the cardinality of the continuum?

It is known that closed sets of $\mathbb{R}$ satisfies continuum hypothesis, that is, every closed subset of $\mathbb{R}$ is either countable or of the cardinality of the continuum. Is the ...
9
votes
1answer
555 views

cardinal exponentiation, $k^{<\lambda}$

I have the following well-known exercise in cardinal arithmetics: If $\kappa, \lambda$ are cardinals such that $\lambda$ is infinite, then $\kappa^{<\lambda}$ equals the supremum of the ...
9
votes
1answer
111 views

Are injections harder to find than surjections?

Given two finite sets $A$ and $B$ with $|A|<|B|$ There are more functions from $B$ to $A$ than from $A$ to $B$ except when $|A|=1$ or $|A|=2,|B|=3,4$. See here for proof. It is also true there are ...
9
votes
2answers
346 views

Are there non-equivalent cardinal arithmetics?

‎Generalizing a concept in mathematics is always a problematic situation. In most cases there are several ways to generalize a notion and it is not easy to decide if a particular generalization is ...
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 ...
8
votes
4answers
1k views

Simple example of uncountable ordinal

Can you make a simple example of an uncountable ordinal? With simple I mean that it is easy to prove that the ordinal is uncountable. I know that the set of all the countable ordinals is an ...
8
votes
4answers
992 views

What's the cardinality of all sequences with coefficients in an infinite set?

My motivation for asking this question is that a classmate of mine asked me some kind of question that made me think of this one. I can't recall his exact question because he is kind of messy (both ...
8
votes
2answers
417 views

What does Martin's Maximum imply for $P(\mathbb{R})$?

Prompted by this question: of course Godel's constructibility axiom implies that $P(S)$ is minimal for any set $S$ and so handily answers the question of the size of the power set of the continuum in ...
8
votes
2answers
508 views

Does taking the power set give you the “next biggest cardinal”

I know that if you take the power set of a set, it has a higher cardinality. Therefore there are an infinite number of them as $P^{n}(\mathbb{N})$(the nth power set of the naturals) Let's say $$C_{n} ...
8
votes
2answers
604 views

Could someone explain aleph numbers?

I am having trouble understanding aleph numbers. I understand $\aleph_0$ is a countable infinity, but after that, I'm lost. What are $\aleph_1,\aleph_2,\aleph_3$, etc. to $\aleph_n$? Is there an ...
8
votes
3answers
345 views

Why infinite cardinalities are not “dense”?

What tells us that the structure of the cardinals is "discrete"? I'm not using the words "discrete" and "dense" with their formal meanings. Maybe I have this confusion because I'm using concepts ...
8
votes
1answer
444 views

Is the axiom of choice needed to show that $a^2=a$?

A comment on this answer states that choice is needed for the statement that $a^2=a$ for all infinite cardinals $a$. In Thomas Jech's Set Theory (3rd edition), his theorem 3.5 proves this statement ...
8
votes
3answers
185 views

Cardinality of the Union is less than the cardinality of the Cartesian product

Suppose I have two collections of sets, $\{A_i\}_{i \in I}$ and $\{B_i\}_{i \in I}$. It is given in the problem that $$\mathrm{card}(A_i) < \mathrm{card}(B_i) \text{ for all }i \in I $$ I want to ...
8
votes
1answer
585 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?
8
votes
4answers
613 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 ...
8
votes
2answers
118 views

Can we conclude $\prod_{\kappa \in Crd, \kappa=1}^{\kappa<\aleph_\alpha}\kappa=2^{\aleph_\alpha}$ in ZFC?

In complex analysis, there is a function called Euler's Gamma function. Whenever given a positive integer $n+1$, it will return $n!=\prod_{i=1}^{i < n+1}i$. I'm not sure if there is similar ...
8
votes
2answers
110 views

Proof of non-existence of non-principal $\kappa$-complete ultrafilter

Let $\lambda$ be a cardinal. I would like to prove that for all cardinals $\lambda < \kappa \leq 2^\lambda$, there can't be a $\kappa$-complete non-principal ultrafilter on $\kappa$. Here is my ...
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 ...
8
votes
2answers
236 views

Cardinality of the set of open functions?

I was wondering what is the cardinality of the set $ \{ f : \mathbb{R} \to \mathbb{R} \mid f \text{ is open } \} $ (i.e., $f(U) \subseteq \mathbb{R}$ is open for all open $U$). There are at least $c = ...
8
votes
1answer
2k views

A simple bijection between $\mathbb{R}$ and $\mathbb{R}^4$ or $\mathbb{R}^n$?

How to form a bijection from $(0,1]$ to $\mathbb{R}$: $$f(x) = \left\{\begin{array}{ll} 2-\frac{1}{x}&\text{if }x\in(0, .5]\\ \frac{2x-1}{1-x}&\text{if }x\in(.5, 1]. \end{array}\right.$$ ...
8
votes
0answers
100 views

What is the degree of a real closure of an ordered field?

Given a subfield $F$ of $\Bbb R$, let the real-closure of $F$ be the smallest subfield of $\Bbb R$ which is real-closed and extends $F$. Since the theory of real-closed fields is complete, this is in ...
8
votes
0answers
98 views

Do an infinite set and its double have the same cardinality? [duplicate]

My question was inspired by this answer. Suppose $A$ is an infinite set. Does its double, $A\times\{0,1\}$, always have the same cardinality? In my head I quickly spotted a simple proof that the ...
8
votes
0answers
2k views

cardinality of set of all real continuous functions [duplicate]

Could somebody explain to me how to prove that the cardinality of all real continuous functions is $c$ ? The first problem is that I don't know how to show that each real continuous function $f: X ...
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?
7
votes
2answers
370 views

Proving existence of a surjection $2^{\aleph_0} \to \aleph_1$ without AC

I'm quite sure I'm missing something obvious, but I can't seem to work out the following problem (web search indicates that it has a solution, but I didn't manage to locate one -- hence the ...
7
votes
2answers
381 views

A question about the cardinality of the set of all the bijections from $M$ to itself

$M$ is a set.We denote the set of all the bijections from $M$ to itself by $K$.Is the cardinality of $K$ larger than the cardinality of $M$?
7
votes
2answers
400 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, ...
7
votes
1answer
374 views

What is the cardinality of the set of all sequences in $\mathbb{R}$ converging to a real number?

Let $a$ be an real number and let $S$ be the set of all sequences in $\mathbb{R}$ converging to $a$. What is the Cardinality of $S$? Thanks
7
votes
1answer
382 views

What is $\aleph_0$ powered to $\aleph_0$?

By definition $\aleph_1 = 2 ^{\aleph_0}$. And since $2 < \aleph_0$, then $2^{\aleph_0} = {\aleph_1} \le \aleph_0 ^ {\aleph_0}$. However, I do not know what exactly $\aleph_0 ^ {\aleph_0}$ is or how ...
7
votes
2answers
3k views

Why do the rationals, integers and naturals all have the same cardinality?

So I answered this question: Are all infinities equal? I believe my answer is correct, however one thing I couldn't explain fully, and which is bugging me, is why the rationals $\mathbb Q$, integers ...
7
votes
3answers
128 views

What questions become answerable/computable given an uncountable character set?

Having reached the concluding portion of my first course in real analysis, one subject that I feel was not adequately addressed was the issue of cardinalities. This is a subject I was interested in ...
7
votes
1answer
149 views

Bijection between $\mathbb{Z}\times\mathbb{Z}\times\dots$ and $\mathbb{R}$

Is there a bijection between $\mathbb{Z}\times\mathbb{Z}\times\dots$ for countably infinitely many $\mathbb{Z}$'s and $\mathbb{R}$? That is, is $\mathbb{Z}\times\mathbb{Z}\times\dots$, repeated ...
7
votes
2answers
2k views

Proving the Cantor Pairing Function Bijective

How would you prove the Cantor Pairing Function bijective? I only know how to prove a bijection by showing (1) If $f(x) = f(y)$, then $x=y$ and (2) There exists an $x$ such that $f(x) = y$ How would ...