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
2answers
319 views

Trouble determining whether relations are reflexive, symmetric and transitive.

I'm having trouble understanding whether or not relations are reflexive, symmetric and transitive. I know that for a relation to be any of those it must satisfy the conditions: reflexive: for every ...
3
votes
3answers
3k views

Is it possible for a relation to be symmetric, antisymmetric, but NOT reflexive?

If A is a set {2,4,6,8}, and we are asked to give a relation on A that is: symmetric, antisymmetric, but not reflexive, is this possible? If we were to say {(2,2),(4,4)}, it would indeed be ...
0
votes
0answers
67 views

Definition of restriction of relation

let be $\mathcal{R}$ a binary relation on $X$, and $\mathcal{T}$ a binary relation on $Y$, $\mathcal{T}$ is restriction of $\mathcal{R}$ if: 1) $Y \subseteq X$ 2) $\forall a,b \in Y( a T b ...
0
votes
1answer
107 views

Is this poset a lattice?

Given the set $\Bbb Z^+\times\Bbb Z^+$ and the relation $$\begin{align*} (x_1,x_2)\,R\,(y_1,y_2)\iff &(x_1+x_2 < y_1 + y_2)\\ &\text{ OR }(x_1 + x_2 = y_1 + y_2\text{ AND }x_1 \le y_1)\;: ...
1
vote
2answers
174 views

Symmetric relations

Let $A=\{ 1, 2, 3, 4 \}$ is $ B = \{ (1, 2), (2, 1), (1, 3), (3, 1) \} $ Is $B$ a symmetric relation on $A$? I said no because not all $x, y \in A$ are in $B$ Is this correct?
0
votes
1answer
72 views

Proving antisymmetry for this partial ordered set

I need to prove the anti-symmetric property of the following relation (the set is the cross-product of all positive integers). (x1,x2) R (y1,y2) <=> EITHER (x1 + x2 < y1 + y2) OR (x1 + x2 = y1 ...
3
votes
2answers
79 views

Relations and Functions - Is my answer correct?

Could someone please advise if my answer is correct or incorrect? Any help will be greatly appreciated. Given the sets $A = \{1, 2, 3\}$, $B = \{−1, 0, 1, 2\}$ and $C = \{3, 4, 5, 6\}$, indicate the ...
0
votes
1answer
29 views

Double embedding or double restriction

The following generalizes both embedding and restriction for sets $A$ and $B$: $A \rightleftarrows B = ( A ; B ; \operatorname{id}_{A \cap B})$. $A \rightleftarrows B$ is considered as a morphism of ...
0
votes
1answer
43 views

Lower Bounds and Greatest Lower Bounds

Let (a, b),(x, y) ∈ R × R and define ≺ as follows: (a, b) ≺ (c, d) iff a < c or a = c and b < d: Define (a, b) ≼ (c, d) if and only if (a, b) = (c, d) or (a, b) ≺ (c, d). Show that there is a ...
0
votes
0answers
50 views

Embedding vs restriction

Embedding is the morphism $( A ; B ; \operatorname{id}_A)$ of the category $\mathbf{Rel}$ for sets $A \subseteq B$. I call restriction the morphism $( A ; B ; \operatorname{id}_B)$ for sets $A ...
0
votes
1answer
66 views

Properties of Binary Relations (Specifically, transitivity)

Suppose there is a set A = {a, b, c}. A binary relation on A is R0 = {(a, a), (b, b), (c, c)}. I have been told that R0 is a preorder of A but am not seeing how this is possible. How is it ...
1
vote
1answer
362 views

Prove the relation to be a Linear Order.

Let (a, b),(x, y) ∈ R × R and define ≺ as follows: (a, b) ≺ (c, d) iff a < c or a = c and b < d: Define (a, b) ≼ (c, d) if and only if (a, b) = (c, d) or (a, b) ≺ (c, d). Show that ≼ is a ...
2
votes
1answer
51 views

Let $S=\{a,b\}$. Of all the relations on $S$ which are symmetric? Reflexive? Transitive?

The relations are as follows: 1.) $\{(a,a)\}$ 2.) $\{(a,b)\}$ 3.) $\{(b,a)\}$ 4.) $\{(b,b)\}$ 5.) $\{(a,a),(a,b)\}$ 6.) $\{(a,a),(b,a)\}$ 7.) $\{(a,a),(b,b)\}$ 8.) $\{(a,b),(b,a)\}$ 9.) ...
3
votes
3answers
1k views

How to solve recurrence relation: f(n) = f(n-1) + 2(n-1) when f(1) = 1?

I am just learning about recurrence relations, and this is an absolute beginner's question. I understand what's going on in the formula, but I have no clue how to write it's solution? This probably ...
2
votes
1answer
53 views

Can objects repeat in commutative diagrams?

Are objects allowed to repeat in commutative diagrams? This seems to be necessary when representing endomorphisms such as the morphism $f : X \to X$ in the category $\mathbf{Set}$, such as when $f$ is ...
0
votes
0answers
32 views

