Chapter 1.1 The Algebra of Sets

In this section, we give an introduction to the language of set theory. Becoming proficient with the language will be able to describe a variety of mathematical objects and model a wide variety of physical process.

Introduction

One of the key goals of this class is to go over The Calculus.

The Calculus is the discipline in mathematics that deals with the study of continuously changing quantities. The basic theory was formulated in late 1600’s independently by Newton (1643–1727) and Leibniz (1646 – 1716). Later on, Euler (1707–1783) was on the leading figures in the period of development.

The Calculus can model a wide variety of motions, one of which is planetary motion. To do this, we will:

  • develop a language for expressing ideas about space and quantity.

  • understand the principles of calculus as extensions of innate human intuition.

  • use the principles of calculus to develop the Calculus and understand some of its applications.

The principles are

  • Decomposition,
  • Transformation,
  • Rigidity,
  • Symmetry,
  • Finite Approximation,
  • Local Linear Approximation,
  • Higher Order Approximation,
  • Integration.

We will learn about the first four principles in Math 2 and the last four in Math 3A and 3B.

Chapter 1 will be all about Decomposition.

Decomposition

The principle of decomposition is to understand something by determining the properties of its simpler separate components.

To explore and use this principle, we need to understand set theory.

The Language of Set Theory

All languages contains primitive notions, which are words that are understood only by shared experiences. For example, the concept of colors. You can point at a blue shirt and ask someone what the color of the shirt is. That person will tell you it is blue even though they might not be able to give you an exact definition of the color blue.

Natural language is full of these kinds of primitive notions, which makes it imprecise. Because natural language is used to describe the full spectrum of human experience, it will be imprecise.

Conversely, mathematics is precise because it deals with idealizations. Mathematics has only two primitive notions: Set and Element (or Member). There is no definition for these primitive notions. Instead, a list of formal rules called axioms determines what statements are true about sets and membership.

In this class, think of a set as a featureless container and membership as the property of something being inside that featureless container. We will use the following notation for sets and membership in a set.

Set Notation and Membership

Write \(a \in A\) to mean: “\(a\) is an element of \(A\)”.

Write \(\{a\}\) to mean: “the set that has only \(a\) as an element”.

Write \(\{a, b, c, d, \dots\}\) to mean: “the set that contains only the elements \(a\), \(b\), \(c\), \(d\), and so on”.

Write \(\{\}\) or \(\emptyset\) to mean: “the set that contains no elements”.

Write \(\{a \in A\colon P(a)\}\) to mean: “the set of all elements of \(A\) for which \(P(a)\) is true”, or, “the set of all \(a\) in \(A\) that satisfy \(P(a)\)”.

Denote by \(\mathbb N\) (read: “En”) the set of natural numbers, and by \(\mathbb N_0\) (Read:“En Naught”) the set of natural numbers with zero, so that \[\mathbb N_0 = \{0, 1, 2, 3, \dots\}\quad\text{and}\quad\mathbb N = \{1, 2, 3, \dots\}.\]

To describe and construct sets, we use set builder notation.

Confirm your understanding with the following example.

Example 1

Use set builder notation to describe the set of all natural numbers whose square is less than 100, then explicitly write out this set as a collection of natural numbers

Take \(\mathbb{N}\) to be the set of natural numbers and \(n\) stand for a natural number. Symbolically, \(n^2\) represents the square of a natural number.

The symbols “\(<10\)” represents less than 100.

The statement \(P(n)\) is the requirement that \(n^2<100\).

In set notation:

\[S=\{n\in \mathbb{N}\colon n^2<100\}\]

Read this as:

  • \(n\) is a natural number (\(n\in\mathbb{N}\))
  • such \((:)\)
  • \(n^2\) is less than \(100\) (\(n^2<100\))

The natural numbers that satisfy the requirement \(n^2<100\) are \(1,2,3,4,5,6,7,8,9\) since

  • \(1^2=1\) is less than 100
  • \(2^2=4\) is less than 100
  • \(3^2=9\) is less than 100
  • \(4^2=16\) is less than 100
  • \(5^2=25\) is less than 100
  • \(6^2=36\) is less than 100
  • \(7^2=49\) is less than 100
  • \(8^2=64\) is less than 100
  • \(9^2=81\) is less than 100.

