Sets

What is a set? It’s a collection of things. A bag of marbles, a box of chocolates, all of the numbers between 4 and 42. Sets are everywhere. In fact, that list is a set of sets. You can see how they come in handy when we want to talk about the real world - or write programs for it.

Watch the video below for an introduction to this useful concept and then answer the questions below.

Six-minute video

You can also view this video on YouTube

You can find the slides here and also as .odp.

Key Points

What is a set?

• A set is a formal way of talking about a collection of things, like {a, b, c} or “the set of all integers from 1-10”
• We usually refer to sets using capital letters, e.g. A, B, etc. and when we define them we use curly brackets: {}.
• Sets are unordered. There is no “first” or “last” element in a set. You can write them in any order, so { 1, 2, 3 } = { 3, 2, 1 }
• Each element is unique. If you have the set { "cat" , "dog" } and you add { "cat" }, you still have the same set!

Defining sets

• Sets can be defined by extension, or listing, by writing down all of the elements of the set, e.g. A ≜ { 1, 2, 3, 4 } The funny symbol (≜) means “is equal by definition to”. You can also use = here.
• Sets can be defined by intension by giving conditions that say what’s in the set without ambiguity, e.g. A ≜ { y | y > 0 and y < 5 } The symbol | is read “given that”. Or you could write, somewhat less formally, B ≜ { x | x is red and x is a ball }

Common sets

• The set with no elements is called the empty set. We use the symbol Ø for the empty set.
• A set with only one member is called a singleton. (Note that { Ø } is not the empty set, it’s a singleton set containing the empty set))
• The natural numbers ℕ ≜ { 0, 1, 2, 3, … }
• The integers ℤ ≜ { … -3, -2, -1, 0, 1, 2, 3 }
• The real numbers ℝ = the integers and all fractions
• ℕ, ℤ, and ℝ are all infinite in size, but infinity is not an element of them.

Sets in Java

Java provides a Set interface in the java.util package. As it is an interface, we also need a class that implements the Set interface, such as HashSet. We need to import both of these by adding imports to the top of our Java file:

import java.util.Set; 
import java.util.HashSet;

Or we could import both at once by importing the whole java.util package.

import java.util.*; 

We construct a HashSet. We can either store it as a HashSet or Set (if you’re wondering why, ask me about Polymorphism). We can use the add() method to add an element to the set, and contains() to check if an element is in the set.

Set<String> hashSet = new HashSet<String>(); 
hashSet.add("My element"); 
hashSet.contains("My element"); // returns true

We need to specifty the type of data that the set will store in angled brackets. E.g. Set<String> is a Set of String types. This is because Sets are generics. Generic types are far too complicated to explain here (and are beyond what you need in this module), but do ask me if you’re interested.

Sets in Python

Python has sets built in. Sets are written using curly brackets, e.g.

my_set = {"some", "set", "elements"}

In Python a set is a collection that is unordered (just like a set in Set Theory).

Python sets are also unindexed, which means you cannot refer to an item by its index. So the following is not allowed: my_set[0] Because this is trying to look at the element in the set with index 0 - but set elements do not have indexes!

In languages that don’t have sets built in you would often use an array to represent a set. Arrays are ordered, and can have duplicate elements, so if you do use an array to represent a set, make sure you don’t accidently do something you shouldn’t!

Accessing items in a set

So how do you access items in a Python set? You can do so in a loop using the in operator.

Because the set is unordered, you will not necessarily get the elements out in the same order!

For more information about sets in Python, W3Schools has a good introduction.

Questions

1. Check your knowledge

1. Defining Sets

The soup served in the canteen today contains potato, carrot, onion, celery, and leeks. Express the set of vegetables in todays soup V using definition by extension V = {}

2. Defining Sets again

Using definition by listing define the following sets: e.g. The set of all 1 digit binary numbers = {0, 1}

1. The set of all even primes greater than 2 {}
2. The letters of the alphabet that appear in the phrase smell the cheese. {}
3. The numbers between 1 and 10 (inclusive) {}

3. Defining more sets

Which of the following phrases are equivalent when their component letters are expressed through set definition? (You may want to use Python to help you)

1. tomorrow is Monday
2. To my mind sand is dirty snow
3. Tommy ran day and night
4. rain wind and snow today and tomorrow

4. Singleton sets

Which of the following are singleton sets? Check all that apply.

1. [1, 1, 1, 1]
2. The vowels in the alphabet between A and D
3. The prime numbers between 1 and 10
4. The set of all numbers used in the binary system

5. The empty set

Which of the following are empty sets? Check all that apply.

1. The set of all Natural numbers ℕ that are not in the set of all integers ℤ
2. The set of all Integers ℤ, less that 0.
3. The set of all letters in the alphabet tham come before the letter a

Check Answers

Summary

In this section we have learned about the most important part of set theory: sets. We now know that sets are unordered collections of unique things. Once you’ve completed the questions above, you can move on to the next section where we learn how to talk about sets in relation to one another using the concepts of subsets and supersets.

Improve this page