Skip to content
Tutorials Center
My learning

Topics

Lesson 2 of 38 ยท Getting Started

Equality and Subsets

Understand when two sets are equal, what a subset and a proper subset are, and how to prove set equality by showing two inclusions.

Once you can write sets, the next question is how to compare them. Two sets can be equal, one can sit inside the other, or they can be unrelated. The idea of a subset is the most used relation in all of set theory, and the method of proving two sets equal by proving two inclusions appears in nearly every proof you will read.

Equality of sets

Two sets A and B are equal, written A = B, when they have exactly the same elements. Formally:

Text
A = B  means  for every x:  x โˆˆ A  if and only if  x โˆˆ B

This principle is called extensionality. It says a set is nothing more than its elements. The sets {1, 2, 3}, {3, 2, 1} and {n : n is a whole number, 1 โ‰ค n โ‰ค 3} are all equal, even though they are written in different ways.

Subsets

A is a subset of B, written A โІ B, when every element of A is also an element of B:

Text
A โІ B  means  for every x:  if x โˆˆ A then x โˆˆ B

For example, {2, 4} โІ {1, 2, 3, 4}. We also say "B contains A" or "A is included in B". Three facts follow right away from the definition:

  • Every set is a subset of itself: A โІ A.
  • The empty set is a subset of every set: โˆ… โІ A. The condition "if x โˆˆ โˆ… then x โˆˆ A" is true for every x, because x โˆˆ โˆ… is never true. Logicians call this vacuous truth.
  • Transitivity: if A โІ B and B โІ C, then A โІ C.

Do not confuse โˆˆ with โІ. The symbol โˆˆ links an element to a set; โІ links a set to a set. We have 2 โˆˆ {1, 2, 3} and โІ {1, 2, 3}, but 2 โІ {1, 2, 3} makes no sense (unless 2 happens to be a set).

Proper subsets

A is a proper subset of B, written A โŠŠ B (some books write A โŠ‚ B), when A โІ B and A โ‰  B. In words: everything in A is in B, and B has at least one extra element. Notation varies between textbooks, so check which convention a book uses for โŠ‚. This track uses โІ for "subset or equal" and โŠŠ for "proper subset" so there is no ambiguity.

Python Subset tests in Python

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Proving two sets are equal

To show A = B you almost always prove two inclusions: A โІ B and B โІ A. This is called a double inclusion proof. It works because both inclusions together say that every element of A is in B and every element of B is in A, which is exactly extensionality.

Example. Let A = { n โˆˆ โ„ค : n is divisible by 6 } and B = { n โˆˆ โ„ค : n is divisible by 2 and by 3 }. Show A = B.

  • A โІ B: take n โˆˆ A. Then n = 6k for some integer k. So n = 2ยท(3k) is divisible by 2, and n = 3ยท(2k) is divisible by 3. Hence n โˆˆ B.
  • B โІ A: take n โˆˆ B. Because 2 divides n, n is even. Because 3 divides n, write n = 3m. Since n is even and 3 is odd, m must be even, so m = 2k and n = 6k. Hence n โˆˆ A.

Both inclusions hold, so A = B.

The pattern is always "let x be an arbitrary element of the first set, and show it is in the second". You are not testing particular values: you are showing the property for any element at all.

Testing claims with a computer (and its limits)

For finite sets you can check subset claims by brute force. For infinite sets such as the integers divisible by 6, a program can only check a finite window. That is useful for catching a wrong guess, but it is not a proof: a claim might hold for the first million numbers and still fail later. The next program checks the divisibility example in the window from -60 to 60, and then looks for a deliberate counterexample.

Python Checking an equality on a window

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Sets of sets and the inclusion chain

Subsets can be chained: โˆ… โІ {1} โІ {1, 2} โІ {1, 2, 3}. The number sets you know form a famous chain too:

Text
โ„• โІ โ„ค โІ โ„š โІ โ„ โІ โ„‚

(natural numbers, integers, rationals, reals, complex numbers). Each is a proper subset of the next. You will study these in the lesson on special sets.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which statement is always true for any set A?

    The empty set is a subset of every set (vacuous truth). A set is never a proper subset of itself.
  2. 2. To prove A = B you usually show:

    Extensionality says A and B have the same elements, which is the same as the two inclusions together.
  3. 3. Is {2} โІ {1, 2, 3} true? Is 2 โІ {1, 2, 3} meaningful?

    The relation โІ compares sets. {2} is a set whose only element lies in the larger set, so the first is true.
  4. 4. Sets A and B satisfy A โІ B and B โІ C. What follows?

    Subset is transitive: an element of A is in B, and then in C.

Summary

  • A = B means the same elements (extensionality).
  • A โІ B means every element of A is in B; A โŠŠ B also requires A โ‰  B.
  • โˆ… โІ A and A โІ A hold for every set; subset is transitive.
  • Prove equality by double inclusion; checking a finite window by computer only finds counterexamples.

Next: Power Sets and Counting Subsets