16 votes

Data structure to determine if sets are disjoint in o(n) time

The communication complexity of the set disjointness problem is $\Omega(n)$. The communication complexity is a lower bound on the time complexity of testing whether the two instances are disjoint. ...
D.W.'s user avatar
  • 12k
9 votes
Accepted

What are the issues with a set-like interpretation of quantifiers in type theory?

I think there may be a little nuance that can be applied to the situation, where 2 different possible hats may be applied, and which both are valid views of type systems. View 1: Types are intrinsic ...
cody's user avatar
  • 13.8k
9 votes
Accepted

Cantor's theorem in type theory

Short answer: yes! You don't need that much machinery to get the proof to go through. One subtlety: it seems on the face of it that there is a use of the excluded middle: one builds a set $D$ and a ...
cody's user avatar
  • 13.8k
9 votes

In the context of regular languages, must the alphabet be finite?

It makes sense in some contexts in mathematics to consider strings or languages over infinite alphabets. For instance, this concept is used in the strong version of Higman's lemma. But a finite ...
David Eppstein's user avatar
8 votes

In the context of regular languages, must the alphabet be finite?

The usual convention in formal languages and automata theory is that an alphabet is finite. However, there are certainly some cases where it's useful to think of an alphabet being infinite. For ...
Jeffrey Shallit's user avatar
7 votes
Accepted

Order notation quirk

The identity is provable in ZF (or even in $\mathrm{RCA}_0^*$). The $\subseteq$ inclusion is trivial. For the $\supseteq$ inclusion, let $f\notin O(n)$. Define an integer sequence $\{n_k:k\in\mathbb N\...
Emil Jeřábek's user avatar
6 votes

Which interesting theorems in TCS rely on the Axiom of Choice? (Or alternatively, the Axiom of Determinacy?)

Some of the work of Olivier Finkel seems related to the question---though not necessarily explicitly about the Axiom of Choice itself---and in line with Timothy Chow's answer. For instance, quoting ...
Sylvain's user avatar
  • 3,374
6 votes

Data structure to determine if sets are disjoint in o(n) time

This is not an answer to the exact question you pose, because the $n$ is different and the set instances are not separate. But there's a data structure for representing subsets of an $n$-element ...
David Eppstein's user avatar
5 votes
Accepted

Do we know a specific $L_{ZFC}$ such that $K(s) \ge L_{ZFC}$ is unprovable in ZFC for all strings $s$?

(Note: This answer works for most any consistient theory, not just $ZFC$.) We will define a machine $p$ based on the universal algorithm. $p$ does a search, looking for a string that represents a ...
Christopher King's user avatar
4 votes
Accepted

Is any computational complexity question solved by injury priority method except Post problem?

Priority method gets used a lot in computability theory - see some of the later chapters of Soare's book on computability. Buhrman and Torenvliet use a resource-bounded priority method to build an ...
Joshua Grochow's user avatar
4 votes

What are the issues with a set-like interpretation of quantifiers in type theory?

Cody's answer very nicely describes an important distinction. I would just like to point out a specific thing about the interpreation of $\forall$ as $\bigcap$. A typical way to get $\forall$ ...
Andrej Bauer's user avatar
  • 28.8k
3 votes

Is there a set theoretic way to look at SQL?

It is common wisdom that database field is firmly grounded in the two math disciplines: predicate logic and set theory. However, this is very fuzzy observation, and reality is more subtle. The ...
Tegiri Nenashi's user avatar
3 votes
Accepted

Do realizable systems always have some non-well-founded sets?

You are using the wrong definition of well-foundedness. Let $R \subseteq A \times A$ be a relation. Consider the following definitions: $R$ is inductive when for all $B \subseteq A$, if $\forall x \...
Andrej Bauer's user avatar
  • 28.8k
2 votes

Do realizable systems always have some non-well-founded sets?

CZF includes the $\in$-induction axiom, which is the constructively sensible version of the foundation axiom. So everything in one of its models is well-founded in that sense. However, while I'm no ...
Dan Doel's user avatar
  • 931
2 votes

Given a partition and an element, find the subset that includes this element

It is unlikely to have a "name" because it is trivial: it can be solved with a hashtable, array, self-balanced binary search tree, or any other data structure that maps $x$ to $X_i$.
D.W.'s user avatar
  • 12k
2 votes

Which interesting theorems in TCS rely on the Axiom of Choice? (Or alternatively, the Axiom of Determinacy?)

My impression reading this question is that no suitable example of a problem that requires more than just PA (let alone ZF) has been given, and the excellent answer by Timothy Chow explains why it's ...
Stella Biderman's user avatar
1 vote
Accepted

A Combinatorial Problem on Extremal Set Theory

This is arguably trivial, but maybe good enough for you: For any $a,b,c$ with $b \le a \le c$ (in particular $a=b=c$), if $\mathcal{F}$ is maximal subject to (i) and (ii), then it satisfies (iii) for ...
Andrew Morgan's user avatar
1 vote

A Combinatorial Problem on Extremal Set Theory

Did you want some condition to make $\mathcal{F}$ a large collection? Because the current definition allows for the following, presumably trivial, case. Consider $\mathcal{F}=\{S_1,S_2\}$, where $S_1=[...
Aryeh's user avatar
  • 10.5k
1 vote

Is there a set theoretic way to look at SQL?

A co-Relational Model of Data for Large Shared Data Banks by Erik Meijer and Gavin Bierman, http://queue.acm.org/detail.cfm?id=1961297 Good article describing SQL and No-SQL databases as categorical ...
Chad Brewbaker's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible