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

Relation symmetric reflexive or transitive

Let the relation $\mathbb{R}$ defined on the set $A= \left \{ 1,2,4,6... \right \}$ by $x\mathbb{R}y$ iff $x$ and $y$ have a common factor other than 1. Then the relation $\mathbb{R}$ is symmetric? ...
1
vote
1answer
13 views

Hasse diagrams for sorts of size 3 and 4?

Does anyone know what does the following mean? I understand that a Hasse diagram represents a given partial order but I don't seem to get this example. Below is a Hasse diagrams for sorts of size 3 ...
0
votes
1answer
16 views

What is the reflexive closure of the empty relation ∅ over a set A?

What is the reflexive closure of the empty relation ∅ over a set A? I understand that R is reflexive if A=∅, and isn't if A is nonempty. But what about the reflexive closure of R?
0
votes
1answer
23 views

Transivity / Binary relation? [on hold]

Discuss the Transitivity of Binary Relations $\mathcal{S} $ $a$ on $\Bbb R $ defined by $a (x, y)$ $\in \Bbb R^2 $--> $x \leq ay$ ( for some a $ \in \Bbb R$ ) I have this assignment about ...
-2
votes
1answer
31 views

Recurrence relation general solutions [closed]

how would I go about tackling this kind of question? I'm struggling with the concept of recurrence relations. Any advice would be apreciated. Find the general solution of each of the following ...
1
vote
2answers
29 views

Where is the transistivity in this equivalence relation

The following set has been given: $A = \{1,2,3\}$, and the following relation on $A$ has been given: $S = \{(1,1),(2,1),(1,2),(2,2),(3,3)\}$. The answer says this is a valid equivalence relation. I ...
0
votes
1answer
20 views

Antisymmetric relation between two transitive relations

My task is the following: elements in set A: {a,b,c,d,e,f} relations between them: {(a,b),(b,f),(c,b),(c,d),(d,e),(e,a),(f,d),(f,e)} Question is, is the relation between them antisymmetric and ...
0
votes
0answers
27 views

Prove the relation $R = \{(x,y)\in \mathbb{R} \times \mathbb{R}: \text{ |x|< |y| or x=y} \}$ is antisymmetric.

Prove the relation $R = \{(x,y)\in \mathbb{R} \times \mathbb{R}: \text{ } |x|< |y|\text{ or $x=y$} \}$ is antisymmetric. Proof: Suppose $ x R y$ and $ yRx $. Then $|x|<|y|$ or $x=y$. ...
1
vote
1answer
31 views

Is the following relation a partial order?

