Relations, cartesian product of sets and ordered pair

Question

I don’t understand these terms. They came up in a math class the teacher rushed through.

Can you illustrate these terms with examples? I’m not really looking for an in-depth understanding of these (I don’t have much background) but only surface-level knowledge of what these even mean.

I’ll mention some things I noted in class to give you an idea of the level I’m supposed to learn this to:

Cartesian product of sets: For two sets A and B, the set of ordered pairs where the first element comes from A and the second from B. The teacher proceeded to illustrate this with an example and said that order matters, A cross B wouldn’t be the same as B cross A.

Relations: These are defined between sets. “For a relation defined between two sets A and B where A has p elements and B has q elements, tr mumber of elements in the set A cross B are pq. A relation is a subset of the cartesian product A cross B. Hence, the no. of relations possible between A and B are 2^pq.” [I quoted my teacher exactly, I don’t understand this at all]

Answer 1

To understand a Cartesian product, let's say you flip a coin twice, and you want to describe all the possible outcomes. Consider getting heads on the first flip and tails on the second as a different outcome from getting tails on the first and heads on the second. This is exactly what a Cartesian product tries to capture. So if $A = \{$ heads, tails $\}$. Then the ordered pairs (heads, tails) and (tails, heads) in $A \times A$ are not the same.

More generally, suppose you flip two coins. The sides of the first one are labelled heads and tails, but the sides of the second are labelled red and blue (because why not). Then you want the ordered pair (heads, blue) to reflect the order in which you flip the coins. So if $B = \{$ red, blue $\}$, then $A \times B$ and $B \times A$ are not the same.

A relation is just a set of ordered pairs. Using the same example, suppose you don't care about outcomes in $A \times B$ where the second coin flips to blue. Then you only consider the outcomes (heads, red) and (tails, red). Of course you can consider any possible subset of $A \times B$ as the only outcomes you care about.

Then it is a standard result that if $|A| = p$, $|B| = q$, then $|A \times B| = pq$, and the number of subsets of $A \times B$ (i.e. the number of possible relations) is $2^{pq}$. I hope this helps!

Answer 2

Welcome to MSE!

The notion of ordered pair is crucial if you want to consider cartesian product and relation.

1) Given two elements $a,b$ of some set. The ordered pair of $a,b$ is written as $(a,b)$. What you need to know is that if you have two ordered pairs, $(a,b)$ and $(c,d)$, then they are equal, i.e., $(a,b)=(c,d)$, if and only if they coincide component-wise, i.e., $a=c$ and $b=d$. Thus $(1,2)\ne (1,3)$ since they do not coincide in the 2nd component.

2) Given two sets $A,B$. The cartesian product $A\times B$ is the set of all ordered pairs $(a,b)$, where $a\in A$ and $b\in B$. Thus if $A=\{0,1\}$ and $B=\{a,b\}$, then $A\times B = \{(0,a),(0,b),(1,a),(1,b)\}$.

3) A relation $R$ from $A$ to $B$ is a subset of $A\times B$, i.e., $R\subseteq A\times B$. In the above example, $R=\emptyset$ (empty set), $R=\{(0,a)\}$, $R=\{(0,a),(1,b)\}$ or $R=A\times B$ are some possibilities.

Hope it helps!

Answer 3

Cartesian product of sets: For two sets A and B, the set of ordered pairs where the first element comes from A and the second from B. The teacher proceeded to illustrate this with an example and said that order matters, A cross B wouldn’t be the same as B cross A.

In short, $A\times B=\{(x,y):x\in A, y\in B\}$, $B\times A=\{(y,x):x\in A, y\in B\}$, so generally $A\times B\neq B\times A$,... unless $A=B$ or at least one of them is the empty set.

Relations: These are defined between sets. “For a relation defined between two sets A and B where A has p elements and B has q elements, tr mumber of elements in the set A cross B are pq. A relation is a subset of the cartesian product A cross B. Hence, the no. of relations possible between A and B are 2^pq.” [I quoted my teacher exactly, I don’t understand this at all]

If $\lvert A\rvert = p$ and $\lvert B\rvert=q$ then $\lvert A\times B\rvert=pq$, basically because $A\times B$ is formed by taking each of the $p$ elements in $A$ and forming pairs with each of the $q$ elements in $B$ -- thus there will be $p\cdot q$ pairs in $A\times B$.

Okay, for any element $x$ of $A$ and element $y$ of $B$, we write $x$ is $R$-related to $y$, as $(x,y)\in R$.   Since we are only concerned with how elements of $A$ related to elements of $B$, then the relation $R$ will contain some of the elements of the Cartessian product $A\times B$, and nothing that is not.   Hence such a relation $R$ will be a subset of $A\times B$ (we write $R\subseteq A\times B$).

You should be aware that there are $2^n$ subsets of any set of size $n$.   Thus there are $2^{pq}$ ways we might we select elements of $A\times B$ to construct such a relation.

(A subset of a set of $n$ elements may be formed by choosing whether to include or exclude each of the $n$ elements in turn: that is by making $n$ independent choices from $2$ options, and there are $2^n$ distinct ways to perform that task.)

So there are $2^{\lvert A\times B\rvert}$ distinct ways to form relations from set $A$ to set $B$.