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
121 views

How can a matrix relation be both antisymmetric and symmetric? Explain this image to me.

Take a look at this picture: From what I am reading, antisymmetric means: $$∀ x ∀ y \,[ R ( x , y ) ∧ R ( y , x ) ⇒ x = y ]$$ However, $(2,1)$ and $(1,2)$, $X\ne Y$. I understand how this is ...
0
votes
1answer
32 views

How to determine whether a given relation on a finite set is transitive?

On $R = \left \{(1,1),(1,2),(1,3),(2,2),(2,3),(3,1),(3,4),(4,5),(5,5) \right \}$ Not reflexive because (3,3) and (4,4) are missing? Not symmetric because (2,1) ,(3,2), (4,3), (5,4) are missing? Not ...
0
votes
1answer
58 views

How can I tell if the function $f(n)=2n$ on $\mathbb Z$ is one-to-one, onto, or both?

The domain of the function is the set of all integers. The codomain of each function is also the set of all integers. $$f(n) = 2n $$ I was thinking that the function is one-to-one but I don't know ...
1
vote
2answers
44 views

How to prove $S=\{(x,y) \in \mathbb{R}\times \mathbb{R}|x - y \in \mathbb{Q} \}$ is an equivalence relation?

I am really stuck with this problem, and I cannot come out with a solution. I know that to prove a relation is an equivalence relation we have to prove that it's reflexive, symmetric and transitive, ...
0
votes
2answers
47 views

Reflexive closure Proof

I have this problem I can't figure out. Suppose R is a relation on A, and let S be the reflexive closure of R. Prove that if R is symmetric, also is S. Could you suggest me how to do it? Thanks
0
votes
1answer
22 views

Let S be the transitive closure of R. Describe the relation S

