Today, we’ll have an introduction to some of the essentials from discrete math that we’ll build on in this course.

This week was an exception in that the assignment and workshop material was a temperature check on material not previously taught in lecture. Future assignments and workshop sessions will happen after the lecture(s) in which we cover the material. Thank you for your patience with me as I determine what background information I need to cover!

Preliminaries

The notation we use here is not an important focus of this class, but I’ll try to show a few different notations that you may see outside of this class. The goal of notation is to help us be precise, I’ll try to not use more than necessary.

Sets

Set definition

A set is a unordered collection of elements. Set elements are distinct—an element is either contained in the set or not (in a programmer’s view, there are no duplicates).

There are many valid ways to define a set.

Often, we’ll define sets by using curly brackets ({}). We can define a small (finite) set by listing elements inside the brackets.

For example, this is the set containing the integers 1, 2, and 3:

The following is not a set.

Pattern notation

We use ellipses $\dots$ to show “this pattern in the set continues”.

Containment/element of

To show that an element is contained in a set, we’ll use the $\in$ notation (pronounced “in”).

(Aside: in class, we voted on the emoji to indicate “the programmer’s view”).

programmer’s view on containment: $\in$ is like Python’s in keyword.

Set builder/set comprehension notation

We can also define sets by specifying, in math notation, which elements are contained in the set. This is called set builder or set comprehension notation.

programmer’s view: This is like Python’s list or dictionary comprehension, for example: {x: x+1 for x in [1,2,3]}.

This notation still uses curly brackets, but has two parts: a variable name on the left, then the specification for which variables are in the set on the right:

$S=\{x|<something>\}$

The vertical bar in the middle, $|$, separates the two parts, and is often pronounced “such that”.

For example, we can define a $S$ as the set of evens by writing:

We’ll use set comprehension notation frequently in the Alloy section of this course.

Special sets

There are a few special sets in math that have their own names/symbols.

• $\mathrm{\varnothing }$ : the empty set (also could be written as $\{\}$). We’ll use this often in CS340.
• $\mathbb{R}$ : the set of reals (the number line). This comes up in other areas of math often, less so in CS340.
• $\mathbb{Z}$ : the set of integers $\{\dots ,-2,-1,0,1,2,\dots \}$.
• $\mathbb{N}$ : the set of natural numbers $\{0,1,2,\dots \}$. Note that some definitions define the natural numbers as not containing 0. Computer scientists, at least in my experience, lean more toward including it!

Set operations

Now that we’ve defined sets, we can do interesting things with them using set operations.

On sets $S$ and $T$:

Subset: $\subseteq$

$S\subseteq T$ is pronounced “$S$ is a subset of $T$” and means every element of $S$ is also an element of $T$.

This matches our intuitive English definition of a subset.

We say it’s a strict subset, $S\subset T$, if there is at least one element in $T$ that is not in $S$ (that is, if $S$ is a subset of $T$ but is strictly smaller than $T$). You can remember this by comparing it to $\le$ vs. $<$ on numbers.

My answer in class: yes, but not very often.

My follow-up answer: this notation ($\supseteq$), does denote the superset when used in that direction: $S\supseteq T$ means every element of $T$ is an element of $S$. This does occasionally come up.

An important aside: subset and containment are different!

programmers view: the types are different. Subset works on things of the same type, contains needs an element type. For example, a subset of Set<Integer> would have type Set<Integer>. An element of Set<Integer> would have type Integer.

Equality: $=$

$S=T$ is pronounced “$S$ equals $T$” and means the sets have the same elements.

Union: $\cup$

$S\cup T=\{x|x\in S\mathtt{\text{ or }}x\in T\}$
$S\cup T=\{x|x\in S\vee x\in T\}$

Note: $\vee$ is just or. In CS240 notation: $+$.

$S\cup T$ is pronounced “$S$ union $T$” (or sometimes “$S$ or $T$”)and the result is a new set that contains all of the elements that are in either $S$ or $T$.

To remember: the word “union” sounds like bringing people together! In my CS240 intuitive framing, union is the more “permissive” operation.

Intersection: $\cap$

$S\cap T=\{x|x\in S\mathtt{\text{ and }}x\in T\}$
$S\cap T=\{x|x\in S\wedge x\in T\}$