Therefore, \[S=\{1,2,3,4,5,6,7,8,9\}.\]

Mathematicians care about describing numbers as sets because doing so can reduce proving statements about numbers to proving equivalent statements about sets.

Example 2

Use set notation to write the set \(S\) that consists of all odd natural numbers that are greater than or equal to \(1\) and less than or equal to \(4\). Describe \(S\) using only set notation.

Take \(\mathbb{N}\) to be the set of natural numbers and \(n\) stand for a natural number.

The symbols “\(1\leq n\)” represents \(n\) greater than or equal to 1.

The symbols “\(n\leq 4\)” represents \(n\) less than or equal to 4.

In set notation:

\[S=\{n\in \mathbb{N}\colon n\text{ is odd and }1\leq n \leq 4\}\]

Read this as:

  • \(n\) is a natural number (\(n\in\mathbb{N}\))
  • such \((:)\)
  • \(n\) is odd and
  • \(n\) is greater than or equal to 1 and less than or equal to 4 (\(1\leq n\leq 4\))

The natural numbers that satisfy the requirement are \(1\) and \(3\) since

  • \(1\) is odd, greater than or equal to 1 and less than or equal to 4
  • \(3\) is odd, greater than or equal to 1 and less than or equal to 4

Therefore, \[S=\{1,4\}.\]

All the sets we wrote in the previous examples were a list of elements from a “bigger” set, which was the set of natural numbers. The language to describe this kind concept of “bigger” is given below.

Subset

A set \(A\) is a subset of \(B\) (denoted \(A\subseteq B\)) if for each \(a\) in \(A\), \(a\) is in \(B\).

The following image illustrates the idea of subset:

As we can see, subset describes how one set is contained in another set. The definition allows for the possibility that the two sets are equal. It is similar to the statement \(1\leq 1\). This statement is true because the symbol \(\leq\) means less than or equal to. However, \(1<1\) is a false statement because \(1\) is not less than \(1\).

We can define a strict requirement like this for sets.

Proper Subset

A set \(A\) is a proper subset of \(B\) (denoted \(A\subset B\)) if \(A\subseteq B\), but \(B\) has an element that is not in \(A\)

Confirm your understand by answering the following example.

Example 3

Which statements are true and which are false?

  1. \(\{a, b, c\}\subseteq \{\{a, b\}, c, d\}\)

  2. \(\{a, b, c\}\subset \{a, b, c, d\}\)

  3. \(\{a, b\}\subset \{\{a, b\}, c, d\}\)

  4. \(\{a, b\}\in \{\{a, b\}, c, d\}\)

  5. \(\{a, b\}\subset \{a, b, c, \{d\}\}\).

  6. \(\{a, b, c\}\subset \{a, b, c\}\).

  1. Take \(A=\{a,b,c\}\) and \(B=\{\{a, b\}, c, d\}\). The set \(A\) contains three elements: \(a\), \(b\), and \(c\). The set \(B\) contains the three elements: \(\{a,b\}\) (the set containing \(a\) and \(b\)), \(c\) and \(d\). The statement \(A\subseteq B\) (\(A\) is a subset of \(B\)) is true provided every element in \(A\) is in \(B\). It is false because the element \(a\) is not in \(B\).

  2. Take \(A=\{a,b,c\}\) and \(B=\{a,b, c, d\}\). The set \(A\) contains three elements: \(a\), \(b\), and \(c\). The set \(B\) contains the four elements: \(a\), \(b\), \(c\) and \(d\). The statement \(A\subset B\) (\(A\) is a proper subset of \(B\)) is true provided every element in \(A\) is in \(B\) and \(B\) has an element that is not in \(A\). It is true because the element \(a\) is in \(B\) and \(B\) contains at least one element not in \(A\). In this case, \(d\) is in \(B\) but not in \(A\).

  3. Take \(A=\{a,b,c\}\) and \(B=\{\{a, b\}, c, d\}\). The set \(A\) contains three elements: \(a\), \(b\), and \(c\). The set \(B\) contains the three elements: \(\{a,b\}\) (the set containing \(a\) and \(b\)), \(c\) and \(d\). The statement \(A\subset B\) is true provided every element in \(A\) is in \(B\). It is false because the element \(a\) is not in \(B\).

  4. Take \(B=\{\{a,b\},c,d\}\). The set \(B\) contains three elements: \(\{a,b\}\), \(c\) and \(d\). The statement \(\{a, b\}\in B\) (the set \(\{a,b\}\) is an element of the set \(B\)) is true provided that \(\{a,b\}\) is an element in \(B\). This is true.

  5. Take \(A=\{a,b\}\) and \(B=\{a,b, c, \{d\}\}\). The set \(A\) contains two elements: \(a\) and \(b\). The set \(B\) contains four elements: \(a\), \(b\), \(c\) and \(\{d\}\). The statement \(A\subset B\) (\(A\) is a proper subset of \(B\)) is true provided that every element of \(A\) is in \(B\) and \(B\) has an element that is not in \(A\). This is true because \(a\) and \(b\) are elements in \(B\) and \(B\) has an element not in \(A\). In particular, \(c\) is an element in \(B\) that is not in \(A\).

  6. Take \(A=\{a,b,c\}\) and \(B=\{a,b, c\}\). The set \(A\) contains three elements: \(a\), \(b\) and \(c\). The set \(B\) contains three elements: \(a\), \(b\) and \(c\). The statement \(A\subset B\) (\(A\) is a proper subset of \(B\)) is true provided that every element of \(A\) is in \(B\) and \(B\) has an element that is not in \(A\). Although every element of \(A\) is in \(B\), the set \(B\) does not contain an element that is not in \(A\).

