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
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
405 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
126 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
196 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
85 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
43 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
27 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 ...
2
votes
2answers
64 views

How to find inverse of function $f(x, y)$?

I am aware of the method to find inverse function $f^{-1}(x)$ of $f(x)$, which is Replace $f(x)$ with $y$ Switch $x$'s and $y$'s Solve for $y$ Replace $y$ with $f^{-1}(x)$ the above method ...
1
vote
2answers
18 views

How to show that $|A/R|=|A|/n$.

Suppose $A$ is a finite set and $R$ is an equivalence relation on $A$. Suppose also there is some positive integer $n$ such that for every $x\in A |[x_R]|=n$. Prove that $A/R$ is finite and ...
0
votes
2answers
41 views

What kind of relation is this?

A person can remember himself at different points in the past. Each of 'himself' that he remembers at each point in the past can also remember a person in the past, and so on. So if we have a, b, ...
-1
votes
1answer
54 views

Induced mappings

Suppose $f$ is a mapping from the powerset of $A$ to the powerset of $B$. Let $S$ and $T$ be subsets of $A$. If both $f(\varnothing)=\varnothing$, and $f(S \cup T) = f(S) \cup f(T)$, then is $f$ the ...
5
votes
2answers
398 views

Main Theorems/Techniques for proving Homeomorphism?

General Question: what are the most common Theorems/Methods used to prove Homeomorphism? I encountered: - find the map explicitly - use the Compact-to-Hausdorff Lemma - find cts maps $f$ and $g$ ...
2
votes
1answer
173 views

Equivalence relation question with cardinality and countability $A=\mathbb R,\ aSb \iff a-b\in \mathbb Q $

Let $A=\mathbb R,\ aSb \iff a-b\in \mathbb Q $ What is the cardinality of $[\pi]_S$ ? Prove that the quotient group $\mathbb R/S$ is uncountable. Well I think that cardinality is ...
1
vote
1answer
186 views

Countability and uncountability of a set $A$ and the set of equivalence classes $A / R$

Let $A$ be a set and $R$ an equivalence relation on $A$. Prove or disprove: If $A$ is countable then all the equivalence classes of $R$ are countable. If $A$ isn't countable then the ...
0
votes
1answer
15 views

A criterion for complete lattice.

Is there an infinite partially ordered set $(X,\le)$, in which for each $A\subseteq X$, either $\inf A$ or $\sup A$ exists but for some $A\subseteq X$ either $\inf A$ or $\sup A$ does not exist.
1
vote
1answer
55 views

Quotient group with functions and relations question

For the set $\mathbb Z/5 \mathbb Z $ (the quotient group of $\mathbb Z$ with the relation R that is defined by $xRy$ if $5|y-x$) We'll define the following operations (both are $\cdot, +$ ...
3
votes
3answers
409 views

Equivalence relation question with functions

We'll define on the set: $A=\Bbb R^{[0,1]}$ the relation $R$ by $fRg$ if $f(0)=g(0)$. Make sure it's an equivilence relation. What is $[\cos x]$ ? Describe all the equivalence classes ...
1
vote
3answers
90 views

Proof that $(a, b) \mathrel{R} (c, d)$ iff $ad = bc$ is an equivalence relation

Let $X = \{(a,b) \mid a,b \in \Bbb Z; b \ne 0\}$. We define $(a,b)\mathrel R (c,d)$ iff $ad = bc$. Prove that $R$ is an equivalence relation on the set $X$. Which known set do the equivalence classes ...
0
votes
1answer
95 views

Transitive closure of binary relation with proof of equivalence

On the set X = {1,2,3,4,5,6,7,8,9}, there is binary relation Q = {(1,9),(2,5),(3,7),(4,1),(5,8),(6,2),(7,3),(8,6),(9,4)}. Make a transitive closure T of the relation Q. Decide and prove whether the ...
-2
votes
1answer
2k views

How to prove a relation is reflexive and transitive. [closed]

In a question paper (I downloaded from internet) there was a question, Let $f\colon A\to B$ be a function. Define $$R := \bigl\{\left(a,b\right) \mid \text{$a,b \in A$ and $f(a)=f(b)$}\bigr\}.$$ ...
0
votes
1answer
40 views

What is the number of inclusive relations?

A binary relation on a set T is inclusive if every element in T relates to at least one element. As an example we can say that {(2, 3), (3, 4)} is not inclusive since 4 does not relate to any ...
1
vote
2answers
56 views

Function and Relations

I have a small question, if anyone could shed some light I would be really grateful! we have this relation R: ∀ x,y ∈ "≈" , [(x≈y) ⇔ (| x - y| ≤ 0.5)] Also relation R belongs to real numbers ℝ. ...
2
votes
1answer
3k views

Number of relations on a set with n elements

Let $A$ be a set with $n$ elements. How many (1)symmetric, (2)anti-symmetric and (3)asymmetric relations are there on $A$ ? (4)How many linear relations are there ? Here's what I did: ...
1
vote
1answer
1k views

How to prove relation is asymmetric if it is both anti-symmetric and irreflexive

