Dec 20

Order Relations

Order Relations

Nurlan Abiev

The present post we devote to order relations.  For preliminaries see our previous post  Equivalence Relations.  Recall that \mathbb{R} and \mathbb{N} are the sets of real and natural numbers respectively.

1 Partially ordered sets

Definition 1.  A partial order on a set X is a relation R \subseteq X\times X satisfying the following conditions for arbitrary x,y,z \in X:
i) xRx  (reflexivity);
ii) If xRy and yRx then y=x  (anti-symmetry);
iii) If xRy and yRz then xRz  (transitivity).

Respectively, given a set X with a chosen partial order R on it we call a partially ordered set.

We often denote a partial order R by the symbol \preceq  (do not confuse it with the usual symbol of inequality).  Moreover, we denote x\prec y if x\preceq y and x\ne y.

Remark 1. The corresponding  definitions of the concepts  partial order and  equivalence relation are distinguished  each from other only with respect to the symmetricity property (compare Definition 1 here with Definition 4 in Equivalence Relations).

Example 1. Examples of partially ordered sets:

i) We can define a partial order on any set X  assuming  a\preceq b if  a=b.

ii) Let  X be any given set. Assuming A\preceq B if A\subseteq B, where A,B  are subsets of X, we obtain a partial order on the power set 2^X (the set of all subsets of  X).

iii) Suppose that  n\preceq m means "n divides m", where n,m\in \mathbb{N}. Then \preceq is a partial order on \mathbb{N}.

iv) For x,y\in \mathbb{R} define x\preceq y if x\le y (x is smaller than y). Consequently we obtain a partial order on \mathbb{R}.

v) The following is a partial order on the set of all real valued functions defined on \mathbb{R}:
f\preceq g if  f(t)\le g(t) for all t \in [a,b].

vi) On \mathbb{R}^2 we can introduce a partial order putting (x_1,x_2)\preceq (x_2,y_2) if x_1\le x_2 and y_1\le y_2.

vii) The alphabetical order of letters a\preceq \cdots \preceq z  is a partial order on the English alphabet.

viii) The lexicographical order on the set of English words is a partial order.

Remark 2. Not every relation may be a partial order.

Example 2. On the set of positive integers  assume n\preceq m if any prime divisor of n also divides m. Such a relation is not a partial order, since it is not anti-symmetric.
Indeed we have true expressions  4\preceq 8 and 8\preceq 4. However they do not imply 4=8 at all.  Reflexivity and transitivity of this relation are obvious.

Definition 2. Assume that X is a partially ordered set and A\subseteq X. We call an element

i)   b\in A  the largest (greatest) in A, if  x \preceq b for every x\in A (b is greater than any other element of A).

ii) a\in A the smallest (least) in A, if a \preceq x for every x\in A (a is smaller than any other element of A).

iii) b\in A a maximal  in  A if x\in A and b \preceq x gives x=b (there is no element of A greater than b).

iv) a\in A  a  minimal in A if x\in A and x \preceq a gives x=a (there is no element of A smaller than a).

Picture 1

Remark 3. The words "largest" and "maximal" seem to us to be synonyms. Accordingly, we identify the words "smallest" and "minimal". Such an identification, of course, is legal on the set of real numbers, for instance. But in general, there is subtle difference between these concepts. To clarify them let's consider the following interesting example (see also  https://bit.ly/36v3ns8).

Example 3. Let X be a set of boxes. In X introduce the partial order accepting x\preceq y if a box y  contains a box x or if they are the same box. Then under the largest box we should mean the box which contains all other boxes, but to be maximal means the property of a box when it can not be contained in any other box.

Picture 2

Case 1. Assume now that X consists of 3 elements (boxes)  as shown in Picture 1. Obviously, the red box is the largest element and the green box is the smallest element.

Case 2. As another case consider X consisting of 4 elements (boxes) as in Picture 2. Clearly, there is no largest element. Red and purple boxes are  maximal elements. There is no smallest element. Green and purple boxes are minimal elements.

Case 3. Finally, let X be consisting of 4 elements (boxes) (Picture 3). There is no largest element. Red and purple boxes are maximal elements. The green box is the smallest element.

Picture 3

Example 4. On \mathbb{R}^2 introduce a partial order (x_1,x_2)\preceq (x_2,y_2) if x_1\le x_2 and y_1\le y_2. Consider the subset A of \mathbb{R}^2 defined by the inequalities 0\le x\le 1 and 0\le y \le 1-x.  Then observe that (0,0) is the smallest element in A, but A has no largest element.  There is an infinite family of maximal elements (x,1-x) in A but no distinct pair of them is comparable.

