A nice problem

[Principe2]

Prove that there exists a non-countable family $F$ of subsets of $\NN$ such that $I\capJ$ is finite, for all distinct $I,J\in F$.

Solutions longer than one line are not accepted!

[Principe2]

"ViciousGoblin": forgive me if I hadn't really understood it at first

don't worry. I think that the confusion was born from my mistake of putting those brackets...

[ViciousGoblin]

"ubermensch":No: $I_s$ is a sequence of natural numbers, i.e. an infinite subset of $\NN$.

Your note prove just that $I_s\cap I_t$ is finite for distinct $s,t\in(0,1)$.

NOW I GET IT. So $I_s$ is a SINGLE subset of $NN$, which is the image of the sequence of all $n$-approximations of $s$ - for instance if $s=0.1324754325...$ , then
$I_s={1,13,132,1324,13247,132475,....}$ I agreee that this is an infinite set (which I hadn't understood before and which makes me feel much better).

And if the $n$-th element of $I_s$ and $I_{s'}$ (oredered in magnitude) coincide, then the same happens for all previous elements of the sequences - which means that if $I_s$ and $I_{s'}$ coincide on an infinite subset they are the same set (due to the nature of the decimal approximations).

I COMPLIMENT YOU - the one line proof is really nice - forgive me if I hadn't really understood it at first

[Principe2]

No: $I_s$ is a sequence of natural numbers, i.e. an infinite subset of $\NN$.

Your note prove just that $I_s\cap I_t$ is finite for distinct $s,t\in(0,1)$.

[ViciousGoblin]

"ubermensch":Maybe I did a bad explanation: I'm taking $I_s$ as the set of the appoximations of $s$. And $U=\{I_s\}_{s\in(0,1)}$. Now is more clear?

Who is $I_s$ ? If $I_s$ is a made only of finite sets the proof doesn't work: $U_{s\in(0,1)} I_s$ is countable - although $(0,1)$ is uncountable.

Notice that if $s=0,547345686...$ and $s'=0,547345685...$ then the first sets in $I_s$ and $I_{s'}$ coincide.

[Principe2]

Maybe I did a bad explanation: I'm taking $I_s$ as the set of the appoximations of $s$. And $U=\{I_s\}_{s\in(0,1)}$. Now is more clear?

[ViciousGoblin]

@ubermensh I'm afraid your proof doesn't work - are you taking $I_s$ made of finite sets? If so they will "replicate" !!
I mean $\cup_{s\in(0,1)}I_s\subset$ "finite subsets of $NN$" is countable.
It is quite easy to see the set of all finite parts of $NN$ is contable ($= U_n{F\subsetNN: F\subset{0,1,...,n}}, $ countabe union of finite sets).

But may be I'm not fully understanding your construction

[fu^2]

yeah, good idea, now i have understood all sentence. Is very nice, as the title

[Principe2]

Of course $I_s$ is countable. "The family of $I_s$'s is uncountable!!". I think that I create a little bit of confusion, since I'm wrong to write the brackets. I don't why... maybe because it was 6 a.m.! $I_s={5,52,520,5209,...}$

[fu^2]

i have had the same idea (i have done $0.pi$ )

but i don't know why $I_s$ is noncontable. In fact for each set in $I_s$ exists one number (or position if you write $s=0.s_1s_2s_3...$) in the code of $s$, so that you can buit a bijective map from $I_s$ to the sequence of $s$.

So the sequence $0.520947...$ is contable: for each number in the sequence of $s$ exists only one $k\in NN$ that define it position, then $I_s$ is contable, (i.e.$|I_s|\sim |NN|$).

where do i failure my reasoning?

[Principe2]

@viciousgoblin
you're right! I didn't think to that possibility!

Anyway, the problem is solved!

I post the solution. I would prefer to insert an hidden solution, but I cannot do it. How one can?

Take $s\in(0,1)$, for example $s=0,520947...$. Define $I_s={5,{52},{520},{5209},....}$. ${I_s}_{s\in(0,1)}$ verifies the required properties.

[rubik2]

"ViciousGoblin":Remind that $U$ was (originally) defined as the set of all families $F$ in $P(NN)$ such that

(a) elements of $F$ are infinite subsets of $NN$ (b) given two elements $i$ and $j$ in $F$ their intersection is finite set

Now obviously $F_0={NN}$ is a possible family verifying (a) and (b). $F_0$ is maximal: if $h$ is an infinite subset of $NN$ then $NN\cap j=j$ is infinite, so $F={NN,j}\notin U$

ok, i finally understand. Thank you

[ViciousGoblin]

"rubik":[quote="ViciousGoblin"]If $\bar F$ is a finite family no contadiction arises- for instance $\bar F={NN}$ is a masimal element in $U$
@rubik By the way this shows that $U\ne\emptyset$ - so this was not the problem.