One benefit to using set theory is it can reformulate what it means for a statement to be more restrictive than another statement as a statement involving sets. This is how we do it:

for any \(x\) in a set \(X\), take \(P\) and \(Q\) to be statements about \(x\).

The requirement that these statements are true for a given \(x\) in \(X\) is a condition on the set \(X\).

Restrictive Condition

Statement \(P\) gives a more restrictive condition than statement \(Q\) if \[\{x\in X\colon P(x)\} \subset \{x\in X\colon Q(x)\}.\]

Do you understand why this statement using subsets captures the idea that \(P\) is more restrictive than \(Q\)?

Try to further your understanding with this example.

Example 4

Take \(P\) and \(Q\) to be the following statements: For any natural number \(n\), \(P(n)\) is the statement “\(n\) is less than 9” and \(Q(n)\) is the statement “\(n\) is less than 4”. The requirement that these statements are true for a given \(n\) is a condition on the set of natural numbers. Which statement gives a more restrictive condition?

The statement \(P(n)\) is \(n\) is less than \(9\). So \[\{n\in\mathbb{N}\colon P(n)\}=\{n\in \mathbb{N}\colon n<9\}=\{1,2,3,4,5,6,7,8\}.\]

The statement \(Q(n)\) is \(n\) is less than \(4\). So \[\{n\in\mathbb{N}\colon P(n)\}=\{n\in \mathbb{N}\colon n<4\}=\{1,2,3\}.\]

Take \(P=\{1,2,3,4,5,6,7,8\}\) and \(Q=\{1,2,3\}\). It is true that \[Q\subset P\]. Therefore, \(Q\) gives a more restrictive condition than \(P\).

Unions and Intersections

There are different kinds of operations on numbers and each operation can be interpreted in different ways. For example, if the numbers \(A\) and \(B\) represent how many students you have in class A and class be respectively, then \(A+B\) gives the total number of students in class \(A\) and \(B\).

There are also operations for sets as well. For example, the symbols \(\cup\) and \(\cap\) represent operations on sets.

Union

The union of sets \(A\) and \(B\), \(A\cup B\), contains everything in either \(A\) or \(B\).

Essentially, a union creates a new set by combining everything from two sets into a single set.

Intersection

The intersection of sets \(A\) and \(B\), \(A\cap B\), contains everything in both \(A\) and \(B\).

An intersection can create a new set by only accepting the elements that are present in both sets.

Confirm your understanding of these two operations by answering the following question.

