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

3
votes
0answers
32 views

Relation between 2 recurrence equations.

I am stuck with the following recurrence relations (actually asked in a programming question).Given the following relationships, is it possible to find the index of the occurrence of any given number ...
0
votes
1answer
24 views

Finding number of Relations using Counting!!!

Consider $A$ = {$w, x, y, z$}. Determine: (a) the number of possible relations on A, i.e., subsets of A×A (b) the number of relations on A that are reflexive and symmetric. (c) the number of ...
1
vote
2answers
226 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 ...
0
votes
1answer
36 views

Is {(1, 1), (2, 2)} symmetric and/or antisymmetric?

For relation $$\left\{(1, 1),(2, 2)\right\}$$ decide whether it is symmetric, whether it is antisymmetric, and whether it is transitive?
2
votes
2answers
38 views

Maximum number of relations?

The question is that we have to prove that if $A$ has $m$ elements and $B$ has $n$ elements, then there are $2^{mn}$ different relations from A to B. Now I know that a relation $R$ from $A$ to $B$ is ...
4
votes
1answer
26 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 := ...
0
votes
2answers
29 views

Showing $(a,b) \sim (c,d)$ iff $a+d=b+c$ is transitive on $\mathbb{N}$

I am given: $a,b,c,d \in \mathbb{N}$, $a \neq c$, and $b \neq d$. The relation $\sim$ on $\mathbb{N}\times\mathbb{N}$ is defined by $(a, b) \sim (c, d)$ iff $a+d=b+c$ for all $(a,b), (c,d) \in ...
0
votes
1answer
22 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 ...
1
vote
1answer
47 views

Relations on the set of Real Numbers

I need a relation on ℝ that is neither reflexive, nor symmetric, nor transitive. I thought of a ~ b where a=b²+1 (mostly) Not reflexive because: a² ≠ a² + 1 (mostly) Not ...
0
votes
1answer
16 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
20 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 ...
0
votes
1answer
11 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) ...
1
vote
2answers
31 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
16 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
2
votes
0answers
30 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 ...
2
votes
2answers
19 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).
7
votes
4answers
8k views

Transitive Relations

For example, $$R = \{ (1,1),(1,2),(2,1),(2,2) \} \quad\text{for}\quad A = \{1,2,3\}.$$ This relation is symmetric and transitive. I understand that the relation is symmetric, but my brain does not ...
1
vote
2answers
34 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'$ ...
0
votes
0answers
6 views

symmetric composed with transitive closure [closed]

I am working on a problem that says I need to prove that with a relation R: prove the symmetric-closure(transitive-closure(R)) is a subset of transitive-closure(symmetric-closure(R)). Any help would ...
0
votes
3answers
28 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
2answers
48 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 ...
0
votes
1answer
18 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), ...
1
vote
2answers
18 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
1answer
21 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 ...
0
votes
0answers
17 views

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

Let R be the relation on natural numbers defined by (a,b) $\in$ R iff 2|(a+b) show it is transitive.
1
vote
2answers
36 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 ...
1
vote
3answers
33 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
15 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
17 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 ...
-3
votes
2answers
36 views

How to find $R^2$ given $S$ and $R$.

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
2answers
31 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. ...
1
vote
0answers
37 views
0
votes
1answer
42 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 ...
0
votes
1answer
47 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
0answers
55 views

Prove the following properties of binary relations

I'm so confused and don't have a clue what I'm doing anymore so any help would be great thanks, I have to Prove the following properties of binary relations. 1 ◦ R = R R ◦ (S ∪ T) = R ◦ S ∪ R ◦ T R ...
0
votes
1answer
15 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 ...
0
votes
1answer
45 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 and $n$ is odd. Further the elements of ...
-1
votes
0answers
29 views

Defining miscellaneous products in a miscellaneous mathematical structure

This is a question about elementary sets, functions and relations, and about a functor $F$ that maps functions $f\subseteq X\times Y$ to relations $F(f)\subseteq F(X)\times F(Y)$. The miscellaneous ...
1
vote
2answers
31 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 ...
0
votes
1answer
23 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 ...
2
votes
1answer
40 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. ...
0
votes
1answer
23 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
104 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. ...
10
votes
3answers
505 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
50 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
468 views

Difference between Reflexive and Symmetric in Discrete Maths

Difference between Reflexive and Symmetric in Discrete Maths? This is what I understand: Reflexive -> <a,a=a>, <b,b=b> uses ...
0
votes
2answers
42 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$ ...
2
votes
2answers
74 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 ...
1
vote
0answers
29 views

Does R(5,7) hold or not in this relation?

This is the question: Let $A=\{1,...,7\}$ and let $R\subseteq A\times A$ be a relation which is symmetric and transitive. You have been given some partial information about the relation which is ...
1
vote
3answers
74 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