• 0 Votes - 0 Average
• 1
• 2
• 3
• 4
• 5
 Countability of Sets
09-25-2010, 12:48 PM
Post: #1
 elim Moderator     Posts: 544 Joined: Feb 2010 Reputation: 0
Countability of Sets
(1) Is the set of all functions from $\{0,1\}$ to $\mathbb{N}$ countable?
(2) Is the set of all functions from $\mathbb{N}$ to $\{0,1\}$ to countable?
(3) Given a set $\mathbb{B}$, a subset $\mathbb{A}$ of $P(\mathbb{B})$ is called an antichain if $\forall A,B \in \mathbb{A} (A \bigtriangleup B \ne \varnothing )$
$\quad\quad$ Is there a uncountable antichain of $P(\mathbb{N})$?
10-18-2010, 02:29 PM
Post: #2
 elim Moderator     Posts: 544 Joined: Feb 2010 Reputation: 0
RE: Countability of Sets
(1) $\mathbb{N}^{\{0,1\}} \simeq \{(a,b) \mid a,b \in \mathbb{N}\}$ is countable
(2) $\{0,1\}^{\mathbb{N}} \simeq P(\mathbb{N})$ is uncountable
(3) Let $\mathbb{N}_1$ be odd numbers of $\mathbb{N}$, $\mathbb{N}_2 = \mathbb{N} \setminus \mathbb{N}_1$
$\quad\quad$Let $g: \mathbb{N}_1 \to \mathbb{N}_2$ be the natural $1-1$ correspondence.
$\quad\quad$Define $A = \{ E \cup g(\mathbb{N}_1 \setminus E) | E ∈ P(\mathbb{N}_1) \}$, Then $A$ is an antichain of $P(\mathbb{N})$ that is uncountable.
 « Next Oldest | Next Newest »

Forum Jump: