[<< wikibooks] Set Theory/Review
Need help creating math symbols?


= Definitions =


== Subset ==

  
    
      
        A
        ⊆
        B
      
    
    {\displaystyle A\subseteq B}
  

  
    
      
        {
        x
        ∣
        x
        ∈
        A
        
          
             then 
          
        
        x
        ∈
        B
        }
      
    
    {\displaystyle \{x\mid x\in A{\hbox{ then }}x\in B\}}
  Subset means for all x, if x is in A then x is also in B.


== Proper Subset ==

  
    
      
        A
        ⊂
        B
      
    
    {\displaystyle A\subset B}
  

  
    
      
        {
        x
        ∣
        x
        ∈
        A
        
          
             then 
          
        
        x
        ∈
        B
        
          
             and 
          
        
        A
        ≠
        B
        }
      
    
    {\displaystyle \{x\mid x\in A{\hbox{ then }}x\in B{\hbox{ and }}A\neq B\}}
  


== Union ==

  
    
      
        ⋃
        A
      
    
    {\displaystyle \bigcup A}
  

  
    
      
        {
        x
        ∣
        x
        ∈
        ⋃
        A
        
          
             iff 
          
        
        y
        ∈
        A
        
          
             s.t. 
          
        
        x
        ∈
        y
        }
      
    
    {\displaystyle \{x\mid x\in \bigcup A{\hbox{ iff }}y\in A{\hbox{ s.t. }}x\in y\}}
  
  
    
      
        A
        ∪
        B
      
    
    {\displaystyle A\cup B}
  

  
    
      
        {
        x
        ∣
        x
        ∈
        A
        
          
             or 
          
        
        x
        ∈
        B
        }
      
    
    {\displaystyle \{x\mid x\in A{\hbox{ or }}x\in B\}}
  


== Intersection ==

  
    
      
        ⋂
        A
      
    
    {\displaystyle \bigcap A}
  

  
    
      
        {
        x
        ∣
        
          
            for all 
          
        
        a
        ∈
        A
        ,
        x
        ∈
        a
        }
      
    
    {\displaystyle \{x\mid {\hbox{for all }}a\in A,x\in a\}}
  
  
    
      
        A
        ∩
        B
      
    
    {\displaystyle A\cap B}
  

  
    
      
        {
        x
        ∣
        x
        ∈
        A
        
          
             and 
          
        
        x
        ∈
        B
        }
      
    
    {\displaystyle \{x\mid x\in A{\hbox{ and }}x\in B\}}
  


== Empty Set ==

  
    
      
        ∅
      
    
    {\displaystyle \emptyset }
  

  
    
      
        
          
            There is a set 
          
        
        A
        
          
             s.t. 
          
        
        {
        x
        ∣
        x
        ∉
        A
        }
      
    
    {\displaystyle {\hbox{There is a set }}A{\hbox{ s.t. }}\{x\mid x\notin A\}}
  


== Minus ==

  
    
      
        A
        −
        B
      
    
    {\displaystyle A-B}
  

  
    
      
        {
        x
        ∣
        x
        ∈
        A
        
          
             and 
          
        
        x
        ∉
        B
        }
      
    
    {\displaystyle \{x\mid x\in A{\hbox{ and }}x\notin B\}}
  


== Powerset ==

  
    
      
        
          
            P
          
        
        (
        A
        )
      
    
    {\displaystyle {\mathcal {P}}(A)}
  

  
    
      
        {
        x
        ∣
        x
        ⊆
        A
        }
      
    
    {\displaystyle \{x\mid x\subseteq A\}}
  


== Ordered Pair ==

  
    
      
        ⟨
        a
        ,
        b
        ⟩
      
    
    {\displaystyle \langle a,b\rangle }
  

  
    
      
        {
        {
        a
        }
        ,
        {
        a
        ,
        b
        }
        }
      
    
    {\displaystyle \{\{a\},\{a,b\}\}}
  


== Cartesian Product ==

  
    
      
        A
        ×
        B
      
    
    {\displaystyle A\times B}
  

  
    
      
        A
        ×
        B
        =
        {
        x
        ∣
        x
        =
        ⟨
        a
        ,
        b
        ⟩
        
          
             for some 
          
        
        a
        ∈
        A
        
          
             and some 
          
        
        b
        ∈
        B
        }
      
    
    {\displaystyle A\times B=\{x\mid x=\langle a,b\rangle {\hbox{ for some }}a\in A{\hbox{ and some }}b\in B\}}
  or

  
    
      
        {
        ⟨
        a
        ,
        b
        ⟩
        ∣
        a
        ∈
        A
        
          
             and 
          
        
        b
        ∈
        B
        }
      
    
    {\displaystyle \{\langle a,b\rangle \mid a\in A{\hbox{ and }}b\in B\}}
  


== Relation ==
A set of ordered pairs


=== Domain ===

  
    
      
        {
        x
        ∣
        
          
             for some 
          
        
        y
        ,
        ⟨
        x
        ,
        y
        ⟩
        ∈
        R
        }
      
    
    {\displaystyle \{x\mid {\hbox{ for some }}y,\langle x,y\rangle \in R\}}
  


=== Range ===

  
    
      
        {
        y
        ∣
        
          
             for some 
          
        
        x
        ,
        ⟨
        x
        ,
        y
        ⟩
        ∈
        R
        }
      
    
    {\displaystyle \{y\mid {\hbox{ for some }}x,\langle x,y\rangle \in R\}}
  


=== Field ===

  
    
      
        
          
            dom(
          
        
        R
        
          
            )
          
        
        ∪
        
          
            ran(
          
        
        R
        
          
            )
          
        
      
    
    {\displaystyle {\hbox{dom(}}R{\hbox{)}}\cup {\hbox{ran(}}R{\hbox{)}}}
  


== Equivalence Relations ==
Reflexive: A binary relation R on A is reflexive iff for all a in A,  in R
Symmetric: A rel R is symmetric iff for all a, b if  in R then  R
Transitive: A relation R is transitive iff for all a, b, and c if  in R and  in R then  in R


== Partial Ordering ==
Transitive and,
Irreflexive: for all a,  not in R


=== Trichotomy ===
Exactly one of the following holds

x < y
x = y
y < x


= Proof Strategies =


== If, then ==
Prove if x then y

Suppose x
...
...
so, y


== If and only If ==
Prove x iff y

suppose x
...
...
so, y

suppose y
...
...
so, x


== Equality ==
Prove x = y

show x subset y
and
show y subset x


== Non-Equality ==
Prove x != y

x = {has p}
y = {has p}
a in x, but a not in y