5
$\begingroup$

I am very weak in logic.

In Wikipedia, there is the following article:

In combinatorics, the union-closed sets conjecture is an elementary problem, posed by Péter Frankl in 1979 and still open. A family of sets is said to be union-closed if the union of any two sets from the family remains in the family. The conjecture states:
For every finite union-closed family of finite sets, other than the family containing only the empty set, there exists an element that belongs to at least half of the sets in the family.

I wonder if $\emptyset$ is a finite union-closed family of finite sets, ohter than the family containing only the empty set or not.
If so, I wonder if there exists an element that belongs to at least half of the sets in $\emptyset$ or not.

Proposition 1:
$\emptyset$ is a finite union-closed family of finite sets and is not equal to $\{\emptyset\}$.

Proposition 2:
There exists an element that belongs to at least half of the sets in $\emptyset$.

Is Proposition 1 true or false?
Is Proposition 2 true or false?

My attempt is the following:

About Proposition 1:
No object belongs to $\emptyset$, but $\emptyset$ belongs to $\{\emptyset\}$.
So, $\emptyset \neq \{\emptyset\}$.
$\emptyset$ is a finite set. (this fact is famous.)
Since $\emptyset\ni S$ is always false, so "if $\emptyset \ni S$, then $S$ is a finite set" is true.
So, $\emptyset$ is a family of finite sets.
Since $\emptyset\ni S, T$ is always false, so "if $\emptyset\ni S, T$, then $S \cup T\in\emptyset$" is true.
So, $\emptyset$ is a finite union-closed family of finite sets and is not equal to $\{\emptyset\}$.

About Proposition 2:
I guess this proposition is false.
There is no set which belongs to $\emptyset$.
So, there is no element that belongs to a set which belongs to $\emptyset$.
I cannot express Proposition 2 by using logical symbols.
How to express Proposition 2 by using logical symbols?

$\endgroup$
2
  • 1
    $\begingroup$ Your thoughts seem to be valid. I have a question though. What do you mean by "there is an element" which belongs to half of the sets? Where does this element come from? Is it a set? Or is it an element from the union of the family? $\endgroup$ Apr 20 at 11:45
  • 1
    $\begingroup$ @AniruddhaDeshmukh: the Wikipedia article is easy to find and should help to explain. The element must be an element of the union of the family and there is no real ambiguity about that. $\endgroup$
    – Rob Arthan
    Apr 20 at 23:43
2
$\begingroup$

To express proposition 2 you need a function that returns the size of a finite set and you need to use some of the language of arithmetic. If the size function is called $\#$, the statement of the proposition could be formalised as: $$ \exists x (2 \cdot \#\{A \in S \mid x \in A\} \ge \#S) $$

$\endgroup$
1
  • $\begingroup$ Rob Arthan, Thank you very much for your answer. $\endgroup$
    – tchappy ha
    Apr 20 at 23:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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