Questions about set theory
2
votes
1answer
48 views
partition to min the max number of intersections
Given $n$ items and $m$ customers, each of whom is interested in some subset of the items, partition the set of items among $k$ different stores so that the maximum number of customers visiting any ...
7
votes
1answer
129 views
Trying understand a move in Cohen's proof of the independence of the continuum hypothesis
I've read a few different presentations of Cohen's proof. All of them (that I've seen) eventually make a move where a Cartesian product (call it CP) between the (M-form of) $\aleph_2$ and $\aleph_0$ ...
11
votes
1answer
204 views
The state of art for sunflower system
I am interesting in the sunflower system and its applications in computer science.
Given a Universe $U$ and a collection of $k$ sets $A_i$ is called a k-sunflower system if $A_i \cap A_j = Y $ for ...
10
votes
4answers
360 views
Forcing method used in Baker-Gill-Solovay Relativization paper and Cohen's Proof of Continuum Hypothesis Independence
I am generally interested in the forcing method used by Baker-Gill-Solovay and Cohen. I am looking for as many sources as I can get my hands on concerning either the technique itself or its use. Does ...
1
vote
0answers
78 views
Is there a name for this property in set-valued analysis or combinatorics?
I asked this question a few days ago on MO, but I haven't received an answer. So I thought I would ask here. I have also added a relaxed version of the question here.
Let $F$ be a set-valued, ...
3
votes
2answers
549 views
Formal Definition/counter part in mathematics for “Objects” of Object Oriented Models
This is a question I asked in mathematics SE forum, and I was referred here. So here is the question-
I'm a newbie in both formal mathematics and theoretical computer science, so please bear with me ...
2
votes
1answer
173 views
Bloom filter for storage
I am reading about the Bloom filter, and I must say I am fascinated by the idea. I would like to know if it is possible to use it for storage.
The problem with the Bloom filter is that, even if we ...
6
votes
3answers
551 views
Type system based on naive set theory
As I understand, in computer science data types are not based on set theory because of things like Russell's paradox, but as in real world programming languages we can't express such complex data ...
0
votes
1answer
290 views
Proving that inclusion is antisymmetric in Coq
I'm a Coq newbie and I'd like to prove that the inclusion relation is antisymmetric, that is: $\forall x\forall y(x\subseteq y\land y\subseteq x\rightarrow x=y)$.
I wrote the following thing:
...
32
votes
5answers
758 views
Results in Theoretical CS independent of ZFC
I'm going to ask a quite vague question, since the borderline between theoretical computer science and math is not always easy to distinguish.
QUESTION: Are you aware of any interesting result in CS ...
47
votes
5answers
2k views
Which interesting theorems in TCS rely on the Axiom of Choice? (Or alternatively, the Axiom of Determinacy?)
Mathematicians sometimes worry about the Axiom of Choice (AC) and Axiom of Determinancy (AD).
Axiom of Choice: Given any collection ${\cal C}$ of nonempty sets, there is a function $f$ that, given a ...
