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

Proving that a relation is acyclic

Let $S$ be the set of triples of positive numbers $(x,y,s)$. Let $R$ be a directed relation defined between triples, such that $R(b,a)$ if at least one of the following four conditions hold: ...
0
votes
1answer
17 views

Relations and functions class $11$ [on hold]

Let f be a function defined by $f:x\to 5 x^2+2; x \in \mathbb R$. i) Find the image of $3$ under $f$ ii) Find $f(3).f(2)$ iii) Find $x$ such that $f(x)=22$ I don't even know how to do it. Answers: ...
2
votes
1answer
63 views

Is there a name for this property: If $a\sim b$ and $c\sim b$ then $a\sim c$?

Let $X$ be a set with a binary relation $\sim$, such that for all $a$, $b$, and $c$ in $X$: If $a\sim b$ and $c\sim b$ then $a\sim c$ Is anyone familiar with this property of a binary relation? ...
0
votes
2answers
19 views

Bijection of a function.

Define the function f: $(2,\infty) -> (-\infty,-1)$ by $f(x)= \frac{-x}{x-2}$. Show that f is bijective. I know i need to prove both injective and surjective, and I was able to solve the equation ...
0
votes
0answers
9 views

How to proove these properties of compositions of relations?

From wikipedia: If R and S are injective, then S ∘ R is injective, which conversely implies only the injectivity of R. If R and S are surjective, then S ∘ R is surjective, which conversely implies ...
0
votes
0answers
15 views

unifying latitude and longitude into single digit finding equation

I am trying to convert a latitude,longitude into a single point using the midpoint formula while still being able to do a radius search around that point. The midpoint formula is wrong for this ...
0
votes
1answer
29 views

Give an example of a relation R on $A^2$ which is reflexive, symmetric, and not transitive

I am just looking for some clarification on this exercise: Let $A = \{a,b,c,d\}$. Give an example of a relation $R$ on $A^2$ which is reflexive, symmetric, and not transitive. I understand that if I ...
1
vote
1answer
24 views

Symmetric relation , why are these symmetric?

$R_1 = \{(a,b)$ such that $a \leq b \}$ $R_2 = \{(a,b)$ such that $a>b \}$ $R_3 = \{(a,b)$ such that $a=b$ or $a=-b \}$ $R_4 = \{(a,b)$ such that $a=b \}$ $R_5 = \{(a,b)$ such that $a=1+b \}$ ...
0
votes
1answer
20 views

linear algebra equivalence relation

In the set of the integers Z, given a positive number m, we define $ \sim = \lbrace (x1,x2) | x1-x2 = m z, z \in Z \rbrace $ Proof that ~ is an equivalence relation. How many equivalence classes does ...
0
votes
1answer
50 views

Proving a relation is transitive

I am trying to understand transitive relations. I understand given that a set may have $\{(a,b)(b,c)\}$ it must contain $(a,c)$ for it to be transitive. But for longer sets I am getting confused in ...
1
vote
1answer
22 views

Is a relation induced by a partition always an equivalence relation?

Is a relation induced by a partition always an equivalence relation? I'm having some serious trouble understanding this concept and I was wondering if this is true.
1
vote
1answer
19 views

Proving a relation is a total order relation

Consider question #21 part a: Here is the solution: However, consider the definition of a total order relation: The solution didn't prove that the relation is a partial order relation. This ...
1
vote
1answer
25 views

Prove that if the relation (R) is symmetric and antisymmetric on the set X, there exists a Y subset of X such that R is the = relation on Y.

Prove that for any relation R on a set X that is both symmetric and antisymmetric, there is subset Y \subseteq X for which R is the relation = on Y. I will tell you what I know. I know that ...
1
vote
2answers
27 views

Lattice from Preorder

I have seen many examples defining a lattice over a partially ordered set $(P, \sqsubseteq)$ together with a greatest lower bound $\sqcap$, a least upper bound $\sqcup$ and a top $\top$, and bottom ...
0
votes
2answers
21 views

equivalence relation on a set $\{a,b,c\}$

Calculation of total no. of equivalence relation can be defined on a set containing $\{a,b,c\}$ $\bf{Solution::}$ A relation is said to be equivalence, If it satisfy the following relation: $(1)$ It ...
0
votes
1answer
21 views

Binary relations on a set

I have a homework problem that asks this... a) List all the different binary relations on the set $\{0,1\}$ I assume that since the relation is not given then the answer must be the graph, or ...
0
votes
1answer
11 views

How to count the number of distinct equivalence classes for a relation involving truth tables?

I am having trouble with question 22 part (2): Here is the solution: How did the author know that there are 256 distinct equivalence classes? Where did they get $2^8$ from?
-1
votes
0answers
22 views

integral of product of functions

