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
1answer
48 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
2answers
23 views

Prove that R is an equivalence relation on F

A relation $R$ is defined on the set $F = \{f: \Bbb R \to \Bbb R\}$ $$fRg \iff f(0) = g(0).$$ My approach: This is reflexive because: $f(0) = f(0)$ is same as $f(0) = g(0)$ This is symmetric ...
0
votes
1answer
47 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
91 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
33 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
30 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
45 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
82 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
69 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
60 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 ...
4
votes
2answers
97 views

Is $a \le b$ a true statement if $a < b$? [duplicate]

My question is: Is $a \le b$ true if $a < b$? For instance: Is $3 \le 4$ a true statement? I think yes, because $a \le b$ is defined as $a < b\vee a = b$ and this should be true, even if $a = ...
2
votes
1answer
367 views

Composite Relations - Give Examples of relations $R_1$ and $R_2$ such that $R_2 \circ R_1 = R_1 \circ R_2$ and $R_2 \circ R_1 \neq R_1 \circ R_2$

Let $S =[a,b,c]$. Give examples of a. relations $R_1$ and $R_2$ on $S$ such that $R_2 \circ R_1 = R_1 \circ R_2$ b. relations $R_1$ and $R_2$ on $S$ such that $R_2 \circ R_1 \neq R_1 \circ R_2$ My ...
0
votes
0answers
80 views

Relational algebraic structures

Recently I came across the notion of relational $\beta$-algebra, defined as a set $S$ and a binary relation $\xi:\beta S-S$, where $\beta S$ denotes the set of ultrafilters on $S$ (and $\beta$ is the ...
1
vote
2answers
46 views

transitive property in a binary relation

I'm looking at a True or False question in my book and it is very close to identical to the definition of the transitive property in the book, though this answer is False. If someone could explain to ...
1
vote
2answers
66 views

understanding reflexive transitive closure

Suppose I have the following relation $$R = \{(1,1), (2,3), (3,1)\}$$ To make it reflexive we add the following missing pairs: $$ \{(2,2), (3,3)\}$$ Now I wonder how to find the reflexive transitive ...
0
votes
0answers
12 views

Name for symmetric irreflexive binary relation

I have an irreflexive relation $\prec$ called unpreference: if $x\prec y$ then I say $x$ is unpreferred (or not preferred) to $y$. I wish to give a name to the symmetric part of the relationship, ...
1
vote
0answers
34 views

Composition relation of P∘P

Consider the following relation P on the set B = {a, b, {a, b}}: P = {(a, a), (a, b), (b, {a, b}), ({a, b}, a)}. Answer questions 6 to 8 by using the given relation P. Question 6 Which one of ...
0
votes
1answer
55 views

Relation $R$ on $V$ is given by $x+y$ is even [closed]

A relation $R$ on $V$ is given by $x+y$ is even. How can we show that if integers $x$ and $y$ are $R$-related then either $x$ and $y$ are both even or $x$ and $y$ are both odd? I've been looking ...
2
votes
2answers
35 views

listing elements of equivalence class

For $m,n$ in $N$ define $m$ equivalent $n$ if $m^2-n^2$ is multiple of $3$ a) show that this is an equivalence relation b) list elements in equivalence class [0] c) list elements in equivalence class ...
1
vote
2answers
48 views

Showing equivalence relation.

On the set $\mathbb N\times \mathbb N$ define $(m,n)\sim(k,l)$ if $m+l=n+k$ Show that $\sim$ is equivalence relation on $\mathbb N\times \mathbb N$ Draw a sketch of $\mathbb N\times \mathbb N$ that ...
0
votes
2answers
195 views

Describing equivalence classes

The problem is : define relation equivalence on Z by m=n in case m^2=n^2. a)Show that its an equivalence relation on Z. b)Describe the equivalence classes for = how many are there. For part a i ...
0
votes
1answer
42 views

Help determining relations on the set {1, 2, 3}

I'm studying for a midterm and I just want to make sure that my understanding of these 2 problems that my teacher gave is logically sound. If you could take a look and give me some feedback I would ...
0
votes
2answers
38 views

