Solve Set Theory Question: Family of Subsets F of {1,2,..k}

Click For Summary
SUMMARY

The discussion revolves around a set theory problem involving a family of subsets F = {F_1,...,F_p} of the set {1,2,...,k}. The subsets must satisfy specific conditions: for every pair of elements a, b in {1,2,...,k}, there exists a subset F_i such that a is in F_i and b is not. The discussion highlights that the minimum number of subsets p must be at least ceiling(log_2(k)). Additionally, the user seeks to prove that the number of maximal sets S_i, where each S_i has a non-empty intersection with every F_j in S_i, is at least k-1.

PREREQUISITES
  • Understanding of set theory concepts, particularly families of subsets.
  • Familiarity with logarithmic functions, specifically ceiling(log_2(k)).
  • Knowledge of maximal sets and their properties in set theory.
  • Basic proof techniques in mathematics, particularly for combinatorial arguments.
NEXT STEPS
  • Research the concept of "families of sets" in combinatorial set theory.
  • Study the properties of maximal sets and their intersections in set theory.
  • Explore proofs related to the minimum number of subsets required for specific conditions.
  • Investigate applications of logarithmic functions in combinatorial mathematics.
USEFUL FOR

This discussion is beneficial for mathematicians, students studying set theory, and anyone interested in combinatorial proofs and properties of subsets.

juanchoba
Messages
2
Reaction score
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}...
 
Physics news on Phys.org
mmh nothing...? :(
 

Similar threads

Prove every subset of countable set is either finite or else countable
  • · Replies 1 ·
Replies
1
Views
2K
Solve Set Theory Question: Can Countably Infinite Set Have Uncountable Subsets?
  • · Replies 3 ·
Replies
3
Views
2K
Understanding Partition of Sets: Definition, Conditions, and Examples
  • · Replies 2 ·
Replies
2
Views
2K
Graduate Minimal Covering Set: System of Distinct Representatives
  • · Replies 1 ·
Replies
1
Views
1K
Sample spaces, events and set theory intersection
  • · Replies 5 ·
Replies
5
Views
2K
Understanding the Coproduct in Grp as a Universal Object
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Can You Tackle the Subset Chain Challenge in Math?
  • · Replies 1 ·
Replies
1
Views
2K
Set Theory: Need help understanding the question
  • · Replies 4 ·
Replies
4
Views
2K
High School Why Is the Trick for Open Sets in Quotient Topology Valid?
  • · Replies 8 ·
Replies
8
Views
3K
Proving the Existence of F from a Family of Finite Subsets of Natural Numbers
  • · Replies 2 ·
Replies
2
Views
2K