Set Theory

This post is a very brief introduction to some of the basic concepts of set theory. Set theory is a branch of mathematical-logic, that has wide applications across disciplines. Its not just used in the obvious way of studying the foundations of mathematics by mathematicians but also in physics, social science and even in philosophey. I'm only going to cover in this post what's needed for predicate logic (although you can do propositional logic without set theory) but it has for many other applications.

A set is a collection of elements, or members; the notation for a set is specified by listing its components. So the set of even numbers can be represented as

• $E: \left \{ 2,4,6,8 ... \right \}$
• $E: \left \{ x: x > 0 \wedge  even\right \}$

Either of these notations is valid. Further, elements of a set can only be in that set once.  

• $E: \left \{ 2,2,2,4,4,6,8 ... \right \} = E: \left \{ 2,4,6,8 ... \right \}$

The notation used to indicate that something is an element of a set, is using the Greek symbol "epsilon". That is:

• $4 \epsilon S$

Two sets, A and B are identical if and only if, they contain the same members. Formally: A = B if and only if, for all x, x ∈ A if and only if x ∈ B. 

For any sets, A and B, such that every member of A is a member of B, A is a subset of B (written A ⊆ B). Formally: A is a subset of B (A ⊆ B) if and only if, for every x, if x ∈ A, then x ∈ B. If A is a subset of B but B is not a subset of A, then A is called a "proper subset" of B. 

Operations on Sets

You can think of an operation as a way of creating a new set, out of old ones. Two operations are particularly important. Those being 'union' and 'intersection'. 

A union of two sets, A ∪ B, is the set of all and only those things that are members of either A or B. Formally: A ∪ B = {x : x ∈ A or x ∈ B}

An intersection between two sets, A ∩ B, is the set of those things that are both members of A and members of B. Formally: A ∩ B = {x: x ∈ A and x ∈ B}

These aren't the only two things we can do with sets, in the 20th century during the early development of set theory, it was thought that for every property, there was an extension (a set containing only its members). The logician Frege was so certain of this he called it "the basic law V of logic" and tried to reduce all of arithmetic down to the logic of sets. 

Today we know better and due to a famous paradox discovered by Bertrand Russell the assumption that every property has a set corresponding to it, that contains those members which posses that property and only those members, is false. 

What we can say, though, is that given a domain set, D, and a subset A of D, there exists a set $A^{c}$ (the complement of A in D), consisting of all those members of D that are not in A. 

• Relative to a given domain D, $A^{c} = {x ∈ D : x ∉ A}$

Ordered n-tuples

Up until now, all we've learned is the logic of one-place predicates, the idea here is that a predicate corresponds to a set over which it applies, but what if we want to understand the semantics of two-place predicate terms like A_1_2  or n-place predicate terms? For these cases, we need an ordered set or an "ordered n-tuple". 

An n-tuple containing the ordered sequence a1, …, an is written as $\left \langle a_{1}, ... a_{n} \right \rangle$ unlike ordinary sets, one can have the same element appearing twice, and the order does matter. 

Ordered n-tuples, as special kinds of sets, can themselves be members of sets. Thus: 

• $T: \left \{ \left \langle 0,0 \right \rangle \left \langle 1,2 \right \rangle \left \langle 2,4 \right \rangle \left \langle 4,8 \right \rangle\right \}$

Is a set of ordered pairs (in this case, the set of ordered pairs $\left \langle x,y \right \rangle$ such that x and y are members of the set of natural numbers, and y = 2x). 

Indeed, we can specify the members of some sets of ordered n-tuples using a description rather than as a list, as in this case: T: {x, y : x ∈ N and y ∈ N, and y = 2x}. 

Given two sets A and B, the Cartesian product of A with B (written A × B) is the set consisting of all and only those ordered pairs whose first member is a member of A and whose second member is a member of B. Formally: A × B = { x, y : x ∈ A and y ∈ B}. If all of our sets are equal, then we can re-write our specification as:

• $T: \left \{ \left \langle x,y \right \rangle \epsilon N^{2} : y = 2x \right \}$

An n-ary predicate A__1… __n will be interpreted as a set A of n-tuples of objects where the objects are all taken from some domain set D (so that A ⊆ Dn).

This completes our background sketch of set theory, hopefully in upcoming posts this will be useful, and not a total waste of time.