This tag is intended for questions concerning partial orders, equivalence relations, properties of relations (transitive, symmetric,...), composition of relations and similar stuff. More-or-less the things about relations taught in the first elementary set theory or discrete math course.

learn more… | top users | synonyms

0
votes
0answers
18 views

Special relations on a finite set

Given a set $S = \{s_1, \dots, s_n\}$, $S \times S$ is the product space of $S$ with itself. Let $S_0 = \{(s_i, s_i), i=1,\dots,n\}$. Are there a name and/or notation for the operation mapping $S$ to ...
1
vote
1answer
42 views

Find all equivalence classes

Let R by a relation defined on pairs $(m,n)$ of integers $m$ and natural numbers $n$ by $(i,j) R (k,l)$ if $il=jk$. Prove that this is an equivalence relation and give the equivalence cases. Show ...
0
votes
2answers
30 views

Transitivity of a relation [closed]

Is the relation {(1,2)(3,4)(5,6)} is a transitive relation. I have found in many references and ncert text that it is transitive. Give reason for u r answer.
1
vote
1answer
25 views

Proving an equivalence relation(specifically transitivity)

I'm currently learning about equivalence relations. I understand that an equivalence relation is a relation that is reflexive, symmetric, and transitive. But I'm having trouble proving the transitive ...
0
votes
1answer
20 views

Composition of relations: Incomplete proof.

Let $R$ be a relation from $A$ to $B$, and $S$ be a relation from $B$ to $C$, and $T$ be a relation from $C$ to $D$. I want to prove that $T\circ (S\circ R)=(T\circ S)\circ R$. This is how I proved ...
1
vote
1answer
45 views

Partial order relation (Antisymmetric property), given a relation $xRy \iff x-y\le 4$

Given the set: $A=\{1,2,3,\dots,19,20\}$. The relation $R$ is defined on $A$ as: $xRy\Leftrightarrow x-y\leq4$ Is $R$ a partial order relation? I know that for a relation to be partial order it has ...
0
votes
1answer
198 views

The “Empty Tuple” or “0-Tuple”: Its Definition and Properties

(I would like to link to a previous discussion on the subject: What is A Set Raised to the 0 Power? (In Relation to the Definition of a Nullary Operation)) In axiomatic (ZFC) set theory, we define ...
1
vote
2answers
30 views

Equivalence Relations (Discrete Math)

Hello I'm having trouble with this math problem on equivalence relations. Let X be any subset of the set of positive integers Z. Define a relation ~ on X as follows: I have reflexive proven, having ...
0
votes
1answer
15 views

Relation symmetric and antisymmetric

Let $A$ a non-empty set. If there is a complete relation on $A$ that is both symmetric and antisymmetric, does it imply that the relation is the "equality" and $A$ has one single element?
0
votes
2answers
18 views

Subset Relation: Is the subset relation a partial order?

