2 of 2

34.1 Sets and Membership

Logic plays a critical role in the field of mathematics. In this chapter and the next, we see how logic allows us to reason about a type of object that is fundamental to mathematics: sets.

Set: a collection of things. The things in the set are called the members or elements.

A set is a collection or group of things. All the players on a basketball team would make a set. All the leaves on a tree would make a set.

The things in the set are call the members or elements of the set.

Sets are called abstract collections of things, because we don’t have to physically gather all the leaves in a bucket, or get all the basketball players in a huddle, in order to talk about the set of them.

That is to say, you don’t have to physically collect all the objects together.

We can just define a set by saying what is in it. For example, I can define set “s” this way: set s is the set containing the numbers 1 and 2. That is: s = {1,2}.

List notation: {1,2}

We write sets with curly braces, and we put the elements inside, separated by commas. When we list out all the elements of a set like that, it is called list notation.

Sometimes it is too annoying or infeasible to list all the members of a set. For example, if I wanted to list all the members of a basketball team, it would be sort of annoying. If I wanted to list all the leaves of a tree, it would be totally infeasible.

Instead, we can use a universal quantifier. If we wanted to define “leaves” to be the set of all the leaves on the maple tree in the front yard, we write it this way:

leaves = {Ax: x is a leaf on the maple tree in the front yard}

Set-builder notation: we can put all the prime numbers in a set by writing {Ax: x is prime}.

This notation is called set-builder notation. Read the notation this way: “leaves” is the set of all x such that x is a leaf on the maple tree in the front yard.

Notice that we are using a combination of FOL and English in order to make it easier to talk about sets. This practice is very common when we want both logical precision and ease of use.

When we talk about sets using English, or a combination of English and FOL, we can use upper-case letters in names. For example, when we wanted to list the set of the original Avengers, we would write:

{Iron Man, Wasp, the Hulk, Thor, Ant-Man}

Your turn to practice.

Set Membership Relation: ∈

The only predicate that gets a symbol in FOL is identity: a=a.

We can start to do set theory with FOL by adding a binary predicate for set membership. a∈b says a is an element of b.

We can use FOL to study the realm of sets by adding just one more binary symbol: ∈, which means set membership.

a∈b says that a is a member or element of b.

The syntax of the ∈ symbol is like identity: it is a binary predicate, and is written infix.

Here are some truths:

  • Iron Man ∈ {Iron Man, Wasp}
  • Iron Man ∈ {Ax: x is an Avenger}
  • Ant-Man ∉ {Iron Man, Wasp}

The ∉ is similar to ≠. a∉b is shorthand for ~(a∈b).

Three Key Facts

There are three key facts about sets that you have to know.

Key fact 1: order doesn’t matter.
{1,2} = {2,1}

First, order doesn’t matter. The set {1,2} is the same set as the set {2,1}.

Second, repetition doesn’t matter. If we repeat the name of an object, that doesn’t mean we “put” it in the set multiple times.

Key fact 2: repetition doesn’t matter.
{1,2} = {1,1,1,2}

Either it is in the set or it isn’t, and repeating the name is irrelevant.

Third, how you refer to an object doesn’t matter. For example, if you use different names for an object, it is still the same set.

Key fact 3: name choice doesn’t matter.
{2} = {two}

{two} = {2}

{Santa Clause} = {St. Nick}

{1} = {the smallest positive odd number}

You’ve seen that sets can contain physical objects, like leaves and basketball players. And they can contain abstract objects, like numbers.

Sets can have other sets as elements.

Sets can also contain other sets. One set can be the member of another set.

For example, let’s say:

a = {1,2}
b = {3,4}

We can then define a new set, c, this way:

c = {a,b}

Another way to write the same thing is this:

c = {{1,2}, {3,4}}

But that is not the same thing as

d = {1,2,3,4}

Sets c and d are not the same set. c ≠ d. Set c has two members, which are both sets. Set d has four members, which are all numbers.

Members of a member of a set are not necessarily members of a set!

This might sound confusing a first, but it is key to understand: a member of a member of a set is not necessarily a member of the set.

To put the point another way: you have to carefully obey the grouping in sets to see what exactly are the elements of a set.

The Empty Set: ∅

{ } and ∅ refer to the empty set.

Sets are just collections of things, but that doesn’t mean that every collection has stuff in it.

Just like an empty bucket, sets can be empty too. The set with no members is called the empty set.

To refer to it, we can use list notation with nothing in it: { }. Since it is unique and important, there is also a special symbol that refers to the empty set: ∅.

Don’t get confused. This is not the empty set: {∅}. That is a set with one element (the empty set)!