Discrete Math - Relations

A relation from set S to set T is a subset of the cartesian product of S and T. R is a relation from S to T iff R⊆(S×T). It is also a subset of the cartesian plane. A binary relation is a relation between 2 sets, this is the most common relation in natural language. The most common example is the following: All coins have an associated value, (∀x)(∃y)Pxy⊆(Coins×Value),I(P)={(Penny,1),(Nickle,5),(Dime,10),(Quarter,25)}.

Arity is an n-ary relation, i.e., it is a subset of S_1×S_2×S_3…×S_n. An n-ary relation is an n-placed relation.
Given a relation R, when $ R=A_1×B_1 $, where R⊆A×B.:
  1. A is the domain of R, where $ A_1⊆A $
  2. B is the codomain of R, where $ B_1⊆B, B_1 $ is the range of R.

We can represent this where certain sets have elements which map onto each other.

Figure 37

The image is the elements in the range. The pre-image is the elements in the domain used in the relation. Relations allow for more than 1 image per pre-image (unlike functions). If (x,y) are in relation R, we can write: xRy, or R(x,y).

An inverse takes a relation between (x,y), and inverts it to (y,x). It can also be written as, R^(-1)={(y,x)|(x,y)∈R}.

Figure 38

A relation R on S is anti-symmetric iff for every x and y in S, if (x,y) is in R and (y,x) is in R, then x is identical to y. In other words, xRy and yRx together imply that x=y.

Instead of stating a relation between A to B, we can look at relations of A to itself. A relation is reflexive if it relates to itself, or xRx,∀x∈A. In the following directed graph, all elements are related to itself, so all elements are reflexive:

Figure 39

A relation on A is symmetric if xRy, then yRx (given ∀x,y∈A).

Figure 40

A relation on A is transitive if xRy∧yRz, then xRz (given ∀x,y,z∈A).

Figure 41

An equivalence relation on a set is a relation that is reflexive, symmetric, and transitive. Example: 3 is equal to 3 where are equal on different sides.


Comments

Post a Comment

Popular posts from this blog

National Accounting - Consumption and Investment

Image
Over the course of a year, a quarter, or a month, we can look at the debits and credits that build up the entirety of an economy. National accounts looks at these debits and credits and record the transactions  While it can be the case we make more than we spend as individuals, this cannot be the case for entire economies. This is the old adage that every sale is something bought. In the context of macroeconomics we say that income over a period of time should be equal to expenditures over that period of time: Expenditures = Income For the case of this post, we will assume a hypothetical economy which only consists of domestic investment and consumption as transactions. We can define the two as follows: Consumption : Transactions that are associated with the destruction of asset values. Investment : Transactions that are associated with increasing assets values. To understand these definitions, we will look at two sets of debit and credit charts to show how these transactions are ...
Read more

Conceptual Analysis

Conceptual analysis is kind of like giving definitions: Conceptual Analysis : A description of constituent properties of a complex property or relation. Some complex property is usually built up of simpler properties. An example of a conceptual analysis is: X is a triangle = df. X is a shape with exactly three angles and straight lines in Euclidean space. This is more than a definition is picking out some properties of a property. Also, = df. means by definition. Another example: X is a bachelor = df. X is an unmarried man. Here a conceptual analysis is: Non-circular, the analysis refers to properties that aren’t the same thing as itself. It tries to include everything it intends to include and exclude what it intends to not exclude. It tries to pick out the properties that do this. (It’s not possible to have one condition without the other). Conceptual analysis helps you: Understand reality : reality contains things with properties, and conceptual analysis picks out properties...
Read more