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
votes
1answer
18 views

binary relation prove

im studying for a test and theres are some questions that ive tried and i dont understand. A) $E$ is a binary relation on group $A$. binary realation $F$ is on group $P(A)$ \ $\{\phi\}$ as: ...
0
votes
0answers
31 views

Definition of fixed point free relation

If we have such relation that for $\forall x$ $f(x)\ne x$ , how is it called in one word? I can come up with only "graph of this function is not a straight line:)" Thank you
0
votes
1answer
18 views

Proving that divisibility in an integral domain is a partial ordering

Given that R is an integral domain. I'm trying to prove that divisibility on this set constitutes a partial ordering. In particular, I have defined the relation $y \leq_{\,d} x$ on R by $y|x$. ...
0
votes
3answers
137 views

Prove or Counter example.For all nonempty sets $A$ and $B$ and for all functions $F: A \to B$, $F(A-B) = F(A) - F(B)$

Prove or counter-example. For all nonempty sets $A$ and $B$ and for all functions $F$, $F(A-B) = F(A) - F(B)$ I am pretty lost on this question. I don't feel like its right since it would be a ...
0
votes
1answer
25 views

Denotation of composite of relations

We denote the composite of relation R and relation S by $S \circ R$. Since the order matters, meaning composite of R and S is not composite of S and R. I am trying to understand why the denotation of ...
1
vote
1answer
1k views

Antisymmetric and irreflexive relation which is not asymmetric

Can anyone give me a counterexample for a relation $R\subset M\times M$ for the statement $$R\text{ antisymmetric} \wedge R\text{ not reflexive}\implies R\text{ asymmetric}$$
8
votes
6answers
4k views

How do the Properties of Relations work?

This is simply not clicking for me. I'm currently learning math during the summer vacation and I'm on the chapter for relations and functions. There are five properties for a relation: Reflexive - ...
0
votes
1answer
22 views

What is the composition of the two given relations $R_1\circ R_2$?

I have a set $A = \{a,b,c,d\}$ on which two relations are $R_1=\{(a,b),(a,d),(b,c),(c,a),(c,d),(d,b)\}$ and $R_2=\{(a,b),(b,c),(d,c),(a,d),(a,c)\}$. What will $R_1\circ R_2$ be? $\circ$ is a the ...
0
votes
1answer
60 views

Associativity of compositions of relations

Prove that given relations $R_1 \subseteq A \times B$, $R_2 \subseteq B \times C$, $R_3 \subseteq C \times D$ then $(R_1 \circ R_2) \circ R_3 = R_1 \circ (R_2 \circ R_3)$ I don't know where ...
2
votes
1answer
34 views

How do i determine whether a relationship is transitive and has the trichotomy property or not?

I have a relation on the set A {a,b,c,d}- R1={(d,c),(c,a),(b,d),(d,a),(a,a),(b,c),(b,a)} I need to determine whether this relation has the trichotomy property or not? P.S- If by any chance you do ...
1
vote
2answers
29 views

Is the relation $P$, for all real numbers $x$ and $y$ that satisfy $xPy $ iff $x^3 - y \ge y^3 - x$, a reflexive, symmetric and transitive relation?

Image of an exam question I am revising link: [1] For (i) I have stated the relation is reflexive as $\forall x ∈ \Bbb R, xPx$ is reflexive as $x^3 \ge x $ For (ii) I have stated that the relation ...
3
votes
4answers
81 views

Show that $R = \{ (x,y) \in \mathbb{Z} \times \mathbb{Z} : 4 \mid(5x+3y)\}$ is an equivalence relation.

Let $R$ be a relation on $\mathbb{Z}$ defined by $$ R = \{ (x,y) \in \mathbb{Z} \times \mathbb{Z} : 4 \mid (5x+3y)\}.$$ Show that $R$ is an equivalence relation. I'm having a bit of trouble ...
2
votes
1answer
22 views

Graph the straight line corresponding to the rule (y=7x) for 0≤x≤15

I have attempted this question but I don't really know where to even start. I have graphed y=7x but i'm not sure where to go from there. I am a bit stuck on graphing a line that is relating to 0≤x≤15. ...
0
votes
1answer
20 views

Calculate the number of equivalence classes [closed]

Let $A = \{1,2,3,4,5,6\}$ and let $B = \{1,2,3\}$ Let $R$ be a relation such that $R=\{(x,y) \in P(A) \times P(A): x \cap B = y\cap B\}$ How many equivalence classes are possible? I'm kinda stuck ...
0
votes
3answers
85 views

Compute equivalence classes of equivalence relation

I have already proven that the relation $R=\{(x,y) \in \mathbb Z \times \mathbb Z \mid x+y\text{ is even}\}$ is an equivalence relation by showing reflexive, symmetric, and transitive properties of ...
0
votes
1answer
23 views

Given two Numbers, Finding Relation to third

I'm trying to find the relation of three numbers. I know that two numbers have a relation that equate to the third. The tricky part is that they don't have to equal the third number exactly,but should ...
1
vote
1answer
29 views

Relation $ (x,y) \in \rho \Leftrightarrow (\exists k \in \mathbb{Z})\mid x- y=3k$

I know that there is a similar question here, but it's about classes of equivalence of this relation. I would like to know how to prove that this is an equivalence relation. It seems simple, but the ...
0
votes
1answer
106 views

Relation on rational numbers that defines a total order

Define the relation on $\mathbb{Q}$ by $$[m,n]<[j,k]$$ if and only if $jn-mk$ belongs to $\mathbb{N}$, $j$ and $m$ belong to $\mathbb{Z}$, $n$ and $k$ belong to $\mathbb{N}$. (a) Show that ...
1
vote
2answers
24 views

How to find all relations of a set and determine which of them aren't functions?

Given the following question: "How many relations are there on {2, 3}, that aren't functions from {2, 3} to {2, 3}?" The answer gives 16 relations, of which 12 aren't functions. How did they ...
0
votes
1answer
19 views

How many reflexive relations on $P(A)$

There exist a set $A = \{1,2,3\}$. How many reflexive relations are there on $P(A)$? I don't even know how to begin (beside writting down the members of $P(A)$). Thank you
1
vote
1answer
35 views

What is the growth relationship of the number of digits a number has as numbers increase?

To clarify the question, since I'm sure the wording is awkward: In the decimal number system, to get from 1 digit to 2, it takes n=10 numbers. To get from 2 to 3, it takes 90 more numbers added to n. ...
1
vote
1answer
24 views

Calculate the number of equivalence relations $S$ that satisfies $R \subseteq S$

Let $A=\{1,2,3,4,5,6,7,8\}$ and let $R=\{(1,2),(5,4),(4,5),(6,2),(4,4),(6,5),(7,8)\}$ be a relation on A. What it the number of equivalence relations $S$ that satisfies $R \subseteq S$ I know what ...
4
votes
2answers
56 views

why are equivalence relations called so?

"an equivalence relation is the relation that holds between two elements if and only if they are members of the same cell within a set that has been partitioned into cells such that every element of ...
0
votes
1answer
16 views

Is this relation symmetric?

While solving questions related to reflexivity, symmetricity and transivity of relations, I came across this question: Show that the relation $R$ in the set $A = \{1,2,3\}$ given by $R = ...
0
votes
2answers
33 views

Total Number of Equivalence classes of R

I was given the following question for homework: Let P denote the set of all compound propositions involving the simple/atomic propositions p, q, and r and the logical connectives ∨, ∧, and ¬ ...
2
votes
1answer
21 views

If A is the range of $f(x) = ^{7-x}C_x$ then the no. of reflexive relation from A to A is…

Problem : If A is the range of $f(x) = ^{7-x}C_x$ then the no. of reflexive relation from A to A is (a) $2^6$ (b) $2^{12}$ (c) $2^{16}$ (d)$2^{20}$ My approach : $f(x) = ^{7-x}C_x = ...
1
vote
1answer
25 views

Prove that $\sigma^*$ is the least group congruence on $S$

Let $S$ be an inverse semigroup and consider the relation $\sigma$ on $S$ given by $$a \sigma b \iff ab^{-1} \in E(S)$$ Consider the congruence generated by $\sigma$, say $\sigma^*$. Prove that ...
5
votes
5answers
503 views

Example of a relation that is reflexive but not symmetric

By definition, $R$, a relation in a set X, is reflexive if and only if $\forall x\in X$, $x\,R\,x$, and $R$ is symmetric if and only if $x\,R\,y\implies y\,R\,x$. I think $x\,R\,x$ can also be ...
0
votes
1answer
10 views

Are any two pairs in a cyclic path of a transitive relation symmetric?

Suppose $R$ is a transitive binary relation that contains a cycle $a_1Ra_2$, $a_2Ra_3$, $\dots$, $a_{n-1}Ra_n$, $a_nRa_1$. Does this imply that $R$ is symmetric for any pairs in this cycle, i.e. ...
1
vote
1answer
555 views

Classify relations “is greater than or equal to”

Classify the following relations as reflexive, irreflexive, symmetric, antisymmetric or transitive. Explain each property in the context of the question. “is greater than or equal to” on the set of ...
4
votes
3answers
381 views

Proving transitive property

I have been working on this problem from Velleman's How to prove book: Suppose A is a set, and F ⊆ P (A). Let R = {(a, b) ∈ A × A | for every X ⊆ A \ {a, b}, if X ∪ {a} ∈ F then X ∪ {b} ∈ F}. Show ...
1
vote
1answer
27 views

given definition of a relation $R$, prove that $R$ is an Equivalence Relation

