Discrete Mathematics Definitions

Whitworth Univeristy Dr. Schepens Discrete Mathematics Course

Subset

A ⊆ B ⇔ ∀ x, if x is in A then x is in B.

Proper Subset

A c B ⇔ A ⊆ B and Ǝ x in B such that x is not in A

Set Equality

A = B ⇔ A ⊆ B and B ⊆ A

Union

A u B, all elements are in at least one of A or B

Intersection

A n B, all elements are in both A and B

Difference

B - A, all elements are in B but not in A

Complement

A^c (the negation of A) or U - A, all elements are in U but not in A

DeMorgan’s Law for Sets

• (A n B)^c = A^c u B^c

• (A u B)^c = A^c n B^c

One to one

For all of x1, x2 in X, if f(x1) = f(x2) then x1 = x2

Onto

For all of y in Y, there exists an x in X such that f(x) = y

Reflexive

For all x in A, xRx

Symmetric

For all x, y in A, if xRy then yRx

Transitive

For all x, y, z in A, if xRy and yRz, then xRz

Equivalence Relation

symmetric, reflexive, and transitive

Connected Graph

For all vertices, v, w in V(G), there exists a walk from r to w