# Tag Info

### in O(n) time: Find greatest element in set where comparison is not transitive

As Ariel notes, the standard maximum-finding algorithm given below: def find_maximum(a): m = a for x in a: if x > m: m = x return m ...

### What exactly is the semantic difference between category and set?

In brief, set theory is about membership while category theory is about structure-preserving transformations – but only about the relationships between those transformations. Set theory is only about ...

### What exactly is the semantic difference between set and type?

In practice, claiming that $x$ being of type $T$ usually is used to describe syntax, while claiming that $x$ is in set $S$ is usually used to indicate a semantic property. I will give some examples to ...
Accepted

### How to find the maximal set of elements $S$ of an array such that every element in $S$ is greater than or equal to the cardinality of $S$?

Sort T. Then take elements while T[i] >= i+1. For example sorted(T)=[6,4,3,3,1,1]. Then, ...

### Boolean search explained

Document 1: The cat is on the table Document 2: My cat is black Document 3: The dog is under the table Document 4: What's the name of your cat? Document 5: This is a black and white photo Search for ...

### What exactly is the semantic difference between set and type?

To start, sets and types aren't even in the same arena. Sets are the objects of a first-order theory, such as ZFC set theory. While types are like overgrown sorts. To put it a different way, a set ...
Accepted

### Lambda Calculus as a branch of set theory

It's false. The $\lambda$-calculus arose through efforts to understand foundations of mathematics. Nowadays some people mistakenly equate foundations with set theory. The Stanford Encyclopaedia of ...
Accepted

### "Regular languages over a common alphabet are closed under union."

I see two possible points of confusion in your question, and I will address them separately. What is meant by the title of your post: ""Regular languages over a common alphabet are closed under union....
Accepted

### Number of finite strings over a countably infinite alphabet

It's countable. The set $S_\ell$ of strings of length $\ell$ is $\Sigma\times\dots\times\Sigma$, which is a finite product of countable sets, so is countable. Now, the set of all finite ...

### Find a regular language that is "infinitely between" two other regular languages

Because regular languages are closed under complement and intersection, $L_2 - L_1$ is regular. Because it's also infinite, it contains words of arbitrarily large lengths. Therefore, by the pumping ...

### How to find the maximal set of elements $S$ of an array such that every element in $S$ is greater than or equal to the cardinality of $S$?

From my comment originally: This is closely related to a quantity ubiquitous in academic productivity assessment, the Hirsh index, better known as the $h$-index. In short it is defined as the number ...

### Is the intersection of infinitely many recursive sets recursive?

For each $i\in \mathbb{N}$, take $S_i = \mathbb{N}\setminus \{i\}$. You can now build any set you want as $X = \bigcap_{i\notin X}S_i$. Similarly, an easier proof that a union of recursive sets can ...
Accepted

### Is there a formal difference between $f:X \to X$ and $f\in X \to X$?

No, they're mostly notational variations. There are different connotations to the different notations, and different notations are common in different fields where they can mean quite different things....

### How to get an element from an existential proposition in Type theory proof assistant (Lean prover)

The existential form of the axioms of set theory is convenient for the meta-theoretic explorations of set theory, such as forcing etc., where it is important to have a minimal language to worry about (...

### Set theory pertaining to category theory and functional programming

The notation $f:E\times F \to G$ means that $f$ is a function that needs two arguments, one from $E$, one from $F$, and the image is in $G$. This is how the function $\text{Union}$ is defined: the two ...
Accepted

### Finding a fixed-size set whose members are contained by the largest number of other sets

I believe your problem is a direct instance of the NP-hard Maximum Coverage Problem, which is related to Set Cover. From wikipedia, Maximum Coverage Problem: As input you are given several sets ...
Accepted

### The meaning of "set" in NP-complete problem

It doesn't matter. If a certain problem has one version in which the encoding of sets allows for repeated elements (which are ignored semantically), and another in which repeated elements are ...

### How to find the maximal set of elements $S$ of an array such that every element in $S$ is greater than or equal to the cardinality of $S$?

There is nothing wrong with your algorithm, and of course most of recursive algorithms can be converted into loops, here a loop version of your recursive code: ...
Accepted

### Find an algorithm that finds a minimal hitting set for sets limited in size

Here are two algorithms for the case $k=2$, also known as Vertex Cover; we think of the sets $S_i$ as edges and of the elements $\{1,\ldots,n\}$ as vertices. We can assume that each edge connects two ...
Accepted

### Subset of numbers whose XOR has least Hamming weight

Your problem is known as calculating the minimal distance of a (binary) linear code, and is NP-hard, as shown by Vardi. It is even NP-hard to approximate within any constant factor, as shown by Dumer, ...
Accepted

### Is the intersection of infinitely many recursive sets recursive?

Since you already know about unions, you could figure this out by remembering the de Morgan laws: the complement of a union is the complement of the intersection of complements. With this in mind: let ...
Accepted

### PL: What solves the type isomorphism $X \cong (X \rightarrow \mathbf{2})$?

To say that we cannot solve $X \cong (X \to 2)$ in sets means that we have to do it in another category. And because we're talking programming languages, we should be looking for one in domain theory. ...

### Smallest set of balls under hamming distance that covers all $n$-bit strings

The object you are looking for is known as a covering code. Finding the smallest covering code for a given radius is generally a difficult problem, just like its more well-known dual problem, error-...
If you know the sums of all the two element subsets you can recover the elements unless $n$ is a power of $2$. See Jan Boman, Ethan D. Bolker, Patrick O'Neil, The Combinatorial Radon Transform modulo ...
Yes, that's it. One important difference could be seen using concatenation: let $L$ be any nonempty language. Then $\{\varepsilon\}L = L$, but $\emptyset L = \emptyset$. Clearly those are different.