2
votes
2answers
20 views

Cardinality of the set of all involutive functions

The following is a section in my homework, I couldnt solve it so I'm asking for some help. I have the following set : $\{f:\mathbb N \to \mathbb N | f(f(a)) = a \text{ for all } a\in \mathbb N\}$. I ...
1
vote
3answers
42 views

Prove that $\{(a,b):a,b\in\mathbb N, a\geq b\}$ is denumerable.

If $S=\{(a,b):a,b\in\mathbb N, a\geq b\}$, how do I prove that $S$ is denumerable? Work: Since $S \subseteq\mathbb{N\times N}$ I know that $S$ is denumerable. But I don't know how to structure the ...
2
votes
2answers
64 views

Proving that (0,1) and [0,1] are numerically equivalent.

as the title suggests, I need help proving that the cardinality of $(0,1)$ and $[0,1]$ are the same. Here is my work: $f:[0,1] \rightarrow (0,1)$ Let $n\in N$ Let $A=\{\frac{1}{2}, \frac{1}{3}, ...
1
vote
2answers
37 views

cardinality with finite sets

$A,B,C$ are finite sets. Suppose $A\subseteq B \subseteq C$ and $\#A=\#C$. Prove that $\#A=\#B$ and $\#B=\#C$. Should I prove this by showing that there exist an element in $A$ that exist in $B$ and ...
1
vote
2answers
38 views

Cardinality of $\lim_{k\to\infty}\mathbb N^k$ vs. $\mathbb N^\infty$

My friend and I are having a disagreement over whether the number of terms in the following series is countable or uncountable: $$\sum_{i=1}^\infty a_i + \sum_{i=1}^\infty\sum_{j=1}^\infty a_{ij}+ ...
1
vote
0answers
15 views

If $X$ is a finite set of cardinality $n$, where $n$ exists in $P$, show that the following conditions on a function $f: X \to X$ are equivalent: [duplicate]

(a) $f$ is an injection (b) $f$ is a surjection (c) $f$ is a bijection I know that (c) implies (a) and (b) and (a) and (b) imply (c). I also have the following definition that I've been playing ...
0
votes
2answers
35 views

Cardinality of two sets cross-multiplied

Let $A$ and $B$ be sets. Prove that $ \#(A \times B) = \#(B \times A)$. What I have done: There exist an element $m$ in $A$ such that the element also exists in $B$. If $\#A = \#B$, then $\#B = ...
4
votes
2answers
42 views

Proving that $\mathrm{card}(2^{\mathbb{N}})=\mathrm{card}(\mathbb{N}^\mathbb{N})$

I'd like to prove that $\mathrm{card}(2^{\mathbb{N}})=\mathrm{card}(\mathbb{N}^\mathbb{N})$, I have the following 'sketch' but I'm not sure if this works. ...
0
votes
1answer
22 views

An alternative succinct proof needed for trivial cardinality fact

Let $|X|$ denote the cardinality of a set, i.e. the least ordinal $\alpha$ such that there is a bijection between X and $\alpha$. For any sets $X$ and $Y$ we write $X\preccurlyeq Y$ if the exists an ...
2
votes
1answer
85 views

What are interesting examples of existential proofs based on cardinality arguments?

Probably the most famous example of a proof, where consideration of cardinalities is used to show existence of some object, it the Cantor's proof that there exist transcendental numbers. What are ...
1
vote
1answer
68 views

Bigger infinity than real number infinity [duplicate]

Is there a bigger infinity than the infinity of cardinality of the real numbers $R$ ? i.e. is there a set to which real numbers can't be mapped one-one to ?
0
votes
3answers
52 views

Are the following sets countable?

I'm trying to determine if the following sets are countable: (a) $\mathbb{Z}^{[0,1]}, (b) [0,1]^{\mathbb{Z}}, (c) \mathbb{Z}^{\mathbb{Z}}$, (d) the set given by functions $f:\mathbb{Z}\to\mathbb{R}$ ...
0
votes
1answer
23 views

Cardinal arithmetic basics

Let's say we have $\omega + \omega$. Since these sets are not disjoint we can replace them by disjoint sets of the same cardinality, namely $\omega \times \{0\}$ and $\omega \times \{1\}$. Then $\big ...
4
votes
1answer
30 views

If $2^{\kappa}<\lambda$, how many subsets of size $\kappa$ are there of a set of size $\lambda$.

Assume both cardinals are infinite. Also assume AC as needed. So, the obvious bound is that there are no more than $\lambda^\kappa\leq 2^\lambda$ of them. But it seems there should be an easy bound ...
1
vote
1answer
24 views

Does for a set of cardinals a finite subset exist such that for any cardinal in the set a larger cardinal in the subset exists?

I am writing an essay for which I need to prove that sufficiently many graphs of a certain type exist. Is it true that for any set of sets (or set of cardinals) $S$ a countable subset $C$ exists such ...
0
votes
2answers
36 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) ? ...
3
votes
2answers
85 views

