Graph View

Backlinks

The Library

Search

SearchSearch

Set Theory

Sep 25, 2024, 5 min read

  • A Set is defined as a collection of objects referred to as elements. Unless otherwise stated, the elements of a set are distinct.

    We denote an element as being an element of set using . Otherwise we denote non-membership as, .

    Notation: By convention, sets are notated with capital letters.

Subsets

  • A set is a subset of denoted if

    Likewise, we say is the superset of denoted .

  • Two sets are equal denoted if and only if and . Otherwise, they are unequal denoted

  • Two sets are equivalent if there exists a bijection that maps each element of to an element of .

  • A Proper Subset of denoted is defined so that and .

  • The Power Set of denoted is defined as the set of all subsets of .

  • The Universal Set is the set containing all elements including itself. It is denoted 1

  • The Null Set is the set containing no elements. It is denoted

Sizes of Sets

  • The Cardinality of a set denoted refers to the number of elements of the set.

  • The following are true about cardinalitieis

    • there exists a bijection .
    • there exists an injection and no bijection .
    • there exists a surjection and no bijection .

  • Cantor’s Theorem Given a set , there is no bijective mapping from to .

    Proof: Argue by contradiction Suppose such a mapping exists. Note that the elements of are subsets of . It is safe to assume that is surjective

    By construction, consider

    That is the set of all elements of which are not elements of their own mapped subset.

    Certainly and . Now suppose , which must exist since we have a supposed bijection.

    If , then .

    Which is a contradiction so our assumption that was surjective is false, and so there is no bijection from to .

  • A set is countable if there exists a bijection with the elements of the set with any subset of the natural numbers. More formally

    • A set is finite if it has a bijective mapping to a proper subset of the natural numbers. More formally . A set that is not finite is infinite
    • A set is countably infinite if there is a bijective mapping with the set of natural numbers so that

  • A set is uncountably infinite if there is no bijective mapping with the set of natural numbers so that

Set Operations

  • For each of the following, let and be sets.

  • The Cartesian Product of and is denoted is defined as the set of all ordered pairs from elements of with .

    If we have we denote it as .

    We can chain Cartesian Products to get ordered tuples

  • The intersection of two sets is defined as

    If we have a sequence of sets we define this as

    • Two sets are disjoint if .
    • A sequence of sets is pairwise disjoint if

  • The union of two sets is defined as

    If we have a sequence of sets we define this as

  • The difference denoted is defined as

  • The complement of set is denoted or and is defined as the set

    If we allow for the Universal Set, an alternative formulation is using

  • The symmetric difference of sets and is denoted and is defined as

Properties of Set Operations

  • For each of these, let be sets. The proof for each of these properties follows from properties of the corresponding logical operations

Commutativity

Associativity

  2. 2.

Distributivity

Identity

  1. $A\cup \emptyset =A$$

Complement

Idempotence

Domination

Absorption

De Morgan’s Laws

Involution

Complement Laws

Difference Properties

Miscellaneous

  • In a partially ordered set, not every two elements need to be comparable.

  • A chain is a subset where every two elements are comparable (that is, trichotomy holds so that one of holds)

  • An element is an upper bound of for partially ordered set if

  • An element of a partially ordered set is maximal if there is no such that .

  • Maximal Principle states the following. Let be a family of sets. If for each chain there exists a member of that contains each member of , then contains a maximal element.

  • Zorn’s Lemma If is a partially ordered set such that every chain in has an upper bound in , then has at least one maximal element.

  • Zorn’s Lemma and the Maximal Principle are equivalent

Topics

Links

Footnotes

  1. Not all formulations of Set Theory allow the formulation of the Universal Set because it gives rise to paradoxes. ↩