Processing math: 89%
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

13.1: The Language of Sets and Functions

( \newcommand{\kernel}{\mathrm{null}\,}\)

All of mathematics can be seen as the study of relations between collections of objects by rigorous rational arguments. More often than not the patterns in those collections and their relations are more important than the nature of the objects themselves. The power of mathematics has a lot to do with bringing patterns to the forefront and abstracting from the “real” nature if the objects. In mathematics, the collections are usually called sets and the objects are called the elements of the set. Functions are the most common type of relation between sets and their elements and the primary objects of study in Analysis are functions having to do with the set of real numbers. It is therefore important to develop a good understanding of sets and functions and to know the vocabulary used to define sets and functions and to discuss their properties.

B.1 Sets

A set is an unordered collection of distinct objects, which we call its elements. A set is uniquely determined by its elements. If an object a is an element of a set A, we write aA, and say that a belongs to A or that A contains a. The negation of this statement is written as aA, i.e., a is not an element of A. Note that both statements cannot be true at the same time

If A and B are sets, they are identical (this means one and the same set), which we write as A=B, if they have exactly the same elements. In other words A=B if and only if forall aA we have aB, and for all bB we have bA. Equivalently, AB if and only if there is a difference in their elements: there exists aA such that aB or there exists bB such that bA.

Example B.1.1. We start with the simplest examples of sets.

  1. The empty set (a.k.a. the null set), is what it sounds like: the set with no elements. We usually denote it by or sometimes by { }. The empty set, , is uniquely determined by the property that for all x we have x. Clearly, there is exactly one empty set.
  2. Next up are the singletons. A singleton is a set with exactly one element. If that element is x we often write the singleton containing x as {x}. In spoken language, ‘the singleton x’ actually means the set {x} and should always be distinguished from the element x:x {x}. A set can be an element of another set but no set is an element of itself (more precisely, we adopt this as an axiom). E.g., {{x}} is the singleton of which the unique element is the singleton {x}. In particular we also have {x}{{x}}.
  3. One standard way of denoting sets is by listing its elements. E.g., the set {α,β,γ} contains the first three lower case Greek letters. The set is completely determined by what is in the list. The order in which the elements are listed is irrelevant. So, we have {α,γ,β}={γ,β,α}={α,β,γ}, etc. Since a set cannot contain the same element twice (elements are distinct) the only reasonable meaning of something like {α,β,α,γ} is that it is the same as {α,β,γ}. Since x{x},{x,{x}} is a set with two elements. Anything can be considered as an element of a set and there is not any kind of relation is required of the elements in a set. E.g., the word ‘apple’ and the element uranium and the planet Pluto can be the three elements of a set. There is no restriction on the number of different sets a given element can belong to, except for the rule that a set cannot be an element of itself.
  4. The number of elements in a set may be infinite. E.g., Z,R, and C, denote the sets of all integer, real, and complex numbers, respectively. It is not required that we can list all elements.

When introducing a new set (new for the purpose of the discussion at hand) it is crucial to define it unambiguously. It is not required that from a given definition of a set A, it is easy to determine what the elements of A are, or even how many there are, but it should be clear that, in principle, there is unique and unambiguous answer to each question of the form “is x an element of A?”. There are several common ways to define sets. Here are a few examples.

Example B.1.2.
1. The simplest way is a generalization of the list notation to infinite lists that can be described by a pattern. E.g., the set of positive integers N={1,2,3,}. The list can be allowed to be bi-directional, as in the set of all integers Z={,2,1,0,1,2,}.
Note the use of triple dots to indicate the continuation of the list.
2. The so-called set builder notation gives more options to describe the membership of a set. E.g., the set of all even integers, often denote by 2Z, is defined by

2Z={2a | aZ}.

Instead of the vertical bar, |, a colon, :, is also commonly used. For example, the open interval of the real numbers strictly between 0 and 1 is defined by

(0,1)={xR:0<x<1}.

