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)

12
votes
1answer
182 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 ...
11
votes
4answers
508 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...
11
votes
3answers
680 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.
11
votes
1answer
202 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 ...
11
votes
4answers
250 views

Is $2^{\aleph_0} = \aleph_1$?

I was reading a thread on Examples of Common False Beliefs in Mathematics on MathOverflow, in which a user wrote: $$2^{\aleph_0} = \aleph_1$$ This is a pet peeve of mine, I'm always surprised ...
11
votes
1answer
210 views

Wimpy powerset function

Define the 'wimpy powerset function' $\mathcal{W} : \mathrm{Set} \rightarrow \mathrm{Set}$ by writing $$\mathcal{W}(B) = \{X \in \mathcal{P}(B) : |X| < |B|\}.$$ A few preliminary observations. ...
11
votes
1answer
107 views

How does equality $\mathfrak{m}^\mathfrak{m} = 2^\mathfrak{m}$ in $\sf{ZF}$ relate to the axiom of choice?

Usually, the equality $\mathfrak{m}^\mathfrak{m} = 2^\mathfrak{m}$ for infinite cardinal $\mathfrak{m}$ is proved like that: $$ 2^\mathfrak{m} \leqslant \mathfrak{m}^\mathfrak{m} \leqslant ...
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
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
1answer
524 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 ...
10
votes
2answers
262 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 ...
10
votes
1answer
564 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 ...
10
votes
1answer
227 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
3answers
277 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
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 ...
9
votes
4answers
364 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
3k 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
637 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
4k 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
3answers
1k views

Is there an infinite countable $\sigma$-algebra on an uncountable set

Let $\Omega$ be a set. If $\Omega$ is finite, then any $\sigma$-algebra on $\Omega$ is finite. If $\Omega$ is infinite and countable, a $\sigma$-algebra on $\Omega$ cannot be infinite and ...
9
votes
2answers
212 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
378 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
331 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
349 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
574 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
118 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
380 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 ...
9
votes
0answers
92 views

Category-theoretic properties of cardinals

Let $\kappa$ be a cardinal, let $\mathbf{H}_\kappa$ be the set of hereditarily $\kappa$-small sets, and let $\mathbf{Set}_{< \kappa}$ be the full subcategory of $\mathbf{Set}$ corresponding to ...
9
votes
0answers
142 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 ...
9
votes
0answers
133 views

Raising a partial function to the power of an ordinal

Consider a set $X$, and let $f : X \rightarrow X$ denote a partial function. Then for natural $n$, we can define $f^n$ as iterated composition, e.g. $f^2 = f \circ f$. Now suppose that $X$ is also ...
8
votes
4answers
2k 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
1k 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
419 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 ...
8
votes
2answers
450 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
524 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
691 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
405 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
6answers
2k views

Proof that aleph null is the smallest transfinite number?

The wikipedia page on the cardinal numbers says that $\aleph_0$, the cardinality of the set of natural numbers, is the smallest transfinite number. It doesn't provide a proof. Similarly, this page ...
8
votes
2answers
459 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, ...
8
votes
1answer
492 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
8
votes
2answers
4k 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 ...
8
votes
3answers
201 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
3answers
2k views

What are Aleph numbers intuitively?

I cannot get my head around the concept of the `types' of Aleph infinity. What is an easy intuitive way to see when you are given the integer numbers $\aleph_0$ the $\aleph_1$ will follow?
8
votes
3answers
3k 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 ...
8
votes
4answers
731 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
1answer
659 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
2answers
121 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
315 views

Can proper classes also have cardinality?

In some set theories such as ZF+GAC, in which GAC is global axiom of choice, the Von Neumann universe $V$ bijects to $Ord$, the class of ordinals. It suggests us that proper classes may also have ...
8
votes
2answers
129 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 ...