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)

0
votes
1answer
27 views

Construct an injective function $f:[a,b]\times[c,d]\rightarrow\mathbb{R}$ for some $a,b,c,d\in\mathbb{R}$

Let $a,b,c,d\in\mathbb{R}$ such that $a<b$ and $c<d$ be given. Construct an injective function $f:[a,b]\times[c,d]\rightarrow\mathbb{R}$. My intuition is to construct a function ...
0
votes
4answers
78 views

Let $S$ and $T$ be sets such that $|S|=|T|$, prove that $|P(S)|=|P(T)|$

Let $S$ and $T$ be sets such that $|S|=|T|$, prove that $|P(S)|=|P(T)|$ where $P$ denotes a power set. From the theorem: If $S$ is a finite set with $n$ elements, then the cardinality of $P(S)=2^n$ ...
0
votes
1answer
44 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 ...
0
votes
2answers
41 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 ...
0
votes
1answer
42 views

Prove that $(0,1) =c\mathbb R$

How do I prove this knowing that $f(x) = \tan(x\pi/2)$ is a bijection between $(0,1)$ and $(0, \infty)$? We also have a bijection between $(-1,1)$ and $(0,1)$.
0
votes
1answer
34 views

Corollary 6.6 in Munkres' TOPOLOGY 2nd ed: Subsets of finite sets are finite? Cardinality of a proper subset is less than that of the set?

Here's Corollary 6.6 in Topology by James R. Munkres, 2nd edition: If $B$ is a subset of the finite set $A$, then $B$ is finite. If $B$ is a proper subset of $A$, then the cardinality of $B$ is less ...
0
votes
1answer
40 views

Cardinality of the set of functions from N to {0,1,2,3,…,9} is equal to card(R)

I know that the set of infinite sequences on {0,1,2,3,4,5,6,7,8,9} is uncountable, but how to show that it has a bijection to R?
0
votes
1answer
39 views

Find the cardinal of $X=\{A\subseteq \Bbb N : A \text{ is finite } \}$

Find the cardinal of $X=\{A\subseteq \Bbb N : A \text{ is finite } \}$. Attempt $$ X=\bigcup_{i\in\Bbb N}X_i$$ Where $X_i$ denotes the set of subsets of $\Bbb N$ with cardinal $i$. Let $A\in X_i, ...
0
votes
2answers
88 views

Trouble with definition of countable, denumerable

I found the following definition: Definition. A set is countable iff its cardinality is either finite or equal to $\aleph_0$. A set is denumerable iff its cardinality is exactly $\aleph_0$. A ...
0
votes
1answer
26 views

Finite Sets Proof on Domains [duplicate]

Just wanted some help with this little proof.: Let X and Y be Finite Sets. Prove that |X^Y| = |X|^|Y|
0
votes
1answer
82 views

Suppes' Axiom of Cardinal Numbers

In Suppes' book, Axiomatic Set Theory he introduces an axiom concerning cardinal numbers,before introducing them, namely that each set is associated with an object known as a cardinal number, and that ...
0
votes
1answer
25 views

bijective, one-to-one, and number of elements

How does one reconcile the following (seemingly) contradiction in using "number of elements" argument? In the "range" [0,1] in R there are more points than in N, to be shown as "take the inverse of ...
0
votes
2answers
50 views

Cardinality of the set of all complex sequences converging to zero.

I was asked to show that the set of all complex sequences converging to zero has the same cardinality as the set [0,1]. This is the only hole in a proof that I am working on. I need to show there ...
0
votes
1answer
48 views

Prove $A$ is either finite or countable.

Let $A$ be a set and let $f:A \to \Bbb{N}$ be an injection. Prove $A$ is either finite or countable. How can one prove such a thing? Since this is so obvious it gets me in a place where I don't know ...
0
votes
1answer
127 views

Cardinality of the set of all (real) discontinuous functions

This is a question from the book Introduction to Set Theory (Hrbacek and Jech), chapter 5, question 2.6. (Show that) The cardinality of the set of all discontinuous functions is ...
0
votes
1answer
40 views

If $\alpha$, $\beta$ are finite cardinals such that both are greater than $1$ and $\gamma$ is an infinite cardinal then $\alpha^\gamma=\beta^\gamma$.

Can someone suggest a rigorous proof of the following: If $\alpha$, $\beta$ are finite cardinals such that both are greater than $1$ and $\gamma$ is an infinite cardinal then $\alpha^\gamma = ...
0
votes
1answer
30 views

Prove that if A~B then Sym(A)~Sym(B).

I tried to prove it with sets. Really, truly clumsy. I know |A|=|B|. Can I simply conclude that |A|!=|B|! => Sym(A)~Sym(B)?? (Sym(A) for a set A is the set of all bijections from A to A.)
0
votes
1answer
35 views

Transfinite fixed points of a function