Is there, for every set $X$, a set $Y$ for which $|Y| < |X|$ but $|\mathcal{P}(Y)| \geq |X|$?

As the title says, my question is: Is there, for every set $X$, a set $Y$ for which $|Y| < |X|$ but $|\mathcal{P}(Y)| \geq |X|$? I'm fairly certain this is true for finite sets but maybe ...
4
votes
4answers
212 views

Conclusion about cardinalty.

Assume that: $$\left| T \right| > {\aleph _0}$$ Why can't one assume immediately that: $$\left| T \right| \cdot \left| T \right| > \left| T \right| \cdot {\aleph _0}$$
0
votes
0answers
43 views

What is the cardinal number of the following?

What is the cardinal number of $\{f:\mathbb{R}\longrightarrow \mathbb{N}\ |\text{ $ f$ is an injective function}\}$?
0
votes
1answer
35 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
1answer
35 views

What is the cardinality of $M_2(\mathbb{R})$

What is the cardinality of $M_2(\mathbb{R})$, i.e the set of all 2 by 2 real matrices( $|M_2(\mathbb{R})|$)?
2
votes
1answer
59 views

Suppose that S and T each have cardinality c. Show that $S\cup T $ also has cardinality c.

I tried to use the Cantor-Bernstein Theorem. First, we have $S\subset S\cup T$, so that $\left | S \right |\leqslant \left | S\cup T\right | $. This implies $\left | S\cup T \right |\geqslant c$. But ...
20
votes
3answers
1k views

If the infinite cardinals aleph-null, aleph-two, etc. continue indefinitely, is there any meaning in the idea of aleph-aleph-null?

If the infinite cardinals aleph-null, aleph-two, etc. continue indefinitely, is there any meaning in the idea of aleph-aleph-null? Apologies if this isn't a sensible question, I really don't know too ...
0
votes
1answer
50 views

Is there always isomorphism between two sets that have the same cardinality?

Is there always isomorphism between two sets that has the same cardinality ? We only know that the two sets have the same cardinality. I tried to find a counter example but couldn't.
0
votes
0answers
13 views

Finding the cardinal of monotone increasing sequences of natural numbers [duplicate]

Find the cardinality of the set of all monotone increasing sequences of natural numbers. Well let's ignore the monotone increasing condition for a moment, then the cardinality of a set of all the ...
0
votes
4answers
30 views

Cardinality for all rational strongly increasing sequences

What is the cardinality for all rational strongly increasing sequences? Using diagonalization, I can show easily that for each list $f_n$ of sequnces, we can present a sequence which is not in ...
2
votes
1answer
42 views

Cardinality of Cartesian Product of Uncountable Set with Countable Set

Is it true that if $I$ is an infinite set, then $I\times \mathbb{N}$ has the same cardinality as $I$? I believe it, but I have minimal background in set theory. My guess is that we can construct an ...
1
vote
1answer
54 views

Ordinality of a Set

What is the difference between Ordinal number and cardinal number of a set?....I have a confusion in understanding the difference between the two.Can anyone help me to understand these two things? ...
4
votes
1answer
127 views

How much is ${\aleph_0}^{\aleph _ 0}$? [duplicate]

How much is ${\aleph_0}^{\aleph _ 0}$? On the left I can find ${2}^{\aleph_0}\le {\aleph_0}^{\aleph _ 0}$ but on the right I can not found someone that is $\le$. In general, how do I use ...
1
vote
1answer
26 views

Cardinality of arithmetic sequences

Let $S$ be the set of arithmetic sequences $(a_n)_n$ in $\mathbb{Z}$, i.e. there exists $d\in\mathbb{Z}$ such that $\forall n\in\mathbb{N}: a_{n+1} -a_n=d$. What is the cardinality of $S$? I ...
-2
votes
1answer
56 views

How many disjoint disks can be found in $\mathbb{R} \times \mathbb{R}$?

I know that the answer is $\mathbb{Q} \times \mathbb{Q}$ so the answer is $\aleph_0$ But why? Can't I find a $\mathbb{R} \times \mathbb{R}$ point in every disk?
0
votes
2answers
36 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
26 views

The Cardinality of infinite series of natural numbers?

Given an infinite sequence $a_1,a_2,a_3,...$,and the map $F(a_1,a_2,a_3...) = {p_1}^{-a_1}{p_2}^{-a_2}{p_3}^{-a_3}...$ Where $p_i$ is the ith prime (chosen by the axiom of choice). Why isn't this ...
2
votes
1answer
29 views