Remark 4. As follows from the definitions and examples above it is quite possible to have more than one maximal (respectively minimal) element of a set, even though the largest (respectively the smallest) element doesn't exist. By the property of anti-symmetry the largest and the smallest elements of a set are both unique (if they exist, of course). Moreover, the largest (respectively, the smallest) element is maximal (respectively, minimal). The maximal element is not always the largest. Likewise, the minimal element need not to be the smallest.

2 Linearly ordered sets. Well ordered sets

Finally, recall some useful definitions.

Definition 3.  A partially ordered set X is said to be linearly ordered if any two elements x,y\in X are comparable under \preceq, in other words, one of the following conditions holds: either x\preceq y or y\preceq x.

For example, the set of reals \mathbb{R} is linearly ordered under the partial order  \le   on \mathbb{R}.

Example 5.  Are the sets considered in Example 1 linearly ordered?

i) No. Any two distinct elements are not comparable.

ii)  No.  Consider X=\{a,b,c\} with subsets \{a,b\} and \{b,c\}.

iii) No. It suffices to take elements 4 and 5 in \mathbb{N}.

iv) Yes. Any two elements of  \mathbb{R} are comparable under the partial order \le .

v) No.  Take functions x^2 and 2-x^2 defined on the interval [0, 2].

vi) No. It suffices to take elements (1,0) and (0,1) in \mathbb{R}^2.

vii) Yes. The alphabetical order is linear.

viii) Yes. The lexicographical order is linear as well.

Example 6. As you can observe from Example 3  the set in case 1 is linearly ordered. But the sets in cases 2 and 3 are not.

Definition 4.  A partially ordered set X is said to be well ordered if every nonempty subset of X has the least element.

Example 7. \mathbb{N} is well  ordered under the usual order  \le   introduced in \mathbb{R} (this fact we will prove in the future).


Oct 20

People need real knowledge

People need real knowledge

Traffic analysis

The number of visits to my website has exceeded 206,000. This number depends on what counts as a visit. An external counter, visible to everyone, writes cookies to the reader's computer and counts many visits from one reader as one. The number of individual readers has reached 23,000. The external counter does not give any more statistics. I will give all the numbers from the internal counter, which is visible only to the site owner.

I have a high percentage of complex content. After reading one post, the reader finds that the answer he is looking for depends on the preliminary material. He starts digging it and then has to go deeper and deeper. Hence the number 206,000, that is, one reader visits the site on average 9 times on different days. Sometimes a visitor from one post goes to another by link on the same day. Hence another figure: 310,000 readings.

I originally wrote simple things about basic statistics. Then I began to write accompanying materials for each advanced course that I taught at Kazakh-British Technical University (KBTU). The shift in the number and level of readership shows that people need deep knowledge, not bait for one-day moths.

For example, my simple post on basic statistics was read 2,300 times. In comparison, the more complex post on the Cobb-Douglas function has been read 7,100 times. This function is widely used in economics to model consumer preferences (utility function) and producer capabilities (production function). In all textbooks it is taught using two-dimensional graphs, as P. Samuelson proposed 85 years ago. In fact, two-dimensional graphs are obtained by projection of a three-dimensional graph, which I show, making everything clear and obvious.

The answer to one of the University of London (UoL) exam problems attracted 14,300 readers. It is so complicated that I split the answer into two parts, and there are links to additional material. On the UoL exam, students have to solve this problem in 20-30 minutes, which even I would not be able to do.

Why my site is unique

My site is unique in several ways. Firstly, I tell the truth about the AP Statistics books. This is a basic statistics course for those who need to interpret tables, graphs and simple statistics. If you have a head on your shoulders, and not a Google search engine, all you need to do is read a small book and look at the solutions. I praise one such book in my reviews. You don't need to attend a two-semester course and read an 800-page book. Moreover, one doesn't need 140 high-quality color photographs that have nothing to do with science and double the price of a book.

