recent forum posts
From categories:
Hints
Dana ErnstDana Ernst 03 Dec 2009 14:53
in discussion Hidden / Per page discussions » Problem 7.4.9

This problem is awesome!

First, the $\LaTeX$ syntax for $\mathcal{P}(\mathbb{N})$ is

[[$\mathcal{P}(\mathbb{N})$]]

Let $X$ be set of all sequences of 0's and 1's. Each element of $X$ is of the form $(a_i)_{i=1}^{\infty}$, where each $a_i$ equals 0 or 1 (but not both!). In order to show that $\mathcal{P}(\mathbb{N})$ and $X$ have the same cardinality, we need to show that there is a 1-1 correspondence between the two sets. Our job is to construct a function between these two sets and then show that it is (1) 1-1, and (2) onto. The hardest part is figuring out what the function should be and actually writing it down nicely. I'll do that part for you now.

Define $f: \mathcal{P}(\mathbb{N}) \to X$ via

(1)
\begin{align} f(A)=(a_i)_{i=1}^{\infty}, \end{align}

where $A\subseteq \mathbb{N}$ and $(a_i)$ is defined by

(2)
\begin{align} a_i=\begin{cases} 0, & \text{if } i\notin A\\ 1, & \text{if } i\in A \end{cases}. \end{align}

The $\LaTeX$ syntax for the above definition of $a_i$ is

[[math]]
a_i=\begin{cases}
0, & \text{if } i\notin A\\
1, & \text{if } i\in A
\end{cases}.
[[/math]]

All that remains to do is to show that $f$ is 1-1 and onto.

Hints by Dana ErnstDana Ernst, 03 Dec 2009 14:53
Hints
Dana ErnstDana Ernst 03 Dec 2009 14:36
in discussion Hidden / Per page discussions » Corollary 7.4.6

Proceed by contradiction. Recall that $\mathbb{R}$ is equal to the union of the rationals and irrationals. If the irrationals are countable, what does Exercise 7.3.9 tell us?

Hints by Dana ErnstDana Ernst, 03 Dec 2009 14:36
Hints
Dana ErnstDana Ernst 03 Dec 2009 14:29
in discussion Hidden / Per page discussions » Corollary 7.4.5

As in Corollary 7.4.4, use a proof by contradiction. In each case, assume the interval is countable. Appeal to Exercise 7.1.2(2) to conclude that each of these intervals has the same cardinality as an interval that you already know something about.

Hints by Dana ErnstDana Ernst, 03 Dec 2009 14:29
Hints
Dana ErnstDana Ernst 03 Dec 2009 14:14
in discussion Hidden / Per page discussions » Corollary 7.4.4

Use a proof by contradiction. Assume that $\mathbb{R}$ is countable. Then by definition, there exists a 1-1 correspondence $f: \mathbb{N}\to \mathbb{R}$. We'd like to use the fact that the interval $(0,1)$ is uncountable (see Theorem 7.4.3) to get a contradiction. Let $X=f^{-1}((0,1))$. Define a new function $f^*:X\to (0,1)$ via $f^*(n)=f(n)$ (this is similar to what we did in the proof of Theorem 5.1.16). Show that $f^*$ is onto. What does Theorem 7.3.5 say in this case?

Hints by Dana ErnstDana Ernst, 03 Dec 2009 14:14
Hints
Dana ErnstDana Ernst 02 Dec 2009 03:44
in discussion Hidden / Per page discussions » Theorem 7.3.6

Consider the set of fractions listed in Figure 7.3 on page 165. Let's call this set $F$. Notice that $\mathbb{Q}\subseteq F$ (we're not reducing the fractions in $F$). If we can show that $F$ is countable, then we're done (by Theorem 7.3.4). The general strategy here is to construct a function $f: \mathbb{N}\to F$ that is onto and then appeal to Theorem 7.3.5. Doing this is rather tricky and probably best to do by drawing a picture. Try to find a path through the grid in Figure 7.3 that hits every fraction exactly once. Define $f: \mathbb{N}\to F$ via $f(n)$ is the fraction that you hit on the $n\text{th}$ step in your path.

If you can figure out the path by drawing a picture, I can help you scan it and post it here.

Hints by Dana ErnstDana Ernst, 02 Dec 2009 03:44
Hints
Dana ErnstDana Ernst 02 Dec 2009 03:32
in discussion Hidden / Per page discussions » Theorem 7.3.5

For each $x\in X$, choose exactly one $n_x\in\mathbb{N}$ such that $f(n_x)=x$. We know that we can do this since $f$ is onto. Also, since $f$ is a function, we know that $f(n_x)\neq f(n_y)$ whenever $x\neq y$. Now, define the set $N'\subseteq \mathbb{N}$ via

(1)
\begin{align} N'=\{n_x:x\in X\}. \end{align}

What does Theorem 7.3.4 tell us about $N'$? Next, define the function $g: N'\to X$ via $g(n_x)=x$. Is $g$ onto? How about 1-1? What does Theorem 7.3.3 tell us?

Hints by Dana ErnstDana Ernst, 02 Dec 2009 03:32
Hints
Dana ErnstDana Ernst 02 Dec 2009 02:54
in discussion Hidden / Per page discussions » Theorem 7.3.3

There are quite a few ways to approach this problem. Here's one way. Consider two cases:

  1. $C$ finite,
  2. $C$ countably infinite.

In case 1, there exists a 1-1 correspondence $g: \{1,2,\dots,k\}\to C$ for some $k$ (by definition of $C$ being finite). Consider the composition $f\circ g: \{1,2,\dots, k\}\to B$ and take a look at Theorem 5.2.3. Conclude that $B$ is finite and hence countable.

In case 2, there exists a 1-1 correspondence $g: \mathbb{N}\to C$ (since $\mathbb{N}$ and $C$ have same cardinality). Again consider the composition $f\circ g$ and argue similar to case 1, except you will conclude that $B$ is countably infinite.

Hints by Dana ErnstDana Ernst, 02 Dec 2009 02:54

This looks perfect now. David, thanks for taking the time to post the original content. Pat, thanks for letting us log in under you. Everyone, thanks for helping edit it.

Looking good! by Dana ErnstDana Ernst, 01 Dec 2009 22:05

Hey Allie, don't get too frustrated. Have you taken a look at the Quick LaTeX Guide? There are a few examples there that you should try to mimic. In general, any mathematical notation is of the form

[[$ insert LaTeX equation here $]]

Between the dollar signs is where you place specific $\LaTeX$ commands for whatever math symbol(s) you want. All $$\LaTeX$ commands begin with the \-symbol. For example, if you wanted to typeset "square root of x squared plus y squared", you would type the following in the page editor.

[[$\sqrt{x^2+y^2}$]]

The result of the above is code is:

$\sqrt{x^2+y^2}$

Also, notice that when you are in the page editor, among the many buttons above the text box are two labelled $\sqrt{x}$ and $x/2$, respectively. The first of these inserts initial code for a mathematical expression or equation that you want to display on its own line and centered. The second button inserts the initial code for an inline mathematical expression. Using these buttons can save you a bit of typing.

Just try it out and see what happens. The beauty of the wiki is that you can go back and fix and/or edit things at any later date. It doesn't have to be perfect on the first go. Let me know if you have more questions.

Re: how.... by Dana ErnstDana Ernst, 26 Nov 2009 02:15

how exactly so I make the symbols on the editor, i'm so lost and beyond frustrated :(

how.... by Alyson SewellAlyson Sewell, 25 Nov 2009 17:56
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License