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

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
71 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
37 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
13 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
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..!!
2
votes
1answer
27 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
39 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
29 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
120 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
33 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
40 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
210 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
870 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
63 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
59 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
59 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 ...
1
vote
0answers
35 views

Prove the following $(R\cap S)^n=R^n \cap S^n$

I would like to prove the following without induction. $$(R\cap S)^n=R^n \cap S^n$$ We can start by take $(a,b)\in (R\cap S)^n$ its represent a path from $a$ to $b$ right? Any hints? Thanks.
-1
votes
1answer
20 views

if a set B has a least upper bound of an on an ordered relation <(a) then will it have least upper bound on an ordered relation <(b)

given a set B ordered by a relation <(a) has a least upper bound property, does B have an least upper bound property if it is ordered by another ordered relation <(b).
0
votes
3answers
55 views

Check the following Relation $R=\{(x,y) |\exists k\in \mathbb{Z} \cdot x*y=3k \}$

I would like to check the following relation: $$R=\{(x,y) |\exists k\in \mathbb{Z} \cdot x*y=3k \},R\subseteq \mathbb{Z} \times \mathbb{Z}$$ Reflexivity Symmetric Transitivity Asymmetric Can I ...
1
vote
3answers
73 views

Given 2 sets (X and Y) is it possible for $f: Y \to X $ to be a relation, or not?

This question is from my Computational Theory course's homework. I completely understand functions and relations (I've taken numerous Calculus courses). Here's a general example of what the question ...
0
votes
1answer
73 views

Shortcut method for proving equivalence relations

Define the relation R on N*N by: (x,y)R(z,w) if and only if x-z = w-y. Check whether R is an equivalence relation. Explain your answer My teacher answer is: Using the shortcut method: ...
0
votes
1answer
47 views

Equivalence class for a relation

Consider the equivalence relation on Z ! Z given by (m, n)R(p, q) if and only if mq = np: (a) Find the equivalence class represented by (2, 5). (b) Describe the set S of the equivalence classes ...
0
votes
1answer
20 views

Question on proving relations

State whether the following statement is true, and either prove it or provide a counter example: Every Relation R on {0,1} satisfies R∘R subset of R. This is a past paper question for an exam I have ...
3
votes
1answer
83 views

$\mathrm{Pol}_m(\mathbb{A})$ viewed as a relation pp-definable from $\mathbb{A}$

First let me recall some (abbreviated, and possibly simplified to suit my situation) definitions: Let $A$ be a finite set and $\mathbb{A}$ some set of relations on $A$. Let $m, n$ be positive ...
-2
votes
1answer
62 views

Determining if $R$ is reflexive, transitive or symmetric on $S$ [closed]

Determine if $R$ is reflexive on $S.$ $S = \mathbb{R}$. Define $R$ by $(a, b)\in R$ if $|a|=|b|.$ $S = \mathbb{R}$. Define $R$ by $(a, b)\in R$ if $a = b + 1.$ $S = \mathbb{R}$. Define $R$ by $(a, ...
0
votes
1answer
46 views

Determining why this is transitive

Why $R_3 = \lbrace (1,2),(3,4)\rbrace$ is transitive? It's like, transitive is said because there's $\{a,b\}$,$\{b,c\}$ then there will be $\{a,c\}$ right? But then, why is that one is said to be ...
0
votes
2answers
53 views

Relations between two functions

Consider the statements (1) "If $f(i) \geq f(j)$ then $q(i) \geq q(j)$", and (2) "If $q(i) < q(j)$ then $f(i) \leq f(j)$". How can we relate these statements? I mean are these related?
1
vote
1answer
132 views

How to prove $R$ is an antisymmetric relation if and only if $R\circ R^{-1}\subseteq\Delta_X$?

$R$ is antisymmetric relation if and only if $R\circ R^{-1}\subseteq\Delta_X$ $\leftarrow$ assume $R\circ R^{-1}\subseteq\Delta_X$. let $(x,y)\in R $ and $(y,x)\in R\rightarrow (y,x)\in R^{-1}$, so ...
0
votes
1answer
44 views

Very Abstract Relation with points

So I have this question on relations, that I really cant understand. I mean, I cant understand the question to be honest. Suppose a set $X$ of points on the plane and we "stabilize" a point $O ∈ X$. ...
0
votes
1answer
79 views

Finding the number of different relations and functions

This must be a very stupid question. Let set $A=\lbrace{a,b\rbrace}$ and $B=\lbrace{1,2,3\rbrace}$. The total number of relations from $A$ to $B$ is $6$. We can calculate this as a has $3$ choices and ...
0
votes
2answers
14 views

$X=\{1,2,\dots,10\},x\rho y\Leftrightarrow x\equiv y(mod\hspace{0.2cm}3)$

$X=\{1,2,\dots,10\},x\rho y\Leftrightarrow x\equiv y(mod\hspace{0.2cm}3)$ i.e $x,y$ have the same reminder when divided by $3$ ( it was actually written in the question). I need to find the number ...
8
votes
3answers
170 views

Can we take images of equivalence relations?

Given a function $f : X \rightarrow Y$, it is well-known that we can take the image under $f$ of any subset $A \subseteq X$, and we can take the preimage under $f$ of any subset $A \subseteq Y$. This ...