Many AP Statistics consumers (that's right, consumers, not students) believe that learning should be fun. Such people are attracted by a book with anecdotes that have no relation to statistics or the life of scientists. In the West, everyone depends on each other, and therefore all the reviews are written in a superlative degree and streamlined. Thank God, I do not depend on the Western labor market, and therefore I tell the truth. Part of my criticism, including the statistics textbook selected for the program "100 Textbooks" of the Ministry of Education and Science of Kazakhstan (MES), is on Facebook.

Secondly, I have the world's only online, free, complete matrix algebra tutorial with all the proofs. Free courses on Udemy, Coursera and edX are not far from AP Statistics in terms of level. Courses at MIT and Khan Academy are also simpler than mine, but have the advantage of being given in video format.

The third distinctive feature is that I help UoL students. It is a huge organization spanning 17 universities and colleges in the UK and with many branches in other parts of the world. The Economics program was developed by the London School of Economics (LSE), one of the world's leading universities.

The problem with LSE courses is that they are very difficult. After the exams, LSE puts out short recommendations on the Internet for solving problems like: here you need to use such and such a theory and such and such an idea. Complete solutions are not given for two reasons: they do not want to help future examinees and sometimes their problems or solutions contain errors (who does not make errors?). But they also delete short recommendations after a year. My site is the only place in the world where there are complete solutions to the most difficult problems of the last few years. It is not for nothing that the solution to one problem noted above attracted 14,000 visits.

Fourthly, my site is unique in terms of the variety of material: statistics, econometrics, algebra, optimization, and finance.

The average number of visits is about 100 per day. When it's time for students to take exams, it jumps to 1-2 thousand. The total amount of materials created in 5 years is equivalent to 5 textbooks. It takes from 2 hours to one day to create one post, depending on the level. After I published this analysis of the site traffic on Facebook, my colleague Nurlan Abiev decided to write posts for the site. I pay for the domain myself, $186 per year. It would be nice to make the site accessible to students and schoolchildren of Kazakhstan, but I don't have time to translate from English.

Once I was looking at the requirements of the MES for approval of electronic textbooks. They want several copies of printouts of all (!) materials and a solid payment for the examination of the site. As a result, all my efforts to create and maintain the site so far have been a personal initiative that does not have any support from the MES and its Committee on Science.

Oct 20

Equivalence Relations

Equivalence Relations

We welcome our new author Nurlan Abiev. He intends to cover topics in Mathematics.

Under a set we mean an undefined term thought intuitively as a collection of objects of common property.

Definition 1. Let A and B be sets.
i) B is said to be  a subset of A if each element of B belongs to A. Usually, this fact we denote by B \subseteq A. Likewise,  A\subseteq A for every set A .

ii) A and B are  equal if they consist of the same elements. We say that B is  a proper subset of A,  if B \subseteq A and B \ne A. Consequently, we accept the notation B\subset A.

iii) Obviously, a set consisting of no elements we  call  the empty set  \emptyset. Moreover, for any nonempty set A we accept the agreement \emptyset\subset A.

Definition 2. The  product set X\times Y of sets X and Y is defined as a set of all ordered pairs (x,y), where x\in X and y\in Y.

Example 1. Let  X=\{a,b,c\} and Y=\{0,1\}. Then we have X \times Y=\{(a,0), (a,1), (b,0), (b,1), (c,0), (c,1)\}. Further, note that (b,1) \in X \times Y, but (1,b) \notin X \times Y.

Definition 3.  Any subset R of X \times Y we call  a relation between  X and Y, in other words R \subseteq X\times Y.

Furthermore, we say that x is in the relation R to y if (x,y)\in R, and denote this fact by xRy. Respectively, the negation \overline{xRy} means (x,y)\notin R.

Definition 4.  An equivalence relation on a set X is a relation R \subseteq X\times X satisfying the following conditions for arbitrary x,y,z \in X:
i) xRx  (reflexivity);
ii) If xRy then yRx  (symmetry);
iii) If xRy and yRz then xRz  (transitivity).

In cases when R is an equivalence relation we will use the notation x\sim y instead of xRy.

Example 2. Assume that  X  is the set of all people in the world. Consider some relations on X.

i)  Descendant relation. A relation x\sim y if x is a descendant of y is transitive, but not reflexive nor symmetric.

ii)  Blood relation. A relation x\sim y if x has an ancestor who is also an ancestor of y is reflexive and symmetric, but not transitive (I am not in a blood relation to my wife, although our children are).

iii)  Sibling relation. Assuming x\sim y if x and y have the same parents we define an equivalence relation.

Recall that \mathbb{R} and \mathbb{Z} are the sets of reals and integers respectively.

Example 3. Examples of equivalence (non equivalence) relations:

i) For x,y\in \mathbb{R} define a relation x\sim y if x-y\in \mathbb{Z}. This is an equivalence relation on \mathbb{R}.

ii) Let x\sim y if x\le y. This relation is not symmetric.

iii) For x,y\in \mathbb{Z} define x\sim y if x-y is even. Consequently we obtain an equivalence relation on \mathbb{Z}.

iv) A relation x\sim y if x-y is odd can not be an equivalence relation on \mathbb{Z} because it is not reflexive and not transitive.