Prove a relation is asymmetric if it is both anti-symmetric and irreflexive (anti-reflexsive). I tried to go from the definitions of the relations: Anti symmetric: $\forall x,y \, (xRy \land ...
2
votes
2answers
87 views

Properties of the relation $R=A\times B \cup B\times A$

A is a set. Let $B\subsetneq A$. $R=A\times B \cup B\times A$ Determine if the relation is (a)reflexive, (b)symmetric, (c)transitive, (d)anti-reflexive, (e)anti-symmetric, (f)asymmetric, ...
1
vote
1answer
76 views

Properties of the relation $R=\{(x,y)\in\Bbb R^2|x-y\in \Bbb Z\}$

$A= \Bbb R \\ R=\{(x,y)\in\Bbb R^2|x-y\in \Bbb Z\}$ Determine if the relation is (a)reflexive, (b)symmetric, (c)transitive, (d)anti-reflexive, (e)anti-symmetric, (f)asymmetric, (g)equivalence ...
1
vote
1answer
69 views

recurrence relation related problems

I'm having some difficulties of finding the recurrence relations of; number of divisions of internal region of n sided polygon number of paths from one point to another point in an NxN grid Can ...
1
vote
3answers
461 views

Define a relation on the set of all real numbers $x,y \in \mathbb{R} $ as follows:

Define a relation on the set of all real numbers $x,y \in \Bbb{R} $ as follows: $x \sim y$ if and only if $x - y \in \Bbb{Z}$ Prove this is an equivalence relation and find the equivalence class of ...
1
vote
3answers
53 views

Why $(a,b)\mid a+b\le3$ is not reflexive and is symmetric?

Why $(a,b)\mid a+b\le3$ is not reflexive and is symmetric? I read because a€ Z so by counter example $(5,5)$, $5+5$ is not less than or equal to $3$ So it's not reflexive But why it's symmetric ? I ...
1
vote
1answer
697 views

Why the divides relation on the set of positive integers antisymmetric

I'd like to know why the divides relation on the set of positive integers antisymmetric. The book says $a|b$ and $b|a$ then $a=b$. But I think if a|b and b not divides a for example $1|2$ but not ...
2
votes
3answers
1k views

Is this relation reflexive, symmetric and transitive?

Define a relation $R$ on the set of functions from $\mathbb{R}$ to $\mathbb{R}$ as follows: $(f, g) \in R $ if and only if $f(x) - g(x) \geq 0$ for all $x \in \mathbb{R}$ Is this relation ...
0
votes
1answer
100 views

Find the number of subsets $S$ of $X$ (of any size) that satisfy the following property

Let $X=\{1,2,\dots,10\}$ define the relation $R$ on $X$ by: for all $a,b\in X$, $a\mathrel{R}b \iff ab$ is even. 1) Find the number of subsets $S$ of $X$ (of any size) that satisfy the ...
0
votes
2answers
112 views

Determining whether a relation is reflexive, symmetric, transitive.

Let $X=\{0,1,2,...,10\}.$ Define the relation $R$ on $X$ by: for all $a,b$ in $X$, $a\mathrel{R}b$ if and only if $a+b=10$ is $R$ reflexive? symmetric? transitive? $a\mathrel{R}a$ $a+a=10$ ...
3
votes
1answer
123 views

Is this relation an equivalence relation? Check my solution please.

Define a relation R on the set {$2, 3, 4, ... $}, as follows. $(x, y)$ ∈ R if and only if $x$ and $y$ have a common factor greater than $1$. Is this relation reflexive? Is it symmetric? Is it ...
0
votes
3answers
34 views

Relation symmetric confusion

So Symmetric = (a,b), (b,a) Set = {<1, 1>, <1, 2>, <1, 4>, <2, 1>, <2, 2>, <3, 3>, <4,1 >, <4, 4>} I understand ...
0
votes
2answers
714 views

Number of asymmetric relation

Let $A$ be a set of $n$ elements. How can we calculate number of asymmetric relations on $A$? I googled for it and got the answer that the number is given by $3^{(n^2-n)/2}$, But I don't know how to ...
1
vote
2answers
987 views

Difference between Reflexive and Symmetric in Discrete Maths

Difference between Reflexive and Symmetric in Discrete Maths? This is what I understand: Reflexive -> <a,a=a>, <b,b=b> uses ...
1
vote
1answer
69 views

Proof that there is an order relation

For an arbitrary set M there is a relation $R \subseteq 2^M \times 2^M$ about $$ A \mathrel R B \Leftrightarrow A \cup \{x\} = B$$ The join is a disjoint join. There are not more details what is $x$. ...
1
vote
3answers
36 views

Help understanding what's required for a relation to be symmetric?

Let $\,X=\{1,2,3,4,5\},\;$ does a symmetric relation on $\,X\,$ need to have all the elements of $\,X\,$ in the relation? Or can if have just a few elements of $X$ like this relation: $\,A ...
1
vote
1answer
4k views

Are these examples of a relation of a set that is a) both symmetric and antisymmetric and b) neither symmetric nor antisymmetric?

I was told to give an example of one of each of these kinds, and this is what I came up with: (these are both relations on the set of all positive integers) R = { (a,b) | a = b} is an example of a ...
1
vote
3answers
62 views

What exactly do “relations on a set” mean?

I have a question that says "How many relations are there on a set with n elements?" so if I have the set A = {a, b} and I wanna find how many relations there are, I thought I would just do R = { ...
2
votes
2answers
187 views

Equivalence Classes of a Relation Given as a Set of Ordered Pairs

Question: The relation R is an equivalence relation on the set A. Find the distinct equivalence classes of R. A = {a, b, c, d} R = {(a, a), (b, b), (b, d), (c, c), (d, b), (d, d)} My work: So when ...