// infinite sets using predicate delegates in C# /* There are two classes implementing Set: PSet for predicate sets, or sets defined by the Axiom of Comprehension, and FSets, which are finite sets represented by a data structure (HashSet). We want operations such as union/intersection to be used on both finite and possibly infinite sets. */ using System; using System.Collections.Generic; interface Set // sets in domain T { bool contains(T x); void add(T x); Set union(Set B); Set intersection(Set B); Set complement(); bool subsetof(Set B); Set clone(); } public delegate bool predicate(T x); class PSet : Set // possibly infinite predicate sets of domain type D { protected predicate P; public PSet(predicate p) {P=p;} public bool contains(D x) { return P(x); } public Set intersection(Set B) { if (B is FiniteSet) return B.intersection(this); // oops! if needed! return new PSet(delegate(D y) // y => contains(y) && B.contains(y) { return this.contains(y) && B.contains(y); }); } // lambda x.z in C# is x=>z public Set union(Set B) { return new PSet( (x)=>(contains(x) || B.contains(x)) ); } public Set complement() { return new PSet( (x)=>(!contains(x)) ); } public void add(D x) { if (contains(x)) return; // dont' add if already there predicate P0 = P; P = delegate(D y) {return P0(y) || x.Equals(y); }; // note closure with P0 } public Set clone() { return new PSet(P); } // problem with infinite sets defined by comprehension: public bool subsetof(Set B) {/* bool answer = false; bool Idontknow = true; while (Idontknow) answer = !answer; // Can't decide! Not decidable! return answer; */ throw new Exception("Undecidable in general. I don't know how to define this and nobody ever will"); } }//PSet ///////////////////////////// finite sets class FiniteSet : Set { protected HashSet H; // .Net finite set structure public FiniteSet() { H = new HashSet(); } // start empty public bool contains(D x) { return H.Contains(x); } public void add(D x) { H.Add(x); } public Set union(Set B) { Set Bclone = B.clone(); foreach (D x in H) { Bclone.add(x); } return Bclone; } public Set intersection(Set B) { FiniteSet I = new FiniteSet(); // start with empty set foreach (D x in H) { if (B.contains(x)) I.add(x); } return I; } public Set complement() { return new PSet(x=>!H.Contains(x)); // returns infinite set } public Set clone() { FiniteSet F = new FiniteSet(); foreach (D x in H) F.add(x); return F; } public bool subsetof(Set B) // now I can define it! { foreach (D x in H) {if (!B.contains(x)) return false;} return true; } public override string ToString() // overrides object.ToString() { string s = ""; foreach (D x in H) s = s+x+" "; return s; } }//FiniteSet public class infsets { // some things are too large for a lambda expression: public static bool isprime(int x) // check if x is prime { if (x==2) return true; if (x<2 || x%2==0) return false; int limit = (int)(Math.Sqrt(x) + 1); for(int i=3;i<=limit;i+=2) if (x%i==0) return false; return true; }//isprime // true if x is the sum of two primes, // e.g. 8=2+5, 6 = 3+3 (the two primes can be the same) public static bool sumprimes(int x) { if (x<4) return false; // find two primes less than x that sums to x for (int i=2;i<=x-2;i++) if (isprime(i) && isprime(x-i)) return true; return false; }// set of all public static void Main() { Set EVENS = new PSet(x=>x%2==0); Set NEGATIVES = new PSet(x=>x<0); Set NEGEVENS = EVENS.intersection(NEGATIVES); Console.WriteLine(NEGEVENS.contains(-8)); Console.WriteLine(NEGEVENS.contains(0)); NEGEVENS.add(0); Console.WriteLine(NEGEVENS.contains(0)); Set F = new FiniteSet(); int[] A = {3,5,7,11,2}; foreach (int x in A) F.add(x); Set G = new FiniteSet(); G.add(13); Set FG = F.union(G); Console.WriteLine(FG); Console.WriteLine(EVENS); Set S = F.intersection(EVENS); Console.WriteLine(S); // should print 2 Set S2 = EVENS.intersection(F); Console.WriteLine(S2); // should print ??? // Console.WriteLine(F.subsetof(EVENS.complement())); //EVENS.complement=ODDS // Set of all primes Set Primes = new PSet(x=>isprime(x)); // Set of all finite subsets of primes: Set> FPrimes = new PSet>(x=>x.subsetof(Primes)); Console.WriteLine(FPrimes.contains(FG)); // set of all numbers that's the sum of two primes: Set SumofPrimes = new PSet(x=>sumprimes(x)); // set of all even numbers greater than 2: Set Even2 = new PSet(x=>x%2==0 && x>2); // solve Goldbach's Conjecture: Console.WriteLine(SumofPrimes.subsetof(Even2)); // ... just kidding }//Main } // still a problem: what is EVENS.intersection(F)? should be finite!