Is the relation $R$ on $A=$ the set of all word of English, defined by $R=\{(x,y)\in A\times A: $ the first letter of the word $y$ occurs at least as late in the alphabet as the first letter of the ...
0
votes
0answers
10 views

Give an example showing Ran(R1 ∩ R2) ⊆ Ran(R1) ∩ Ran(R2) may not hold as an equality.

I have managed to prove Ran(R1 ∩ R2) ⊆ Ran(R1) ∩ Ran(R2), but I am having trouble finding an example that shows it doesn't hold as an equality.
1
vote
1answer
188 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 ...
2
votes
1answer
24 views

How many transitive and symetric relations that are not equivalence are in a set of $n$ elements?

I have a Set $S$, $|S|=n$, and I need to count how many symetric and transitive relations are in $S$ that are not equivalence relations. I know how to count equivalence relations (Bell number) but I ...
-3
votes
2answers
25 views

Why is this relation $R=\{ (a,b), (b,c), (a,c) \}$ transitive? [closed]

I am confused here. For the set $\{ a, b, c\}$ how is the relation $\{(a, b), (b, c), (a, c)\}$ transitive ?
0
votes
3answers
24 views

Prove transitivity or not of some relation

I'm trying to prove if this equation is an equivalence relation or not. $R =\{(x,y) \in N\times N: \mbox{There exist }m,n \in N\mbox{ such that } x^m = y^n\}$ It's relatively easy to prove both ...
1
vote
1answer
26 views

Interpreting a first order sentence

I've been given this first order sentence with a binary relation symbol $R$: $\forall x \exists y (R(x, y) \land \forall z(R(x, z) \implies (R(y, z) \land (y=z)) ) $ We are then given two ...
0
votes
1answer
450 views

Equivalence Relations On a Set of All Functions From $\mathbb{Z} to $\mathbb{Z}$

The question is, "Which of these relations on the set of all functions from $\mathbb{Z}$ to $\mathbb{Z}$ are equivalence relations. $\{(f,g)|f(1)=g(1)\}$ I just want to make certain that I am ...
1
vote
1answer
36 views

What is the term for relation whose inversion is a function?

Do we have a conventional term/name for such a relation $R$ (which is not necessarily a function) that $R^{-1}$ is a function? If not, what are your suggestions?
-1
votes
1answer
15 views

How do we show that $A$ is polynomial time reducible to itself? [duplicate]

How do we show that $A$ is polynomial time reducible to itself, i.e. that $A \le_p A$? I know how to prove that it is transitive, but I don't know how to prove it's reflexive. I'm aware that it's ...
2
votes
1answer
31 views

Why is this function well definded?

I have to take a look at the relation of $ x \sim y: \Leftrightarrow \exists k \in \mathbb{Z} : x-y=5k$ in $\mathbb{Z}$. I have no idea how to show at $\mathbb{Z} / \sim$ that the addition is well ...
0
votes
1answer
31 views

How to derive relationship between two functions

I have two functions: $f(x) = x^2 + 200$ $g(x) = (x + 8)^2$ I am interested in the relationship between the two functions in the region between the two minimums (from x = -8 to x = 0), which ...
1
vote
1answer
22 views

Let $A$ be a finite set and $\mathcal R$ an equivalence relation in A. Prove that exists a function …

Let $A$ be a finite set and $\mathcal R$ an equivalence relation in A. Prove that exists a function $f: A \to \Bbb N$ such that $\forall a, b \in A$ the following is true: $$a \mathcal R b \iff f(a) = ...
1
vote
0answers
38 views

Set of functions is not a bifunctor on Rel [migrated]

Let Rel be the category whose objects are sets and whose morphisms are binary relations, with composition defined by $x (S \circ R) z \Leftrightarrow (\exists y : x R y \wedge y S z)$, and identity ...
1
vote
1answer
20 views

Solution check. How many relations of equivalence $R$ are there in $\Bbb N$ that verify silmultaneously the following properties.

I'm revising some old psets while preparing an exam and going through some things that I left unverified. How many relations of equivalence $R$ are there in $\Bbb N$ that verify silmultaneously the ...
0
votes
1answer
34 views

Relations and functionss

I am unsure how to do this, is it possible someone could give me a step by step guide so I can have a good understanding of it. f(x) and g(x) are defined over the real number set R as follows: $g(x) ...
2
votes
1answer
32 views

Count a Partial Equivalence Relations on a set

A Partial Equivalence Relation is a relation that is symmetric and transitive, and to count the number of equivalence relations on a set exists Bell Numbers, my question is How I can count the number ...
1
vote
1answer
13 views

Let $H = \{2^m : m \in \mathbb{Z}\}$ & define a relation $R$ on the set $\mathbb{Q^{+}}$ of positive rationals by $a\mathbin{R}b$ iff $a/b \in H$.

Let $H = \{2^m : m \in \mathbb{Z}\}$ and define a relation $R$ on the set $\mathbb{Q^{+}}$ of positive rational numbers by $a\mathbin{R}b$ if and only if $a/b \in H$. Prove that $R$ is an equivalence ...
1
vote
0answers
28 views

Symmetry of a relation

Let $A\neq\emptyset$ and $\mathcal{R}\subset A\times A$ a binary relation on $A$ such that the domain $D(A):=\{x\in A\mid \exists y\in A \text{ such that }(x,y)\in\mathcal{R}\}=A$ and ...
1
vote
1answer
78 views

How do you pronounce $\preceq$?

I've been reading about partial orders and partially ordered sets and have come across sentences like "Suppose that $\preceq$ is a partial order on $X$" and "If $x\preceq y$ and $y \preceq z$ then $x ...
-2
votes
0answers
19 views

how to do such type of R&F? [duplicate]

the number of functions f from {1,2,...20} onto {1,2,...20} such that f(k) is a multiple of 3 whenever k is a multiple of 4 is
0
votes
0answers
12 views

Let $A$ be a nonempty set. Prove that if $S$ and $R$ are equivalence relations on $A$, then $S \cup R$ is both reflexive and symmetric.

Let $A$ be a nonempty set. Prove that if $S$ and $R$ are equivalence relations on $A$, then $S \cup R$ is both reflexive and symmetric. My method: Let $x \in A$ be given. Then $x \in S$ or $x \in ...
3
votes
2answers
29 views

A relation $R$ is defined on $\mathbb{Z}$ by $aRb$ if and only if $2a + 2b\equiv 0\pmod 4$. Prove that $R$ is an equivalence relation.

A relation $R$ is defined on $\mathbb{Z}$ by $aRb$ if and only if $2a + 2b\equiv 0\pmod 4$. Prove that $R$ is an equivalence relation. My method: Let $a \in \mathbb{Z}$ be given. So, for any $a \in ...
1
vote
0answers
15 views

Let A be a set with $\lvert A \rvert$ = $4$. What is the max number of elements tht a relation R on A can contain so tht $R \cap R^{-1}$ = $\emptyset$

Let A be a set with $\lvert A \rvert$ = $4$. What is the maximum number of elements that a relation R on A can contain so that $R \cap R^{-1}$ = $\emptyset$? I am not sure at all how to start this ...
0
votes
1answer
14 views

Let A be the set of U. S. states. One example of a relation on A is $R = [(s,t) : s = t or s shares a border with t].

Let A be the set of U. S. states. One example of a relation on A is R = {(s,t) : s = t or s shares a border with t}. Notice that the domain of R is A, and the range of R is A. Give a different ...
0
votes
0answers
13 views

Determine whether the following relation is reflexive, symmetric, antisymmetric and/or transitive?

Q is defined on P(N) by aQb iff |a ∩ b| ≥ 2. I've concluded that it's symmetric, not reflexive, not antisymmetric and not transitive. Is this right?
0
votes
1answer
16 views

Relation that is reflexive, transitive, but not antisymmetric

A = {1,2} R = {(1,2)} I was just wondering if this relation meets the criteria.
1
vote
1answer
39 views

Are R,S and T equivalence relation or partial order relation?

Let $R$, $S$ and $T$ be binary relations defined as follows R is defined on $P(\mathbb{N})$ by $ARB$ if and only if $|A∩B| ≥ 2$ $S$ is defined on $Q$ by $x\mathbin{S}y$ if and only if $|x|=|y|$. ...
0
votes
1answer
21 views

What is the difference between partial order relations and equivalence relations?

From googling it i understood that a relation is both partial order relation and equivalence relation when they are reflexive, symmetric and transitive. So it appears they are the same. But as far I ...
0
votes
2answers
36 views

How to tell if the relations R, S and T are reflexive, symmetric, anti-symmetric or and transitive?

Let $R$, $S$ and $T$ be binary relations defined as follows R is defined on $P(\mathbb{N})$ by $ARB$ if and only if $|A∪B| ≥ 2$ $S$ is defined on $Q$ by $xSy$ if and only if |$x$|=|$y$|. (Note that ...
0
votes
1answer
28 views

What is the difference between total order relations and well order relations?

I know it has to be a partial order relation in order for it to be a well order relation or total order relation, but what are the differences between them.
0
votes
0answers
16 views

Determine whether this relation is reflexive, symmetric, antisymmetric and/or transitive?

R is defined on N × N (where N are natural numbers) by (a, b)R(c, d) iff a ≤ c and b ≤ d. I think it's reflexive and transitive. Not too sure about it being symmetric or antisymmetric. Any help ...
1
vote
1answer
20 views

Write out relation from a function

I have this problem: "Let $R$ be a binary relation $(x,y)\in R$ if and only if $f(x) = f(y)$ where $f: \{a, b, c, d\} \rightarrow \{0, 1\}$ given by $f(a) = 0$, $f(b) = 1$, $f(c) = 0$, $f(d) = 0$ ...
1
vote
1answer
641 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 ...
2
votes
1answer
44 views

Functions: Relations

I'm stuck on this question and would appreciate the solution, thanks! Let $R$ and $S$ be the relations on $A = \{1,2,3,4,5\}$ given by$$R = ...
6
votes
5answers
22k views

Antisymmetric Relations

Given a set $\{1,2,3,4\}$, how is the following relation $R$ antisymmetric? $$R = \{(1, 2), (2, 3), (3, 4)\}$$ Note: Antisymmetric is the idea that if $(a,b)$ is in $R$ and $(b,a)$ is in $R$, then ...
0
votes
2answers
29 views

Prove by contradiction that If $R$ is a transitive relation on set $A$ then $R^2$ is transitive.

I saw this problem and read through it but I am still kind of confused as to what $u_1$ and $u_2$ stand for. Prove by contradiction that for a transitive relation $R$ on $A$, $R^2$ is also transitive ...
0
votes
2answers
36 views

Equivalence relation and equivalence classes given function and relation

Given a function $f : A → B$, let $R$ be the relation defined on $A$ by $aRa′$ whenever $f(a) = f(a′)$. Prove that $R$ is an equivalence relation and determine the equivalence classes. To prove that ...
0
votes
0answers
30 views

Which of the following are equivalence classes?

For example 37, I've determined which ones are equivalence relations but am having trouble on example 37: 1-7 determining which of the following are equivalence classes. I'm having trouble ...
1
vote
0answers
13 views

Symmetric and reflexive closure on positive integers

Finding the symmetric and reflexive closure of the relation $R = \{(a, b) | a > b\}$ on the set of positive integers. For symmetric closure I have: $R = \{(a, b) | a > b\} U \{(b, a) | a > ...
0
votes
1answer
21 views

Finding equivalence classes in a set of functions with a condition

I can't seem to work around this problem... Let $n$ and $m$ be two positive integers. $F$ is the set of functions from {1,..,n} to {1,...,m}. We define the relation $R$ as: $f R g$ if and only if ...