Restricting binary relations by composing with an “inclusion binary relation”

If $X' \subseteq X$ then we may define an inclusion map $\iota : X' \to X$ where $\iota(x) = x$. One use of $\iota$ is that we can express the restriction of some $f : X \to Y$ to $X'$ as $f|_{X'} = f ...
2
votes
2answers
125 views

Set theory relation: irreflexive and transitive

Which of the following relations on $T = \{1, 2, 3\}$ is irreflexive and transitive. $\{(2, 1), (2, 3)\}$ $\{(1, 1), (2, 1), (3, 2)\}$ $\{(2, 1), (1, 2), (3, 2), (2, 3)\}$ $\{(1, 1), (2, 2), (3, 3), ...
1
vote
1answer
442 views

Antisymmetric Relation

Determine whether the relation R on the set of all people is antisymmetric. (a) a is taller than b. (b) a and b are born on the same day. (c) a has the same first name as b. ...
1
vote
2answers
78 views

“Preimage” of a binary relation

Consider the binary relation $R \subseteq X \times Y$. Is there a standard name and notation for the set $X' = \{x\ |\ (x, y) \in R\}$? ProofWiki calls $X'$ the preimage of $R$, denoted as ...
1
vote
1answer
22 views

Validity of an inequality

Is this relation true ? $\Pi_{i=1}^n v_n \le \left(\frac{\sum_{i=1}^{n} v_n}{n}\right)^n$ Thank you
1
vote
1answer
52 views

discrete mathematics relations question 2

I am a little confused by this relation R3 is a subset of Z×Z defined by (x,y) in the set R3 if and only if x>2y is it reflexive? Symmetric? antisymmetric? or transitive? i say its NOT reflexive ...
1
vote
1answer
177 views

Discrete mathematics Relations Question

if r2 is in the set of N*N ( natural numbers) with (X,y) in the subset of r2, if and only if x+y=0 is it reflexive? is it symmetric? is it anti symmetric? is it Transitive? i said it is reflective ...
-1
votes
1answer
83 views

Show that ≡ is an equivalence relation, Show that ⊕ is well-defined, and Show that ⊕ is a commutative and associative operation.

Let $(a,b),(x,y) \in\Bbb R\times\Bbb R$ and define $(a,b) \equiv (x,y)$ iff $a+b = x+y$. a. Show that $\equiv$ is an equivalence relation. Define the operation $\oplus$ on the equivalence classes as ...
1
vote
1answer
309 views

Antisymmetric and transitive relations in a 2 element set.

I'm supposed to find all antisymmetric and transitive relations in a 2 element set. I have so far:$$ \text{antisymmetric: } (a,b) ;(b,a); (\emptyset); (a,a),(a,b); (a,a),(b,a); (b,b),(a,b); ...
1
vote
1answer
162 views

non-transitive, antisymmetric and reflexive binary relation on $\mathbb Z$

Does anybody know about a reflexive, antisymmetric, but not transitive relation on $\mathbb Z$? I really cant figure any out and I am having doubts that something like that exists.
0
votes
1answer
75 views

Equivalence classes for a Relation on a product set.

How do you determine the the equivalence classes for a relation on a product set? Background: Let $S=\left\{1,2,3,4\right\}$ and $A=S\times S$. The relation $R$ on $A$ can be defined by ...
1
vote
1answer
93 views

Understanding syntax for defining a relation.

Let T = {1, 2, 3, 4} and A = T * T. We can define a relation R on A; (a,b)R(c,d) <=> (a/b)=(c/d) For example: (1,2)R(2,4) since (1/2)=(2/4) Does this mean that ((1,2),(2,4)) ∈ R ...
4
votes
1answer
254 views

Prove a relation is asymmetric.

Prove that if a non-empty relation $R$ on $A$ is transitive and irreflexive, then it is asymmetric. I assume that I need to prove this one by contradiction, but I'm having a hard time wrapping my ...
4
votes
1answer
122 views

$F : \mathbb{Z} \to \mathbb{Z}$, $F(n) = 2 -3n$. Is $F$ one-to-one? Onto?

Define $F : \mathbb{Z} \to \mathbb{Z}$ by the rule $F(n) = 2 -3n$, for all $n \in \mathbb{Z}$. Is $F$ one-to-one? Onto? Now, I understand that one-to-one means that nothing in the co-domain is ...
1
vote
1answer
46 views

Trying to make sure I have this right: Properties of Relations

Can somebody tell me if this is correct? Let's say we are working with the set A = {a, b, c, d} and the relation R comes from A. Reflexive: the relation is reflexive if and only if all of (a, a), ...
0
votes
1answer
17 views

What other statements of this general form can we prove about the direct image function?

Given a relation $R : X \rightarrow Y,$ write $R_* : \mathcal{P}(X) \rightarrow \mathcal{P}(Y)$ for the direct image function defined by asserting that $$b \in R_*(A) \Leftrightarrow \exists a \in A : ...
0
votes
1answer
104 views

algebra, equivalence relation regarding associates

If f(x) ~ g(x) if and only if f and g are associates, prove this is an equivalence relation have tried to prove this both ways, struggling
1
vote
5answers
353 views

Reflexivity: How can something be related to itself?

Background: I'm a philosophy student. I'm comfortable with math, but don't have much of a background in it. One of the topics I'm writing about (I-relation in theories of identity) closely mirrors ...
0
votes
1answer
43 views

Discrete and combinatorial mathematics

Suppose we have a relation on a set $A$, i.e. $A \times A$, where $|A| = n; \;n$ a positive integer. How can we count the number of relations on set $A$ which are reflexive, symmetric, transitive and ...
0
votes
1answer
67 views

Proof on relation

Let $R$ be the relation on $\mathbb{Z}$ such that $(x, y) \in \mathbb{Z}$ iff the difference between $x$ and $y$ is a multiple of 10 a) Provide a general proof that $R$ is symmetric b) Determine one ...
1
vote
1answer
786 views