v) Let x,y\in \mathbb{R}. Clearly, x\sim y if |x-y|\le 1 is not an equivalence relation since it is not transitive.

vi) Any function f\colon X\rightarrow Y induces an equivalence relation on X setting x\sim y if f(x)=f(y).

Definition 5.  Assume that R is an equivalence relation on a given set X. We say that R_a:=\left\{x\in X \; | ~\; xRa \right\} is the equivalence class determined by a\in X under the equivalence relation R.

The set \{R_a~|~ a\in X\} of all equivalence classes we call  the quotient set of X over R, in symbols X/ R.

Theorem 1. Every equivalence relation on a given set provides a partition of this set to a disjoint union of equivalence classes, in other words, if R is an equivalence relation on X then
i) X=\bigcup_{x\in X}R_x;
ii) aRb \Rightarrow R_a=R_b;
iii) \overline{aRb} ~\Rightarrow~ R_a\cap R_b=\emptyset.

Thus any two equivalence classes coincide if they admit a nonempty intersection.

i) By reflexivity x\in R_x for every x\in X. So X= \bigcup_{x\in X}R_x.

ii) Let x\in R_a. Then xRa and aRb imply xRb \:\Leftrightarrow\: x\in R_b, showing R_a\subseteq R_b.
By symmetry we also have bRa. Then R_b \subseteq R_a analogously. Therefore, R_a=R_b.

iii) Suppose that R_a \cap R_b \ne \emptyset, and let x be their common element. According to symmetry and transitivity it follows then xRa and xRb, which implies aRb.
Theorem 1 is proved.

The converse of Theorem 1 is also true.

Theorem 2. Every partition of a set X to a disjoint union of its subsets defines on X an equivalence relation x\sim y if x and y belong to the same subset of X.


Apr 20

Microsoft Teams is a jail

Microsoft Teams is a jail

With the quarantine due to COVID-19, my universities had to switch to online teaching. One uses Google Classroom, the other Microsoft Teams. I have something to compare and I am enraged with the Teams. I wanted to post this review on the Internet but could not find a good place. All sites are blowing their trumpets to Microsoft:




Firstly, judging by their terminology, Teams has been developed for enterprises. I have been using it for one month and I still don't know what a channel means. Is it a communication channel? If yes, why don't you call it email or chat? Is it a combination of activities, like a class? Then why not name it a class?

The first time you look for it, they suggest you to download Teams. If you do, it will constantly load on Windows startup without even asking you. Hell, I don't use it every day and I don't want it to take up my computer's resources. Then I learned that there is a browser version of Teams. Even then there are features I don't like. With Google, you log into your email account. Then every Google app that you want to use knows that it is you and the apps you need are constantly open. With Teams, you have to sign into Teams first and then use everything else. I want to use the Teams app (for seeing team membership), OneDrive (for reading what I have uploaded) and Assignments app at the same time. But the damn program periodically logs me out.

The learning curve is steep. On the toolbar there is a chat button. To start a message, you need to type @ first. If my colleague didn't tell me that, I would to have to read the online intro. Sorry, don't have time for that. There is a profusion of apps you can use with Teams. Each time you have to try before you understand what it is good for. Descriptions are short, just one sentence. Again, don't have time for that.

All of this is just minor growl. Here is the main problem. Teams takes control of my computer! Next time I start it, I see a prompt to log in! This is my home computer, there are no secrets and I hate typing a password and even a pin. So I log in, then look on the Internet for ways to get rid of the login prompt. Most of those advices are outdated and the ones that work require me to dance around a lot. The menu in Windows 10 settings has changed, many options have been removed or renamed.

Moreover, Teams thinks that my computer belongs to my school! I am working typing something and all of a sudden my computer shuts down and restarts. The message I see is that my computer was restarted following the policies set by my school!

Of course, none of this happens with Google Classroom. This is where I am now. I want to remove the Microsoft account from my computer and I want to use it only in the browser, like with Google. One site says I have to find it in the settings and press the Remove button. There is no such a button! There is the Manage button which takes you to the Internet. There you can say Remove but then all your tabs in the browser related to Teams log you out. I deeply regret the day I started Teams. It behaves like one of those invasive species that wreak havoc around the world.

Update. I posted the above in April 2020. Hoping that by August 2020 it has become better I installed Teams again. Same story: Teams turned my home computer into a corporate one. The interface is as crazy as it was. I want to get a list of my team members in the Excel format on my computer. Seemingly Microsoft has powerful means to give me such an opportunity: Office 365 and OneNote. But no, you have to install PowerShell and work with scripts. I am an advanced user but I am horrified by the description of the procedure.