Skip to main content
95 votes

Boolean search explained

The counting principle that applies here is inclusion-exclusion. $$ \left|X \cup Y\right| = \left|X\right| + \left|Y\right| - \left|X \cap Y \right|$$ To make the numbers work out, $\left|X \cap Y \...
200_success's user avatar
  • 1,012
63 votes
Accepted

Boolean search explained

Hint: The search x AND y will result in 10 000 hits.
Yuval Filmus's user avatar
59 votes
Accepted

What exactly is the semantic difference between set and type?

To understand the difference between sets and types, ones has to go back to pre-mathematical ideas of "collection" and "construction", and see how sets and types mathematize these. ...
Andrej Bauer's user avatar
  • 30.4k
38 votes

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

The standard algorithm for finding a maximum still works. Start with $a_1$ and go over the elements, if you see a larger value, update the maximum to be that value. The reason this works is that every ...
Ariel's user avatar
  • 13.4k
29 votes
Accepted

Recover a set with the information of the sums of all its subsets

No you can't. Consider any set $S=\{a,b,c\}$ with $a+b+c=0$, and the set $S'=\{a+b,b+c,c+a\}$. The subset sums for $S$ are $0, a, b, c, a+b, b+c, c+a, a+b+c=0$. The subset sums for $S'$ are $0, a+b, b+...
xskxzr's user avatar
  • 7,455
25 votes

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[0] for x in a: if x > m: m = x return m ...
Ilmari Karonen's user avatar
18 votes

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 ...
PJTraill's user avatar
  • 380
16 votes

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 ...
Discrete lizard's user avatar
  • 8,248
14 votes
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, ...
Karolis Juodelė's user avatar
13 votes

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 ...
Vor's user avatar
  • 12.5k
10 votes

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 ...
Derek Elkins left SE's user avatar
10 votes
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 ...
Andrej Bauer's user avatar
  • 30.4k
9 votes
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....
ctj232's user avatar
  • 208
8 votes

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 ...
The Vee's user avatar
  • 418
8 votes

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 ...
David Richerby's user avatar
8 votes
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....
Derek Elkins left SE's user avatar
8 votes

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 (...
Andrej Bauer's user avatar
  • 30.4k
7 votes

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 ...
Nathaniel's user avatar
  • 15.6k
6 votes
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 ...
Yuval Filmus's user avatar
6 votes
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 ...
Soeholm's user avatar
  • 76
6 votes

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: ...
fernando.reyes's user avatar
6 votes
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 ...
Yuval Filmus's user avatar
6 votes
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, ...
Yuval Filmus's user avatar
6 votes
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 ...
Andrej Bauer's user avatar
  • 30.4k
6 votes
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. ...
Andrej Bauer's user avatar
  • 30.4k
6 votes

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-...
Yuval Filmus's user avatar
6 votes

Recover a set with the information of the sums of all its subsets

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 ...
Ethan Bolker's user avatar
6 votes
Accepted

What is the difference between the set containing the empty string and the set containing nothing at all?

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.
Nathaniel's user avatar
  • 15.6k
5 votes

Partitioning a set to the maximum number of subsets summing to zero

3-Partition reduces to this problem, so it's strongly $NP$-hard. Moreover, 4-Partition also reduces to it (and the blowup is linear), so assuming the exponential time hypothesis there's no $2^{o(n)}$ ...
Tom van der Zanden's user avatar
5 votes
Accepted

How to find a minimum set of axioms within a set of propositions?

Determining whether a proposition follows from a set of axioms is an NP-Complete problem. Finding a minimal set of axioms from a set of propositions naturally invokes this problem many times as a ...
Lieuwe Vinkhuijzen's user avatar

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