If $R$ is described as follows $R = \{ (p, q) \in P\times P | \mbox{ The person } p \mbox{ is a parent of the person } q\}$, and $P$ is the set of people. I describe $S$ as the follows $S = \{(p, q) ...
2
votes
2answers
26 views

Relations involving division

Can someone explain me how to do it? Let R be a relation on integers such that xRy and iff 3|5x+7y. Show that relation is reflexive ( I am done with it!) and symmetric (I need help with this one).
1
vote
2answers
111 views

Find the transitive closure of a relation

Let the relation $R=\{(0,0),(0,3),(1,0),(1,2),(2,0),(3,2)\}$ Find the $R'$ the transitive closure of R. I honestly don't understand this question at all. Am I being asked to first find $R'$ ...
1
vote
1answer
22 views

Equivalence Relation Properties

I have to define whether the following relation is symmetric, reflexive, and transitive. Define a relation R on Z as follows: (x, y) ∈ R if and only if x = |y|: This is my answer so far: Is ...
2
votes
0answers
130 views

Which of the following is always true for A and B

Given that: $ P(A) = 0.5$ $P(B) = 0.7$ $P(A \cap B) = 0.3$ I have to choose one option that is true... However they all seem to be false which means I am possibly making a mistake.. The only option ...
0
votes
3answers
57 views

Equivalence relation example. How is this even reflexive?

Is the below question a mistake? How is this an equivalence relation? For example, how would it even be reflexive? E.g if you pick any A $\subseteq$ $U$, say A = {a, b}, then A ~ A is not true, ...
0
votes
1answer
45 views

Should I repeat the element of a composite of a relation?

Let's say I have to get the composite of a relation: R composite of R. What if the elements in that composite repeat? Should I say it twice? Example: R is a relation. R= { (1,1), (1,2), (1,3), ...
0
votes
2answers
53 views

Find equivalence relations and classes for a given set

Find how many equivalence relations on the set: $\{1,2,3,4,5,6,7\}$ contain the set $\{\langle6,4\rangle,\langle4,7\rangle,\langle3,3\rangle,\langle5,1\rangle\}$ And do not contain the set ...
1
vote
2answers
37 views

Describes Equivalence Classes

Let $R$ be the relation on the natural numbers defined by $(a,b)\in R$ if and only if $2\mid(a+b)$ I already proved this was an equivalence relation, but how do I determine the number of equivalence ...
0
votes
0answers
29 views

Showing relation is transitive $(a,b) \in \mathcal R \Leftrightarrow 2|(a+b)$

Let $\mathcal R$ be the relation on natural numbers defined by $(a,b) \in \mathcal R \Leftrightarrow 2|(a+b)$ Show it is transitive.
0
votes
1answer
32 views

if $R_1$ and $R_2$ are symmetric and transitive, then $R_1 \cup R_2$ is still symmetric and transitive.

This is an exercise of the assignment we have: Suppose $R_1$ and $R_2$ are relations on A. Prove (with a formal proof) or confute (with a counterexample) that if $R_1$ and $R_2$ are symmetric ...
1
vote
2answers
88 views

What is the difference between a relation and a closure?

I know what a transitive, reflexive and symmetric relation is. When I study transitive, reflexive and symmetric closure of a binary relation, I find it difficult to get an intuition and so am unable ...
2
votes
3answers
502 views

Suppose that R and S are reflexive relations on a set A. Show that R-S is irreflexive.

Suppose that R and S are reflexive relations on a set A. Show that R - S is irreflexive, i.e., $$\forall x \in A, (x,x) \notin R\setminus S$$ We have: $$\forall r\in R, (r,r) \in R\\ \forall s\in ...
0
votes
1answer
123 views

Construct equivalence classes for a relation R

Define relation R as follows: xRy if x and y are bit strings with |x| >= 2 and |y| >= 2 such that x and y agree in their first two bits. Show that R is an equivalence relation. Construct the ...
1
vote
1answer
213 views

Consider P a partition of set A. Given relation R on A and xRy if and only if x, y $\in$ X for some X $\in$ P. Show R is equivalence relation on A

Consider $P$, a partition of a set $A$. Define a relation $R$ on $A$ such that $x\mathrel{R}y$ if and only if $x, y \in X$ for some $X \in P$. Show that $R$ is an equivalence relation on $A$. Next ...
0
votes
2answers
56 views

Show whether a relation R is transitive for xRy iff 3|(2x+y)

Define a relation $$R : Z^+ \rightarrow Z^+$$ by xRy iff (2x+y)mod3=0. R is reflexive: Let x=y. So (x,x) is in R. Then we have 2x+x=3x, and since x is an integer, it must clearly be divisible by 3. ...
0
votes
1answer
629 views

Prove that if R is a symmetric relation, so is R^2.

Prove that if R is a symmetric relation, so is R^2. My attempt : The Relation R has (a,b) provided (b,a) is a member of R. So if I go on to find R^2 it will always have element (a,a) that makes R^2 ...
-4
votes
2answers
61 views

How to find $R^2$ given $S$ and $R$. [closed]

If $S = \{1,2,3\}$ has a relation $R = \{(1,2), (1,3), (2,3)\}$, find the relation $R^2$? I am not able to find $R^2$, can anyone please help me with this?
0
votes
1answer
59 views

Is relation a partial order?

can you give me few hints how to solve this problem ? Relation R on the set P(A) A = {a,b,c,d} is a set of four elements. We also have relation R on the set P(A), which is defined R={(A,B)│A ⊆ B. ...
0
votes
1answer
24 views

Transitive closure relation

I have a following relation on the set {A,B,C,D} R = {(a,a);(a,c);(b,d);(c,d);(d,c)} What is the smallest number of tuples that has to be added in order for the relation to become transitive? It is ...
1
vote
2answers
305 views

Proofs with Relations and functions

I need help with setting up a homework problem. I am having trouble finding where to start. Problem: Suppose A is a set. Show that $i_A$ is the only relation on A that is both an equivalence relation ...
2
votes
1answer
643 views

how to find relation R^2

Suppose S is a set of airports, and R is the following relation on S: aRb if and only if there is a direct flight from a to b. Explain your answers to the following questions and use common sense. a. ...
1
vote
0answers
349 views

Real life example of relations with various combination of properties

Attempted a set of questions as below: ...
1
vote
2answers
209 views

to find total number of subsets

I was working out some problem where I needed permutation and combination. I took the cartesian product of $n$ sets where number of elements in each set is even. Further the elements of this cartesian ...
0
votes
1answer
136 views

Prove: The relation $R$ on $\mathbb{N}$ is reflexive, symmetric and transitive

Prove: The relation $R$ on $\mathbb{N}$ given by $mRn$ iff there are natural numbers $p$, $q$ with $m^p$ = $n^q$ is reflexive, symmetric and transitive. Proving $R$ is reflexive: Proof. Suppose $m$ ...
0
votes
1answer
263 views

Proving properties of binary relations

Attempting to find answers to solve these questions. I've been looking all over the web for references since my textbooks aren't being helpful. Now, I'm still at the starting point. ...
14
votes
3answers
1k views

Sole minimal element: Why not also the minimum?

A minimal element (any number thereof) of a partially ordered set $S$ is an element that is not greater than any other element in $S$. The minimum (at most one) of a partially ordered set $S$ is an ...
1
vote
1answer
2k views

Example of an antisymmetric, transitive, but not reflexive relation

The question I'm tackling right now is this: Give an example of a relation R on a set S that is not reflexive, transitive and not symmetric. My answer: Let S = {1,2,3} and let R = {(1,1), (2,2), ...
1
vote
2answers
184 views

Tell whether the relation is reflexive, symmetric, asymmetric, antisymmetric or transitive.

Tell whether the relation is reflexive, symmetric, asymmetric, antisymmetric or transitive.Identify equivalence relations or partial orders. $R$ is the relation on people such that $a R b$ if $a$ ...
1
vote
3answers
78 views

Prove a relation for a set

If $ R,S $ are relations on the set $ A $, where $ S $ is reflexive $ S \subseteq R $ Prove that: $ R $ is reflexive How do I begin? How could a relation be a subset of another relation ? thanks
3
votes
2answers
97 views

In $\mathsf{Rel}$, are any two objects isomoprhic?

My knowledge of categories is rather basic, and I was just trying to find out what are isomoprhisms in $\mathsf{Rel}$ where objects are sets and morphisms are relations. As far as I got, an ...
0
votes
1answer
23 views

Relationship Between 4 Variables

Let (a-1) d = b (c-1) such that $ a,b,c,d \in \mathbb{R} $. How do you find the relationships between a,b,c,d? Do you look at what makes both sides equivalent? I considered 3 cases where: a = 1, ...
5
votes
1answer
95 views

Composition of relations. Both relations are functional and mutually inverse mappings. Zorich - MAI p22

$\def\R{\mathcal{R}}$ The composition $\mathcal{R}_2 \circ \mathcal{R}_1$ of the relations $\mathcal{R}_1$ and $\mathcal{R}_2$ is defined as follows: $$\mathcal{R}_2 \circ \mathcal{R}_1 := ...
1
vote
0answers
79 views

Inverse Relation of Irreflexive Property.

We are taking the inverse of relation to check that inverse of R is transitive, reflexive , symmetric and anti-symmetric to as it is on R (not inverse).. My question is that why we are not taking the ...
0
votes
1answer
65 views

Properties of Relations and their negations.

There are three properties of relation, 1. Reflexive 2. Symmetric 3. Transitive and if all properties are satisfy by a relation then its known as ...
0
votes
2answers
46 views

Why does $A = X-B$ is equivalent to $A \cup B = X$ and $A \cap B = \emptyset$

I was looking at a solution to the problem and it says that $A = X-B$ is equivalent to $A \cup B = X$ and $A \cap B = \emptyset$. I am wondering why this is true? Any help would be highly ...
1
vote
3answers
45 views

Determining the list elements of $U = \{(A,B)\in \mathcal P(X) ×\mathcal P(X)\mid A=(X−B)\}$

Define $X = \{1,2,3,\ldots,n\}$, for some positive integer $n$. The set $U$, is defined as: $U =\{(A,B)\in \mathcal P(X) ×\mathcal P (X)\mid A=(X−B)\}$. If $n=3$, show the elements of $U$. I ...
0
votes
1answer
44 views

Proving equivalence relation and classes

I was wondering how I could prove aRb if and only if 5 | (a + 4b) , on the set of all integers I'm used to proving for sets of numbers so I have no idea how to start out for this... Equivalence ...
-2
votes
2answers
40 views

Proving a Relation that is a Function by Division Algorithm [duplicate]

Let A=B=$\mathbb{N}$ R is: (a,b)$\in$R iff for some q$\in$Integers a=5q+b WHERE 0$\leq$b<5 Given a relation, show that it's a function. To Show: 1) $\forall$a$\in$A$\exists$b$\in$B((a,b)$\in$R) ...
0
votes
1answer
41 views

Is the relation on integers, defined by $(a,b)\in R\iff a=5q+b$, a function? [closed]

Let $A=B=\mathbb N$. Relation $R$ is: $(a,b)\in R$ iff for some $q \in \mathbb Z$ we have $a=5q+b$ Given a relation, show that it's a function. To Show: $\forall a \in A \ \exists b \in B$ such ...
0
votes
1answer
47 views

Language and Finite Models

Let us consider the language consisting of one symbol $R$ for a binary relation. Let $\sigma$ denote the following sentence: $\forall x \exists y \exists z \ x\neq y \wedge y \neq z \wedge x \neq z ...
0
votes
1answer
95 views

number of antisymmetric and not irreflexive relations

What is the number of relations on a n element set that are antisymmetric and not irreflexive? I have tried doing this as fallows- no of antisymmetric relations having atleast one self pair[like ...
0
votes
1answer
45 views

Number of relations on a set

What is the number of relations on a $n$ element set that are antisymmetric and not symmetric? I have soved this question using the fact that 'antisymmetric and not symmetric' means asymmetric... ...
1
vote
0answers
90 views

Finding Equivalence Classes for Infinite Sets

Let $R$ be the relation on the set of rational numbers $\Bbb Q$ defined as follows: for all $q, r \in \Bbb Q$, $qRr$ iff $q − r \in \Bbb Z$. Then $R$ is an equivalence relation on $\Bbb Q$. What is ...
2
votes
1answer
50 views

Well founded relations.

I'm reading a proof in Jech Set theory and I cannot understand a line. Why is it the case that the replacement axiom guarantees the existence of $\theta$ such that $P_\theta = P_{\theta + 1}$? Last ...