set-theory.lisp

;;;; Operations and definitions for Cantor and Dedekind's set theory.

(defpackage bachelor-cs.set-theory
  (:use :cl)
  (:export :Ø :∈ :⊆ :power :size :∪ :∩ :diff :Δ :× ))

(in-package :bachelor-cs.set-theory)

(defvar Ø ()
  "Empty set Ø")

;;; Sets are represented either as a list or as a predicate function.

(defgeneric ∈ (element set)
  (:documentation "Predicate to check if ELEMENT is in SET."))

(defmethod ∈ (element (set list))
  (not (null (member element set :test #'equal))))

(defmethod ∈ (element (set function))
  (funcall set element))

(defgeneric ⊆ (set-x set-y)
  (:documentation "Predicate to check if SET-X is a subset of SET-Y.
Implemented only for SET-X represented as a list."))

(defmethod ⊆ ((set-x list) set-y)
  (null (loop for element in set-x
	   unless (∈ element set-y) return t)))

(defun power (set)
  "Returns the power of SET."
  (lambda (element)
    (or (equal element Ø)
	(⊆ element set))))

(defgeneric size (set)
  (:documentation "Returns cardinality of SET (usually |set|). Only
implemented for SET represented as a list."))

(defmethod size ((set list))
  (length set))

(defmethod size ((set function))
  :∞)

(defgeneric ∪ (set-x set-y)
  (:documentation "Returns union of SET-X and SET-Y."))

(defmethod ∪ ((set-x list) (set-y list))
  (remove-duplicates (append set-x set-y)
                     :test #'equal))

(defmethod ∪ (set-x set-y)
  (lambda (element)
    (or (∈ element set-x)
	(∈ element set-y))))

(defgeneric ∩ (set-x set-y)
  (:documentation "Returns intersection of SET-X and SET-Y."))

(defmethod ∩ ((set-x list) (set-y list))
  (intersection set-x set-y :test #'equal))

(defmethod ∩ (set-x set-y)
  (lambda (element)
    (and (∈ element set-x)
	 (∈ element set-y))))

(defgeneric diff (set-x set-y)
  (:documentation "Subtracts SET-Y from SET-X."))

(defmethod diff ((set-x list) set-y)
  (remove-if (lambda (element) (∈ element set-y))
	     set-x))

(defmethod diff (set-x set-y)
  (lambda (element)
    (and (∈ element set-x)
	 (not (∈ element set-y)))))

(defun Δ (set-x set-y)
  "Returns symmetric difference for SET-X and SET-Y."
  (∪ (diff set-x set-y) (diff set-y set-x)))

(defgeneric × (set-x set-y)
  (:documentation "Returns cartesian product of SET-X and SET-Y."))

(defmethod × ((set-x list) (set-y list))
  (remove-duplicates
   (loop for element-x in set-x append
	(loop for element-y in set-y collect
	     (list element-x element-y)))
   :test #'equal))
  
(defmethod × (set-x set-y)
  (lambda (element)
    (and (∈ (first element) set-x)
	 (∈ (second element) set-y))))