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

Can someone explain antisymmetric versus symmetric relation of sets?

If $$A = \{1,2,3,4\} $$ and $$R = \{(3,3), (4,4), (1,4)\}$$ This example is antisymmetric but not symmetric. However, the definition of Antisymmetric taken from Merriam-Webster is this: ...
0
votes
0answers
37 views

What is a relation R on a set S? [on hold]

I do not really comprehend the question fully. However, I thought the question is asking about what constitutes a relation on a set S. Hence I could state that a relation R on S is when the three ...
-2
votes
0answers
44 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
14 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
25 views

Transivity / Binary relation? [closed]

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
30 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 ...
1
vote
1answer
35 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
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$. ...
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
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.
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
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
32 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
1answer
27 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 ...
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) ...
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
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
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
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 ...
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 ...
-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
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
14 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
49 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
2answers
37 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
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 ...
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
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 ...
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$ ...
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 = ...
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 > ...
1
vote
2answers
27 views

Counting number of relations that are symmetric and reflexive.

I've looked at the other two problems similair to mine but I'm having a bit of an issue understanding as their solutions seems a bit more complex. While I for the most part understand my professors ...
0
votes
0answers
31 views

Equivalence Relations and Cardinality

I'm looking at the question below from a past paper: What is an equivalence relation? Say that two sets $X$ and $Y$ are related via the relation $\rho$ if $X$ and $Y$ have the same cardinality. Prove ...
-4
votes
1answer
34 views

Let f be the function from $A = \{a, b, c, d\}$ to $B = \{e, f, g, h\}$ given by $f = \{(a,e), (b,f), (c,g), (d,g)\}$. [closed]

Let $f$ be the function from $A = \{a, b, c, d\}$ to $B = \{e, f, g, h\}$ given by $f = \{(a,e), (b,f), (c,g), (d,g)\}$. If $D = \{a,b\}$, what is $f(D)$? If $G = \{f,g\}$, what is $f^{-1}(G)$? If ...
0
votes
1answer
12 views

Confirming my understanding in determining if a relation is reflexive, symmetric, or transitive

I think I have a grasp on how to determine if a relation is reflexive, symmetric, or transitive. Just to make sure I understand it correctly, if I have the following relation: for $(a,b) \in ...