Questions tagged [set-theory]
Questions about set theory
50
questions
0
votes
0
answers
46
views
Proving the Equivalence of REGEX r^n and r^{..n} when r Is Nullable
Im seeking clarification and a rigorous proof regarding the equivalence of r^n and r^{..n} in the context of formal languages, particularly when r is nullable.
To clarify the terminology:
r denotes ...
- 1
0
votes
0
answers
78
views
Can lambda-calculus, or other formal systems / calculi, be represented using set theory?
Background: I'm a fresh grad student looking into interesting ideas I have. I do not have any theoretical computer science background beyond basic Theory of Computation stuff from undergrad.
If I have ...
- 129
1
vote
2
answers
96
views
Do realizable systems always have some non-well-founded sets?
Suppose we are standing outside a realizable system which admits CZF or a similar constructive set theory. Then consider the following:
LEM is not realized (e.g. this MSE answer)
The traditional ...
- 271
0
votes
0
answers
86
views
Existence of a family of size 2^Ω(n) of subsets of {1,...,n} each of cardinality n/4 where two subsets have at most n/8 elements in common
Let $\mathcal{G}$ be a family of $t=2^{\Omega(n)}$ subsets of $N=\{1,2,...,n\}$, each of cardinality $n / 4$ so that any two distinct members of $\mathcal{G}$ have at most $n / 8$ elements in common.
...
- 101
1
vote
0
answers
52
views
Better approximation of the subset in the membership oracle
A standard tool for estimating the size of a subset via membership oracle queries is given below.
Lemma 2.8: . Consider two (finite) sets $B ⊆ U$, where $n = |U|$. Let $ε ∈ (0, 1)$ and $γ ∈ (0, 1/2)$ ...
- 41
2
votes
0
answers
105
views
Faster algorithms to estimate the subset sizes
Lemma: Consider two sets $B ⊆ U$, where $n = |U|$. Let $ξ, γ ∈ (0, 1)$ be parameters, such that
$γ < 1/ \log n$. Assume that one is given an access to a membership oracle that, given an element $x ∈...
- 41
2
votes
1
answer
314
views
Is any computational complexity question solved by injury priority method except Post problem?
As we know, there are many questions of Turing Degree closed by injury priority method. Is any computational complexity question solved by injury priority method except Post problem or Turing Degree?
...
- 1,058
7
votes
1
answer
180
views
Order notation quirk
Is it true that $$O(n) = \bigcap \{ O(g) \mid g \in \omega(n) \}?$$
This appears to be a straighforward question about sets of functions, but on closer examination leads to some murky waters.
I would ...
- 18.9k
1
vote
0
answers
54
views
Is this a variant of the set cover problem?
$\textbf{Decision Problem:}$
Given a finite set of elements $E$ and a collection $C$ of non empty sets, $C=\{E_1,...,E_n\}$, such that each $E_i$ covers at least one element of $E$. The goal is to ...
- 13
10
votes
2
answers
461
views
What are the issues with a set-like interpretation of quantifiers in type theory?
In his answer to a question that tries to treat universal and existential quantifiers as intersections and unions of sets, Andrej Bauer says:
Forget the intersections and unions. People get this idea ...
- 332
0
votes
1
answer
71
views
Given a partition and an element, find the subset that includes this element
I am interested in the following simple problem: Let $X$ be a set and $X_1\cup X_2\cup\cdots\cup X_k$ be a finite partition of $X$. Given $x\in X$, find the subset $X_i$ for which $x\in X_i$. I am ...
2
votes
0
answers
161
views
Set-theoretic encoding of functions in type theory
Functions usually get encoded in set theory as follows. A function $A\to B$ is a subset $f\subset A\times B$ such that $\pi_1:f\to A$ is a bijection.
In type theory to give a function $A\to B$ is to ...
user61651
5
votes
0
answers
179
views
On the interpretation of coinduction in type theory
The notion of (co)datatype can be modeled satisfactorily in category theory as fixed-points of polynomial functors. Then, (co)induction principles are derived from initial algebras/terminal ...
- 921
5
votes
2
answers
643
views
Data structure to determine if sets are disjoint in o(n) time
My initial question was exactly the title of this post, but after feedback from commenters I have formulated a more precise version of the question that attempts to capture its essence.
Does there ...
- 159
2
votes
1
answer
248
views
Optimal partition according to partition cardinality
Given $N$ sets of integers $S_1, \ldots,S_N$ with $|S_i| \le K$.
We want to partition those sets such that the union of all sets in any given partition doesn't contain more than $K$ elements.
Can ...
user30584
9
votes
1
answer
397
views
Cantor's theorem in type theory
Cantor's theorem states that
For any set A, the set of all subsets of A has a strictly greater cardinality than A itself.
Is it possible to encode something like this using only types / ...
- 193
6
votes
1
answer
435
views
Do we know a specific $L_{ZFC}$ such that $K(s) \ge L_{ZFC}$ is unprovable in ZFC for all strings $s$?
Chaitin's incompleteness theorem states for any formal system $F$ (which satisfies various criteria), there is a $L$ such that for any $s$ the statement $$K(s) \ge L_F$$ is unprovable in that formal ...
- 471
1
vote
0
answers
482
views
Equality Constraints over Sets with Tree Automata
Tree Automata can be used to model sets of values of a Herbrand Universe, for example, to model possible values in a functional program.
Systems of subtype constraints over set expressions have ...
- 2,830
1
vote
0
answers
85
views
Equality Theorems with Type Theoretic Proof
I am investigating how I might be able to translate even commonplace equalities/ inequalities via the so-called Curry-Howard Correspondance - from a generic, set theoretic plus AOC foundation - into a ...
- 51
7
votes
2
answers
2k
views
In the context of regular languages, must the alphabet be finite?
In The Theory of Parsing, Translation, and Compiling, Volume I, Section 0.2.1 (p.15 / 1972), Aho and Ullman casually write that "[a]n alphabet need not be finite or even countable, but for all ...
- 71
8
votes
0
answers
215
views
Is there a known automatic proof of the independence of the continuum hypothesis?
In 2002, L.C. Paulson gave a mechanized proof of the consistency of the axiom of choice by formalizing $V=L$ and its consistency. We could ask whether there is a formalized proof of the independence ...
- 181
7
votes
2
answers
350
views
A Combinatorial Problem on Extremal Set Theory
Given a ground set $[n]$, under what condition of parameters $a,b,c$ does a family of subsets $\mathcal{F}\subseteq 2^{[n]}$ with the following property exist?
(i) $\forall S\in \mathcal{F}$, $|S|=a$....
- 437
4
votes
3
answers
1k
views
Is there a set theoretic way to look at SQL?
I have been learning about SQL and at times it feels like set theory. A statement like SELECT * FROM myTable is like a set $\{ x: x \in \text{myTable} \}$.
A ...
- 568
10
votes
3
answers
1k
views
Universal and existential types
I'm trying to wrap my head around the concepts of universal and existential types but everywhere I look, I see either logical or operational intuitions (or implementations) (e.g. TAPL book by B. ...
- 121
16
votes
3
answers
684
views
Applications for set theory, ordinal theory, infinite combinatorics and general topology in computer science?
I am a mathematician interested in set theory, ordinal theory, infinite combinatorics and general topology.
Are there any applications for these subjects in computer science?
I have looked a bit, and ...
- 263
1
vote
1
answer
312
views
How can I formalize key value stores with set theory? [closed]
I'm currently developing a simple key-value NoSQL store and want to build its formal model. I'm interested in knowing if there some work about formalization of key-value stores outside of category ...
1
vote
1
answer
105
views
Minimum order of partite in a bipartite graph
I want to create a bipartite graph where the first partite $U$ contains $L$ vertices with degree $k$ and the second partite $V$ contains $N$ other vertices with degree $a$. I need to find the minimum ...
- 113
0
votes
0
answers
73
views
Finding exact value with a quotients of products of random values
Sorry for the haphazard title: really not sure what this should be called
Suppose we have a set of $z$ random values $S = r_1, \dots, r_z$ drawn from $\mathbb{Z}_N$ (where $N$ is some large prime).
...
- 149
-3
votes
1
answer
77
views
Explanation of Cantor's diagonal argument? [closed]
I struggled to understand the Cantor's diagonal argument, but I have some problems comprehending the following:
By construction, $s$ differs from each $s_n$, since their $n^{th}$ digits differ (...
7
votes
1
answer
2k
views
Are there presentations of set theory in terms of lambda-calculus?
I am planning to implement in software a set theory language, based on a binary function, which in set theory is the so called adjunction operation: $f(x, y) = x \cup$ {y}. Therefore, a presentation ...
- 71
5
votes
3
answers
433
views
Variation on partial Set Cover with penalties
I'm looking at the following problem, which I'm hoping is perhaps a known variant of the Set Cover problem:
Input: We're given a universe $U$ and two disjoint subsets $A$ and $B$ such that $A \cup B=...
- 171
1
vote
1
answer
743
views
Rings and the set of all minimum s-t-cuts
Let $N$ be a flow network with nodes $V$ and edges $E$. For technical reasons, the source side of a minimum $s$-$t$ cut $(A,B)$ with $s \in A$ and $t \in B$ is defined as $A - \{s\}$. Now, let $\...
- 439
2
votes
0
answers
390
views
Theorem prover fails to find simple set theory proof?
I am trying to use an automated theorem prover (SNARK) to prove a theorem in first-order logic.
Tarski claims in his "a work on mereology" that
the goal is provable from assertions 1-3 but he does ...
- 279
2
votes
2
answers
865
views
Which formalism is best suited for automated theorem proving in set theory?
Abbreviations - FOL is first-order logic; NBG is Von Neumann–Bernays–Gödel set theory; SEP is Stanford Encyclopedia of Philosophy; HOL is higher-order logic; ATP is automated theorem proving.
Context ...
- 279
5
votes
1
answer
236
views
Kruskal-Katona Theorem with Majority?
I am interested in the following problem which seems like an extension of the Kruskal-Katona Theorem.
Let $A_k \subseteq \{0,1\}^n$ be a subset of the hypercube such that every element in $A$ has ...
- 666
4
votes
3
answers
1k
views
How to construct a special data structure that allows for "fast" subset operation?
If I have a set S = {1,2,3,4,5} that represents a universe and the following subsets of S:
U1 = {1,2}
U2 = {3,4,5}
C1 = {3,5}
C2 = {2}
The above sets are guaranteed to be subsets of S, however ...
- 153
1
vote
2
answers
244
views
Using partial functions to prove correctness
I'm interested in proving that a program (which may or may not terminate) will give the correct answer if it terminates. Given:
$P$ is a family of programs, parameterized by a function $f$. Write $...
- 45
1
vote
2
answers
3k
views
What's the relation between the dominating set and vertex cover?
I wonder if the minimal dominating set is always a subset of the minimal vertex cover in any graph. If so, what's the proof?
- 121
6
votes
1
answer
143
views
What's complexity of this set problem which looks like "Linear Programming"?
I came up with a problem below, which looks like a linear programming problem:
Given $n$ sets $S_{1}, S_{2},..., S_{n}$, with constraints of :
$$
\forall i=1, 2, 3,...,n\space\space \left | S_{i} ...
- 439
2
votes
1
answer
121
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 ...
- 21
7
votes
1
answer
171
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$ ...
- 533
11
votes
1
answer
469
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 ...
- 329
15
votes
4
answers
783
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 ...
- 533
1
vote
0
answers
94
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, finite-...
- 779
9
votes
2
answers
1k
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 ...
- 193
2
votes
1
answer
421
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 ...
- 203
14
votes
3
answers
2k
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 ...
- 381
1
vote
2
answers
811
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:
...
- 31
39
votes
5
answers
1k
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 ...
- 491
70
votes
7
answers
4k
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 ...
- 27.3k