recent forum posts
 From categories: All categories general discussion: help! technical questions: wiki stuff technical questions: typesetting mathematics

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

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


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

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?

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.

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?

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.

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?

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.

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.

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.

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