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
1answer
219 views

Equivalence Relation on R (real numbers)

Let R be the relation on R(real numbers) defined by: For all x, y (that belong) to R(real numbers), x relates y <=> x-y (that belongs) to Z. (a) Is R an equivalence relation? Prove your answer. ...
1
vote
1answer
119 views

Let A = {1,2,3,4} Let F be the set of all functions from A to A. (check the parts)

Let $\operatorname{S}$ be a relation on $F$ defined by: $\forall f, g \in F, f\,\operatorname{S}\,g \iff f(i) = g(i), \exists i \in A$. (a) Recall that the identity function $I_A : A \mapsto A$ is ...
1
vote
2answers
47 views

How to show properties of a given relation?

I am given that R is a relation on the given set X, and I have to show if the relation is (i) reflexive, (ii) symmetric, (iii) transitive, (iv) asymmetric, and (v) give an example of an element of ...
1
vote
1answer
68 views

$M_{R^n}$; how to derive $n$ for transitive closure?

When finding the transitive closure of a relation $R$, I convert $R$ into a boolean matrix $M_R$, and find the union between $M_R$ and its powers up to $n$. $$M_{R^*} = M_{R^1} \lor M_{R^2} \lor ...
0
votes
1answer
124 views

Show that if $R$ is a strict partial order on $X$, and $R$ is not linear, then there exists a strict partial order $R'$ and $R' \supsetneqq R$.

Question: Show that if $R$ is a strict partial order on $X$, and $R$ is not linear, then there exists a strict partial order $R'$ and $R' \supsetneqq R$. My attempt: By definition 6.23,6.3.1, and ...
0
votes
1answer
84 views

Given a Relation (set of ordered pairs), prove transitivity without going through each pair?

Give a relation, R, on the set of integers, such as R = {(1,2)(2,2) ... } is there a way to determine transitivity without going through each ordered pair (x,y)(y,z) to see if (x,z) is there?
0
votes
1answer
34 views

questions about a proof to a question (about relations)

1) $R,S,T$ are relations on the same set. Prove that $R(S\cup T)=RS\cup ST$ The proof that I stumbled upon was the following: $(a,b)\in R(S\cup T)⇒((a,x)\in R)∧((x,b)\in S∨(x,b)\in T)⇒(a,b)\in ...
3
votes
1answer
72 views

Discrete math functions help?

I'm doing a review for my discrete math test on functions and I'm having troubles with a few questions. Can I get some guidance in how to do these questions so I can be more prepared for the test? ...
0
votes
2answers
31 views

Prove that R is an equivalence relation on F

A relation $R$ is defined on the set $F = \{f: \Bbb R \to \Bbb R\}$ $$fRg \iff f(0) = g(0).$$ My approach: This is reflexive because: $f(0) = f(0)$ is same as $f(0) = g(0)$ This is symmetric ...
0
votes
1answer
58 views

Determining Equivalence Relation on $\Bbb{Z}$

Alright, I have a homework problem which I have researched, read up on and I (think) solved. I just need someone to either confirm my answer (and re-affirm my knowledge) or explain why I am wrong. ...
1
vote
1answer
253 views

Determine if R is an equivalence relation

I've got this question: Consider the relationship $R$ between ordered pairs of natural numbers such that $(a, b)$ is related to $(c, d)$ (denoted by $(a, b) R (c, d)$) if and only if $ad = bc$. ...
0
votes
2answers
41 views

Use of “for all” in definition of reflexive and symmetric relations.

My book says that a relation R on A is reflexive, if $\ (a,a) \in R, \ for\ every \ a \in A$ symmetric, if $\ (a_1,a_2) \in R \implies (a_2,a_1) \in R,\ for\ all\ a_1,a_2 \in A$ Although I ...
2
votes
1answer
70 views

Prove transitivity of relation.

Let $\sim$ be a relation where $x \sim y \Leftrightarrow x = y \lor (x \in I \land y \in I)$. Show $\sim$ is a congruence relation on $S$ where $S= \{a,b, c, d, e\}$ and $I = \{a, d\}$. One of the ...
1
vote
1answer
261 views

Proving the dual and self-dual of a poset.

The dual of a poset $(S \leq)$ is the poset $(S, \geq)$, where for all $x,y \in S$ $x \leq y$ if and only if $ y \geq x$. A poset is self-dual if it is isomorphic to its dual. Questions: Verify ...
2
votes
1answer
177 views

Proving isomorphisms from posets.

An isomorphism from a poset $(S_1,R_1)$ to a poset $(S_2,R_2)$ is a bijection $f: S_1 \rightarrow S_2$ such that, for all $x,y \in S_1$ $(x,y) \in R_1 \leftrightarrow (f(x), f(y)) \in R_2$ When ...
3
votes
1answer
410 views

$R$ is transitive if and only if $ R \circ R \subseteq R$

Question: Let $R$ be a relation on a set $S$. Prove the following. $R$ is transitive if and only if $ R \circ R \subseteq R$. Definition 6.3.9 states that we let $R_1$ and $R_2$ be relations on a ...
4
votes
2answers
109 views

