Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

1.1: Sets and Relations

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

1.1.1 The Integers

Kronecker once said, "God made the integers; all the rest is the work of man." Taking this as our starting point, we assume the existence of the set

Z={,3,2,1,0,1,2,3,}.

the set of integers. Moreover, we assume the properties of the operations of addition and multiplication of integers, along with other elementary properties such as the Fundamental Theorem of Arithmetic, that is, the statement that every integer may be factored into a product of prime numbers and this factorization is essentially unique.

1.1.2 Sets

We will take a naive view of sets: given any property p, we may determine a set by collecting together all objects which have property p. This may be done either by explicit enumeration, such as, p is the property of being one of a,b, or c, which creates the set {a,b,c}, or by stating the desired property, such as, p is the property of being a positive integer, which creates the set

Z+={1,2,3,4,}.

The notation xA indicates that x is an element of the set A. Given sets A and B, we say A is a subset of B, denoted AB, if from the fact that xA it necessarily follows that xB. We say sets A and B are equal if both AB and BA.

Given two sets A and B, we call the set

AB={x:xA or xB}

the union of A and B and the set

AB={x:xA and xB}

the intersection of A and B. We call the set

AB={x:xA,xB}

the difference of A and B.

More generally, if I is a set and {Aα:αI} is a collection of sets, one for each element of I, then we have the union

αIAα={x:xAα for some α}

and the intersection

αIAα={x:xAα for all α}.

Example 1.1.1

For example, if I={2,3,4,} and we let

A2={n:nZ+,n>1,n2m for any mZ+with m>1}

and, for any iI,i>2,

Ai={n:nAi1,nmi for any mZ+with m>1},

then iIAi is the set of prime numbers.

If A and B are both sets, we call the set

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

the cartesian product of A and B. If A=B, we write

A2=A×A.

Example 1.1.2

Z2={(m,n):mZ,nZ} is the set of all ordered pairs of integers.

1.1.3 Relations

Given two sets A and B, we call a subset R of A×B a relation. Given a relation R, we will write aRb, or simply ab if R is clear from the context, to indicate that (a,b)R.

Example 1.1.3

We say that an integer m divides and integer n if n=mi for some integer i. If we let

R={(m,n):mZ,nZ,m divides n},

then R is a relation. For example, 3R12.

Consider a set A and a relation RA2. For purposes of conciseness, we say simply that R is a relation on A. If R is such that aRa for every aA, we say R is reflexive; if R is such that bRa whenever aRb, we say R is symmetric; if aRb and bRc together imply aRc, we say R is transitive. We call a relation which is reflexive, symmetric, and transitive an equivalence relation.

Exercise 1.1.1

Show that the relation R on Z defined by mRn if m divides n is reflexive and transitive, but not symmetric.

Exercise 1.1.2

Show that the relation R on Z defined by mRn if mn is even is an equivalence relation.

Given an equivalence relation R on a set A and an element xA, we call

[x]={y:yA,yRx}

the equivalence class of x.

Exercise 1.1.3

Given an equivalence relation R on a set A, show that

a. [x][y] if and only if xRy

b. [x]=[y] if and only if xRy.

As a consequence of the previous exercise, the equivalence classes of an equivalence relation on a set A constitute a partition of A (that is, A may be written as the disjoint union of the equivalence classes).

Exercise 1.1.4

Find the equivalence classes for the equivalence relation in Exercise 1.1.2.


This page titled 1.1: Sets and Relations is shared under a CC BY-NC-SA 1.0 license and was authored, remixed, and/or curated by Dan Sloughter via source content that was edited to the style and standards of the LibreTexts platform.

Support Center

How can we help?