If $A_1$ and $A_2$ are countably infinite, and that $A_1\cap A_2=\phi$. Then prove that $A_1 \cup A_2$ is countably infinite.

If $A_1$ and $A_2$ are countably infinite, and that $A_1\cap A_2=\phi$. Then prove that $A_1 \cup A_2$ is countably infinite. My work: As $A_1$ and $A_2$ are countably infinite, there exists a ...
1
vote
2answers
55 views

prove if x ≡ y (mod m) then GCD(x, m) = GCD(y, m)

By definition $x=km+y$ for some $k \in \mathbb{Z}$. Let $d=gcd(x,m)$. By definition $d|x$ which implies that $d|km+y$. Since $d$ also devides $m$ we note that $d|y$. now suppose there is some larger ...
6
votes
2answers
336 views

Is there a relation that is irreflexive, anti-symmetric and not transitive?

from the set $\{a, b, c, d\}$? Of the one's I have tried, it at best is two of the three, but never all.
2
votes
1answer
75 views

Problems with the definition of transitive relation

Recently I found this problem, which made me realize I have some problems with relations that are vacuously transitive. Problem: Assume that $R$ is a relation on $A$ and define the relation $S$ as ...
2
votes
1answer
105 views

The closures of a binary relation

I have the following dilemma concerning the equivalence closure of a binary relation. Let $X$ be a nonempty set and $R\subseteq X\times X$ (i.e., a binary relation over $X$). Consider the following ...
2
votes
1answer
28 views

Union of Cartesian squares

I am trying to find sufficient and necessary conditions for a relation to be representable as a union of Cartesian squares: $\bigcup_{i\in I}(X_i\times X_i)$ for some family $X_i$ of sets. One ...
1
vote
0answers
71 views

General (Set Builder) definition for a relation composed with itself n times

Questions What does the set builder notation for $S\circ R$ look like? I'm having the most trouble knowing when there is too much information or not enough information on either side of the 'such ...
1
vote
2answers
31 views

How do you call this feature and property of relation?

If an operator can be defined for $k$ operands, $k \in \mathbb N$, how do you call this feature of the operator? For example, "+" is such an operator. Similarly, for a relation $R$ on a set $X$, $R$ ...
2
votes
1answer
25 views

Checking the equivalence relations of sets

$S=\{0,1,2,3\}, R:SxS, (m,n)\in R \text{ if } m+n=4$. From the condition of $R$, I found that $R=\{(2,2),(1,3),(3,1)\}$. Now I have to see if $R$ is reflexive, symmetric, antisymmetric, and ...
0
votes
1answer
45 views

How can I prove that $(ℤ, ≺)$ is not isomorphic to $(ℕ, ≤)$

We define the relation $≺$ between pairs of integers like this: $n≺m$ is true if and only if one of the following conditions holds: a) $0≤n≤m$ b) $0≤n$ and $m<0$ c) $n<0 , m<0$ and ...
0
votes
1answer
29 views

Are all relations that are symmetric and anti-symmetric a subset of the reflexive relation?

Simple question, but I can't seem to find a guaranteed answer. A symmetric set contains (a, b) if it contains (b, a), but an ...
0
votes
1answer
38 views

Equivalence relation example

On the Wikipedia page about Equivalence Relations, there is a simple example: Let the set $\{a,b,c\}$ have the equivalence relation $\{(a,a),(b,b),(c,c),(b,c),(c,b)\}$. The following sets are ...
0
votes
1answer
65 views

Help understanding a theorem on transitivity of a relation

The theorem states this: The relation R on a set A is transitive if and only if $R^n \subseteq R$ for n = 1, 2, 3,... What I'm reading is that the nth power of that set is transitive if the set ...
1
vote
3answers
603 views

Is the relation $R = \emptyset$ is it reflexive, symmetric and transitive ? Why?

Can someone help me understand the properties of the relation $R = \emptyset$ ? It looks to me like it's not reflexive, since there is no element related to any element, so the elements are not ...
0
votes
1answer
36 views