Is $a \le b$ a true statement if $a < b$? [duplicate]

My question is: Is $a \le b$ true if $a < b$? For instance: Is $3 \le 4$ a true statement? I think yes, because $a \le b$ is defined as $a < b\vee a = b$ and this should be true, even if $a = ...
3
votes
1answer
413 views

Composite Relations - Give Examples of relations $R_1$ and $R_2$ such that $R_2 \circ R_1 = R_1 \circ R_2$ and $R_2 \circ R_1 \neq R_1 \circ R_2$

Let $S =[a,b,c]$. Give examples of a. relations $R_1$ and $R_2$ on $S$ such that $R_2 \circ R_1 = R_1 \circ R_2$ b. relations $R_1$ and $R_2$ on $S$ such that $R_2 \circ R_1 \neq R_1 \circ R_2$ My ...
1
vote
2answers
183 views

transitive property in a binary relation

I'm looking at a True or False question in my book and it is very close to identical to the definition of the transitive property in the book, though this answer is False. If someone could explain to ...
1
vote
2answers
107 views

understanding reflexive transitive closure

Suppose I have the following relation $$R = \{(1,1), (2,3), (3,1)\}$$ To make it reflexive we add the following missing pairs: $$ \{(2,2), (3,3)\}$$ Now I wonder how to find the reflexive transitive ...
1
vote
1answer
60 views

Composition relation of P∘P

Consider the following relation P on the set B = {a, b, {a, b}}: P = {(a, a), (a, b), (b, {a, b}), ({a, b}, a)}. Answer questions 6 to 8 by using the given relation P. Question 6 Which one of ...
0
votes
1answer
68 views

Relation $R$ on $V$ is given by $x+y$ is even [closed]

A relation $R$ on $V$ is given by $x+y$ is even. How can we show that if integers $x$ and $y$ are $R$-related then either $x$ and $y$ are both even or $x$ and $y$ are both odd? I've been looking ...
2
votes
2answers
127 views

listing elements of equivalence class

For $m,n$ in $N$ define $m$ equivalent $n$ if $m^2-n^2$ is multiple of $3$ a) show that this is an equivalence relation b) list elements in equivalence class [0] c) list elements in equivalence class ...
1
vote
2answers
86 views

Showing equivalence relation.

On the set $\mathbb N\times \mathbb N$ define $(m,n)\sim(k,l)$ if $m+l=n+k$ Show that $\sim$ is equivalence relation on $\mathbb N\times \mathbb N$ Draw a sketch of $\mathbb N\times \mathbb N$ that ...
0
votes
2answers
1k views

Describing equivalence classes

The problem is : define relation equivalence on Z by $m=n$ in case $m^2=n^2$. a)Show that its an equivalence relation on Z. b)Describe the equivalence classes for = how many are there. For part a, ...
2
votes
1answer
145 views

Help determining relations on the set {1, 2, 3}

I'm studying for a midterm and I just want to make sure that my understanding of these 2 problems that my teacher gave is logically sound. If you could take a look and give me some feedback I would ...
0
votes
2answers
43 views

If $A_1$ and $A_2$ are countably infinite, and that $A_1\cap A_2=\phi$. Then prove that $A_1 \cup A_2$ is countably infinite.

If $A_1$ and $A_2$ are countably infinite, and that $A_1\cap A_2=\phi$. Then prove that $A_1 \cup A_2$ is countably infinite. My work: As $A_1$ and $A_2$ are countably infinite, there exists a ...
1
vote
2answers
119 views

prove if x ≡ y (mod m) then GCD(x, m) = GCD(y, m)

By definition $x=km+y$ for some $k \in \mathbb{Z}$. Let $d=gcd(x,m)$. By definition $d|x$ which implies that $d|km+y$. Since $d$ also devides $m$ we note that $d|y$. now suppose there is some larger ...
6
votes
2answers
1k views

Is there a relation that is irreflexive, anti-symmetric and not transitive?

from the set $\{a, b, c, d\}$? Of the one's I have tried, it at best is two of the three, but never all.
2
votes
1answer
109 views

Problems with the definition of transitive relation

Recently I found this problem, which made me realize I have some problems with relations that are vacuously transitive. Problem: Assume that $R$ is a relation on $A$ and define the relation $S$ as ...
2
votes
1answer
141 views

The closures of a binary relation

I have the following dilemma concerning the equivalence closure of a binary relation. Let $X$ be a nonempty set and $R\subseteq X\times X$ (i.e., a binary relation over $X$). Consider the following ...
2
votes
1answer
31 views

Union of Cartesian squares

I am trying to find sufficient and necessary conditions for a relation to be representable as a union of Cartesian squares: $\bigcup_{i\in I}(X_i\times X_i)$ for some family $X_i$ of sets. One ...
1
vote
0answers
348 views

General (Set Builder) definition for a relation composed with itself n times

