# Thread: Infinite sets and Countable sets

1. ## Re: Infinite sets and Countable sets

I'm sorry I still don't get it.

I don't understand what (c) and (d) are and how do their elements look like.

2. ## Re: Infinite sets and Countable sets

Originally Posted by jfk
I'm sorry I still don't get it.
I don't understand what (c) and (d) are and how do their elements look like.
For c). The characteristic function is ${1_A}(x) = \left\{ {\begin{array}{rl} {1,}&{x \in A} \\ {0,}&{x \notin A} \end{array}} \right.$.
Look at the collection $\left\{1_{\{k\}}:k\in\mathbb{N}\right\}$

For d) define $f_k=\{(0,k),(1,k+1)\}$. Now for each $n\in\mathbb{N}$ the function $f_n$ mapps $\{0,1\}\to\mathbb{N}$.

3. ## Re: Infinite sets and countable sets

Originally Posted by jfk
I don't understand what (c) and (d) are and how do their elements look like.
If you need to visualize them to help you see the problem better, try visualizing them in terms of the suggestion made by DrSteve earlier in this thread.

(c) Functions from $\mathbb N$ to $\{0,1\}$ are essentially infinite sequences of $0\text{'s}$ and $1\text{'s}$ – e.g. $(1,0,1,0,1,\ldots),$ $(0,0,1,0,0,1,\ldots),$ $(1,1,1,1,\ldots),$ etc. Can you visualize an infinite list of such infinite sequences?

(d) Functions from $\{0,1\}$ to $\mathbb N$ can be regarded as sets of two ordered pairs of the form $\{(0,m),(1,n)\}$ where $m,n$ are natural numbers. Can you visualize an infinite list of such sets?

4. ## Re: Infinite sets and Countable sets

An algebraic number is the solution of a polynomial equation with integer coefficients. For example, the fraction m/n is a solution of nx-m=0. This shows that all rational numbers are algebraic numbers. But there are also lots of algebraic numbers that are irrational. For example, the polynomial equation x^2-c=0 gives two algebraic numbers that are irrational whenever c is not a perfect square. It is not hard to show that the set of algebraic numbers is countable. Therefore, there are uncountably many transcendental numbers.

5. ## Re: Infinite sets and Countable sets

Thanks DrSteve, and thank you all for your time and your patience,
I believe that the source of confusion came along with something I read somewhere, where it said that "all the Transcendental numbers are not Algebraic" therefore I concluded that all the Irrationals should be Transcendental however, now I understand my mistake since ${x^2}-2=0$ gives two irrational numbers that are not transcendental since they solve the last polynomial equation.

by the way I figured out (c) and (d):

(c) $\{f\in\{0,1\}^\mathbb{N}|f(n)=\begin{cases}{1, n\in\{n\}} \\ {0, n\notin\{n\}}\end{cases}\}$.
This should generate a set with the following sequences: $\{(1,0,0,0,...),(0,1,0,0,...),(0,0,1,0,...),(0,0,0 ,1,...),\}$

(d) $\{f\in\mathbb{N}^{\{0,1\}}|f(\{n\})=\{(0,n),(1,n+1 )\}\}$.
This should generate a set which contains sets of the form: $\{\{(0,1),(1,2)\},\{(0,2),(1,3)\},\{(0,3),(1,4)\}, ...\}$

Is that correct?

6. ## Re: Infinite sets and Countable sets

Originally Posted by jfk
Is that correct?
The idea is correct, but the notation is a bit off.

Originally Posted by jfk
(c) $\{f\in\{0,1\}^\mathbb{N}|f(n)=\begin{cases}{1, n\in\{n\}} \\ {0, n\notin\{n\}}\end{cases}\}$.
If $f(n)=\begin{cases}{1, n\in\{n\}} \\ {0, n\notin\{n\}}\end{cases}\}$, then f(n) = 1 for all n because $n\in\{n\}$ for all n

Originally Posted by jfk
(d) $\{f\in\mathbb{N}^{\{0,1\}}|f(\{n\})=\{(0,n),(1,n+1 )\}\}$.
There is a type error here because if $f\in\mathbb{N}^{\{0,1\}}$, then f cannot be applied to {n}.

7. ## Re: Infinite sets and Countable sets

How can I generate the above sequences? I really spent a lot of time trying to understand this and I'm still stuck...

8. ## Re: Infinite sets and Countable sets

Specifying a countable subset of some set X is more easily done by giving a sequence of elements of X (i.e., a function from $\mathbb{N}$ to X) than by using a set-builder notation {x ∈ X | ...}. So a sequence of function $f_0, f_1,\dots$ in $\{0,1\}^{\mathbb{N}}$ can be defined by

$f_k(n)=\begin{cases}1& n=k \\0& n\ne k\end{cases}$

A sequence of function $f_0, f_1,\dots$ in $\mathbb{N}^{\{0,1\}}$ can be defined by

$f_k=\{(0,k),(1,k+1)\}$

9. ## Re: Infinite sets and Countable sets

$f_k(n)=\begin{cases}1 & n=k \\0 & n\ne k\end{cases}$
But n and k are always equals, aren't they? That would lead every component in the sequence to be 1 as fa as I understand...

10. ## Re: Infinite sets and Countable sets

Originally Posted by jfk
But n and k are always equals, aren't they?
The notation

$f_k(n)=\begin{cases}1 & n=k \\0 & n\ne k\end{cases}$

means (in this context) that f is a function from $\mathbb{N}\times\mathbb{N}$ to {0, 1}: f(k, n) = 1 or 0 depending on whether n = k. We write f(k, n) as $f_k(n)$. The arguments (k, n) of f can be any pair from $\mathbb{N}\times\mathbb{N}$.

11. ## Re: Infinite sets and Countable sets

Thanks emakarov now I got it

Page 2 of 2 First 12