Skip to main content

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 by philosophers as a theory of semantics for predicate logic (although you can do propositional logic without set theory).

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 a
  • $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. So  
  • $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 '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 can use what we've learned is for one-place predicates, the idea here being 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. 

Comments

Popular posts from this blog

William Lane Craig and the Hartle-Hawking No Boundary Proposal

Classical standard hot Big Bang cosmology represents the universe as beginning from a singular dense point, with no prior description or explanation of classical spacetime. Quantum cosmology is different in that it replaces the initial singularity with a description in accord with some law the "quantum mechanical wave function of the universe", different approaches to quantum cosmology differ in their appeal either to describe the origin of the material content of the universe e.g., Tyron 1973, Linde 1983a, Krauss 2012 or the origin of spacetime itself e.g., Vilenkin 1982, Linde 1983b, Hartle-Hawking 1983, Vilenkin 1984.

These last few proposals by Vilenkin, Hartle-Hawking and others are solutions to the Wheeler-DeWitt equation and exist in a category of proposals called "quantum gravity cosmologies" which make cosmic applications of an approach to quantum gravity called "closed dynamic triangulation" or CDT (also known as Euclidean quantum gravity). I&#…

How Should Thatcherites Remember the '80s?

Every now and again, when I talk to people about the '80s I'm told that it was a time of unhinged selfishness, that somehow or other we learned the price of everything but the value of nothing. I can just remember that infamous line from Billy Elliot; 'Merry Christmas Maggie Thatcher. We all celebrate today because its one day closer to your death'. If it reflected the general mood of the time, one might wonder how it is she won, not one but three elections.

In an era when a woman couldn't be Prime Minister and a working-class radical would never lead the Conservative party, Thatcher was both and her launch into power was almost accidental owing in part to Manchester liberals and the Winter of Discontent. Yet I'm convinced her election victory in '79 was the only one that ever truly mattered. Simply consider the calamity of what preceded it, the 1970s was a decade of double-digit inflation, power cuts, mass strikes, price and income controls, and the three…

Creation Of Universes from Nothing

The above paper "Creation of Universes from Nothing" was published in 1982, which was subsequently followed up in 1984 by a paper titled "Quantum Creation of Universes". I decided it would be a good idea to talk about these proposals, since last time I talked about the Hartle-Hawking model which was, as it turns out, inspired by the above work. 
Alexander Vilenkin also explains in a non-technical way the essential idea in his book; Many World's in One – one of the best books I've ever read – it mostly covers cosmic inflationary theory but the 17th chapter covers how inflation may have begun. In fact Vilenkin is one of the main preponderant who helped develop inflation along with Steinhardt, Guth, Hawking, Starobinsky, Linde and others. 
Although I won't talk about it here, Vilenkin also discovered a way of doing cosmology by using something called "topological defects" and he has been known for work he's done on cosmic strings, too.
In ex…