Example 5

Take \[X = \{a, b, c, d, e, f, g\}\] and \[Y = \{d, e, f, g, h, i\}.\] What is \(X\cup Y\) and \(X\cap Y\)?

The set \(X\cap Y\) (\(X\) intersect \(Y\)) is the set the contains all elements that are in both \(X\) and \(Y\). The common elements are \(d,e,f\) and \(g\): \[X\cap Y=\{d,e,f,g\}.\]

The set \(X\cap Y\) (\(X\) union \(Y\)) is the set the contains all elements that are in either \(X\) and \(Y\). The common elements are \(d,e,f\) and \(g\). The elements in \(X\) that aren’t in \(Y\) are \(a\),\(b\),\(c\). The elements in \(Y\) that aren’t in \(X\) are \(h\) and \(i\). Altogether, we have \[X\cup Y=\{a,b,c,d,e,f,g,h,i\}.\]

As seen in the above example, two sets can have overlaps. What if we wanted to describe all elements in a set that are unique to that set relative to another set?

We can do this using set difference.

Set Difference

The set difference of sets \(A\) and \(B\), denoted by \(A\smallsetminus B\), is the set that contains all elements of \(A\) that are not in \(B\).

Practice your understanding with this example.

Example 6

Take \[X = \{a, b, c, d, e, f, g\}\] and \[Y = \{d, e, f, g, h, i\}.\] What is \(X\smallsetminus Y\) and \(X\smallsetminus Y\)?

To determine both sets, it may be helpful to first find the intersection of \(X\) and \(Y\) because that will give us all the common elements. The intersection is \[X\cap Y=\{d,e,f,g\}.\]

The set \(X\smallsetminus Y\) (\(X\) set difference \(Y\)) is the set the contains all elements that are in \(X\) that are not in \(Y\). The common elements are \(d,e,f\) and \(g\). Remove these elements from \(X\) to get that \[X\smallsetminus Y=\{a,b,c,d\}.\]

The set \(Y\smallsetminus X\) (\(Y\) set difference \(X\)) is the set the contains all elements that are in \(Y\) that are not in \(X\). The common elements are \(d,e,f\) and \(g\). Remove these elements from \(Y\) to get that \[Y\smallsetminus X=\{h,i\}.\]

The following are useful properties about sets.

Example 7

For any sets \(A\), \(B\), and \(C\), the following statements are true:

  1. \(A\cup (B\cup C) = (A\cup B)\cup C\) (associative property);

  2. \(A\cap (B\cap C) = (A\cap B) \cap C\) (associative property);

  3. \(A\cap (B\cup C) = (A\cap B) \cup (A\cap C)\) (distributive property);

  4. \(A\cup (B\cap C) = (A\cup B) \cap (A\cup C)\) (distributive property).

Find examples for each of these statements.

Take \(A=\{1,2,3\}\), \(B=\{2,3,4\}\), and \(C=\{1,4\}\).

  1. \(A\cup(B\cup C)=A\cup \{1,2,3,4\}=\{1,2,3,4\}\) and \((A\cup B)\cup C=\{1,2,3,4\}\cup C=\{1,2,3,4\}.\)

  2. \(A\cap(B\cap C)=A\cap \{4\}=\{\}\) and \((A\cap B)\cap C=\{2,3\}\cap C=\{\}.\)

  3. \(A\cap(B\cup C)=A\cap\{1,2,3,4\}=\{1,2,3\}\) and \((A\cap B) \cup (A\cap C)=\{2,3\}\cup\{1\}=\{1,2,3\}.\)

  4. \(A\cup (B\cap C)=A\cup\{4\}=\{1,2,3,4\}\) and \((A\cup B) \cap (A\cup C)=\{1,2,3,4\}\cap\{1,2,3,4\}=\{1,2,3,4\}.\)

The language of sets is a useful framework for applying decomposition because sets decompose nicely into subsets.

We will study the decomposition of sets into subsets in the next section.

Return

© Copyright 2024 by the POC Writing Team: Bryan Carrillo, Yat Sun Poon, and David Weisbart.

All rights reserved. No part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the POC Writing Team.