The complement of a set A is the set of elements that are in the universe but not in A.

{x | x ∉ A}

[image]

[image]

[image]

The set of elements in (A or B) but not in (A and B)

[image] = {x | x∈A or x∈B and x∉(A and B)}

For every element of a set, that element is related to itself.

∀a∈A, aRa

(a, a)∈R

Find an a∈A such that a is not related to a.  Find a missing (a,a)

∃a∈A such that (a, a)∉R

For every element a in A, a is not related to itself.

∀a∈A, (a, a)∉R

Find an a in A such that aRa...  Find a member of the diagonal

∃a∈A | (a, a)∈R

If there is an (a, b)∈R, then (b, a)∈R ∀a, b∈A

The relation that occurs when you switch the ordering of the elements of a relation.

R^-1 = { (b, a) | (a, b)∈R }

The ordered pairs not R

[image] = { (a, b) | (a, b) ∉ R }

If R is an equivalence relation on A, an equivalence class of a in A is the set of elements that are related to a.  Written [a]

note: a is merely a representative of the equivalence  class, any other would work just as well

What is congruence modulo?

a[image]b (mod n)

a and b have the same remainder when divided by n

a - b = nz, z∈Z

Let A be any set.

The identity function, i_A:A→A, is the function such that i_A(a) = a.

The identity function is a bijection

if f:A→B

the inverse function, f^-1:B→A

such that f^-1(b)=a if f(a)=b

f^-1 is a bijection as well

Note:

f^-1(f(a)) = a

think:round trip for a

f(f^-1(b)) = b

If the codomain of g is the domain if f, then f composed with g takes the output of g and applies f to it.

f: A[image]B

g: C[image]A

f[image]g:C[image]B = f(g(x))

AKA greatest integer function

the floor function [x] or ⌊x⌋

maps ℝ to ℤ

and is the greatest integer ≤ x

⌊2.5⌋ = 2

⌊-2.5⌋ = -3

Defintion: summation

Identify: components of summation notation

The sum of terms in a sequence.

[image]

j: index of summation

a_j: j^th term, think f(j)

m: lower limit

n: upper limit

m, n ∈ ℤ

m≤n

Reflexive: A≅A since i_A:A[image]A is a bijection

Symmetric: if A≅B then B≅A ∀sets A,B

since A≅B, there is a f:A[image]B that is a bijection

then f^-1:B[image]A is a bijection

Transitive: if A≅B and B≅C, then A≅C ∀sets A,B,C

since A≅B, there is a f:A[image]B that is a bijection

and since B≅C, there is a f:B[image]C is a bijection

a. if f:A[image]B and g:B[image]C are both 1:1 then g[image]f is 1:1

b. if f:A[image]B and g:B[image]C are both onto, then g[image]f is onto

countable.

If the set is finite, its subsets are finite

If the set is infinite, there exists a bijection with P

countable.

The index and the set must be countable

A proof by contradiction:

Assume the reals are countably infinite and therefore can be enumerated (r₁, r₂, r₃, r₄, ...., r_n)

1.

r₁ = a₁.b₁₁b₁₂b₁₃b_14....

r₂ = a₂.b₂₁b₂₂b₂₃b_24....

r3 = a₃.b₃₁b₃₂b₃₃b_34....

r_n = a_n.b_n1b_n2b_n3b_n4....b_nn

a_i is the integer portion of r_i, a_i∈ℤ

b_ij is the j^th decimal place of a_i, b_ij∈{0, 1, 2, ..., 9}

2.

consider the the diagonal: b_ii

define a [image] = {0 if b_ii is 1, 2, 3, ..., 9; and 1 if b_ii is 0}

define [image]

3.

[image] is a real number but is not in the enumeration because:

[image] ≠ r₁; because [image]

[image] ≠ r₂; because [image]

and so on because we defined [image] to be different from b_ii, thus we have a contradiction and the reals cannot be enumerated

Use Cantor's diagonal but let a_i = 0.

Use Cantor's diagonal but let a_i = {x | x is in the interval} ie 1, 2, 3, 4

B is uncountably infinite.

Note: this does not mean that subsets of uncountably infinite sets are uncountably infinite. The set of integers is a subset of reals, and the cardinality of integers is aleph null.

What are 5 ways to prove an infinite set A has cardinality aleph null?

1. Prove there is a bijection between A and P

2. Show the subset can be enumerated and state the theorem.

3. Show A is a subset of a known aleph null set and state theorem.

4. Show A is a countable union of countable sets and state theorem.

5. Show A=SxT where S,T are countable and state theorem

What are 4 ways to show that an infinite set A is uncountably infinite?

1. Use Cantor's diagonal argument

2. Prove there is a bijection between A and R

3. Show a subset of A is uncountably infinite

4. Show A is the difference between an uncountably infinite set and a countably infinite set