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 \...
- 1,012
63
votes
Accepted
48
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.
...
- 28k
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 ...
- 13.2k
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+...
- 7,249
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
...
- 1,915
15
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 ...
- 304
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, ...
- 3,567
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 ...
- 12.2k
11
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 ...
- 6,978
10
votes
Accepted
If $A \cap B$ or $A \cup B$ or $A \times B$ is recursively enumerable is it true to say that both $A$ and $B$ are recursively enumerable?
Notice that $\mathsf{RE}$ is not closed under complementation. Therefore there exists an $A\in\mathsf{RE}$ such that $B=A^c\notin\mathsf{RE}$, while $A\cap B$ and $A\cup B$ are trivially recursively ...
- 1,163
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 ...
- 11.8k
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 ...
- 28k
9
votes
Accepted
Returning a random subset with length k of N strings while only storing at most k of them
Use reservoir sampling. This is a good description in Wikipedia, or in Knuth.
Let's start with the simple case, where $k=1$. You always have one string in memory. When you read the first string, ...
D.W.♦
- 140k
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....
- 208
8
votes
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 ...
- 545
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 ...
- 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 ...
- 80.1k
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....
- 11.8k
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 (...
- 28k
7
votes
Accepted
What does $\{$ a set $\}^{+}$ mean in the context of languages?
This is the Kleene plus. It stands for
$$ L^+ = \bigcup_{i \geq 1} L^i. $$
Here $L^i$ is the set of concatenations of $i$ words from $L$.
In words, $L^+$ consists of all concatenations of one or more ...
- 269k
7
votes
Accepted
Data structure for a static set of sets
Generically, these are sometimes called subset/containment dictionaries. The fact that you had partial matching in your question (but deleted it) is actually not a coincidence, because subset/...
- 1,230
7
votes
Accepted
Does "contains only" imply "contains"?
My view is that vernacular would consider that S is not empty,
i.e. $\emptyset \neq S\subseteq T$, while mathematical language would
consider that S can be empty, i.e. $\emptyset\subseteq S\subseteq T$...
- 19.1k
7
votes
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 ...
- 80.1k
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 ...
- 7,127
6
votes
What is the point of (Compactness theorem in the) Overspill principle?
The theorem says that when a sentence has arbitrarily large (finite) models, then it also has infinite models.
The antecedent of the theorem:
$\phi$ is a sentence of predicate logic such that for ...
- 4,611
6
votes
Accepted
What is the name of the property where $f(A) \supseteq f(B)$ when $A\supseteq B$?
It is called monotonicity with respect to the inclusion ordering of sets.
More precisely, it is in this case increasing monotonicity since the order is preserved. If the order was reversed, it would ...
- 19.1k
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 ...
- 76
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 ...
- 269k
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:
...
- 169
Only top scored, non community-wiki answers of a minimum length are eligible