Naive Set Theory

Set

Set formalizes the idea of "collection of objects". A simple way to denote a set is listing all elements in it. e.g. \( A := \{1, 2, 3\} \)

We can implement set using list in Haskell.

>>> a = [1, 2, 3]

Another way to denote a set is by specifying a pattern. e.g. \( \{0, 2, 4, ...\} \) denotes the set of even natural numbers.

Haskell also has a similar notation.

>>> a = [0, 2 ..]

Yet another way to denote a set is by specifying properties of elements in the set. A general form looks like: \( \{s \in S | s\ satisflies\ P\} \). It specifies a set whose elements (s) belong to a larger set (S) (the symbol \(\in\) means "is an element of..."), and satisfy a property (P).

For example, the set of even integers can be written as \(\{a \in Z|(\exists n \in Z)\ a = 2n\}\).

As a shorthand, it can also be written as \(\{2n|n \in Z\}\).

The 2 notations represent the same set in math, but are evaluated differently if you translate them literally to haskell

>>> evens = [a | a <- ints, exists ints (\n -> a == 2*n)]
>>> take 3 $ evens
-- never terminate

>>> evens = [2*n | n <- ints]
>>> take 3 $ evens
[0,2,-2]

Inclusion of sets

A set S is a subset of T, if every element in S is also an element of T. In math, we write \(S \subseteq T\). It is defined as \[ x \in S \implies x \in T \].

subset :: [a] -> [a] -> Bool
s `subset` t = forall s (\x -> (x `elem` s) ==> (x `elem` t))
-- or simply
s `subset` t = forall s (\x -> x `elem` t)

Equality of 2 sets \(S = T\) is defined as \[ S \subseteq T \land T \subseteq S \]

eq:: [a] -> [a] -> Bool
s `eq` t = s `subset` t && t `subset` s

Note that order of elements or repetition doesn't matter in sets. Thus, \( \{1, 2, 3\} = \{3, 2, 1\} = \{1, 1, 2, 3, 2\} \).

>>> [1,2,3] `eq` [3,2,1]
True
>>> [1,2,3] `eq` [1,1,2,3,2]
True

\(|S|\) denotes the number of elements in S. e.g. \(|\mathbb{Z}| = \infty \)

sizeof :: (Eq a) => [a] -> Int
sizeof = length . uniq
    where uniq [] = []
          uniq (x:xs)
               | x `elem` uniq xs = uniq xs
               | otherwise = x : uniq xs

>>> sizeof [1,2,3]
3
>>> sizeof [1,1,3]
2