Cartesian squares and relations

-
This post was first published on WordPress at
https://explainingmaths.wordpress.com/2021/07/27/cartesian-squares-and-relations/

I'm continuing to transfer some selected posts from the Piazza forum for my Autumn 2020 first-year pure module Foundations of Pure Mathematics (FPM) to my two blogs (on WordPress and on Blogger).

Don't forget that videos from this module are available (complete sets of recordings from the 2014-15, 2018-19 and 2019-20 editions of FPM).

Here is a question and answer concerning Cartesian squares and relations.

Question

Hi, can someone please explain how are Cartesian squares and relations connected and why the number of relations on a finite set \(S\) is the same as the number of subsets of \(S \times S\)?

My answer

Hi,
The relevant lecture is Lecture 8, Cartesian Products and Relations. 
Let \(S\) be a set (usually non-empty). Then \(S \times S\) (the Cartesian square of \(S\)) is the set of all ordered pairs whose co-ordinates are both in \(S\), so \[S \times S = \{(x,y):x,y \in S\}\,.\] Now suppose that \(S\) is a non-empty, finite set with exactly \(n\) elements for some \(n \in \mathbb{N}\). With the usual notation, we have \(|S|=n\). Then \(|S \times S|=n^2\).
Now, suppose you want to form a subset, say \(M\), of \(S \times S\). Then, for each \((x,y)\in S \times S\), you have two choices: either \((x,y)\) is in \(M\) or it isn't. You can make this choice separately for each of the \(n^2\) points of \(S \times S\), and if you change even one decision, you change the subset \(M\). So there are exactly \(2^{n^2}\) possible subsets of \(S \times S\).
What about relations on \(S\)?  Suppose we want to define a relation \(R\) on \(S\). Then, for each ordered pair \((x,y) \in S \times S\), we have to decide whether \(x\,R\,y\) or not. We can make this choice separately for each of the \(n^2\) points of \(S \times S\), and if you change even one decision, you change the relation. Does that look familiar?
In fact, the Pure Mathematician's definition of a relation on \(S\) is just a subset of \(S \times S\). But this is like the abstract definition of a function: we usually work with some sort of practical rule instead of the abstract formulation. Still, there is certainly a bijection between relations on \(S\) and subsets of \(S \times S\): given a relation \(R\) on \(S\) you can define a corresponding subset \(M\) of \(S \times S\) by setting \[M=\{(x,y) \in S \times S: x\,R\,y\,\}.\] For the inverse function: given a subset \(M\) of \(S \times S\), you can define a corresponding relation \(R\) by \[x\,R\,y \Leftrightarrow (x,y) \in M\,.\] Whichever way you think about it, the number of relations on \(S\) is still \(2^{n^2}\).

If, instead, \(S\) is an infinite set, the bijection above still works (and this fits with the discussions in Lecture 8). But then if we start counting we are looking at cardinalities of infinite sets, and this is no longer in the FPM syllabus. (It was covered in Lectures 19 and 20 of the old syllabus, see for example the 2014 G11FPM lectures on YouTube.)

Best wishes,
Dr Feinstein

Comments

Post a Comment

Popular posts from this blog

Sums and integration against counting measure: Part I

-
For other posts in this series, see https://explaining-maths.blogspot.com/search?q=Sums+and+integration+against+counting+measure In case the MathJax mathematics below does not display properly in your browser, I have made a PDF of the main article available via my  WordPress blog  at  https://explainingmaths.files.wordpress.com/2023/08/sums-and-integration-against-counting-measure_-part-i.pdf Note added 30/8/23: I'm not quite sure when I started to say "integration against a measure". I'm not alone, but I think that "integration with respect to a measure" is a lot more common! However, I don't want to change the titles of my latest 10 blog posts, so I'll leave it as it is. I'll probably change back to "integration   with respect to a measure" in future though! It has been a while since I wrote a mathematical post! Here I thought I would say something about Measure and Integration which is relevant to my research. For these posts I as
Read more

Discussion of the proof that the uniform norm really is a norm

-
In response to a request on Piazza, I gave a detailed proof that the uniform really is a norm, including some comments and warnings on possible pitfalls along the way. Here (essentially) is what I said. Let’s have a look at \(\|\cdot\|_\infty\) on the bounded, real-valued functions on \([0,1]\) (but you can also work with bounded functions on any non-empty set you like, and the same proof will work). We define \(\ell_\infty([0,1]) = \{f: f \textrm{ is a bounded, real-valued function on }[0,1]\,\}\,,\) and this is the set/space we will look at. So we set \(Y=\ell_\infty([0,1])\). Then you can check for yourselves that \(Y\) really is a vector space over \(\mathbb{R}\) (using the usual "pointwise" operations for functions). Note that the zero element in this vector space is the constant function \(0\) (from \([0,1]\) to \(\mathbb{R}\)), which I'll denote by \(\mathbf{0}\) here for clarity. (We also used \(Z\) for this function in one of the exercises.) I'll first give
Read more

Revisiting liminf and limsup

-
This post is also available in PDF form from my WordPress Blog at  https://explainingmaths.wordpress.com/2023/09/01/revisiting-liminf-and-limsup/ My recent series of posts about Fatou's Lemma for sums was aimed primarily at mathematics students at 3rd-year undergraduate level or above. So I think I should write a post more suitable for first-year undergraduate students. So I'm going to have another look at the topic of $\liminf$ and $\limsup$ for bounded sequences of real numbers (though most of what I say can be generalised to sequences, or even nets, of extended real numbers). I said quite a lot about this in a previous post on my WordPress blog in the post https://explainingmaths.wordpress.com/2009/01/10/an-application-of-absorption-to-teaching-lim-inf-and-lim-sup/ and there was a lot of discussion in the comments below the post. In particular, in those comments, I discussed the $\liminf$ and the $\limsup$ of some examples of sequences $(x_n)$, including the following exam
Read more