Note: $\wedge$ is just and. In CS240 notation: $\cdot$.

$S\cup T$ is pronounced “$S$ intersection $T$” (or sometimes “$S$ and $T$”) and the result is a new set that contains all of the elements that are in both $S$ or $T$.

To remember: street “intersections” are the parts of the road where both streets meet. In my CS240 intuitive framing, intersection is the more “strict” operation.

Complement: $S^c$, $\bar{S}$, $S^{\prime }$

$S^c$ is pronounced “the complement of $S$” or “not $S$” and means all of the elements that are not in S.

This could be an infinite number of elements if we are considering the entire universe to be our domain. Often, we’ll combine the complement operator with an intersection operator to talk about smaller, more useful sets.

Set difference: $\setminus$

$T\setminus S$ is pronounced “$T$ minus $S$” or “$T$ set difference $S$” and means the elements in $T$ and not in $S$.

Note that this is equivalent to the previous exercise: $T\setminus S=T\cap S^c$. Another way to write this would be $\{x|x\in T,x\notin S\}$

Note that when we use “,” inside a set comprehension, this means “and”. It would be equivalent to write $\{x|x\in T\wedge x\notin S\}$.

Ordered tuples/pairs

We can express ordered pairs or tuples using parenthesis.

programmer’s view: this is like Python tuples.

Aside: Like Python tuples, sets can be heterogenous (that is, have elements of seemingly different types)

So:

Relations

Relations are a useful special type of set.

Binary relations

Binary relations are sets of ordered tuples.

General relations

A general relation has elements that are $n$-tuples, where $n$ is fixed for a given relation.

Back to the programmer’s view: we can make analogies to other data representations

Cartesian Product

The cartesian product of sets $A$ and $B$ is defined as:

$A\times B=\{(a,b)|a\in A,b\in B\}$

That is, the cartesian product is all possible combinations of the elements in set $A$ and set $B$.

We can have a cartesian product on a single set:

$S\times S=S^2=\{(x,y)|x,y\in S\}$

which is the same as:

$S\times S=S^2=\{(x,y)|x\in S,y\in S\}$

Relation definition, again

Now that we have cartesian products, we can more formally define a relation.

A relation $R$ on set $A\times B$ is any subset $R\subseteq A\times B$.

Relation properties

For a relation $R$ on $A\times A$, we can define useful properties:

Reflexive

$R$ is reflexive if for all $a\in A,(a,a)\in R$.

Symmetric

$R$ is symmetric if for all $a,b\in A,(a,b)\in R\Rightarrow (b,a)\in R$.

Transitive

$R$ is transitive if for all $a,b,c\in A,(a,b)\in R\wedge (b,c)\in R\Rightarrow (a,c)\in R$.

Functions

Mathematical functions can be defined as a special kind of relation, where each value $a$ in $(a,b)\in R$ has one distinct value $b$.

Said more formally:

A function $F$ on sets $A$ and $B$ is a subset $F\in A\times B$ such that:

• For all $a\in A$, these exists a $b\in B$ such that $(a,b)\in F$, and
• $(a,b)\in F\wedge (a,c)\in F\Rightarrow b=c$.

The first condition says that every element in $A$ maps to something, and the second condition says that it maps to only one distinct thing.

programmer’s view: Python dictionaries are a close mental model for functions.

In class, we drew out the 2D plane to relate this to the vertical line test for determining if a line in the plane is a function (the 2D plane is a visual representation of ${\mathbb{R}}^2$). A unit circle is not a function, because it does not pass the vertical line test, but it is a relation on $\mathbb{R}\times \mathbb{R}={\mathbb{R}}^2$.

If $C$ is the unit circle:

Logic

We’ll cover logic more in the next lecture, but for now, a quick note on logical implication.

Implication: $\Rightarrow$

In short, this is the truth table for implication:

A B    A => B
-------------
T T    T
T F    F
F T    T
F F    T

For example, consider if I said:

Which we can also write as:

These statement are both $true$!

The statements themselves are not a lie, since the first part of the conditional is never true. In logic, false implies anything. More on this on Monday.

This is the truth table for equality/bidirectional implication, which might feel more intuitive:

A B    A <=> B
-------------
T T    T
T F    F
F T    F
F F    T

To be continued next week!