Let the function $F\colon On \rightarrow On$ be defined by the following recursion: $F(0) = \aleph_0$ $F(\alpha+1) = 2^{F(\alpha)}$ (cardinal exponentiation) $F(\lambda) = \sup\{F(\alpha): \alpha ...
0
votes
1answer
32 views

a question concerning multiplication of cardinal numbers

Consider $\{B_i\}$ where $i\in I$ and $I$ is countable infinite. $|B_i|=|B_j|=n$ for all $i,j$ and $n \ge |\mathbb{N}|$. I want to show that $| \large \cup_{i\in I}$$B_i|=n$ I am given that $a*a=a$ ...
0
votes
1answer
49 views

How to define an explicit bijection from P(N) to 2^N [closed]

How do I define an explicit bijection between the power set of N and $2^N$ with $2^N =\{f|f:N\to\{0,1\} \text{ is a function} \}$?
0
votes
1answer
52 views

Mapping between set cardinalities

Please help me prove the following equalities between set cardinalities by explicitly showing an appropriate mapping: $$\left | (0,1) \right |= \left | (1,+\infty ) \right |$$
0
votes
2answers
88 views

Show that $\aleph_{\alpha} +\aleph_{\alpha} = \aleph_{\alpha}$ and $n \cdot \aleph_{\alpha} = \aleph_{\alpha}$

a) Give a direct proof of $\aleph_{\alpha} +\aleph_{\alpha} = \aleph_{\alpha}$ by expressing $\omega_{\alpha}$ as a disjoint union of two sets of cardinality $\aleph_{\alpha}$. b) Give a direct proof ...
0
votes
1answer
180 views

Prove cardinal arithmetic (exponentiation)

Suppose $|K|=\kappa, |L|=\lambda, |M|=\mu$ and $L \cap M=\emptyset$. Prove that $$(\kappa^{\lambda})^{\mu}=\kappa^{\lambda \cdot \mu}$$ My attempt: Suppose $F : K^{ L \times M} \rightarrow (K^L)^M$. ...
0
votes
1answer
36 views

For every ordinal $\alpha$, there is a cardinal number greater then $\alpha$.

I am trying to prove that for every ordinal $\alpha$, there is a cardinal number greater then $\alpha$. Proof: $\alpha$ is a (well ordered) set. Take the set $P(\alpha)$. Assume that we know that for ...
0
votes
2answers
71 views

Prove that the sets $S$ and $D$ have the same cardinality

Prove that the sets $S$ and $D$ have the same cardinality, where $S = \{(x,y)\mid-1\leq x \leq 1\text{ and }-1\leq y\leq 1\}$ and $D = \{(x,y)\mid x^2 + y^2 \leq 1\}$.
0
votes
1answer
101 views

How to prove there is no surjection $f\colon X \rightarrow 2^X$ [duplicate]

