Post Reply 
 
Thread Rating:
  • 0 Votes - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Countability of Sets
09-25-2010, 12:48 PM
Post: #1
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})$?
Find all posts by this user
Quote this message in a reply
10-18-2010, 02:29 PM
Post: #2
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.
Find all posts by this user
Quote this message in a reply
Post Reply 


Forum Jump:


Contact Us | Software Frontier | Return to Top | Return to Content | Lite (Archive) Mode | RSS Syndication