Set Theory

Probably all you need to know about it is contained in http://www.ii.uib.no/~wagner/UASCR/UAPrelm.htm.

But on a more practical level, I think all undergraduate Mathematics students learn it (I certainly did), so its basic concepts and notation are a well-known body of knowledge, more so than other branches of pure mathematics and logic (which you don't study unless you specialize in it). Therefore I think it is useful to us computer people.

All the nice interesting foundation questions about whether mathematics is Set Theory, or whether there are any paradoxes, are kind of irrelevant to us.

-- DanielPoon

SetTheory underpins logic, which certainly is useful to programmers. For instance, quantifiers can be defined in terms of sets: 

  forall x elem A (p(x)) <-> {x:x elem A ^ p(x)=true}=A
  exists x elem A (p(x)) <-> {x:x elem A ^ p(x)=true} =/= 0
[It would be nice to have English versions of this syntax here]

So if C is a set of Customers = {p,q,r} with credit limits L(p)=10K,L(q)=20K,L(r)=30K then 

  exists x elem C (L(x)>20K)
is true using the above.

I assume in the above statement, the term "logic" means boolean mathematics. It is no more correct to say that boolean mathematics is based on Set Theory than to claim arithmetic is based on set theory. Each is its own separate branch of mathematics, based on different underlying assumptions. As each is intended to help explain real world issues, it should be no surprise that each produces similar results, but that does not imply a relationship.

[we need to clarify what we understand by "based" and "relationship". By "based" I mean "can be defined/formalized by", "a foundation for". By "relationship" typically that means a verb or preposition linking subject and object. forall and exists (quantifiers central to formal logic) above have been defined in terms of set builder notation, part of SetTheory therefore clearly there is a relationship if you accept it as accurate since "have been defined" is the verb phrase. One is defined in terms of the other hence "based". Set theory is also defined in terms of logic they are inextricably entwined for instance A intersect B = {x:x elem A ^ x elem B}. Set intersection is defined in terms of the logical operator "^" (and). Logic and Set definitions are MutuallyRecursive?. As for arithmetic, numbers can be defined as sets: 

  0 = {}
  1 = {{}}
  2 = {{},{{}}}
  ...
Again related. The resemblances between each branch are more than superficial. The proofs of theorems in SetTheory are a direct result of the properties of logical operators in the Set operator definitions.

Example: The Logic statement ~(A v B) <-> ~A ^ ~B and the Set theoretic one (A union B)' = A' intersect B' are both called De Morgan's Law. Coincidence? The definition of A' (complement) is {x:x elem U ^ ~(x elem A)} where U is the universal set in consideration. Also, equality in sets is defined A=B <-> A subset B ^ B subset A. Defn subset: A subset B <-> (x elem A -> x elem B). De Morgan's as a Set equation has the (partial) proof: 

  (A union B)' -> exists x elem (A union B)' -> ~(x elem (A union B))
  -> ~(x elem A) ^ ~(x elem B) -> x elem A' ^ x elem B' -> x elem (A' intersect B') 
  -> (A union B)' subset A' intersect B'    


  Similarly, it can be shown A' intersect B' subset (A union B)' (I could write it out
  but I think the point is made) hence (A union B)' = A' intersect B'
  by the definition of set equality, QED. All the steps depend on the logical connectives.
Of course, a student can learn a*(b+c)=a*b+a*c without knowing Sets, just as a programmer can make programs without learning DenotationalSemantics, but as a theory the foundations are important. Have you never heard of Hilbert's Program? (See http://plato.stanford.edu/entries/hilbert-program/) Ultimately it could not be carried out completely in the form he proposed but certainly it is false that ~(existsReln(R)(R(SetTheory,Logic)^R(SetTheory,Arithmetic)) ]

Logic and sets are closely related, and the former is a prerequisite for the latter. In the same sense, arithmetic and sets are related, to the point where the former is usually defined completely in terms of the latter. In any case, though, the reference to quantifiers means that boolean logic isn't the thing under consideration.

BooleanLogic is just one type of logic - you seem to be referring to propositional logic, which has neither variables nor quantifiers. Predicate logic introduces quantifiers, and statements in mathematics are formalized using this. There is also the distinction between 1st, 2nd, omega order, temporal, modal (which introduces new quantifiers such as necessary, diamond and square boxes). Each logic retains features of the lower order ones, i.e., universal (forall) and existential quantifiers are still part of modal logic, as are the usual ~,^,-> etc. Quantifiers were only one example of a relation between logical connectives and sets. The alphabet, sentences, operators, semantics of logics can all be treated as sets and analysed with set theory (and lattice theory, which is defined using set theory). The latter you mention (sets) is also a prerequisite for the former (logic - hence mutual recursion). For instance proving Every Hintikka set is quantificationally consistent requires set theory even though it is a metatheorem in predicate logic.

{x : some statement} is "Set Builder Notation" like a select in StructuredQueryLanguage (SQL) allows you to create a set from other sets. So if S = {flowers, trees, ants, bees, chickens} then B = {x : x elem S ^ Insect(x)} means B = {ants,bees}. PrologLanguage has a setof functor which lets you play with this on a computer (in a method closer to SetTheory notation than SQL) for example: 

  test :- 
    setof(X,testStatement(X),B),
    write(B).


  testStatement(X) :-
    elem(X,[flowers, trees, ants, bees, chickens]),
    insect(X).
  insect(X) :-
    elem(X,[ants,crickets,wasps,bees,butterflies]).
  elem(X,S) :- member(X,S). %built in to most prologs

Set constructors can be nested for instance in the definition of a completely distributive lattice, if for all index sets S,T =/= {} 

  /\{\/{x[s,t]|t elem T}|s elem S}=
  \/{/\{x[s,phis]|s elem S}|phi:S -> T}
where "[]" are subscripts and "f:A->B" is function mapping in this case also {x:statement} is written instead as {x|statement} i.e. "such that" is "|" not ":".

Looking at SetTheory you can't help comparing CurlyBraces? in it with programming if you use C++, Java, Perl etc. But the "{}" in those languages are really tuples, not sets - the order of statements in them is important, both for statement blocks and arrays. Somehow though

int main() < 

  printf("hello world\n"),
  return 0
>

Would not quite be the same.

ASCII-based Examples 

 q = set(A B C D)
 r = set(B D E)
 s = set(B D)
 t = set(E D B)
 u = set(A C)
 v = set(B C D)


 union(q, r)
 .
   (A B C D E)
 .
 intersection(q, r)
 .
   (B D)
 .
 intersection(s, u)
 .
   ()  // the empty set
 .
 isSubset(r, q)
 .
   False
 .
 isSubset(s, q)
 .
   True
 .
 isSubset(t, r)
 .
   True
 .
 isSubset(r, t)
 .
   True
 .
 isSubset(t, t)
 .
   True         // The subset operator is not strict - a set
                // is always a subset of itself. (One can also
                // define a "strict subset" operator. Or one could
                // add "and not Equiv(...)".
 .
 minus(q, r)    // Also known as "complement"
 .
   (A C)
 . 
 minus(r, s)
 .
   (E)
 .
 disjointUnion (t, v)  // all elements in either t or v, but not in both
 . 
   (E C)
 .
 Equiv(r, t)
 .
   True
 . 
 Equiv(r, s)
 .
   False
 .
(Dots added because Mozilla browsers show too many blank lines between examples.)

Does anybody know what the minimum set of operations that is required? For example, in BooleanAlgebra "NAND" can be used to define all the rest of the operations. Is there something equivalent for set operations?

Very little. I believe all you need is a complete logical system (not, and, or, if-then, if-and-only-if), either for-each or exists-such-that (either can be defined in terms of the other), and element-of. Although all other sets and operators can be defined in terms of these, some of them need axioms to prove that they exist.

Are you saying that there is a tight link between Boolean and Sets such that the first's determine the second's operations? If so, is there a Nand equivalent that can compose the others?

Not necessarily Boolean logic, but some type of logic, yes. The leading axiomatic set theory, Zermelo-Fraenkel, uses first-order logic, but as I said, all that's necessary are the basic logical operators, element-of, and either universal or existential quantification.

Well, sticking with the kind of operators shown above, what is the minimum set of these operators that can produce the others in combination?

'Does anybody know what the minimum set of operations that is required?' Applying set theory to set theory is always interesting. Because it ultimately means that we cannot really reason about set theory mathematically - only philosophically (see also StrangeLoop). -- .gz

That isn't true on several different levels. In the general sense, applying a theory to itself does not create a StrangeLoop. One can discuss types of type theories without any circular dependencies of concept, and one can discuss sets of set theories similarly. In the more specific sense, one doesn't need to apply set-theory to talk about the 'set' of operations needed to describe a particular set-theory (since we wouldn't be using set-theory upon that set of operations).

That depends on whether "talking about" includes (possibly implicit) use of set-theory.

Related:

SetsAndPolymorphism RelationalDatabase ExtendedSetTheory

External References:

CategoryMath

EditText of this page (last edited June 19, 2014) or FindPage with title or text search