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

1
vote
1answer
16 views

Proving projection map is onto

Let $X$ be a nonempty set and let $R$ be an equivalence relation on $X.$ Given $X/R={[a]:a \in X}$. Prove that there is a map called the projection where $p_x:X\to X/R$ given by $p_x(t)=[t].$ Then ...
0
votes
0answers
20 views

Any hint for the last part of the proof on partial order equivalence?

I wanted to ask you, whether you can tell me how to continue or not. The question was the following: Let A be a set with the partial order ≤.Proof the equivalence of: (1) {(w,z) | w=z ˅ (w !≤ z ˄ ...
3
votes
2answers
39 views

Definition of totality in relations

I see two apparently different definitions for totality which don't seem to be equivalent. Definition 1. A relation $R \subset X \times Y$ is total if it associates to every $x \in X$ at least one $y ...
3
votes
1answer
32 views

Why is x=1 not reflexive? (or determining the properties of reflexive relations)

I have a question that I got wrong in my homework and I am having trouble understanding. It says "Determine whether the relation R on the set of all real numbers is reflexive, sym- metric, ...
1
vote
1answer
47 views

Is it true that the relation |A| < |B| is a sufficient condition for claiming that $f$ is a bijection?

This is an exercise of an assignment I have: Suppose $A$ and $B$ are finite sets and $f\colon A\to B$ is surjective. Is it true that the relation “$|A| < |B|$” is a sufficient condition for ...
0
votes
1answer
41 views

What is at the difference bijection and equinumerous?

I have to explain what a bijection function is, but it seems that equinumerous is a synonym for bijection. Is that correct?
0
votes
1answer
32 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 ...
0
votes
1answer
37 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?
3
votes
0answers
50 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 ...
2
votes
2answers
39 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 ...
1
vote
1answer
48 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
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 ...
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 ...
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
18 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
12 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
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).
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'$ ...
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 ...
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
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), ...
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 ...
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
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.
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 ...
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 ...
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. ...
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 ...
-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
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 ...
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 ...
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. ...
1
vote
0answers
38 views

Real life example of relations with various combination of properties

Attempted a set of questions as below: ...
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 ...
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
506 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), ...
0
votes
2answers
45 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
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
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
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 ...
0
votes
1answer
16 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, ...