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

4
votes
0answers
77 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
52 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
46 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
2answers
72 views

Reflexive relation on set of $n$ elements [duplicate]

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
32 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
45 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
40 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
69 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
41 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
49 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
1k 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
39 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
48 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
28 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
30 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
417 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
2k 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
98 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
29 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
62 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
82 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
26 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
158 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
29 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
75 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
36 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
23 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
58 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
86 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
137 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
74 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
95 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 ...
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
57 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
410 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
46 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
128 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
16 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
198 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 ...
0
votes
2answers
48 views

To find $R\circ R^{-1}$ in Discrete mathematics

Today I came across a question in DMS which says: If $R$ is the relation “Less Than” from $A = \{1, 2, 3, 4\}$ to $B = \{1,3,5\}$ then find $R\circ R^{-1}$. Now what is $R\circ R^{-1}$? I know ...
1
vote
1answer
36 views

Number of Relations

I was stacked in one question . It was about number of reflexive relations on set with N elements. I know the solution but i don't know the logic behind it . I know we construct nxn matrix and number ...
0
votes
1answer
67 views

Calculating a union of 2 relations

I have 2 relations: $$ xSy \Leftrightarrow y = 2x$$ and $$ xTy \Leftrightarrow y = 3x$$ The problem I have is calculating $$x(T \cup S)y$$ and $$xS^+y $$ Could you please help me?
1
vote
1answer
64 views

Does $\neg(x > y)$ imply that $y \geq x$?

Given any arbitrary binary relation $\geq$ defined on some set $S$, we define a new binary relation $>$ on $S$ by: $$ x > y \quad\text{iff}\quad (x \geq y) \wedge \neg(y \geq x) $$ In accordance ...
2
votes
1answer
87 views

Does(n't) associativity of functional composition follow straightaway from associativity of relational composition?

One thing I find puzzling about the typical way in which associativity of functional composition is proved is that it makes explicit use of the fact that a function is a 'right-unique' relation, i.e. ...
3
votes
1answer
66 views

Rigorous definition of relation composition

Let $R$ be an $n$-ary multivalued function on $A$, and let $S_1, ..., S_n$ be a list of length $n$, each member of which is an $m$-ary multivalued function on $A$. How does one rigorously define the ...
0
votes
1answer
44 views

$M_1 = (x,y)\quad x²+y²+6y = 7 $ to $x \rightarrow y$

I have two relations: $$M_1 = (x,y)\qquad x²+y²+6y = 7 $$ $$M_2 = (x,y)\qquad x²+y²-6x = 7, \qquad y \ge 0$$ The question is if this relations also reflex functions like $x \rightarrow y$? I ...
0
votes
1answer
46 views

If $E_1$ and $E_2$ are equivalence relations, is $E_1\circ E_2$ an equivalence relation?

I'm given two equivalence relations $E_1$ and $E_2$ over a set A and need to show whether the composition $E_1 \circ E_2$ is reflexive, symmetric and transitive. I only managed to show that $E_1 ...
0
votes
2answers
28 views

Points of a relation

I have the following relation: $M =${$ (x,y), x =$$ {1}\over{t+1}$, $y =$$ {5t + 8}\over{t + 1}$,$t\in\mathbb R$} The task is to sketch the points of M into a coordinate system! But my opinion is ...