Introduction to Sets

Definition...?

◼
  • “Set” is the word in English with the most number of definitions. Nevertheless it is one of the things that takes mathematicians the longest time to define. As such we shall think of a set as an orderless collection of non-repeating mathematical objects, called its members or elements.
    • ◼
  • To indicate that an element x is a member of A we say that x is in A(or x belongs to A), and write x∈A in symbols.
    • ◼
  • To indicate that an element x is not in A we write x∉A.
    • ◼
  • We say that two sets are equal if they have the same elements. That is, A=B if and only if every a∈A is an element of B and every b∈B is an element of A.
    • ◼
  • It is common to denote sets using curly braces {, } on top of this there are also two main ways of denote them.
    • ◼
  • By listing all the elements that belong to the set. We call this explicit notation,
    • ◼
  • For example {Keno, Ope, Rob}
    • ◼
  • In our informal definition of sets above by orderless we mean that the order in which the elements are listed is not important to us so for example {1,2,3} = {3,2,1} ={2,3,1}
    • ◼
  • In our informal definition of sets above by non-repeating we mean that the number of times in which an element appears in a set is not important to us, and will count only as one. so for example {1,2}={1,2,2} = {1,1,1,2} ={1,1,1,2,2}.
    • ◼
  • or by listing a property that all elements of the set satisfies, and no other elements besides those in the set satisfy. We call this implicit notation.
    • ◼
  • For example the set of people who are Kibo founders.
    • ◼
  • WARNING: Misuse of implicit notation may sometimes falsely lead to constructing things that are not necessarily sets.
    • ◼
  • Suppose we could have a set S that is the set of sets that do not belong to themselves. We can then ask whether or not S belongs to S. If it does, then S is a set that belongs to itself so it is not a set that does not belong to itself, hence it is not in S, which gives us a contradiction. If S does not belong to itself, then by definition of S it does, arriving once more to a contradiction. This conundrum is often referred to as Russell’s Paradox.Thus the only explanation is that S itself is not a set.
    • ◼
  • This is an interesting concept that may be slightly hard to grasp the first time we run into it, but for the most part all the collections of mathematical objects that we are going to encounter during the Mathematical Thinking course are actually sets.
    • ◼
  • There is a completely formal study of sets that goes beyond the scope of this class but for the interested reader we will add some notes at the end that briefly scrape the topic.
    • ◼
  • IMPORTANT: To avoid such issues as mentioned above we will always assume that we are working in something called a Universal Set. This Universal Set will vary depending on context. For example, it can be the set of all people, or it can be a specific set of numbers. In the case of abstract sets with no context we will assume the universal set is just a set .
    • ◼
  • Thus whenever we are denoting sets in implicit form we would write
    ​{x∈: x satisfies a specific property}.
    • ◼
  • As such we should have said before {x∈ Set of People: x is a founder of Kibo}.
    • https://youtu.be/cLUugbTBJPc

    Subsets and Power Set

    ◼
  • The empty set is a set that contains no elements. We usually denote it with just the curly braces with no elements inside {} but also with the symbol ∅.
    • ◼
  • A subset of a set is a set whose elements belong to the original set, but does not necessarily contain all elements of the original set. We sometimes write A⊆B to denote that A is a subset of B. We sometimes use the notation A⊂B to denote that A is a subset of B but is not equal to B.
    • ◼
  • {Keno},{Ope},{Rob},{Keno,Ope},{Keno,Rob},{Ope,Rob},{Keno,Ope,Rob}, and {}, are all the subsets of the set {Keno,Ope,Rob}.
    • ◼
  • Note that the empty set is a subset of every set.
    • ◼
  • Given a set S. The set of subsets of S is called the power set of S.
    • ◼
  • The set {{Keno},{Ope},{Rob},{Keno,Ope},{Keno,Rob},{Ope,Rob},{Keno,Ope,Rob}, ∅} is the power set of {Keno, Ope, Rob}
    • ◼
  • How many subsets does a set of size n have?

    • Singleton

    ◼
  • It is important that we understand the distinction between the element x and the set that contains only the element x, namely {x}.
    • ◼
  • Notice how in our discussion above we had Keno, as an element of the set {Keno, Ope, Rob} but also the set {Keno} as an element of the power set of {keno, Ope, Rob}.
    • ◼
  • A set with just one element in it, such as {x} is called a singleton while the element x itself need not be a set.

    • Sets as elements

    ◼
  • Even though we make a distinction between {x} and x. It could well happen that the elements of a set are sets themselves.
    • ◼
  • An example of this occurrence is the Power Set, which is a set of sets.
    • ◼
  • Note that {1, {2,3}} this set has 2 elements.

    • Special Sets of Numbers

    ◼
  • There are several well known sets of numbers. We will give an informal definition to them here.
    • 1
    .
    The set of Natural numbers, denoted by the double struck letter N ( ). These are what were originally considered counting numbers like 1,2,3,4,... etc. There is no universal consensus on whether 0 belongs or not to this set, but for the purpose of this class we will assume that it does.
    1
    .
    1
    .
    Some would argue that 0 is not natural, and call the set with 0 the set of whole numbers.
    2
    .
    The set of Integer numbers, denoted by the double struck letter Z () for zal. This is the set of Natural numbers with its negatives. {0,1,-1,2,-2,...}
    3
    .
    The set of Rational numbers, denoted by the double struck letter Q () for quotient. This is the set of numbers that can be expressed with fractions of integers, such as 1/2, 0.25, 1/3.
    4
    .
    The set of Real numbers, denoted by the double struck letter R (). This set contains all the numbers in the so-called number line.
    5
    .
    The set of Complex numbers, denoted by the double struck letter C (). Starting with
    =
    -1
    this is the set of numbers of the form
    a+b
    where
    a
    and
    b
    are real numbers.

    Set operations

    ◼
  • There are a few ways in which we can construct sets from other sets.
    • ◼
  • For the purpose of this subsection we will have that A, B, and C are sets

    • Union

    ◼
  • The union of A and B, denoted by A⋃B is the set of elements that belong to either A or B.
    • ◼
  • In symbols we would write A⋃B = {x∈: x∈A or x∈B}
    • ◼
  • Examples:
    • ◼
  • If A={1,2,3} and B={2,3,4}, then A⋃B={1,2,3,4}
    • ◼
  • If A={x∈: x is even} and B={x∈: x is odd} then A⋃B=

    • Intersection

    ◼
  • The intersection of A and B, denoted by A⋂B, is the set of elements that belong to both A and B.
    • ◼
  • In symbols we would write A⋂B={x∈: x∈A and x∈B}.
    • ◼
  • Examples:
    • ◼
  • If A={1,2,3} and B={2,3,4}, then A⋂B={2,3}
    • ◼
  • If A={x∈: x is even} and B={x∈: x is odd} then A⋂B=∅
    • ◼
  • We say that two sets A and B are disjoint if their intersection is the empty set.
    • ◼
  • So looking at the examples above , {x∈: x is even} and {x∈: x is odd} are disjoint.

    • Set Difference

    ◼
  • The set difference of A and B, denoted by A\B, is the set of elements that are in A but are not in B.
    • ◼
  • In symbols we would write A\B={x∈: x∈A and x∉B}.
    • ◼
  • Examples
    • ◼
  • If A={1,2,3} and B={2,3,4}, then A\B={1}
    • ◼
  • If A={1,2,3} and B={2,3,4}, then B\A={4}
    • ◼
  • If A={x∈: x is even} and B={x∈: x is odd} then A\B=A
    • ◼
  • If A={x∈: x is even} and B={x∈: x is odd} then A\B=B
    • ◼
  • Notice how the set difference is not symmetric.

    • Cartesian Product

    ◼
  • The Cartesian product of A and B, also known as their cross product, denoted by AB is the set of ordered pairs where the first component belongs to A, and the second component belongs to B.
    • ◼
  • In symbols we would write AB={(a,b)∈: a∈A and b∈B}.
    • ◼
  • Examples
    • ◼
  • If A={1,2,3} and B={2,3,4}, then
    ​AB={(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,2),(3,3),(3,4)}
    • ◼
  • If A={1,2,3} and B={2,3,4}, then
    ​AB={(2,1),(2,2),(2,3),(3,1),(3,2),(3,3),(4,1),(4,2),(4,3)}
    • ◼
  • If A={x∈: x is even} and B={x∈: x is odd} then AB={(a,b)∈: a is even and b is odd}
    • ◼
  • Notice that the Cartesian product is also not symmetric.
    • ◼
  • Sometimes we abbreviate the Cartesian product of A with itself as
    2
    A
    .
    • ◼
  • Even though technically speaking the elements of (AB)C should be elements of the form ((a,b),c) where a∈A, b∈B, and c∈C, the extra parenthesis is cumbersome so we use just (a,b,c).
    • https://youtu.be/9ZL5BBesp40

    Cardinality

    Definition

    ◼
  • The cardinality of a set can be thought of as the size of a set. I say thought of, since when we think of sets as lists {1,2,2} is technically the same as {1,2} one with size 3 and the other with size 2. By cardinality we mean the size of the set when no repetition is allowed.
    • ◼
  • We usually denote the cardinality of A as |A|.
    • ◼
  • Examples
    • ◼
  • |{a,b,c}|=3
    • ◼
  • |{a,a,a,b}|=2
    • ◼
  • |{}|=0
    • ◼
  • We say that a set is finite if its cardinality is a natural number.
    • ◼
  • In symbols, A is finite if |A|∈
    • ◼
  • A set is called infinite if it is not finite.

    • On operations

    ◼
  • The cardinality of |A⋂B| is less than |A| and less than |B|.
    • ◼
  • The cardinality of |A⋃B| is greater than |A| and greater than |B|, but not greater than the sum |A|+|B|.
    • ◼
  • The cardinality of |AB| = |A| x |B| that is the product of the cardinality of the two original sets A and B.

    • Extra Notes

    Infinite sets

    ◼
  • Infinite sets still have cardinality. We will make this notion more formal once we cover functions but it will interest the reader to know that ||=||=||. This may seem counter intuitive at first, but there is a formal reason we will explain later.
    • ◼
  • The above may lead the reader to conclude that all infinite sets have the same cardinality. In fact we have that || and || are different. We will look into an argument about this in the classes about functions.

    • Successor Function

    ◼
  • Given a set A the successor of A is the set A⋃{A}.
    • ◼
  • The successor of the empty set is {∅} which has 1 element
    The successor of the successor of the empty set is {∅,{∅}}, which has 2 elements.
    The successor of the successor of the successor of the empty set is {∅,{∅},{∅,{∅}}}, which has 3 elements.
    • ◼
  • The construction above can be continued and it is the “set-theoretic” way of defining the natural numbers. So we could consider
    • ◼
  • 0 -> ∅
    • ◼
  • 1->{∅} ->{0}
    • ◼
  • 2->{0,1}
    • ◼
  • 3->{0,1,2}
    • ◼
  • ...
    • ◼
  • n = {x∈:x<n}
    • ◼
  • ...

    • ZFC

    ◼
  • There is a branch of Mathematics called Set Theory that considers every object to be a set.
    • ◼
  • There are some formal generally accepted axioms about sets. What follows are their names, and a paraphrasing of what the mean
    • 1
    .
    Extensionality
    1
    .
    1
    .
    “two sets are the same if they have the same elements”
    2
    .
    Regularity (foundation)
    2
    .
    1
    .
    “Every set contains an element which is disjoint to it.”
    3
    .
    Schema of Specification
    3
    .
    1
    .
    “Given any property and any set, there is set composed of the elements of the set that satisfy that property”
    4
    .
    Pairing
    4
    .
    1
    .
    “If we have to elements there is a set that contains both of them”
    5
    .
    Union
    5
    .
    1
    .
    “Given two sets their union is a set”
    6
    .
    Schema of Replacement
    6
    .
    1
    .
    “The image of any set under a function is also a set”
    7
    .
    Infinity
    7
    .
    1
    .
    “There is an infinite set, namely a set that contains all the natural numbers as constructed using the successor function starting from the empty set”
    8
    .
    Power Set
    8
    .
    1
    .
    “The collection of subsets of a set is a set”
    9
    .
    Choice
    9
    .
    1
    .
    “Given a set of sets, we can pick one element from each set”
    ◼
  • Axioms 1-8 are usually called Zermelo-Frankel, usually shortened to ZF. All axioms together are usually denoted by ZFC.
    • ◼
  • A more detailed exploration of this topic lies outside the scope of the class.