Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [set-theory]

Questions about set theory

14 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
8 votes
0 answers
231 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 ...
Hanul Jeon's user avatar
2 votes
0 answers
107 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 ∈...
Com's user avatar
  • 41
2 votes
0 answers
162 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 ...
user avatar
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 ...
Atriya's user avatar
  • 279
1 vote
0 answers
54 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)$ ...
Com's user avatar
  • 41
1 vote
0 answers
57 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 ...
mahou_2019's user avatar
1 vote
0 answers
483 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 ...
Joey Eremondi's user avatar
1 vote
0 answers
86 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 ...
Krpcannon's user avatar
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-...
Ankur's user avatar
  • 779
0 votes
0 answers
53 views

Data structure for storing set of sets

Let key space $K_n =$ { $1, 2,...,n$ } Let Data Structure $D$ implementing a set $S$ of sets such that All sets in $S$ are of same size $l$, $1 \le l \le n$ All sets in $S$ contain keys belonging to $...
Yolov4's user avatar
  • 1
0 votes
0 answers
47 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 ...
J.Doe's user avatar
  • 1
0 votes
0 answers
88 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 ...
The Pointer's user avatar
0 votes
0 answers
87 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. ...
C. Mürtz's user avatar
  • 101
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). ...
Dave's user avatar
  • 149