03 Relations and Functions Free Online FlashCards

What is a relation from $A$ to $B$?

A relation from a set $A$ to a set $B$ is a subset of the Cartesian product $A\times B$, so it consists of ordered pairs $(a,b)$ with $a\in A$ and $b\in B$.

Find the domain and range of $R=\{(1,a),(2,a),(2,b)\}$.

For $R=\{(1,a),(2,a),(2,b)\}$, the domain is $\{1,2\}$ and the range is $\{a,b\}$.

When is a relation reflexive?

A relation $R$ on $A$ is reflexive when every element is related to itself: $\forall a\in A,\ aRa$.

What does antisymmetric mean?

A relation $R$ is antisymmetric when $aRb$ and $bRa$ together imply $a=b$. It may also be symmetric, as equality demonstrates.

What three properties define an equivalence relation?

A relation is an equivalence relation exactly when it is reflexive, symmetric, and transitive.

What is the equivalence class $[a]$ modulo $n$?

The equivalence class of $a$ modulo $n$ is $[a]=\{x\in\mathbb Z:x\equiv a\pmod n\}$, containing all integers congruent to $a$ modulo $n$.

What properties define a partial order?

A partial order is a relation that is reflexive, antisymmetric, and transitive. A set equipped with one is called a partially ordered set, or poset.

Give an example of incomparable sets under $\subseteq$.

In $\mathcal P(\{1,2\})$, the sets $\{1\}$ and $\{2\}$ are incomparable because neither set is a subset of the other.

What condition makes a relation a function?

A function $f:A\to B$ assigns exactly one element of $B$ to each element of $A$. The set $A$ is the domain, and $B$ is the codomain.

When is a function injective?

A function is injective when distinct inputs have distinct outputs: $f(a_1)=f(a_2)\Rightarrow a_1=a_2$. It is also called one-to-one.

When is a function surjective?

A function $f:A\to B$ is surjective when every element of $B$ is the image of at least one element of $A$; equivalently, $f(A)=B$.

What is a bijection?

A bijection is both injective and surjective. Thus, every codomain element is the image of exactly one domain element.