Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $[\mathbb{N}]^2$ denote the set collection in size $2$. Now, let $f:[\mathbb{N}]^2\to \{1,2\}$.

How can one show that, if we fixing some $n\in \mathbb{N}$, then there exist infinite set $R_1\subseteq {\mathbb{N}-\{n\}}$ such that $f$ is constant on sets of the form $\{n,r_1 \}$ where $r\in R_1$ .

share|improve this question
    
What is "set collection in size $2$"? If you mean the set of unordered pairs, then $\binom{\Bbb N}2$ (pronounced $\Bbb N$ choose $2$) would be a more understandable notation. –  Marc van Leeuwen Nov 15 '12 at 14:20

1 Answer 1

up vote 2 down vote accepted

Fixing $n\in\Bbb N$, there are infinitely many $r\in\Bbb N\smallsetminus\{n\}$, and so infinitely many sets $\{n,r\}$ with $r\in\Bbb N\smallsetminus\{n\}$. Now, each $\{n,r\}$ is mapped to either $1$ or $2$. If there were only finitely many $\{n,r\}$ mapping to $1$ and only finitely many $\{n,r\}$ mapping to $2$, then since a union of two finite sets is finite, we would only have finitely many $\{n,r\}$ to begin with, which we've already seen is not the case. Hence, there are infinitely many $\{n,r\}$ mapping to $1$ or there are infinitely many $\{n,r\}$ mapping to $2$.

If there are infinitely many $r$ such that $f$ maps $\{n,r\}\mapsto 1$, then we let $$R_1=\left\{r\in\Bbb N:\{n,r\}\in f^{-1}\bigl(\{1\}\bigr)\right\}.$$ Otherwise, we let $$R_1=\left\{r\in\Bbb N:\{n,r\}\in f^{-1}\bigl(\{2\}\bigr)\right\}.$$

share|improve this answer
    
Actually, $R_1 = \{r:\{n,r\}\in f^{-1}(\{1\})\}$, isn't it? $f^{-1}(\{1\})$ is not a subset of $\mathbb N$ –  Thomas Andrews Nov 15 '12 at 14:07
    
Ah! Right you are, Thomas. –  Cameron Buie Nov 15 '12 at 14:38
    
@ThomasAndrews why "If not, then there must be only finitely many sets {n,r}, which is certainly not the case."? –  17SI.34SA Nov 16 '12 at 17:30
1  
@17SI.34SA: Because there are infinitely many $r\in\Bbb N\smallsetminus\{n\}$, and so there are infinitely many sets $\{n,r\}$ with $r\in\Bbb N\smallsetminus\{n\}$. All of these sets are mapped to either $1$ or $2$, but if only finitely many map to $1$ and only finitely many map to $2$, then there can be only finitely many to begin with (since the union of two finite sets is finite). –  Cameron Buie Nov 16 '12 at 17:37
    
Thank you again! It's all clear now! –  17SI.34SA Nov 16 '12 at 17:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.