Share Your Experience: Take the 2024 Developer Survey

# Questions tagged [set-theory]

50 questions
Filter by
Sorted by
Tagged with
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 ...
53 views

327 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? ...
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 ...
1 vote
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 ...
489 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 ...
73 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 ...
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 ...
880 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 ...
449 views

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 ...
801 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 ...
2k 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 ...
240 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 ...
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 ...
1 vote
246 views