×

# Prove or Disprove:

Given a finite collection of of sets, closed under union (that is, if $$A$$ and $$B$$ are sets belonging to the collection, then $$A\cup B$$ is also a set in the collection.)

Prove or disprove: There exists an element that belongs to at least half the sets in the collection.

Note by Calvin Lin
2 years, 2 months ago

Sort by:

I'll be impressed if someone comes up with a proof/disproof here, as it is presently an open question in mathematics, (first posed by Peter Frankl in 1979). :) · 2 years, 2 months ago

I don't know about what does this "closed under union" means exactly !! No theoretical knowledge about it. But I think It can be proved using the Principle of Mathematical Induction. One can easily show it for only sets (that is A and B). Assume it true for $$n$$ sets and then try to prove it for $$n+1$$sets. · 2 years, 2 months ago

As explained, a collection of sets is closed under union if given any 2 sets $$A$$ and $$B$$ in the collection, then $$A \cup B$$ must also be in the collection.

Standard Induction on the number of sets in the collection would unlikely work. Strong Induction might offer a possibility of approach. Staff · 2 years, 1 month ago

Any hints, @Calvin Lin? · 2 years, 1 month ago

Not really. Brian gave it away by stating that it is an open question.

Sometimes, open questions are solved by "amateur mathematicians" who had no idea that the problem was really difficult. This is a question that has "Olympiad Combinatorics" roots, so I felt was interesting to the L4/5's, and so I posted it. I was hoping that someone had an ah-ha moment, and could figure out a way to solve this.

I am interested in seeing approaches that people tried, and how far they pushed it out. Staff · 2 years, 1 month ago

Sorry for spoiling the fun, but I thought it would help others to know the background of the question and what approaches have been taken before. · 2 years, 1 month ago

I was going to mention the empty set, but then I realized that you mentioned that "there exists an ELEMENT", not a set. If that were the case, this conjecture would have been proven a long time ago. · 2 years, 1 month ago

Well, avoid trivial cases by adding "non-empty collection" into the conditions. Staff · 2 years, 1 month ago

×