# Definitions

## Subset

$A\subseteq B$

• $\{x\mid x\in A{\hbox{ then }}x\in B\}$

Subset means for all x, if x is in A then x is also in B.

## Proper Subset

$A\subset B$

• $\{x\mid x\in A{\hbox{ then }}x\in B{\hbox{ and }}A\neq B\}$

## Union

$\bigcup A$

• $\{x\mid x\in \bigcup A{\hbox{ iff }}y\in A{\hbox{ s.t. }}x\in y\}$

$A\cup B$

• $\{x\mid x\in A{\hbox{ or }}x\in B\}$

## Intersection

$\bigcap A$

• $\{x\mid {\hbox{for all }}a\in A,x\in a\}$

$A\cap B$

• $\{x\mid x\in A{\hbox{ and }}x\in B\}$

## Empty Set

$\emptyset$

• ${\hbox{There is a set }}A{\hbox{ s.t. }}\{x\mid x\notin A\}$

## Minus

$A-B$

• $\{x\mid x\in A{\hbox{ and }}x\notin B\}$

## Powerset

${\mathcal {P}}(A)$

• $\{x\mid x\subseteq A\}$

## Ordered Pair

$\langle a,b\rangle$

• $\{\{a\},\{a,b\}\}$

## Cartesian Product

$A\times B$

• $A\times B=\{x\mid x=\langle a,b\rangle {\hbox{ for some }}a\in A{\hbox{ and some }}b\in B\}$

or

• $\{\langle a,b\rangle \mid a\in A{\hbox{ and }}b\in B\}$

## Relation

A set of ordered pairs

### Domain

$\{x\mid {\hbox{ for some }}y,\langle x,y\rangle \in R\}$

### Range

$\{y\mid {\hbox{ for some }}x,\langle x,y\rangle \in R\}$

### Field

${\hbox{dom(}}R{\hbox{)}}\cup {\hbox{ran(}}R{\hbox{)}}$

## Equivalence Relations

• Reflexive: A binary relation R on A is reflexive iff for all a in A, <a, a> in R
• Symmetric: A rel R is symmetric iff for all a, b if <a, b> in R then <b, a> R
• Transitive: A relation R is transitive iff for all a, b, and c if <a, b> in R and <b, c> in R then <a, c> in R

## Partial Ordering

• Transitive and,
• Irreflexive: for all a, <a, a> not in R

### Trichotomy

Exactly one of the following holds

• x < y
• x = y
• y < x

# Proof Strategies

## If, then

Prove if x then y

Suppose x
...
...
so, y

Prove x iff y

suppose x
...
...
so, y
suppose y
...
...
so, x

Prove x = y

show x subset y
and
show y subset x

## Non-Equality

Prove x != y

x = {has p}
y = {has p}
a in x, but a not in y