B.2 Subset, union, intersection, and Cartesian product

Definition B.2.1. Let A and B be sets. B is a subset of A, denoted by BA, if and only if for all bB we have bA. If BA and BA, we say that B is a proper subset of A.

If BA, one also says that B is contained in A, or that A contains B, which is sometimes denoted by AB. The relation is called inclusion. If B is a proper subset of A the inclusion is said to be strict. To emphasize that an inclusion is not necessarily strict, the notation BA can be used but note that its mathematical meaning is identical to BA. Strict inclusion is sometimes denoted by BA, but this is less common.

Example B.2.2. The following relations between sets are easy to verify:

  1. We have NZQRC, and all these inclusions are strict.
  2. For any set A, we have A, and AA.
  3. (0,1](0,2).
  4. For 0<ab,[a,a][b,b]. The inclusion is strict if a<b.

In addition to constructing sets directly, sets can also be obtained from other sets by a number of standard operations. The following definition introduces the basic operations of taken the union, intersection, and difference of sets.

Definition B.2.3. Let A and B be sets. Then

  1. The union of A and B, denoted by AB, is defined by AB={x | xA or xB}.
  2. The intersection of A and B, denoted by AB, is defined by AB={x | xA and xB}.
  3. The set difference of B from A, denoted by AB, is defined by AB={x | xA and xB}.

Often, the context provides a ‘universe’ of all possible elements pertinent to a given discussion. Suppose, we have given such a set of ‘all’ elements and let us call it U. Then, the complement of a set A, denoted by Ac , is defined as Ac=UA. In the following theorem the existence of a universe U is tacitly assumed.

Theorem B.2.4. Let A,B, and C be sets. Then

  1. (distributivity) A(BC)=(AB)(AC) and A(BC)=(AB)(AC).
  2. (De Morgan’s Laws) (AB)c=AcBc and (AB)c=AcBc.
  3. (relative complements) A(BC)=(AB)(AC) and A(BC)=(AB)(AC).

To familiarize your self with the basic properties of sets and the basic operations if sets, it is a good exercise to write proofs for the three properties stated in the theorem.

The so-called Cartesian product of sets is a powerful and ubiquitous method to construct new sets out of old ones.

Definition B.2.5. Let A and B be sets. Then the Cartesian product of A and B, denoted by A×B, is the set of all ordered pairs (a,b), with aA and bB. In other words,

A×B={(a,b) | aA,bB}.

An important example of this construction is the Euclidean plane R2=R×R. It is not an accident that x and y in the pair (x,y) are called the Cartesian coordinates of the point (x,y) in the plane.

B.3 Relations

In this section we introduce two important types of relations: order relations and equivalence relations. A relation R between elements of a set A and elements of a set B is a subset of their Cartesian product: RA×B. When A=B, we also call R simply a relation on A.

Let A be a set and R a relation on A. Then,

  • R is called reflexive if for all aA,(a,a)R.
  • R is called symmetric if for all a,bA, if (a,b)R then (b,a)R.
  • R is called antisymmetric if for all a,bA such that (a,b)R and (b,a)R,a=b.
  • R is called transitive if for all a,b,cA such (a,b)R and (b,c)R, we have (a,c)R.

Definition B.3.1. Let R be a relation on a set A. R is an order relation if R is reflexive, antisymmetric, and transitive. R is an equivalence relation if R is reflexive, symmetric, and transitive.

The notion of subset is an example of an order relation. To see this, first define the power set of a set A as the set of all its subsets. It is often denoted by P(A). So, for any set A,P(A)={B:BA}. The, the inclusion relation is defined as the relation R by setting

R={(B,C)P(A)×P(A) | BC}

Important relations, such as the subset relation, are given a convenient notation of the form a<symbol>b, to denote (a,b)R. The symbol for the inclusion relation is .

