Set Theory: Sets and Functions

Definitions of {}∈∉⊂⊆=.

Further definitions on , arbitrary, disjoint, pairwise disjoint. Shows how union and intersection are associative, commutative, and distributive. Defines difference, symmetric difference, complement. Shows the duality principle, leading to dual theorems.

Definitions of (real) function f on X, domain, range, mapping of M into N, image, preimage, image of A, preimage of B, map into, map onto, one-to-one, one-to-one correspondence, inverse of f.

Theorem 1

f1(AB)=f1(A)f1(B)

Theorem 2

f1(AB)=f1(A)f1(B)

Theorem 3

f(AB)=f(A)f(B)

Note f(AB)f(A)f(B). Also note that Theorems 1-3 hold for an arbitrary number of sets.

Definitions of decomposition or partition into classes, a is related to b by the (binary) relation R, equivalence relation, reflexitivity, symmetry, transitivity.

Theorem 4

M can be partitioned into classes by a relation R R is an equivalence relation on M.

Problems

  1. Show AB=A and AB=A A=B

    BA since AB=A and AB since AB=A. Hence, A=B

  2. Show (AB)BA

    Take A to be the empty set and B to be any non-empty set.

  3. Let A={2,4,...,2n,...} and B={3,6,...,3n,...}. Find AB and AB

    AB={6,12,...,6n,...}. AB={2,4,8,10,14,16,...}

  4. Prove that (AB)C=(AC)(BC) and AB=(AB)(AB)

    Step through using definitions, complements, idempotence, duality principle, distributivity, associativity, commutativity.

  5. Prove αAααBαα(AαBα)

    Evident once some thought has been applied.

  6. Let An be the set of all positive integers divisible by n. What are n=2An and n=2An?

    n=2An={2,3,4,...,n,...}
    n=2An=

  7. What are n=1[a+1n,b1n] and n=1(a1n,b+1n)?

    If ba>1 n=1[a+1n,b1n]=(a,b)
    If ba1 n=1[a+1n,b1n]=[b1,a+1]
    n=1(a1n,b+1n)=[a,b]

  8. Let Aα be the set of points lying on the curve y=1xα with 0<x<. What is α1Aα?

    (1,1)

  9. y=f(x)={x} (fractional part of x). Prove every closed interval of length one has the same image under f. What is this image? Is f one-to-one? What is the preimage of the interval 14y34? Partition the real line into classes of points with the same image.

    Simple enough.

  10. Given set M, let R be the set of all ordered pairs (a,a) with aM. Let aRb(a,b)R. Interpret R.

    Equality.

  11. Find a binary relation which is:

    1. Reflexive and symmetric, but not transitive.

    2. Reflexive, but neither symmetric nor transitive.

    3. Symmetric, but neither reflexive nor transitive.

    4. Transitive, but neither reflexive nor symmetric.

    Blood relative. Remembers name of (provided everybody knows their own name). Not equal to. Strictly greater than. (Credit to CoveredInChocolate for the first two answers.)