Elements of Set Theory: Ordering Relations

From the first section of this chapter, we've covered about the ordering relation of the ordered set <center><img src="https://images.hive.blog/768x0/https://cdn.steemitimages.com/DQmact8JhnudajrhsxQ2ELPUS7xg4aRhfELt2j5k4iY71jK/image.png" srcset="https://images.hive.blog/768x0/https://cdn.steemitimages.com/DQmact8JhnudajrhsxQ2ELPUS7xg4aRhfELt2j5k4iY71jK/image.png 1x, https://images.hive.blog/1536x0/https://cdn.steemitimages.com/DQmact8JhnudajrhsxQ2ELPUS7xg4aRhfELt2j5k4iY71jK/image.png 2x" /> Now we want to consider the ordering relation on other sets. But first, we will deal with the basic concepts of ordering relations which we will find useful in chapter 5. What, in general, should it mean to say that R is an ordering relation on a set A? Basic instinct tells us that ordering relation is about determining given any distinct x and y which one is smaller. <code>Definition Let A be any set. A linear ordering on A (also called a total ordering on A) is a binary relation R on A (i.e., $R \subseteq A \times A$) meeting the following two conditions: a) R is a transitive relation; i.e., whenever xRy and yRz, then xRz b) R satisfies trichotomy on A, by which we mean the for any x and y in A exactly one of the three alternatives, <center><img src="https://images.hive.blog/768x0/https://cdn.steemitimages.com/DQmRiWARxkDSNqWkyqbBHzZUe84XQecsE6oTayYxsYCbDrC/image.png" srcset="https://images.hive.blog/768x0/https://cdn.steemitimages.com/DQmRiWARxkDSNqWkyqbBHzZUe84XQecsE6oTayYxsYCbDrC/image.png 1x, https://images.hive.blog/1536x0/https://cdn.steemitimages.com/DQmRiWARxkDSNqWkyqbBHzZUe84XQecsE6oTayYxsYCbDrC/image.png 2x" /> holds <code>Theorem 3R Let R be a linear ordering on A. i) There is no x for which <img src="https://images.hive.blog/768x0/https://cdn.steemitimages.com/DQmWQHEq4JyHejxLxrBeqfUCPoWaXwDCVgNznLpNDR5tjd2/image.png" srcset="https://images.hive.blog/768x0/https://cdn.steemitimages.com/DQmWQHEq4JyHejxLxrBeqfUCPoWaXwDCVgNznLpNDR5tjd2/image.png 1x, https://images.hive.blog/1536x0/https://cdn.steemitimages.com/DQmWQHEq4JyHejxLxrBeqfUCPoWaXwDCVgNznLpNDR5tjd2/image.png 2x" /> ii) For distinct x and y in A, either <img src="https://images.hive.blog/768x0/https://cdn.steemitimages.com/DQmX8YifXcGfc5uWhZVYqtV5tznEEydxTN8RKaR7rmfizFM/image.png" srcset="https://images.hive.blog/768x0/https://cdn.steemitimages.com/DQmX8YifXcGfc5uWhZVYqtV5tznEEydxTN8RKaR7rmfizFM/image.png 1x, https://images.hive.blog/1536x0/https://cdn.steemitimages.com/DQmX8YifXcGfc5uWhZVYqtV5tznEEydxTN8RKaR7rmfizFM/image.png 2x" /> This theorem is about the trichotomy conditions. A relation meeting condition (i) is called irreflexive while those relations satisfying (ii) is said to be connect on A. Note that we cannot have a linear ordering R leading us to circles, <center><img src="https://images.hive.blog/768x0/https://cdn.steemitimages.com/DQmXX7b9B3JS75Mn1837cWW6UNebimRr8ZGa2cXBqEehXeV/image.png" srcset="https://images.hive.blog/768x0/https://cdn.steemitimages.com/DQmXX7b9B3JS75Mn1837cWW6UNebimRr8ZGa2cXBqEehXeV/image.png 1x, https://images.hive.blog/1536x0/https://cdn.steemitimages.com/DQmXX7b9B3JS75Mn1837cWW6UNebimRr8ZGa2cXBqEehXeV/image.png 2x" /> The transitivity is contradicting the condition (i) of the foregoing theorem. We can't have that in our linear ordering relation. The commonly used symbol for linear ordering is not R but "<". For then we can write "x < y" which implies that the pair is related and a member of the set <. Visualization of the Ordering The members of set A can be represented by dots, with the rule that we place the dot x below the dot y whenever x < y. We add vertical lines to connect the dots. For an easy visualization consider the following figure, <center><img src="https://images.hive.blog/768x0/https://cdn.steemitimages.com/DQmeW1nmgVchBPcptvf5SykvKBeJ2neAD9MipaEsz1i9twY/1528820869672.png" alt="1528820869672.png" srcset="https://images.hive.blog/768x0/https://cdn.steemitimages.com/DQmeW1nmgVchBPcptvf5SykvKBeJ2neAD9MipaEsz1i9twY/1528820869672.png 1x, https://images.hive.blog/1536x0/https://cdn.steemitimages.com/DQmeW1nmgVchBPcptvf5SykvKBeJ2neAD9MipaEsz1i9twY/1528820869672.png 2x" /> There are other important concepts of linear ordering but we will discuss them more in the first section of Chapter 7. We will encounter a "non-linear" form of the ordering relation, <center><img src="https://images.hive.blog/768x0/https://cdn.steemitimages.com/DQmfXp44k1LQJSZNesoyCj33U2hi83vrYsfjprJ6g9FX5LN/image.png" srcset="https://images.hive.blog/768x0/https://cdn.steemitimages.com/DQmfXp44k1LQJSZNesoyCj33U2hi83vrYsfjprJ6g9FX5LN/image.png 1x, https://images.hive.blog/1536x0/https://cdn.steemitimages.com/DQmfXp44k1LQJSZNesoyCj33U2hi83vrYsfjprJ6g9FX5LN/image.png 2x" /> <hr /> Disclaimer: this is a summary of section 3.7 from the book "Elements of Set Theory" by Herbert B. Enderton, the content apart from rephrasing is identical, most of the equations are from the book and the same examples are treated. All of the equation images were screenshots from generated latex form using typora <ol> <li><a href="https://github.com/valjen/book_collection" target="_blank" rel="nofollow noreferrer noopener" title="This link will take you away from hive.blog" class="external_link">Elements of Set Theory by Herbert B. Enderton <center> Thank you for reading ... <img src="https://images.hive.blog/0x0/https://steemitimages.com/0x0/https://media.giphy.com/media/ohdY5OaQmUmVW/giphy.gif" /> <img src="https://images.hive.blog/768x0/https://steemitimages.com/DQmNXXLQdbXpB1WuRn2YErhQLznZVCdUW3kc7sutPWxA8vv/image.png" srcset="https://images.hive.blog/768x0/https://steemitimages.com/DQmNXXLQdbXpB1WuRn2YErhQLznZVCdUW3kc7sutPWxA8vv/image.png 1x, https://images.hive.blog/1536x0/https://steemitimages.com/DQmNXXLQdbXpB1WuRn2YErhQLznZVCdUW3kc7sutPWxA8vv/image.png 2x" />