I don't understand why ${NN}$ is maximal in $U$, we have $2^((NN))in F$ and $2^((NN))<{NN}$ isn't true because ${1}in2^((NN))$ and ${1}\notin {NN}$ (for $2^((NN))$ i mean all finite subsets of $NN$), ${NN}$ is "just" a singleton in $P(NN)$, maybe i'm wrong but i thing there is a little misunderstanding between subsets of $NN$ and subsets of $P(NN)$.
I'm asking for $U!=\emptyset$ because i think that Zorn's lemma ask for it (it also ask for a set but usually nobody proves it!)
(i hope my english isn't too bad)[/quote]


Remind that $U$ was (originally) defined as the set of all families $F$ in $P(NN)$ such that

(a) elements of $F$ are infinite subsets of $NN$ (b) given two elements $i$ and $j$ in $F$ their intersection is finite set

Now obviously $F_0={NN}$ is a possible family verifying (a) and (b). $F_0$ is maximal: if $h$ is an infinite subset of $NN$ then $NN\cap j=j$ is infinite, so $F={NN,j}\notin U$

[rubik2]

"ViciousGoblin":If $\bar F$ is a finite family no contadiction arises- for instance $\bar F={NN}$ is a masimal element in $U$
@rubik By the way this shows that $U\ne\emptyset$ - so this was not the problem.

I don't understand why ${NN}$ is maximal in $U$, we have $2^((NN))in F$ and $2^((NN))<{NN}$ isn't true because ${1}in2^((NN))$ and ${1}\notin {NN}$ (for $2^((NN))$ i mean all finite subsets of $NN$), ${NN}$ is "just" a singleton in $P(NN)$, maybe i'm wrong but i thing there is a little misunderstanding between subsets of $NN$ and subsets of $P(NN)$.
I'm asking for $U!=\emptyset$ because i think that Zorn's lemma ask for it (it also ask for a set but usually nobody proves it!)
(i hope my english isn't too bad)

[ViciousGoblin]

"ubermensch":It works!

It doesn't

If $\bar F$ is a finite family no contadiction arises- for instance $\bar F={NN}$ is a masimal element in $U$
@rubik By the way this shows that $U\ne\emptyset$ - so this was not the problem.

Anyway its seems to me that be the argument can be modified to work just adding the condition $#F=\infty$ in the definition of $U$ - the price to pay is that $U\ne \emptyset$ isn't trivial anymore.
So to accomplish the task I need to provide a "starting point" - a family $F_0$ of ininite sets having the finite intersection property.
Well it seems that if $j_n:={n+2^k,k\in NN}$, then $F_0:=\cup_{n\in NN}{j_n}$ should do. Indeed if $n>m$ it seems to me that there is just a finite number of pairs $(h,k)$ such that
$n+2^h=m+2^k <=> n-m=2^h(2^{k-h}-1)$ (at most one -I guess, due to divisibility arguments).

This time things seem reasonable - we start from $F_0$ and we add sets until we reach a maximal family, which needs to be uncountable. Well I hope I am not just going deeper in the swamp.

@ubermensh - you need not say it not going to be accepted - I am really eager to see the simpe argument

[rubik2]

"ViciousGoblin":hope it works since it costed me blood

I think that you should prove that $U!=\emptyset$

[Principe2]

It works! But it cannot be accepted!

[ViciousGoblin]

I try - but it isn't going to fit into one line. If there really is a trivial example I will ....

Let $U:={F\subset P(NN): j\in F\Rightarrow #j=\infty; i\ne j\in F\Rightarrow #(i\cap j)<+\infty}$ (all families, made only of infinite sets having the finite intersection property)
We order $U$ by inclusion: $F_1 It is clear that every chain $U_1$ in $U$ has an upper bound given by $\bar F:=\cup_{F\in U_1}F$ Indeed
$F\subset \bar F$ for all $F$ in $U_1$ and $\bar F\in U$ because given $i\ne j$ in $\bar F$, then $i,j$ both lie
in some $F\in U_1$ (due to $U_1$ being well ordered), so $#(i\cap j)<+\infty$.
By Zorn's Lemma there exists a maximal element $\bar F$ in $U$.
We claim that $\bar F$ is uncountable. By contradiction assume $\bar F={j_1,j_2,...,j_n,...}$ and remind that
$#j_i=+\infty, #(j_i\cap j_k)<+\infty$ whenever $i\ne k$. We define a sequence $(x_n)$ by the properties
$x_1\in j_1$, $x_n\in j_n\setminus \cup_{k=1}^{n-1}j_k$
Such a sequence can be easily constructed by induction PROVIDED $j_n\setminus \cup_{k=1}^{n-1}j_k\ne\emptyset$ $\forall n$.
This is indeed true, because otherwise $j_n=\cup_{k=1}^{n-1}j_n\cap j_k$ would be finite.
Finally we define $\bar j={x_1,...,x_n,...}$. Clearly $#\bar j=+\infty$. Moreover $\bar j\cap j_n\subset{x_1,...x_n}$ (by the way $(x_n)$ was defined)
so it is finite. We can then add $\bar j$ to $\bar F$ contradicting the maximality of $\bar F$.
The only possible way out is admitting that $\bar F$ is uncountable

hope it works since it costed me blood

[Principe2]

Do you mean the set of sequences of natural numbers?
And why is the intersection always finite?

[nato_pigro1]

power set of $NN$?

P.S.: i've looked for the capital "P" of power set but without success...