This is the following problem: Let $X$ be a set. Prove that there is not a surjection from $X \rightarrow 2^X$ (Hint: Assume to the contrary that $f\colon X \rightarrow 2^X$ is a surjection and ...
0
votes
1answer
35 views

How to show $A_1 \approx A_2 \iff \mathrm{card}(A_1)=\mathrm{card}(A_2)$

For any set $A_1$ and $A_2$, let us define the relation $\approx$ if there exists a bijection between $A_1$ and $A_2$. Then I want to show that $A_1 \approx A_2 \iff ...
0
votes
1answer
29 views

Seemingly basic cardinality question

If $A\subset A'$, $B\subset B'$, if $card(A)=card(B)$ and $card(A')=card(B')$, why is it that $card(A'\backslash A)=card(B'\backslash B)$ ?
0
votes
2answers
46 views

A question about the size of the set of all countably-infinite subsets of a countably-infinite set

Let $A$ be a countably-infinite set , then how do we prove that the power set of $A$ and the set of all countably-infinite subsets of $A$ have the same cardinality (i.e. that there is a bijection) ? ...
0
votes
1answer
59 views

What is the cardinality of the equivalence class

Consider this relation: $$R = \left\{ {\left\langle {f,g} \right\rangle \in {{\left\{ {0,1} \right\}}^N} \times {{\left\{ {0,1} \right\}}^N}|\exists k \in N\left| {\left\{ {i \in N|f(i) \ne g(i)} ...
0
votes
2answers
275 views

How do you solve for the cardinality of a power set of some complex set? (i.e. $|\mathcal P(A^n)|$ , $|\mathcal P(A\cup B)|$ )

Suppose $A$ is some set such that $A = \{a_1,a_2,\dotsb,a_n\}$. We know that $|A|=n$. We know that $\mathcal P(A)= 2^n$. Now let $A^n$ denote the cartesian product of a set A with itself n times. ...
0
votes
2answers
222 views

Some questions about elementary set theory (cardinal and ordinal numbers)

I have three questions about elementary set teory and i don't figure out how to solve them: 1)Let $X$ a subset of the cardinal number $2^{\aleph_0}$ (seen as an initial ordinal). Is true or false ...
0
votes
1answer
80 views

If $\gamma >0,$ then $ \alpha < \beta $ implies that $\gamma \ . \alpha<\gamma \ . \beta$ and that $\alpha \ . \ \gamma \leq \beta \ . \ \gamma.$

Show that if $\gamma >0,$ then $ \alpha < \beta $ implies that $\gamma \ . \alpha<\gamma \ . \beta$ and that $\alpha \ . \ \gamma \leq \beta \ . \ \gamma.$ (All operations are cardinal ...
0
votes
1answer
121 views

Constructing a bijection between intervals [closed]

So I am trying to solve questions below Let $A = \{(\alpha_1,\alpha_2,\alpha_3,\ldots): \alpha_i \in \{0,1\}, i \in N\}$, i.e., $A$ is the infinite cartesian product of the set $\{0,1\}$. Show ...
0
votes
2answers
59 views

Show that for a set $A$, $|^A 2|$ = $|^{|A| }2|$.

Question: Show that for a set $A$, $|^A 2|$ = $|^{|A| }2|$. Comments: This is a part of a larger problem that I'm attempting to solve and it seems like the equality is true, but I'm not quite sure ...
0
votes
1answer
47 views

$L$ is a class of languages that cannot be represented by a regular expression. How to state cardinality of $L$.

$L$ is a class of languages that cannot be represented by a regular expression. The book says that the cardinality of $L$ is $2^{\aleph_0} > \aleph_0$ what's the logic behind getting the ...
0
votes
1answer
49 views

Cardinality of given set

Given, $$A=\{B\subset \mathbb{N}: B \text{ is finite} \vee B^c \text{ is finite }\}$$ How can I prove that A is countable. For me it seems it is uncountable.
0
votes
1answer
145 views

Equinumerosity: A Bijection Existence Proof

I'm told that if $m<n$, then the intervals $(0,1)$ and $(m,n)$ are equinumerous. I'm asked to prove this by exhibiting a specific bijection between them. I came up with this: ...
0
votes
2answers
57 views

Looking an abstract proof to an elementary set theory property

I've been scratching and pulling my hair for an hour and a half trying to come up with an abstract solution to a simple property. For finite sets $A_1, A_2$, show that $$|A_1 \cup A_2| \leq |A_1| ...
0
votes
1answer
46 views

A hint for a simple question about cardinality.

Somebody can to give me a hint in the following question? Let $X$ be an infinite set. Show that $X$ has the same cardinality that $X \cup \mathbb{Q}$.
0
votes
1answer
154 views

Closed Form Cantor Snake Function

Does anyone have the closed form for the Cantor-Snake function and its inverse? By Cantor-Snake, I mean the bijection that maps the Naturals to the Rations - the classic proof that the rationals ...
0
votes
1answer
218 views

The limit elements of well-ordered proper classes

For any well-ordered class $W$ with no maximum element, we can define a successor function $f_W : W \rightarrow W$ by asserting that $f_W(w) = \mathrm{min}\{x > w \mid x \in W\}.$ This allows us to ...
0
votes
2answers
307 views

Closed, unbounded subset of a cardinal.

I missed two lectures in my set theory course, and now I don't understand the homework problems. One is this: let $\kappa$ be a regular uncountable cardinal. Show that the following sets are closed ...
0
votes
1answer
84 views

A conjecture on closed discrete subset

I am struggling with this old problem: Let $X$ satisfy countable chain condition(abbreviated as CCC) and $X$ has a regular $G_\delta$-diagonal. Then the cardinality of $X$ is at most $\mathfrak ...
0
votes
2answers
61 views

Question about power of sets

If two sets are finite and they have the same power, can we say that the two sets are equivalent? Is every finite set countable?
0
votes
3answers
347 views

Proof of equal cardinality $|\Bbb N \times\Bbb N \times\Bbb N| = |\Bbb N|$

How do I prove that the following sets have equal cardinality? $|\Bbb N \times\Bbb N \times\Bbb N| = |\Bbb N|$ ($|\Bbb N \times\Bbb N| = |\Bbb N|$ also for that matter) $|\Bbb Z \times\Bbb Z| = ...
0
votes
1answer
189 views

problem of a cardinality of a union

Let $\lambda$ a cardinal and $\delta<\lambda^+$. I want to proof there exists a increasing chain $$\{A^i_\delta : i< cf(\lambda)\}\subseteq[\delta\times\delta]^{<\lambda}$$ converging to ...
0
votes
1answer
62 views

Set of regular polygons

Defined set S of regular polygons on plane. Known for every polygon: at least one of it's sides is parallel to x,and this side's length is rational number. Also known- there is at least one vertex ...
0
votes
1answer
156 views

The minimal cardinal set from a choice between a set and its complement

Given a set $A$ I would like to know if already exist a math definition for a Set $L$ being: $L$="the smaller cardinal set from a choice between a set and its complement" i.e a set with this ...
0
votes
1answer
41 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 = ...