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&#…

Can inflation be eternal into the past?

Back in 2003 a paper appeared on the arXiv titled "Inflationary spacetimes are not past complete" that was published by Arvind Borde, Alan Guth and Alexander Vilenkin which has had considerable amounts of attention online. The theorem is rather uninteresting but simple and doesn't require a very complicated understanding of math. So I thought I'd explain the result here.

It's purpose is to demonstrate that inflationary models are geodesically incomplete into the past which they take as "synonymous to a beginning" but Vilenkin stresses that the theorem can be extended to non inflationary models so long as the condition of the theorem that the average rate of expansion is never below zero is met. These models too then are incomplete into the past. Consider the metric for an FRW universe with an exponential expansion


Where the scale factor is


Since the eternal inflation model is a "steady state cosmology" the mass density and the Hubble paramet…