# Tag Info

### 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. ...
• 12.2k
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 ...
• 13.9k

### 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 ...
• 51.1k
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 ...
• 13.9k

### 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 ...
• 6,986
Accepted

• 29.2k

### 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 ...
• 1,021

### 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$.
• 12.2k

### 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 ...
• 1,046
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 ...
• 1,429
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=[...
• 10.6k

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