Proposition B.3.2. Inclusion is an order relation. Explicitly,

  1. (reflexive) For all BP(A),BB.
  2. (antisymmetric) For all B,CP(A), if BC and CB, then B=C.
  3. (transitive) For all B,C,DP(A), if BC and CD, then BD.

Write a proof of this proposition as an exercise.

For any relation RA×B, the inverse relation, R1B×A, is defined by

R1={(b,a)B×A | (a,b)R}.

B.4 Functions

Let A and B be sets. A function with domain A and codomain B, denoted by f:AB, is relation between the elements of A and B satisfying the properties: for all aA, there is a unique bB such that (a,b)f. The symbol used to denote a function as a relation is an arrow: (a,b)f is written as ab (often also ab). It is not necessary, and a bit cumbersome, to remind ourselves that functions are a special kind of relation and a more convenient notation is used all the time: f(a)=b. If f is a function we then have, by definition, f(a)=b and f(a)=c implies b=c. In other words, for each aA, there is exactly one bB such that f(a)=b. b is called the image of a under f . When A and B are sets of numbers, a is sometimes referred to as the argument of the function and b=f(a) is often referred to as the value of f in a.

The requirement that there is an image bB for all aA is sometimes relaxed in the sense that the domain of the function is a, sometimes not explicitly specified, subset of A. It important to remember, however, that a function is not properly defined unless we have also given its domain.

When we consider the graph of a function, we are relying on the definition of a function as a relation. The graph G of a function f:AB is the subset of A×B defined by

G={(a,f(a)) | aA}.

The range of a function f:AB, denoted by range(f), or also f(A), is the subset of its codomain consisting of all bB that are the image of some aA:

range(f)={bB |  there exists aA such that f(a)=b}.

The pre-image of bB is the subset of all aA that have b as their image. This subset if often denoted by f1(b).

f1(b)={aA | f(a)=b}.

Note that f1(b)= if and only if b \in B \setminus range (f ).

Functions of various kinds are ubiquitous in mathematics and a large vocabulary has developed, some of which is redundant. The term map is often used as an alternative for function and when the domain and codomain coincide the term transformation is often used instead of function. There is large number of terms for functions in particular context with special properties. The three most basic properties are given in the following definition.

Definition B.4.1. Let f : A \rightarrow B be a function. Then we call f

  1. injective (f is an injection) if f (a) = f (b) implies a = b. In other words, no two elements of the domain have the same image. An injective function is also called one-to-one.
  2. surjective (f is a surjection) if range (f ) = B. In other words, each b \in B is the image of at least one a \in A. Such a function is also called onto.
  3. bijective (f is a bijection) if f is both injective and surjective, i.e., one-to-one and onto. This means that f gives a one-to-one correspondence between all elements of A and all elements of B.

Let f : A \rightarrow B and g : B \rightarrow C be two functions so that the codomain of f coincides with the domain of g. Then, the compositiong after f ’, denoted by g \circ f , is the function g \circ f : A \rightarrow C, defined by a \mapsto g(f (a)).

For every set A, we define the identity map, which we will denote here by {\rm{id}}_A or {\rm{id}} for short. {\rm{id}}_A : A \rightarrow A is defined by {\rm{id}}_A (a) = a for all a \in A. Clearly, {\rm{id}}_A is a bijection.

If f is a bijection, it is invertible, i.e., the inverse relation is also a function, denoted by f^{ -1} . It is the unique bijection B \rightarrow A such that f^{-1} \circ f = {\rm{id}}_A and f \circ f^{-1 }= {\rm{id}}_B .

Proposition B.4.2. Let f : A \rightarrow B and g : B \rightarrow C be bijections. Then, their composition g \circ f is a bijection and

(g \circ f )^{-1} = f^{ -1} \circ g^{ -1} .

Prove this proposition as an exercise.


This page titled 13.1: The Language of Sets and Functions is shared under a not declared license and was authored, remixed, and/or curated by Isaiah Lankham, Bruno Nachtergaele, & Anne Schilling.

Support Center

How can we help?