• Support PF! Buy your school textbooks, materials and every day products Here!

Set theory question!

  • Thread starter juanchoba
  • Start date
  • #1
2
0

Homework Statement


Hi everyone, i have the following problem, that for the moment i couldn't find the solution or even how to search about...

This is it, we have a family of subsets F ={F_1,...,F_p} of the set {1,2,...,k}.

We know that, for every i != j, F_i !=F_j
and for every pair of elements a, b \in {1,2,...k} there exists one F_i
such that a belongs to F_i but b does not.
(this is, no pair of elements belong to exactly the same sets)

Notice that with this restriction, at most one element can be outside every F_i.

it is clear that p should be at least ceiling ( log_2 ( k ) ).

First question. Does this family of sets have any name in the literature?

Second question:
Consider now the maximal sets S_1,S_2,...S_s such that
S_i is a subset of F and the intersection of every F_j \in S_i is non-empty.
The maximality means that there is no S_i subset of S_j with exactly
the same intersection, i.e., the intersection of F_x \in S_i != intersection of F_x \in S_j
for S_i subset of S_j.

I want to prove that s >= k-1

Thank you all for any answer :)
Juan!


Homework Equations





The Attempt at a Solution


No idea how to solve but just in particular cases, for example for p = k-1
and F_i ={i}....
 

Answers and Replies

  • #2
2
0
mmh nothing...? :(
 

Related Threads on Set theory question!

  • Last Post
Replies
1
Views
439
  • Last Post
Replies
2
Views
958
  • Last Post
Replies
3
Views
467
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
3
Views
583
  • Last Post
Replies
2
Views
734
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
10
Views
3K
  • Last Post
Replies
1
Views
770
Top