The relation is on set $\mathbb{R}^\mathbb{R}$ and the definition of the relation $R$ is: $f \mathop{R} g \iff \exists _{y\in \mathbb{R}} \forall_{x\in \mathbb{R}}\ ((x>y)\to(f(x)-g(x)\in ...
1
vote
2answers
209 views

Partition of Real Numbers

Let R be the set of all real numbers. Is $\{\mathbb R^+,\mathbb R^−,\{0\}\}$ a partition of $\mathbb R$? Explain your answer. My answer is no because of $\{0\}$. I am confused with $\{0\}$. please ...
0
votes
2answers
19 views

Relation of equivalence with sgn

Test if the relation $$(x, y)ρ(a, b)\Leftarrow\Rightarrow sgn(y+\pi x) = sgn(b + \pi a)$$ is a relation of equivalence on $R^2$ and if so, determine the quotient set and $C_{(2, \pi)}$. Also, ...
0
votes
0answers
102 views

Is there any partial order that extends $\delta$?

Let $M = \{(x_n)_{n\ge1} | x_n \in \mathbb Z, \forall n \in \mathbb{N}^{*}\}$ We define relations $\delta$ and $\sim$ on $M$ as: $(x_n)_{n\ge1}\ \delta\ (y_n)_{n\ge1} \iff \forall n \in ...
-1
votes
1answer
34 views

Prove that if a relation R on a set A is reflexive, symmetric and antisymmetric, then $R=I_A$ [closed]

Prove that if a relation $R$ on a set $A$ is reflexive, symmetric and antisymmetric, then $R=I_A$ I know a relation is a set of ordered pairs and that $I_A = (x,x)$ but I have no idea how to do this ...
0
votes
1answer
55 views

Whether Subset of a Power Set is a Lattice?

$A=$ countably infinite set $p(A)=$ power set of $A$ $p(A)$ is uncountably infinite I have this question as book i am using explicitly mentioned it as A:finite set now, poset $(P(A)$,subset) is it ...
1
vote
0answers
39 views

Topology given by a relation

I have a problem with creating an equivalence relation ~ in a set : $ S^{1}\times S^{2}$ so that $ (S^{1}\times S^{2})/$~ (a quotient space of the given relation) is homeomorphic to 3-dimensional ...
2
votes
1answer
77 views

Which of the sets are well ordered? Which ones are isomorphic?

I'm new to StackExchange and I'd like to ask you for help. I have been trying to solve this exercise: $$A = \left\{3 - \frac{1}{2n} : n \in \mathbb{N} - \left\{ 0 \right\} \right\}$$ $$ B = \left\{ ...
-2
votes
1answer
33 views

Compositions of Sets 2 [closed]

Given set A = {a, b, c} relation R = {(a,b),(b,c),(c,a)} relation S = {(a,c),(c,a)} ...
1
vote
1answer
25 views

Relation of divisibility - hasse diagram

$A = \{3,4,5,10,15,20,30,60\}$ Relation $R: \forall x,y \in A : (x,y) \in R \Leftrightarrow y \mid x $ Here is my Hasse diagram Is my Hasse diagram drawn correctly?
5
votes
2answers
668 views

Ordering the field of real rational functions

Perusing the Wikipedia article on ordered fields, I encountered an interesting statement, a variation of which I am now trying to prove. Basically, I am trying to show that the set of real rational ...
2
votes
1answer
408 views

A relation that is Reflexive & Transitive but neither an equivalence nor partial order relation

Set $A = \{0,7,1\}$ 1. So for a relation that is reflexive and transitive but neither an equivalence relation nor partial order...Can a relation be both partial order and equivalence? Attempt: ...
1
vote
5answers
38 views

Proving a relation on Z×(Z-{0}) is an equivalence relation

Question:Let $X=\mathbb{Z}\times(\mathbb{Z}\setminus\{0\})$. Define a relation $\sim$ on $X$ by declaring that $(a, b)\sim(c, d)$ if and only if $ad = bc$ Prove that the relation $\sim$ is an ...
0
votes
0answers
47 views

Relations Question

I have some trouble understanding relatons. Below there is a question that I am working on. I believe that the a) part its correct but I have no idea how to do the b) and c) As part of a computer ...
0
votes
1answer
33 views

Solve the relation with congruence

On $\Bbb Z$ consider the relation $xRy \Leftrightarrow x-y \not\equiv 0 \mod 3$. Prove (with explanation), whether the relation reflexive, symmetric, antisymmetric transitive is and prove if they are ...
3
votes
5answers
491 views

example of a relation that is symmetric and transitive, but not reflexive

Can you give an example of a relation that is symmetric and transitive, but not reflexive? By definition, $R$, a relation in a set X, is reflexive if and only if $\forall x\in X$, $x\,R\,x$. $R$ ...
2
votes
1answer
32 views

Find the domain and image of the relation $R=\{(a, b), (c, b), (a, b)\}$

Let $A={a, b, c}$, and let $R=\{(a, b), (c, b), (a, b)\}$. Find the domain of $R$ and the image of $R$. This would be very elementary, but I want to get my answer checked. Let $R$ be a relation ...
37
votes
3answers
5k views

Why isn't reflexivity redundant in the definition of equivalence relation?

An equivalence relation is defined by three properties: reflexivity, symmetry and transitivity. Doesn't symmetry and transitivity implies reflexivity? Consider the following argument. For any $a$ ...
1
vote
3answers
30 views

Intrepreting tuples as functions

I have been mulling over this for a while now. I am told $\mathbb R^n$ can be interpreted as a set of functions. Take $\mathbb R^2$, for example I can see how we might interpret it as a set containing ...