Home MATH 318 Monday, November 14, 2011

Monday, November 14, 2011 CC-BY-NC
Couldn't make it to class

Maintainer: admin

1There is no set that is onto its power set

Claim: For any $A$, there is no function $f: A \rightarrow P(A)$ which is onto $P(A)$. N.B. $a \mapsto \{a\}$ is an injection from $A$ onto $P(A)$.

Proof: Suppose $f:A \rightarrow P(A)$ ( So $f(a) \subseteq A$ for each $a \in A$. Let $S_f = \{a \in A: a \notin f(a)\}$. I claim that $S_f \notin ran(f)$. If it were, then it is $F(a)$ for some $a \in A$. But then $a \in S_f$, which is a contradiction.

1.1More about $\omega$

Assuming that $\omega$ exists, it is infinite. $P(\omega)$ is a larger infinite set, and $P(P(\omega))$ is even larger. Generally, for $n \in \omega$, we define $P^n(\omega)$ recursively. Given $P^n(\omega)$, let $P^{n+1}(\omega) = P(P^n(\omega))$. Consider $\{P^n(\omega):n \in \omega\}$. Let $P^{\omega}(\omega) = \bigcup \{P^n(\omega): n\in \omega \}$. (Very informally, $P^{\omega}(\omega)$ is $\omega \cup P(\omega) \cup P(P(\omega)) \cup ...$) This is bigger than any $P^n(\omega)$.

Let $P^{s \omega}(\omega) = P(P^{\omega}(\omega))$, etc, etc.

1.2$P(\omega) \sim R$

Given a set $A$ and $B \subseteq A$, let $X_B \in \{0,1\}$ be defined by $X_B(a) = 1$ if $a \in B$ and $X_B(a) = 0$ if $a \notin B$. The function $\Phi : P(A) \mapsto 2^A$ given by $\Phi(B) = X_B$ is a bijection (N.B. T show that $\Phi$ is onto, let $f:A \mapsto \{0,1\}$ and $B = \{a \in A: F(a) =1\}$. Then $f = X_B$.

1.3If $\omega$ exists, it is an ordinal

  • To see it's transitive, let $y \in x \in \omega$. $x$ is a natural number. So $y$ is a natural number, and hence $y \in \omega$.
  • If $x \in \omega$, $x \notin x$ (since $x \in Sx$ is an ordinal).
  • If $x, y \in \omega$, we can't have $x \in y \land y \in x$
  • If $x, y, z \in \omega$, $x \in y \land y \in z$, then $x, y, z$ are natural numbers, hence transitive. So $x \in z$.
  • If $x, y \in \omega$, then they are ordinals, so $x\in y \lor x = y \lor y \in x$
  • Finally, suppose $B \neq \varnothing$ and $B \subseteq \omega$. Let $x \in B$, where $x$ is an ordinall. Possibly, $x \cap B = \varnothing$; if so, $x$ is the smallest element of $B$. If not, $x \cap B$ is a nonempty subset of $x$, and has a smallest element $y$. Uf there is $z \in B, z \in y$, then by transitivity, $z \in x$; so $\in x\cap B$. //

1.4$S\omega$ is not a cardinal

$S\omega$ is an ordinal, and so is $SS\omega$. I will define a bijection $f: S\omega \mapsto \omega$, thus showing that $S\omega$ is not a cardinal.

Let $f(\omega)=0$. Any $n \in S\omega$ that isn't $\omega$ is a natural number; let $f(n) = S(n)$.

$\omega$ itself is a cardinal. Why?

Consider the set $A = \{x \in \omega : x \not \sim \omega\}$. $0 \in A$ since 0 doesn't have elements byt $\omega$ does. Now suppose $x \in A$. I claim that $Sx \in A$. If so, $A$ is inductive and $w \subseteq A$. Since $A \subseteq \omega$, $A = \omega$.

We'll prove this by contradiction. Suppose $x \in A$, $Sx \notin A$. let $f:\omega \mapsto Sx$ be a bijection. There must be $n \in \omega$ such that $f(n) = x$. The restriction $g=f:\omega \setminus \{n\} \mapsto x$ is a bijection between $\omega \setminus \{n\}$ and $x$ ($g(m) = f(m)$ if $m \neq n$).

But $w \setminus \{n\} \sim \omega$. To see this, let $h: \omega \mapsto \omega \setminus \{n\}$ be given by $h(m) = m$ if $m < n$ and $h(m) = Sm$ if $m > n$.

$g \circ h: \omega \mapsto x$ is a bijection. That's a contradiction. $\blacksquare$