Re: Infinite Meet or no-meets


Jesse F. Hughes wrote:
"Pubkeybreaker" <Robert_silverman@xxxxxxxxxxxx> writes:

Jesse F. Hughes wrote:
"Pubkeybreaker" <Robert_silverman@xxxxxxxxxxxx> writes:

Jesse F. Hughes wrote:
"Pubkeybreaker" <Robert_silverman@xxxxxxxxxxxx> writes:

Guy L. wrote:
I am a bit perplexed by the following problem.

Suppose a set of aleph_0 many people are given. Show there is an
infinite subset of that set such that either all the people in the
subset have met one another or all the people in the subset have not
met one another.

How does one go about to prove the above problem? I would ask my
teachers, but none of my teachers at my high school would know...

Let S be your set. Partition it into two disjoint subsets A and B. So
S = A U B.
Let A be the set of people who have not met one another.

I don't see that your set A is well defined. Suppose that our set
consists only of three people (rather than aleph_0). Suppose persons
1 and 2 have met, but no other pair of persons have met.

Then 1 hasn't met 3, so I guess both 1 and 3 are in the set. But 2
hasn't met 3 either, so is 2 in the set or not?


A is the set of all people such that each person in the set has not
met all others in the set. So 2 is in the set. In your example,
1,2, and 3 are in the set since none of them have met all the
others. It does not matter if some people in the set have met some
of the others.

But the problem says that we need to find an infinite set such that
either (1) everyone in that set has met everyone else in the set or
(2) no one in the set has met anyone else in the set.

I don't see that your partition helps us do that.

If A is infinite we have satisfied the conditions of the problem.
We have an infinite subset where every member has not met all the
the others in that set.

As you say, we interpret the problem differently.

The aim is to find a set where "all the people in the subset have
not met one another." Now, I parse that as: We need a set A such that
for all x and y in A, x has not met y.

You seem to interpret it instead as: Find a set A such that for every
x there is a y such that x has not met y.

I don't think your interpretation is correct, but I suppose only the
original poster can settle this.

The original problem said:

"Suppose a set of aleph_0 many people are given. Show there is an
infinite subset of that set such that either all the people in the
subset have met one another or all the people in the subset have not
met one another. "

So if partition S, the set of all people, as S = A U B, where the
set A
conforms to your interpretation, then set B would be:

For all x,y, in B x and y have met. (i.e. all have met everyone
else)

Is this correct??? Or does B become:

For all x in B, x has met at least one other.????

But suppose we label the people 1,2,3,4,5,6....... and suppose
that 2i has met 2i-1, but noone else for all i. Certainly this
is possible.

Then the partition seems impossible. Since every person has met
exactly
one other, set A is empty under your interpretation. Thus S = B.
But
B does not satisfy the conditions, because everyone in B has not met
everyone
else....

.

Relevant Pages

  • Re: Infinite Meet or no-meets
    ... I don't think your interpretation is correct, ... original poster can settle this. ... So if partition S, the set of all people, as S = A U B, where the ... That was your own suggestion, ...
    (sci.math)
  • Re: Infinite Meet or no-meets
    ... infinite subset of that set such that either all the people in the ... teachers, but none of my teachers at my high school would know... ... I don't see that your partition helps us do that. ... part of who I am is an endless amount of energy as long as there is ...
    (sci.math)
  • Re: Infinite Meet or no-meets
    ... I don't see that your partition helps us do that. ... We have an infinite subset where every member has not met all the ... we interpret the problem differently. ... "They are anti-mathematicians, evil incarnate, dedicated to undermining ...
    (sci.math)