1

I would like some help on these claims. Thanks in advance!

True or false? If true, give a proof, if not, give a counterexample.

  1. If $A$ is a set of functions $\Bbb N \rightarrow \Bbb N$ and for each $f,g\in A$, the set $\{n\in N : f(n)\neq g(n)\}$ is finite, then $A$ is finite or countable ($\aleph_0$).

  2. If $A$ is a set of infinite subsets in $\Bbb R$ and for every $X, Y\in R$, $X\cup Y=\emptyset$, then A is countable.

Thanks again for any help, tips etc'!!!

ohad
  • 633
  • Don't you mean that A is a subset of the set of functions from the natural numbers to themselves? We already know what's the cardinality of this set. – AnonymouseCat Apr 30 '13 at 12:40
  • Also, about 2, we already know what's the cardinality of the set of infinite real subsets, so I think that you should say that A is a subset of infinite real subsets. – AnonymouseCat Apr 30 '13 at 12:41
  • @NoySoffer I think 1. is clear. The OP says "a set of functions" and not "the set of all functions". Furthermore, the condition he gives makes only sense if it's a subset. – Elmar Zander Apr 30 '13 at 12:57
  • Concerning 2.: Shouldn't it be rather something like "... and for all $X,Y\in A$ with $X\not=Y$ it holds that $X\cap Y=\emptyset$, then..."? – Elmar Zander Apr 30 '13 at 13:02

1 Answers1

2

HINTS:

  1. Fix some $f_0\in A$. For each $g\in A$ let $F_g=\{n\in\Bbb N:g(n)\ne f_0(n)\}$; by hypothesis each $F_g$ is finite.

    • How many finite subsets of $\Bbb N$ are there?
    • If $F$ is some finite subset of $\Bbb N$, how many different functions $g:\Bbb N\to\Bbb N$ are there such that $F_g=F$?

  2. I’m pretty sure that you meant $X\cap Y=\varnothing$ in the statement of the problem, so I’m answering on that basis. Consider sets of the form $x+\Bbb Z=\{x+n:n\in\Bbb Z\}$.

Brian M. Scott
  • 616,228