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
50 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
285 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
57 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
27 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
63 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
24 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
25 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
35 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
20 views

finding the transitivity of a given set [closed]

Let A={1,2,3,4,5,6}. Define the relation R on A as follows aRb if and only if |a-b| is less or equal to 2. a) decide with reasons if (A, R) is transitive
0
votes
1answer
59 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
382 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
59 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
29 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
66 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
36 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
1k 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
11 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
37 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
45 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..!!
2
votes
1answer
26 views

Example of an equivlance relation that is transitive

I am just tying to figure our this example but am having difficulty understand the math being used. The example state: Let R be a relation on the set $\mathbb{Z}$ defined as $(m,n)\in$ R if and only ...
0
votes
2answers
38 views

Trying to understand an example of an equivlance relation that is symmetric

I am just tying to figure our this example but am having difficulty understand the math being used. The example state: Let R be a relation on the set $\mathbb{Z}$ defined as (m,n)$\in$ R if and only ...
0
votes
1answer
25 views

Partial order up to equivalence

In certain contexts one runs into something like a partial order, but the antisymmetry property is weakened as follows: if $x \preceq y$ and $y \preceq x$ then $x \simeq y$, where $\simeq$ is a given ...
1
vote
3answers
64 views

How to write this set?

I hope someone can help me out here :) We have to sets : STUDENTS » All the students of the school CLASSES » All the classes of the school And the relation : STUDENTSCLASSES » Relates the students to ...
0
votes
1answer
21 views

reflexive relations

Let $R_1, R_2$, relations such that: $R_1 \subseteq R_2$. If $R_1$ is reflexive then $R_2$ is also reflexive. I understood it's true, but I don't see why. if $R_1 \subseteq R_2$ there's ...
0
votes
1answer
35 views

Questions regarding composition and constant function

Suppose A is a non-empty set and f is a function on A. Suppose for all g(which is also a function on A), composition of functions f and g is f, then f is a constant function. I try to prove it but ...
0
votes
2answers
114 views

How do I prove if a relations is symmetric,transitive or reflexive?

I have no idea how to start this problem. It is asking to prove if the following relation R on the set of all integers where $(x,y) \in R$ is reflexive, symmetric and/or transitive. 1) $(x, y)\in R ...
0
votes
1answer
32 views

Is a relation$ R=\{(a,a):a\in I\}$ said to be reflexive, symmetric and transitive?

Consider a relation $R=\{(a,a): a\in A\}$ where $A=\{1,2,3\}$. i.e $R=\{(1,1),(2,2),(3,3)\}$ This clearly reflexive but is it necessary that all such relations are necessary to be symmetric and ...
1
vote
2answers
39 views

Transitive & symmetric relation; why is this wrong?

"Give a relation that satifies the condition:" Symmetric and transitive but not reflexive. This is what I gave: R = {(x,y), (y,z), (z,x), (y,x), (z,y), (x,z)} I was told this was not ...
0
votes
1answer
23 views

Set Theory - Given 2 sets, are they order-isomorphic

We are given the sets $A=(1,2]\cup ((3,4)\cap \mathbb Q)$ and $B=(1,2)\cup ((3,4)\cap \mathbb Q)$ with the standard order $\leq$ of the reals. Are they order-isomorphic? Meaning, is there a bijective ...
0
votes
1answer
25 views

Simple set theory - Show a set is finite

let $(X, \leq_*)$ be a partially ordered set. Assume there is an isomorphism $f: (X,\leq_*) \to (\mathbb Z, \leq)$ let $A \subseteq X$ be a well ordered subset of $X$ with an upper bound. Meaning ...
0
votes
1answer
193 views

Count number of binary relations between sets

He, I have following questions: We have sets $A$ and $B$, $\left | A \right | = m,\left | B \right | = n$. 1) How many binary relations are there from $A$ to $B$? 2) How many binary relations are ...
1
vote
1answer
805 views

Prove that between every two rational numbers a/b and c/d that there is a rational number and there are an infinite number of rational numbers [duplicate]

So the full problem is Prove that between every two rational numbers $a/b$ and $c/d$ that: There is a rational number There are an infinite number of rational numbers I am having ...
5
votes
1answer
58 views

Question about sets of well-orders and isomorphisms between well-orders

I was thinking about this problem in trying to better get a feel for and understand well-orders (I'm trying to learn some set theory) - right now, I'm not really hoping for anybody to supply me with a ...
1
vote
1answer
25 views

Show that f is a symmetric relation on A

I am learning about relations and I come across this exercise. And I don't understand the problem. Let me first state the problem here: Let $f: A \rightarrow A$ be a function for which $f(f(x))=x$ ...
3
votes
1answer
58 views

Can a relation be transitive when it is not reflexive?

Lets say I have the following set: $$ \{1, 2\}$$ and on it the following relation is given: $$\{(1, 2), (2, 1)\}.$$ Now is the above relation transitive? My confusion: we can see, that it is ...
-1
votes
3answers
56 views

Class Transitivity Proof

Prove that a class $T$ is transitive iff $\bigcup_{t \in T},\, t \subseteq T$ iff $a \in t$ whenever $a \in b$ and $b \in T$. I know that I need to begin by proving the first statement implies ...
0
votes
2answers
25 views

Relations & modular artithmetic

Given the following partition on the set N:{ n being natural : n = 7k+p} , where p= 0,1,2,3,4,5,6. 1) Find an equivalence relation ~ on the set N that partitions N into the sets mentioned in the ...
2
votes
1answer
133 views

Is there a name for this property of a binary relation? $\forall x\forall y(x\mathsf{R}y\to\exists z(x\mathsf{R}z\land y\mathsf{R}z)))$

Consider a binary relation $\mathsf{R}$ such that $x\mathsf{R}y$ is the case only if there is some $z$ such that both $x\mathsf{R}z$ and $y\mathsf{R}z$ are the case. Is there a well-known name for the ...
0
votes
1answer
28 views

Prove the following $R \subseteq A\times B$ and $S\subseteq B\times C \rightarrow $ $ S \circ R $ is symetric

I want to prove the following $ S \circ R $ is symetric, A,B, C are sets $R \subseteq A\times B$ is Symetric $S\subseteq B\times C$ is Symetric Any Suggestions? Thanks!
1
vote
1answer
46 views

proving antisymmetry of partition refinement

Suppose $P$ is the set of all partitions of some set $S$. $R$ is a binary relation on $P$, the refinement relation, defined as $(\Pi_1,\Pi_2) \in R $ if and only if for every $S_1 \in \Pi_1$, there ...
1
vote
1answer
57 views

On the size of a set of functions such that $f(i)\ne f(i+1)$ for every $i$ (and similar conditions)

For a finite set $A$,let $|A|$ denote the number of elements in the set $A$. (a) Let $F$ be the set of all functions $$f: \{1,2,\ldots,n \} \to \{1,2,\ldots,k\}~~~~~~~~~~ (n\ge 3,k\ge 2)$$satisfying ...