I read in a Wikipedia entry (subset in german http://de.wikipedia.org/wiki/Teilmenge): "Every set is a subset of itself" But for example, if A is a set of all sets, with maximum 5 Elements, than A ...
1
vote
1answer
61 views

The composition of the $<$ relation with itself

I am struggle with answering this question. I do not understand how to approach this question. 1.Let <􏰈 denote the less than relation on the set of integers. Describe the squared relation <^2 ...
1
vote
1answer
51 views

Notation interpretation

Consider the set $$\Bbb R^n :=\{x=(x_1,...,x_n):x_1,...,x_n \in \Bbb R \}.$$ For $x,y\in \Bbb R^n$, we define $<$ as below: $$ x<y \iff \exists j \in \{1,..,n \} \left( x_j<y_j \wedge ...
0
votes
0answers
37 views

Implies the $\leq$ relation a lexicographical relation?

Consider the set $\Bbb R^n = \{ x = ( x_1, ..., x_n): x_1,...,x_n \in \Bbb R \}.$ For $x,y\in \Bbb R^n$, we define $ x<y \iff \exists j \in \{1,..,n \}(x_j<y_j)$ $\wedge \forall i \in \Bbb N ...
0
votes
2answers
66 views

Lexicographical order in $\Bbb R^n$?

Consider the set $ \Bbb R^n = \{ x = (x_1, ..., x_n) : x_1, ..., x_n \in \Bbb R \}.$ For $x,y\in \Bbb R^n$, we define $<$,$\leq$ as below: $$ x<y \iff j \in \{1,..,n \} (x_j<y_j) ...
1
vote
1answer
76 views

Lexicographical order

Hello everyone i'm trying to solve an exercise that contains the following istructions. Let it be $ \Bbb R^n = \{ x = (x_1, ..., x_n) : x_1, ..., x_n \in \Bbb R \}.$ Let define on $ \Bbb R^n$ a ...
0
votes
1answer
51 views

For semigroups, $S\preccurlyeq T$ iff there exists an injective relational morpism $\mu: S\to T$.

This is Exercise 1.16 of Howie's Fundamentals of Semigroup Theory. The Details. Definition 1: Let $A$ and $B$ be sets. A relation $\rho$ from $A$ to $B$ is a subset of $A\times B$. Define ...
0
votes
0answers
33 views

Is this relation reflexive, symmetric, antisymmetric, transitive, or whether it is equivalence relation

Is this relation reflexive? symmetric? transitive? Is it an equivalence relation? Explain. I know that for it to be an equivalance relation, it has to be reflexive, symmetric and transitive.
0
votes
1answer
23 views

Does (f(0)=g(0) or f(1)=g(1)) define a transitive relation on function?

I need is to check if a relation is an equivalence or not. I can see that it is reflexive and symmetric but I'm not able to find out if it is transitive. The relation is defined on the set of all ...
1
vote
1answer
22 views

Is every left-unique relation right-uniqe?

Lets say we have a relation A x B. As far as I unterstood, in a right-unique relation, for every element from A, there is at least one element in B. But there might be elements in B which do not have ...
0
votes
3answers
24 views

Why is this Relation R (graph) not transitive?

Let the arrow graph of R be the following: If we get the ordered pairs we have that R = { (a,a), (a,b), (a,c), (b,b), (b,a), (b,c), (c,a), (c,b), (d,d) } If we analyze this: *Reflexive - NOT ...
0
votes
1answer
33 views

Set of ordered pairs of the transitive closure R* of R

I pretty much know how to get the ordered pairs by doing the arrow graph method since the matrix method is much more complex. let R be: R = { (a,b), (b,a), (a,c), (c,d), (c,e), (e,c) } (I am ...
0
votes
2answers
31 views

How do you determine if a relation is transitive?

Suppose I have the relation P such that $$ x P y $$ iff $$ x = y^2 $$ How do I determine whether or not the relation is transitive?
1
vote
1answer
47 views

Venn diagram for a relation

My high school math book says the following diagram is a Venn diagram. But I think this is not correct. Is it right? If not, what is the following diagram that represents a relationship called?
1
vote
1answer
28 views

Steps to determine if a relation of a set is reflexive,symmetric or transitive?

I am having problem understanding these concepts. For example, let $A = \{2,3,4,5,6,7,8\}$. The definition I found says that $x R y \iff 3 | (x-y)$. How do I know if the relation $R$ on $A$ is ...
0
votes
1answer
38 views

Properties of a relation

$\cong\;=\{((x_1,y_1), (x_2,y_2))\in \mathbb R^2 ×\mathbb R^2 |x_1^2-x_2^2=3y_1^2-3y_2^2\}$ finitary relation meaning $(x_1,y_1) \cong (x_2,y_2)$ if $x_1^2-x_2^2=3y_1^2-3y_2^2$ Is this finitary ...
0
votes
1answer
15 views

equivalence relations proof over the same set

I want to proof the following theorem: Let R be an equivalence relation on set A. Then {R[a]:a that belongs to A} is a partition of A. So long I have manage to proof that each a that belongs to A, ...
0
votes
3answers
61 views

Recursive definition of the relation greater than on N X N

Give a recursive definition of the relation greater than on N X N using the successor operators s? I started this question throw this way: basis: (1,0) ∈ N x N could someone help me in recursive ...
0
votes
1answer
22 views

are these binary relations?

I have found the following examples of Binary Relations, but I am not pretty sure is the conclusion the author arrived is correct. X is a number of people x N y, implies that x lives next to y; for ...
12
votes
3answers
845 views

Symbol for unknown relation?

When solving equations like $$\begin{align} 4x-4 &=\frac{(2x)^2}{x} \\ -4 &= \frac{4x^2}{x} -4x \\ -4 &= 4x -4x \\[0.2em] -4 &= 0\end{align}$$ using the equality-symbol feels like ...
0
votes
1answer
21 views

Difference between Inclusion and continuation

Halmos defines the order continuation as follows: We shall say that a well ordered set A is a continuation of well ordered set B if B is a subset of A, if, in fact, B is an intial segment of A and ...
0
votes
1answer
20 views

$aRb$ iff $a=b(10)^k$ for some $k \in \mathbb{Z}$ [Prove Equivalence Relation]

The question: $R$ is a relation on $\mathbb{N}$ defined by $aRb$ iff $a=b(10)^k$ for some $k \in \mathbb{Z}$. Prove that $R$ is an Equivalence relation. The problem: I can define an ...
0
votes
2answers
38 views

How to find relation between 2 numbers

I have been practicing programming for many months now and what I found difficult is not about solving problem. But it is how to find the "how to solve problem" to make computer solves that for me! ...
0
votes
1answer
23 views

Does an asymmetric relation entail an antisymmetric relation?

So if there exists an asymmetric relation within a set, does it also entail that there will be an antisymmetric relation in that same set? If so, then it is possible to find out whether a set ...
-1
votes
1answer
30 views

How is a relation defined on ordered sets?

I am reading that $(\mathbb{Z}, \leq )$ is a total ordered set. I understand how it satisfies reflexivity, antisymmetry, transitivity. But it says that because for any $a,b \in \mathbb{Z}$, either ...
0
votes
0answers
11 views

Partial Order Matrix Representaion

What would be the general matrix representation of a partial ordering ? i.e. since the relation must be reflexive, mat(i,i) = 1.
1
vote
2answers
66 views

Good book for self-studying Binary Relations

I am studying economics and I frequently encounter Binary Relations. But without any good knowledge of it, I get confused. Here is some background, if it's helpful: I know calculus(single and ...
0
votes
1answer
53 views

Why is this relation recursive?

A relation $R \subset \mathbb{N}^d$ is called recursive if there exists a primitive recursive function f with $$ (x_1 ,\dots,x_d) \in R \Leftrightarrow f(x_1,\dots,x_d)=0.$$ In Kurt Gödel's article ...
-1
votes
1answer
50 views

condition for transitivity

In transitive relations, $aRb$ and $bRc$ implies $aRc$. But what if there are no $bRc$, can we say that the relation is transitive? For example, are relations $R\subseteq V\times V$, corresponding to ...
2
votes
1answer
50 views

I have two symmetric relations on a set. How can I prove that the symmetric difference is irreflexive?

I have this problem. Let R and S be symmetric relations on a set A. Prove or disprove: $R \oplus S$ is irreflexive. Now I'm assuming it's not true, because $(x,x)$ can be an element of $R$ ...
-1
votes
3answers
91 views

A big list of non-trivial examples of functions from outside mathematics

I will be teaching my students about functions, and want to stress that functions are not only the usual mathematical ones (linear, logs, exponential, ...), but that function is fundamentally a ...
5
votes
1answer
124 views

Where can I learn more about the Galois connection induced by a graph on its own powerset?

Given a binary relation $R \subseteq X \times Y$, we get an antitone Galois connection $(F,U) : \mathcal{P}(X) \rightarrow \mathcal{P}(Y)$ in the usual way: The function $U : \mathcal{P}(X) ...
2
votes
2answers
35 views

Determining if the relation is an equivalence one.

Determine if the relation : $$x \sim y \iff |y-x| \text{ is an integer multiple of } 3$$ is an equivalence one. Now, I think this is an equivalence relation but I am having troubles formally ...
1
vote
1answer
28 views

Why is this relation a function?

I need to determine whether or not the relation $\{ (a^2,a) | a \in \Bbb {R}, a \geq 0\}$ is a function from $\Bbb {R}$ to $\Bbb {R}$. I think that it is a function. But I don't know how to ...
2
votes
2answers
69 views

Is the relation a function

I'm trying to determine if the relation $\{(\frac{a}{b}, a-b) | a,b \in \Bbb {Z}, b \neq 0\}$ is a function from $\Bbb {Q}$ to $\Bbb {Z}$. I know that a relation is a function from A to B if dom(f)=A ...
1
vote
2answers
42 views

Is the relation a function?

Is the relation on $\Bbb {R}$ a function from $\Bbb {R}$ to $\Bbb {R}$? $$\{(a^2,a)\mid a \in \Bbb {R}\}$$ How do I determine whether or not the relation is a funtion? Would I treat $(a^2,a)$ as ...
1
vote
1answer
28 views

Transitive closure of $H=\{(a,b) \in \mathbb{R}^2: |a-b| \leq 0.1\}$

$$H = \{(a, b) \in \mathbb{R}^2: |a − b| \leq 0.1\}$$ In class today we went over this problem as an example to show transitive closure. I know that the transitive closure of $H$ is "All real ...
0
votes
1answer
49 views

What is the cardinality?

Let $A=\left\{1,2,\cdots,10\right\}$ Let $f,g:A\to A$. Consider the equivalence relation $$ fRg \iff \exists h:A\to A. f=h\circ g$$ where $h$ is invertible. Now, let $g(x)=5$: Why is $\left| ...
3
votes
3answers
525 views

How many functions are transitive?

Let the set of all functions defined as: $\left\{a,b,c,d\right\} \rightarrow \{a,b,c,d\}$ How many functions are transitive? I've been told to use the fact that a function is transitive iff "it's ...
0
votes
2answers
60 views

Prove that the binary relation “is a subset of” is a…

Prove that the binary relation "is a subset of" is a partial order (POSET)? Should I try to prove this in reference to the power set of a general set? When is this relation a total order?
1
vote
1answer
23 views

An accessible example of a preorder that is neither symmetric nor antisymmetric

For a project I am working on, I need an example of a preorder (reflexive and transitive relation) that is neither symmetric (like an equivalence relation) nor antisymmetric (like less than or equal ...