The Story So Far
•	Formal Systems
>	Syntax
»	language: alphabet  + grammar
»	deductive system: axioms + rules of inference
>	Semantics
»	interpretation
•	Propositional logic
•	Predicate logic (with equality)
•	Natural deduction
•	New theories
This Lecture
•	In this lecture we will develop one of the most important theories for modelling software systems
>	set theory
>	relations
>	functions
Sets
•	Collection of distinct objects
•	In this course elements of well-formed sets are drawn from a larger homogeneous set.
•	Examples:
>	{1, 3, 5, 7, ... }
>	{red, green, blue, green}
>	{Peter, Doug, Kevin, Eduardo, ... }
>	{ yes, no }
•	But not: {red, 1, 2, 3 }
Set Definition & Membership
•	Sets can be defined by enumeration
Odds == {1, 3, 5, 7, ... }
Colors == {red, green, blue, blue, green}
15-671 == {Elizabeth, Doug, Kevin, Eduardo, ... } 
>	Note the use of “==“ for definition (    )
•	Membership test: 3 Œ Odds ;  2 œ Odds
>	note Œ  is a predicate over sets and elements
•	Some sets have predefined names
∆  the set with no elements (the “null” or “empty” set) -- also written {}
N  the set of natural numbers  {0, 1, ... }
Z  the set of integers  {... -2, -1, 0, 1, 2, ... }
Given Sets
•	We can define new sets of primitive elements
>	Called “basic sets”
>	Written [TheSet]
>	We know nothing about the elements, but assume there is an = operator over them
•	Examples
>	[BookIdentifiers]
>	[Date,Name,Place]
•	Later we will see how we can additional assertions about the elements of a new given set.
Set Equality and Cardinality
•	Sets have an equality operator.
Two sets are equal if they have the same elements. That is:
(S = T) €  (" x ∑ x Œ  S € x Œ  T) 
•	Note this implies that ordering of elements does not matter.

•	Cardinality (size) of a set: #
>	# {1, 2, 4} = 3
>	# { {1,2}, {1,2,3,4,5,6,7} } = ?
>	# {1, 2, 2, 4} = ?

Set Operators
•	Can form new sets from other sets using operators: 
>	 « (intersection), » (union), \ (difference)
•	Examples: Let A == {1,2,3} and B == {3,4,5}
>	A « B = {3}
>	A » B = {1,2,3,4,5}
>	A \  B = {1,2}
•	Note the use of "=" versus "==".
•	A is a subset of B ( A    B) if every element of A is also an element of B.
•	A = B if A      B and B      A.
Set Axioms & Laws
•	Basic axioms
>	Set membership: " x ∑ x Œ  {x}
>	Empty set: " x ∑ ~ (x Œ  ∆ )
•	Laws (can be proven)
>	A « B = B « A		A » B = B » A
>	(A » B) » C = A » (B » C)
>	(A « B) « C = A « (B « C)
>	A « (B » C) = (A « B ) » (A « C )
>	and lots of others
Set Comprehension
•	Enumerating all of the elements of a set is not always possible.
•	Would like to describe a set by in terms of a distinguishing property of its elements.
>	Roster == the set of students in 15-671
>	Pgh == the set of residents of Pittsburgh
>	Primes == the set of integers that are prime
•	Each element "satisfies"some "criterion".
Qn: How can we define such criteria?
Ans: Predicates!
•	This kind of set specification is called set comprehension
Set Comprehension (2)
•	Simple form of set comprehension
{x : S | P(x)}
“the set of all x in S that satisfy P(x)”, or
“the set of all x in S such that P(x)”
•	Examples
>	natural numbers less than 20: {x: N | x < 20}
>	even integers: {x: Z | ($ y: Z ∑ x = 2y)}
»	note we identify the types of variables in predicates
>	all natural numbers: {x: N | true}
>	empty set of natural numbers: {x: N | false}
Set Comprehension (3)
•	Sometimes it is helpful to specify a “pattern” for the elements.
>	We will use the form: {x: S ∑ f(x)}, where f is some function defined on elements of S.
>	Note the use of “∑ ” instead of “|” 
•	Examples:
>	squares:  {x: N ∑ x 2}
>	authors of books in library:
     {b: Library ∑ author-of(b) }
where  author-of: Book Æ Author
>	birthdays of people in 15-671
     {person: 15-671∑ birthday-of(person) }

Alternative Notation
•	In more traditional mathematics the expression part is usually written first
•	Examples
>	{x: N ∑ x 2} would be written { x 2 | x Œ N }
•	For reasons that will be come clear later in the course we do not do this.
Set Comprehension (4)
•	Most general form combines the two forms
 {x: S  | P(s) ∑ f(x)}
•	Examples
>	squares of integers less than 20:
     {x: N | x < 20 ∑ x 2}
>	squares of even integers:
     {x: Z | ($ y: Z ∑ x = 2y) ∑ x 2}
•	Can think of this as “nested pipelines”
Power Sets
•	The set of all subsets of S is referred to as the power set  of S and written R S.
•	Examples:
>	R {1, 2, 3 } = 
       { ∆, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}
>	R N = { ∆, {1},{1,2}, {1,3} ...}
•	Power sets can be used to define new types, and can be used in declarations
>	class-groups == R Student
>	Integer-sets == R N
>	If x : R N, then x is a set of Integers.
>	Whenever you see “ .. : P ..” read “set of”
>	Alternatively could write:  x: Integer-sets
Cartesian Products
•	Ordered pairs, triples, etc. 
•	Examples:
>	(2, 3) π (3, 2)
>	S == { (2, red), (5, blue), (3, red) }
•	The set of all tuples constructed from two sets is called a Cartesian Product, or just Product of those sets.
>	If S and T are those sets, this is written S x T
•	Examples
>	N x N   pairs of natural numbers
>	(2, red): N x Color
>	S: R  (N x Color)
More Tuples
•	In general tuples can be described using variables, much like the record constructor of Pascal
•	General form: 
>	{declarations | predicate}
>	the predicate is sometimes called an invariant over the state space defined by the declarations
•	Examples
>	{(x, y): N x N | y = x + 1} = {(0,1), (1,2), (2,3), …}
>	{x, y: N | y = x + 1} = {(0,1), (1,2), (2,3), …}
>	{x: R Z; y: N | y = #x} = { ({-1,2,3}, 3), ( ∆, 0)…}
	
Relations
•	A relation is a set of pairs.
•	Examples:
>	A == { (1,1), (1,2), (2,2) }
>	B == { (2, red), (5, blue), (3, red) } 
>	C == { (David, Jun 1}, (Mary, Aug 2), (Bill, Feb 5) }
•	The set of all relations over sets S, T is indicated by S ´ T  
>	(Note S ´ T is equivalent to R (S x T).)
•	Examples:
A: N ´ N      B: N ´ Color     C: Person ´ Date
Relations (2)
•	The domain of a relation is the set of first elements. (“dom”)
•	The range of a relation is the set of second elements. (“ran”)
•	Examples:
A == { (1,1), (1,2), (2,2) } 
		dom A = { 1, 2 } and ran A =  { 1, 2 }
even though A  Œ  N ´ N 
B == { (2, red), (5, blue), (3, red) } 
		dom B = { 2,3,5 } and ran B = { red, blue } 
C == { (David, Jun 1}, {Mary, Aug 2}, {Bill, Feb 5) }
		dom C = { David, Mary, Bill}
		ran C =  { Jun 1, Aug 2, Feb 5 } 
Functions
•	A function is a relation such that no two distinct pairs contain the same first element.
•	Examples:
	B == { (2, red), (5, blue), (3, red) } 
	C == { (David, Jun 1}, {Mary, Aug 2}, {Bill, Feb 5) }
No:
	A == { (1,1), (1,2), (2,2) }

Some special cases
Suppose f: A ´ B
1. f is a function defined for all values of A
we say f is a “total” function, and write A Æ B
2. f is a function defined for some values of A
we say f is a “partial” function, and write A Æ B
3. f is a function defined for a finite set of values of A
we say f is a “finite” function, and write A Æ B
4. f is a function for which no element in ran(f) is  associated with more than one element in dom(f)
we say f is a “one-to-one”  or “injective” function, and write A Æ B
5. f is a function whose range is B
we say f is an “onto” or “surjective” function, and write     A Æ B
6. f is both one-to-one and onto
we say f is a “bijection” function, and write A Æ B

Special Cases (2)
Relations/Functions as Sets
•	Since relations are just sets (of pairs) we can apply set operators to them.
•	Example: 
>	R1 = {(1,red), (2,blue)}
>	R2 = {(3,green), (2,blue)}
>	R1 »  R2 = {(1,red), (2,blue), (3,green)}
>	# R1 = 2
Relational Composition
•	If the range of one relation is the domain of another can form the composition (R1;R2)
Overwriting
•	Frequently we will want to change the value of a function for one or more values
•	The overwriting operator does this:
•	Example: 
>	f = {(1,red), (2,blue), (3,green)}
>	g = {(1,pink), (4,mauve)}
>	f ≈ g = {(1,pink), (2,blue), (3,green), (4,mauve) }
Other Operators
•	There is a rich library of other auxiliary definitions.
•	We’ll be encountering many as we proceed through the class
•	Some examples:
>	N, the set of natural numbers
>	N1, the set of positive natural numbers
>	.., the "between" operator: 2..5= {2,3,4,5}
Last Slide
More Functions
•	Partial versus total functions
•	Example:  
>	sqroot is a partial function from N to N
>	square is a total function from N to N
•	One-to-one (injective) functions.
•	Onto (surjective) functions
•	Bijection (1-1, onto)
•	Finite functions
Fancy Function Symbols
•	A number of special symbols have been defined for relations and functions:
>	relations		A ´ B
>	total functions	A Æ B
>	partial functions 	A Æ B
>	finite functions 	A Æ B
>	onto functions 	A Æ B
>	1-1 functions 		A Æ B
>	bijection 		A Æ B
and combinations of these