Proving the symmetry of an equivalence relation

When proving the symmetry of an equivalence relation, must each equivalence class be closed under symmetry. for example: the relation both x and y > 10 or both x and y < 10 across all ...
0
votes
2answers
1k views

How to create a Reflexive-, symmetric-, and transitive closures?

I'm working on a task where I need to find out the reflexive, symmetric and transitive closures of R. Statement is given below: ...
3
votes
1answer
130 views

Relations and transitivity

I am just now starting to grasp the concepts of transitivity in relations and I have the following question: In my textbook, it is noted that $R = \{(1, 1), (1, 2), (2, 1)\}$ is not transitive. ...
0
votes
3answers
115 views

How to show that $ \succ acyclic \implies \succ asymmetric $

For a preference relation defined as $$ \succ := \{ (x,y) \in X\times X : x\ is\ better\ than\ y \}$$ one has to show that $$ \succ acyclic \implies \succ asymmetric $$ whereas $$ acyclic := ...
2
votes
3answers
211 views

$(a,b)R(x,y) \iff ay=bx$ is an equivalence on $\Bbb Z \times (\Bbb Z\setminus\{0\})$ [duplicate]

Define a relation $R$ on $\mathbb{Z}\times(\mathbb{Z}\setminus\{0\})$ by $(a,b)R(x,y)\iff ay=bx.$ $a)$ Prove that $R$ is an equivalence relation. $b)$ Describe the equivalence classes ...
2
votes
1answer
66 views

Is this an equivalence relation?

I think the wording is throwing me off, and I also haven't done math in 4 months so basically my mind is scrambled eggs. Let $\sim$ be a relation on $\Bbb Z$ defined by letting $m \sim n$ if ...
1
vote
2answers
402 views

A function on binary relations

Let $\rho$ is a function mapping every binary relation $f$ (on some set $U$) into a function which maps binary relations into binary relations by the formula $$(\rho(f))(g) = f\circ g.$$ Is $\rho$: ...
0
votes
2answers
87 views

Image of the intersection is contained in the intersection of images; why are not these equal?

If there are any minor mistakes in my proof, it would be great if they were pointed out - but let it not be the central discussion. I'm rather concerned why the answer is $\subset$ instead of $=$ ...
0
votes
1answer
55 views

Binary relations: Can someone see if I have done this correctly?

I would appreciate some help. Here are the binary relations: Below we are defining some binary relations over the set {a, b, c} S ₁: {〈a, a⟩, 〈a, b⟩, 〈b, b⟩, 〈b, c⟩} S ₂: {〈a, a⟩, 〈a, b⟩, 〈b, b⟩} ...
0
votes
1answer
177 views

Which one is a transitive relation?

I'm trying to figure out which one of these relations are transitive relation(s) ...
0
votes
1answer
195 views

Why is phi symmetric and transitive?

Take A={0,1}. Now if we find all the subsets of binary relation i.e. A × A we get one of them as R=Ø. Now I can understand that R does not have (0,0) and (1,1). So R=Ø is not reflective. But how is it ...
1
vote
4answers
110 views

Finding relation between elements

I have seen the following type of problems in reasoning tests: If $A \le B = C > F < G = L$ , then which of the following is true? a. $A < G$ and $A >F$ b. $C >F$ c. $G =B$ ...
0
votes
0answers
606 views

Is = (equality) a partial order relation?

We know that a partial order relation is a relation which is reflexive , antisymmetric and transitive. Example: (x,y) belongs to R iff x=y. For A={1,2,3}, we get R= {(1,1), (2,2), (3,3)}. Now R is ...
2
votes
2answers
3k views

How to find the number of anti-symmetric relations?

I know that given a set $A = \{1, 2, 3, ... , n\}$, the total number of relations on $A$ is $$2^{n^2}$$ The number of reflexive relations is $$2^{n^2 - n}$$ The number of symmetric relations is ...
1
vote
1answer
440 views

Binary relation composition (with itself)

To start off on the right foot. I've read: Relations (Binary) - Composition but I still can't really figure it out because those deal with finite sets. I have a infinite set: $R= \{(n,n+2)|n \in ...