# Tag Info

Accepted

### Applications for set theory, ordinal theory, infinite combinatorics and general topology in computer science?

One major application of topology in semantics is the topological approach to computability. The basic idea of the topology of computability comes from the observation that termination and ...
• 31.7k

### 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. ...
• 10.5k
Accepted

### Universal and existential types

Set theory is doing you some harm here and the sooner you liberate yourself from it the better it will be for your understanding of computer science. Forget the intersections and unions. People get ...
• 26.7k

### 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 ...
• 50.3k
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.2k

### 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,898
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.2k
Accepted

• 10.1k
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 ...
• 2,331
1 vote

### 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 ...
1 vote

### Universal and existential types

I suggest not to give up on the operational intuition. Operational is primary, all semantics are derived, and are but proof techniques for operational semantics. The key ideas are as follows. A ...
• 10.3k
1 vote
Accepted

### Explanation of Cantor's diagonal argument?

It's actually more trivial. Suppose that $s$ occurs in the enumeration. Then it occurs at some specific index. Let's call this index $n$. This means that $s = s_n$. But this is impossible, because ...
1 vote
Accepted

### Rings and the set of all minimum s-t-cuts

Here I'll show that the statement is true, assuming that $V=U\cup\{s,t\}$, i.e. source and sink are not elements of $U$. Let $S=\bigcap\limits_{R\in\mathcal R}R$, \$P=\bigcup\limits_{R\in\mathcal R}R\...

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