Cardinality of $F\times\Bbb N$

Suppose $F$ is an infinite set (that is $\#F\geq\#\mathbb N$). Various sources I have consulted claim that $$\# F=\# (F\times\mathbb N)$$ without proof (# denotes cardinality). I guess that this is so ...
1
vote
1answer
71 views

continuum and aleph one

We have symbols of cardinal numbers. The most known are aleph zero and continuum. Somewhere I've noticed the sequence of cardinal numbers as aleph zero, aleph one, aleph two... where $\aleph_n$ = ...
0
votes
1answer
91 views

Are there any infinites not from a powerset of the natural numbers?

With the cardinality of the natural numbers as $|\mathbb{N}| = \aleph_0$ and its powerset as $|\mathcal{P}(\mathbb{N})| = 2^{\aleph_0}$, the continuum hypothesis and the axiom of choice says that ...
0
votes
2answers
54 views

Cardinality of Integers, Positive Integers, and Rational Numbers all equal $\aleph_0$

Prove that $|\mathbb{Z}|=|\mathbb{Z}^+|=|\mathbb{Q}|=\aleph_0$ I am to use cardinal addition and multiplication to reduce this to finding an injection $\mathbb{Q}^+ \to ...
1
vote
3answers
37 views

Altering an Infinite Set does not change cardinality

Let X be an infinite set. Show that adding or subtracting a single point does not change its cardinality. I have a plan but need help writing the actual proof. I need to show that it doesn't matter ...
0
votes
2answers
56 views

Why do “Set of even Integers” and “Set of all Integers” have same cardinality? [duplicate]

Despite "Set of even Integers" and "Set of all Integers" are infinite sets, we can see that 3 is member of only one of them. Only one example is enough to say that both can't have same cardinality ...
2
votes
1answer
78 views

Prove: if $A$ is infinite set and $B$ is finite set then $\left| {A - B} \right| = \left| A \right|$

Prove: if $A$ is infinite set and $B$ is finite set then $\left| {A - B} \right| = \left| A \right|$ Well, one way to show it, is to find an injective function, for both directions. First, ...
1
vote
1answer
51 views

Prove: $2^{\aleph_0}\not=\aleph_{\epsilon_0}$

Prove: $2^{\aleph_0}\not=\aleph_{\epsilon_0}$ I would like a hint for this problem
1
vote
2answers
22 views

What $P(E)\sim (E \to \{ 0,1\} )$ mean?

i was asked to prove: $P(E)\sim (E \to \{ 0,1\} )$. the left-hand side is the set of all subsets of $E$. (Right?) What about the right-hand side? Thanks.
0
votes
1answer
28 views

Proof Check: The cardinality of the set of all binary series with an infinite amount of 0's and 1's:

Label the set of all binary series with an infinite amount of 0's and 1's as $C$. It's easy to prove that the set (labeled $A$) of all binary series with a finite number of 1's is countable. I can ...
1
vote
1answer
22 views

Given two cardinalities, $m$ and $n$, how many solutions does $n*x = m$ have? How about $n+x=m$?

It looks to me like in the case where both the cardinalites are finite, there exists one solution for the first equation and one solution for the second as long as $m>=n$. Otherwise there's none. ...
0
votes
1answer
26 views

Subset of an infinite set with same cardinality

Let $A$ be an infinite set. Show that there is a subset $B\subseteq A$ such that $|B|=|A-B|=|A|$. I've tried using Zorn's lemma with $P(A)$ and $\subset$ and got nowhere. I would like a hint.
2
votes
1answer
26 views

Set of Cardinals

Let $A$ be a set of cardinals. Prove that there is a cardinal that that is greater than every cardinal in $A$. Assume that there isn't such a cardinal. Then for any cardinal $x$ there is $y\in A$ such ...
1
vote
2answers
62 views

equivalence classes and cardinality

I need to prove that every equivalence class created by the equivalnce relation $\sim$ on $\mathbb{R}$, that is defined by: $a\sim b \Leftrightarrow (a-b) \in \mathbb{Q}$, is $\aleph_0$. Furthermore, ...
0
votes
1answer
41 views

Find the cardinal of the set of all infinite sequences of $0,1,-1$ such that each sequence contains each digit at least once - Check my answer

As the title says, we are asked to find the cardinal of the set of all infinite sequences made from the digits $0,1,-1$ such that each sequence contains each digit at least once. My answer I solved ...
3
votes
1answer
39 views

Supremum of a set of cardinalities.

Let $A$ be a set of cardinalities. Does $A$ have a supremum among all cardinalities. How about infimum?
0
votes
2answers
78 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 ...