Questions What does the set builder notation for $S\circ R$ look like? I'm having the most trouble knowing when there is too much information or not enough information on either side of the 'such ...
1
vote
2answers
35 views

How do you call this feature and property of relation?

If an operator can be defined for $k$ operands, $k \in \mathbb N$, how do you call this feature of the operator? For example, "+" is such an operator. Similarly, for a relation $R$ on a set $X$, $R$ ...
2
votes
1answer
38 views

Checking the equivalence relations of sets

$S=\{0,1,2,3\}, R:SxS, (m,n)\in R \text{ if } m+n=4$. From the condition of $R$, I found that $R=\{(2,2),(1,3),(3,1)\}$. Now I have to see if $R$ is reflexive, symmetric, antisymmetric, and ...
0
votes
1answer
63 views

How can I prove that $(ℤ, ≺)$ is not isomorphic to $(ℕ, ≤)$

We define the relation $≺$ between pairs of integers like this: $n≺m$ is true if and only if one of the following conditions holds: a) $0≤n≤m$ b) $0≤n$ and $m<0$ c) $n<0 , m<0$ and ...
0
votes
1answer
69 views

Are all relations that are symmetric and anti-symmetric a subset of the reflexive relation?

Simple question, but I can't seem to find a guaranteed answer. A symmetric set contains (a, b) if it contains (b, a), but an ...
1
vote
1answer
61 views

Equivalence relation example

On the Wikipedia page about Equivalence Relations, there is a simple example: Let the set $\{a,b,c\}$ have the equivalence relation $\{(a,a),(b,b),(c,c),(b,c),(c,b)\}$. The following sets are ...
0
votes
1answer
137 views

Help understanding a theorem on transitivity of a relation

The theorem states this: The relation R on a set A is transitive if and only if $R^n \subseteq R$ for n = 1, 2, 3,... What I'm reading is that the nth power of that set is transitive if the set ...
5
votes
3answers
6k views

Is the relation $R = \emptyset$ is it reflexive, symmetric and transitive ? Why?

Can someone help me understand the properties of the relation $R = \emptyset$ ? It looks to me like it's not reflexive, since there is no element related to any element, so the elements are not ...
0
votes
1answer
37 views

Understanding relations when it's about $\langle{x,x}\rangle$ instead of $\langle{x,y}\rangle$

I have difficult to understand relations when we talk about $\langle{x,x}\rangle$ instead of $\langle{x,y}\rangle$ .. it's hard for me to realize for example is the following relation is reflexive, ...
1
vote
1answer
115 views

Bijection on a component of a cartesian product

I have been recently studying relations and mappings and I have come across the following problem. Consider two non empty finite sets $I,J$ and their cartesian product $I\times J$. Let $f\colon ...
0
votes
2answers
35 views

Can I write a Non Homogenerous equation as homogenous

Say I have Fibonacci R.Relation, $$ r^2=r+1 $$ Can I write it as $r^2-r-1=0$? From what I know a homogeneous equation is an equation equated to zero.
1
vote
4answers
105 views

I do not understand the definition of antisymmetric relations

OK, let A be a set and let R be a binary relation on A. In my class we say that R is antisymmetric if and only if for every a, b in A, if (a, b) in R and (b, a) in R then a = b. Fair enough, but what ...
1
vote
1answer
58 views

prove a set relation R is transitive?

I have been thinking this problems all the evening, please help Let R be a relation on A. Prove that if Dom(R)∩ Range(R) = Ø, then R is transitive. Oh my god, how to prove this???
5
votes
3answers
10k views

How many equivalence relations on a set with 4 elements.

Let S be a set containing 4 elements (I choose {$a,b,c,d$}). How many possible equivalence relations are there? So I started by making a list of the possible relations: ...
0
votes
1answer
58 views

Discrete Maths: I'm not familiar with this notation

I've the following relation: $(x,y) \in A \times B, x S y ↔ 2|(x-y)$ What does $2|(x-y)$ mean? Thank you.
1
vote
1answer
57 views

Does $f \leq f \circ f^\dagger \circ f$ hold in an arbitrary allegory?

If $f$ is an arrow of $\mathrm{Rel}$, then $f \leq f \circ f^\dagger \circ f.$ Proof. Suppose $xy \in f$. Then $xy \in f, yx \in f^\dagger, xy \in f$. Thus $xy \in f \circ f^\dagger \circ f.$ ...
4
votes
0answers
83 views

Where can I learn more about the concept that is dual to “relation”?

Let $X$ and $Y$ denote sets. Then a relation $X \rightarrow Y$ is, by definition, a subset of $X \times Y$. Dually, we can define that a "corelation" $X \rightarrow Y$ is a partitioning of $X \uplus ...
0
votes
3answers
53 views

How can I prove that $(a,b) = (c,d) \land (c,d)=(e,f) \implies (a,b)=(e,f)$ is true

I am trying to prove this relation, but I just cant. I know it is true, but I can not prove it, because I dont know how. Can someone give me some pointers. $(a,b) = (c,d) \land (c,d)=(e,f) \implies ...