Understanding relations when it's about $\langle{x,x}\rangle$ instead of $\langle{x,y}\rangle$

I have difficult to understand relations when we talk about $\langle{x,x}\rangle$ instead of $\langle{x,y}\rangle$ .. it's hard for me to realize for example is the following relation is reflexive, ...
1
vote
1answer
65 views

Bijection on a component of a cartesian product

I have been recently studying relations and mappings and I have come across the following problem. Consider two non empty finite sets $I,J$ and their cartesian product $I\times J$. Let $f\colon ...
0
votes
2answers
31 views

Can I write a Non Homogenerous equation as homogenous

Say I have Fibonacci R.Relation, $$ r^2=r+1 $$ Can I write it as $r^2-r-1=0$? From what I know a homogeneous equation is an equation equated to zero.
1
vote
4answers
74 views

I do not understand the definition of antisymmetric relations

OK, let A be a set and let R be a binary relation on A. In my class we say that R is antisymmetric if and only if for every a, b in A, if (a, b) in R and (b, a) in R then a = b. Fair enough, but what ...
1
vote
1answer
38 views

prove a set relation R is transitive?

I have been thinking this problems all the evening, please help Let R be a relation on A. Prove that if Dom(R)∩ Range(R) = Ø, then R is transitive. Oh my god, how to prove this???
0
votes
0answers
17 views

Transitive closure of Relation

We know that $$R^* = R \cup R^1 \cup R^2 \cup \cdots \cup R^n$$ $\text{Where R is a relation from set A with n elements}$ My problem is, why we had limited to $R^n$ ? There can be more paths of ...
2
votes
2answers
2k views

How many equivalence relations on a set with 4 elements.

Let S be a set containing 4 elements (I choose {$a,b,c,d$}). How many possible equivalence relations are there? So I started by making a list of the possible relations: ...
0
votes
1answer
56 views

Discrete Maths: I'm not familiar with this notation

I've the following relation: $(x,y) \in A \times B, x S y ↔ 2|(x-y)$ What does $2|(x-y)$ mean? Thank you.
1
vote
1answer
52 views

Does $f \leq f \circ f^\dagger \circ f$ hold in an arbitrary allegory?

If $f$ is an arrow of $\mathrm{Rel}$, then $f \leq f \circ f^\dagger \circ f.$ Proof. Suppose $xy \in f$. Then $xy \in f, yx \in f^\dagger, xy \in f$. Thus $xy \in f \circ f^\dagger \circ f.$ ...
0
votes
0answers
15 views

What kind of relation does an ambiguous organization scheme introduce?

Please consider an arbitrary set of items, i.e. products in a supermarket or news in a news channel. Let's say we want to apply an organization scheme to that items. There are unambiguous ones, like ...
4
votes
0answers
65 views

Where can I learn more about the concept that is dual to “relation”?

Let $X$ and $Y$ denote sets. Then a relation $X \rightarrow Y$ is, by definition, a subset of $X \times Y$. Dually, we can define that a "corelation" $X \rightarrow Y$ is a partitioning of $X \uplus ...
0
votes
3answers
50 views

How can I prove that $(a,b) = (c,d) \land (c,d)=(e,f) \implies (a,b)=(e,f)$ is true

I am trying to prove this relation, but I just cant. I know it is true, but I can not prove it, because I dont know how. Can someone give me some pointers. $(a,b) = (c,d) \land (c,d)=(e,f) \implies ...
0
votes
1answer
39 views

Proving that $(a_1, b_1)\sim(a_2, b_2)\Leftrightarrow\ a_1=a_2\land b_1=b_2$

This assingment is preparation for exam. I need to prove with $(a_1, b_1)\sim(a_2, b_2)\Leftrightarrow\ a_1=a_2\land b_1=b_2$ that $\sim$ is equivalence relatio. Can you tell me how to do this. ...
0
votes
1answer
46 views

Reflexive relation on set of $n$ elements

How many reflexive relations are there on a set of $n$ elements? I did the problem and I got the answer $2 ^ {n ^ 2}$. Is it correct? Thanks for the help..!!