How do we prove that $\int f(x)g(x) dx \le (\int f^2(x)dx)^{1/2}(\int g^2(x)dx)^{1/2}$ both functions are positive and between $[0,1]$
1
vote
2answers
34 views

Find the value of $x$ for which $ff=gf$.

Functions $f$ and $g$ are defined by $f:x \mapsto \frac{1}{2x+1}$, $x \neq \frac{-1}{2}$ and $g:x \mapsto x+1$. Find the value of $x$ for which $ff=gf$. So I started in this way: $f[f(x)]=g[f(x)]$ ...
-3
votes
0answers
19 views

Relations and Functions

I want to know the basics of relations and functions can some one please solve a couple of problems to make me understand what it is. I have gathered some stuff on it Relation can be used to ...
0
votes
0answers
21 views

Relations basics

I need help explaining some of the properties of sets. Suppose you're given three sets A, B, C with A = {z, y, d}, B= {a, x, z, d} and C = 0. How many elements are there in AxBxC? The answer ...
1
vote
1answer
32 views

Find the fuction $g$.

If $f:x \mapsto x^2 + 3$, find function $g$ such that $gf:x \mapsto 2x^2 + 3$. I don't know how to do it, there is no such example in my book. Help?
0
votes
2answers
9 views

Finding the present property

For each relation, determine which of these properties are present: reflexivity, symmetry, antisymmetry, and transitivity: I know the definitions of each of the properties but unclear as to how to ...
1
vote
0answers
17 views

What does a null relation on all real numbers look like?

I'm being asked to test for reflexivity, symmetry, transitivity, and antisymmetry on a null relation for all real numbers, i.e. $X=\mathbb{R}; R = \emptyset $. What would such a resulting set look ...
0
votes
0answers
25 views

Combinatorics of relations

Let A = {1,2,3}. Find the total number of relations on A that are both symmetric and transitive. I know that there are 64 symmetric relations, but how can I find out of those how many are transitive ...
0
votes
0answers
15 views

Is this a Partial Order relation?

Doing some review for my exam. Here is a sample question: Find the partial order relation on {1,2,3} that contains (1,2) and (2,3). My attempt: R: { (1,2), (2,3), (1,3), (1,1), (2,2), (3,3) } ...
0
votes
1answer
14 views

Is this relation transitive?

R: { (1,1), (1,3), (2,2), (3,1) } My answer is no. My logic is that If (3,1) is in the relation, and (1,3) is in the relation, that implies that (3,3) must also be in the relation. Just wanted to ...
0
votes
2answers
10 views

Find a relation over $P(${$1,2,3$}$)$ such that $|R|=12$ and the transitive closure of $R$ is the proper subset relation

I'm having trouble finding relation $R$ over $P(${$1,2,3$}$)$ such that $|R|=12$ and the transitive closure of $R$ is $T$, the proper subset relation over $P(${$1,2,3$}$)$. My thoughts: a pair of ...
0
votes
1answer
24 views

Find the transitive closure of {$(1,2),(2,3),(4,4),(5,4),(5,7)$}

I want to find the transitive closure of $R=${$(1,2),(2,3),(4,4),(5,4),(5,7)$}. I'm having trouble with transitive closure. We have that $(1,2)$ and $(2,3)$, so the transitive closure of $R$ is $R ∪ $ ...
0
votes
1answer
42 views

How many symmetric and transitive relations are there on ${1,2,3}$?

I'm trying to count the number of relations on ${1,2,3}$ that are symmetric and transitive. I know how to count the symmetric relations but I can't seem to find the method for this one. I've counted ...
0
votes
1answer
24 views

State the range of the function below.

Sketch the graph of $f:x \mapsto -4x + 5$ , $x<2$ and state the range. I got the graph, but can't state the range...how to find them?
0
votes
0answers
25 views

Draw arrow diagram to show the following function.

Draw arrow diagram with two parallel lines to show the function $f:x \mapsto 3 - 2x^2$. Let the domain be the set of integers and draw six arrows for the function. How to draw it?
0
votes
1answer
31 views

Proving equivalence relations in special symbols

For a function $f: A\to B$, I have a relation $@$ on $A$ described by $(\forall x,y \in A)\quad x @ y \Leftrightarrow f(x) + f(y)$ Is there any way to show that $@$ is an equivalence relation?
0
votes
1answer
31 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. ...
0
votes
0answers
24 views

Prove that this partial order relation is a chain with infinite length.

The natural numbers are denoted as a divisibility partial order prove that this relation is a chain with infinite length.
1
vote
1answer
53 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
33 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
42 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 ...
1
vote
1answer
56 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
21 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
30 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
39 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
1answer
42 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
66 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
30 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 ...
0
votes
0answers
26 views

Prove congruence 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 ...
2
votes
1answer
38 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
57 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 ...
1
vote
1answer
47 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 ...
2
votes
1answer
41 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 ...