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

2
votes
1answer
25 views

partitioning a set using a non-equivalence relation

I understand that a set can be partitioned into equivalence classes by an equivalence relation (wikipedia article). However can we partition a set into a forest of trees by a relation that's simply ...
1
vote
0answers
16 views

Hasse Diagrams - Relations

I have the following question: Draw the Hasse diagram for the following partially-ordered set: The relation $X$ is a subset of $Y$, on the set $\{ \{0\}, \{2\}, \{0,1\}, \{0,2\}, \{2,4\}, ...
1
vote
1answer
57 views

Relations - Reflexive, Symmetric, Transitive

I have the following question and corresponding answers, but I cannot quite understand how it works. Can anyone describe to me in plain English the reason why these relations are reflexive, symmetric, ...
0
votes
0answers
22 views

Is there a particular name for the set of all relations?

I know that a relation on a set $S$ is a subset $R \subseteq S \times S$ such that for all $(s,s') \in S \times S$, $(s,s') \in R$ iff $sRs'$, therefore the set $T$ of all relations on $S$ is the set ...
1
vote
2answers
24 views

Not sure how to do Non-Homogeneous Recurrence Relations

I have a sample exam paper, and the answer is given, but I can't work out the answer from the question: Find the solution of: $a_n = \frac{1}{3}a_{n-1} + 2$ using $a_0 = 4$ Given Answer: $a_n = ...
2
votes
1answer
17 views

Need help proving that $ fRg \Leftrightarrow fg = f $ on $ B^{n} $ to $ B $ if and only if $ f(b_1,…,b_n) \leq g(b_1,…,b_n) $

I'm trying to gather my thoughts for proving the following claim: For $ fRg \Leftrightarrow fg = f$ on $B^{n}$ to $B$, show that $ fRg $ if and only if for any input values $ b_1,...,b_n $, we ...
0
votes
1answer
27 views

Equivalence Relation ~

let S = {1,2,3,4} Explain why each of the below are not equivalence relation. { (1,1), (1,2), (2,1), (2,2), (3,3) } { (1,1), (1,2), (2,3), (1,3), (2,2), (3,3), (4,4) } { (1,1), (2,2), (3,3), ...
3
votes
3answers
78 views

Find $f(2a-x)$ from given equation

I have been trying to solve an exercise based on the relations and functions. Right now I had stuck to a question based on functions. The question says: A real valued function $f(x)$ satisfies the ...
3
votes
1answer
51 views

Rel: the category of relations

$\text{Rel}$ is the standard name for the category of sets and relations. Confusingly in "Abstract and concrete categories" (ACC), page 22, $\text{Rel}$ is defined as a category whose objects are ...
0
votes
3answers
50 views

Relations and partial order

I'm having some trouble answering a question and any help would be appreciated. The question is: "Let $\mathbb Z$ be the set of integers and consider the set $X = \mathbb Z\times \mathbb Z$. Consider ...
0
votes
1answer
19 views

Prove that $P(\Bbb R)/\prec$ is countable and show that the class $[A]_\prec$ is an infinite set and not countable

Let $\prec$ be the relation over $P(\Bbb R)$ defined as: $A \prec B$ if and only if $|A \cap \Bbb Q| = |B \cap \Bbb Q|$. Prove that the quotient set $P(\Bbb R)/\prec$ is countable and show that ...
0
votes
4answers
28 views

Let $(A,<_A)$ and $(B,<_B)$ be two partially ordered sets. Show that $(A,<_A)$ is not isomorphic to $(B,<_B)$.

Let $(A,<_A)$ and $(B,<_B)$ be two partially ordered sets, where $A=\{a,b,c\}$ and $<_A=\{(a,b),(a,c)\}$; $B=\{x,y,z\}$ and $<_B=\{(x,y),(y,z),(x,z)\}$. How to show $(A,<_A)$ is not ...
1
vote
1answer
37 views

state the relations of a set

Consider the following relations: ...
0
votes
1answer
29 views

Need help with compositions of relations

Prove that given relations $R_1 \subseteq A \times B$, $R_2 \subseteq B \times C$, $R_3 \subseteq C \times D$ then $(R1 \circ R2) \circ R3 = R1 \circ (R2 \circ R3)$ I don't know where exactly to ...
0
votes
1answer
204 views

Is an anti-symmetric and asymmetric relation the same? Are irreflexive and anti reflexive the same?

I don't understand the difference between an anti symmetric and asymmetric relation. From my understanding, it is asymmetric if there is not any element where: if (x,y) (y,x). But what if you have ...
0
votes
1answer
24 views

Partition induced by a Relation

Here's the problem: Let $A=\{1,2,3,4,5,6,7,8,9\}$. Define a relation $R$ on set $A$ by $xRy$ if and only if $2\mid(x+y)$ Assuming that $R$ is an equivalence relation, determine the partition of set ...
1
vote
1answer
51 views

symmetric/antisymmetric

according to both the text and my professor, these properties are not mutually exclusive. i.e. a relation can be both symmetric and antisymmetric. I understand the properties themselves, but I don't ...
1
vote
1answer
51 views

Is there way to classify the quantifier rank $m$ first order sentence in first order logic

In its simplest situation, for example, if the signature contains only a binary relation $\sigma$, so the signature $\tau = \{ \sigma \}$, what are the inequivalent classes of all first order ...
0
votes
1answer
36 views

Equivalence relations and power sets.

Let $\mathcal{A}$ be the class of all sets and define the relation $R$ on $\mathcal{A}$ as: $A\space R\space B$ iff there is a bijective function $f:A \to B$. Prove that $R$ is an equivalence relation ...
1
vote
1answer
34 views

List all elements of the relations

The task is to List all elements of the relations (d) S`, S-1 and S ₀T. ...
0
votes
1answer
41 views

Relations between sets

I have a mutiple choice question on finding the relation but I seem to be blanking. Can someone explain to me how this works? Let $X = \{2,3,4\}$ and $Y = \{0,1,2,3,4\}$. If a relation $P$ ...
0
votes
1answer
19 views

Need help clarifying relation properties

So I am facing some issues determining the right properties for: $ xRy\;if\,\sin^2(x) + \cos^2(y) = 1 $. (On real numbers) Obviously this one is reflexive as $\sin^2(x) + \cos^2(x) = 1 $ is a basic ...
0
votes
0answers
33 views

Transitive, Reflexive, Symmetric

So i know what each of these properties are..but this question does not provide any information on a 3rd variable so i was wondering how i would do it? ...
2
votes
1answer
23 views

If $R=\{(n,k) \mid n,k\in \{1,2,3,4,5,6\}, n \mid k\}$ is a relation. What does the notation $n \mid k$ mean?

Let $R=\{(n,k) \mid n,k\in \{1,2,3,4,5,6\}, n \mid k\}$ be a relation. What does the notation $n \mid k$ mean? I haven't seen this before, does this mean that $n$ is divisble by $k$?
1
vote
1answer
124 views

Exercise in Well Orderings

Prove that if $\prec$ is a well-ordering on a set X and if $Y \subseteq X$, then $\prec_Y=\{(x,y) \mid (x \in Y) \wedge (y \in Y) \wedge (x \prec y)\}$ is a well ordering on Y. I am a little ...
0
votes
1answer
14 views

Proving that a relation is acyclic

Let $S$ be the set of triples of positive numbers $(x,y,s)$. Let $R$ be a directed relation defined between triples, such that $R(b,a)$ if at least one of the following four conditions hold: ...
2
votes
1answer
78 views

Is there a name for this property: If $a\sim b$ and $c\sim b$ then $a\sim c$?

Let $X$ be a set with a binary relation $\sim$, such that for all $a$, $b$, and $c$ in $X$: If $a\sim b$ and $c\sim b$ then $a\sim c$ Is anyone familiar with this property of a binary relation? ...
0
votes
1answer
40 views

Function on the set of relations: $f(R)=RK$ where $K$ is a fixed relation

$\ M$ is the set of all relations on $\ A = \{1,2,3\}$ $\ K$ is the following relation on A $\ K=\{(1,1),(2,1),(3,1)\}$ let there be $\ f :M\rightarrow M$ $\ f(R) = RK$ prove that ...
0
votes
2answers
27 views

Bijection of a function.

Define the function f: $(2,\infty) -> (-\infty,-1)$ by $f(x)= \frac{-x}{x-2}$. Show that f is bijective. I know i need to prove both injective and surjective, and I was able to solve the equation ...
0
votes
0answers
32 views

unifying latitude and longitude into single digit finding equation

I am trying to convert a latitude,longitude into a single point using the midpoint formula while still being able to do a radius search around that point. The midpoint formula is wrong for this ...
1
vote
1answer
62 views

Give an example of a relation R on $A^2$ which is reflexive, symmetric, and not transitive

I am just looking for some clarification on this exercise: Let $A = \{a,b,c,d\}$. Give an example of a relation $R$ on $A^2$ which is reflexive, symmetric, and not transitive. I understand that if I ...
1
vote
1answer
27 views

Symmetric relation , why are these symmetric?

$R_1 = \{(a,b)$ such that $a \leq b \}$ $R_2 = \{(a,b)$ such that $a>b \}$ $R_3 = \{(a,b)$ such that $a=b$ or $a=-b \}$ $R_4 = \{(a,b)$ such that $a=b \}$ $R_5 = \{(a,b)$ such that $a=1+b \}$ ...
0
votes
1answer
27 views

linear algebra equivalence relation

In the set of the integers Z, given a positive number m, we define $ \sim = \lbrace (x1,x2) | x1-x2 = m z, z \in Z \rbrace $ Proof that ~ is an equivalence relation. How many equivalence classes does ...
0
votes
1answer
54 views

Proving a relation is transitive

I am trying to understand transitive relations. I understand given that a set may have $\{(a,b)(b,c)\}$ it must contain $(a,c)$ for it to be transitive. But for longer sets I am getting confused in ...
0
votes
1answer
31 views

Is a relation induced by a partition always an equivalence relation?

Is a relation induced by a partition always an equivalence relation? I'm having some serious trouble understanding this concept and I was wondering if this is true.
1
vote
1answer
27 views

Proving a relation is a total order relation

Consider question #21 part a: Here is the solution: However, consider the definition of a total order relation: The solution didn't prove that the relation is a partial order relation. This ...
1
vote
1answer
58 views

Prove that if the relation (R) is symmetric and antisymmetric on the set X, there exists a Y subset of X such that R is the = relation on Y.

Prove that for any relation R on a set X that is both symmetric and antisymmetric, there is subset Y \subseteq X for which R is the relation = on Y. I will tell you what I know. I know that ...
1
vote
2answers
48 views

Lattice from Preorder

I have seen many examples defining a lattice over a partially ordered set $(P, \sqsubseteq)$ together with a greatest lower bound $\sqcap$, a least upper bound $\sqcup$ and a top $\top$, and bottom ...
0
votes
2answers
32 views

equivalence relation on a set $\{a,b,c\}$

Calculation of total no. of equivalence relation can be defined on a set containing $\{a,b,c\}$ $\bf{Solution::}$ A relation is said to be equivalence, If it satisfy the following relation: $(1)$ It ...
0
votes
1answer
23 views

Binary relations on a set

I have a homework problem that asks this... a) List all the different binary relations on the set $\{0,1\}$ I assume that since the relation is not given then the answer must be the graph, or ...
0
votes
1answer
18 views

How to count the number of distinct equivalence classes for a relation involving truth tables?

I am having trouble with question 22 part (2): Here is the solution: How did the author know that there are 256 distinct equivalence classes? Where did they get $2^8$ from?
1
vote
2answers
36 views

Find the value of $x$ for which $ff=gf$.

Functions $f$ and $g$ are defined by $f:x \mapsto \frac{1}{2x+1}$, $x \neq \frac{-1}{2}$ and $g:x \mapsto x+1$. Find the value of $x$ for which $ff=gf$. So I started in this way: $f[f(x)]=g[f(x)]$ ...
1
vote
1answer
41 views

Find the fuction $g$.

If $f:x \mapsto x^2 + 3$, find function $g$ such that $gf:x \mapsto 2x^2 + 3$. I don't know how to do it, there is no such example in my book. Help?
0
votes
2answers
11 views

Finding the present property

For each relation, determine which of these properties are present: reflexivity, symmetry, antisymmetry, and transitivity: I know the definitions of each of the properties but unclear as to how to ...
1
vote
0answers
25 views

What does a null relation on all real numbers look like?

I'm being asked to test for reflexivity, symmetry, transitivity, and antisymmetry on a null relation for all real numbers, i.e. $X=\mathbb{R}; R = \emptyset $. What would such a resulting set look ...
0
votes
1answer
19 views

Is this relation transitive?

R: { (1,1), (1,3), (2,2), (3,1) } My answer is no. My logic is that If (3,1) is in the relation, and (1,3) is in the relation, that implies that (3,3) must also be in the relation. Just wanted to ...
0
votes
2answers
10 views

Find a relation over $P(${$1,2,3$}$)$ such that $|R|=12$ and the transitive closure of $R$ is the proper subset relation

I'm having trouble finding relation $R$ over $P(${$1,2,3$}$)$ such that $|R|=12$ and the transitive closure of $R$ is $T$, the proper subset relation over $P(${$1,2,3$}$)$. My thoughts: a pair of ...
0
votes
1answer
75 views

Find the transitive closure of {$(1,2),(2,3),(4,4),(5,4),(5,7)$}

I want to find the transitive closure of $R=${$(1,2),(2,3),(4,4),(5,4),(5,7)$}. I'm having trouble with transitive closure. We have that $(1,2)$ and $(2,3)$, so the transitive closure of $R$ is $R ∪ $ ...
0
votes
1answer
71 views

How many symmetric and transitive relations are there on ${1,2,3}$?

I'm trying to count the number of relations on ${1,2,3}$ that are symmetric and transitive. I know how to count the symmetric relations but I can't seem to find the method for this one. I've counted ...
0
votes
1answer
26 views

State the range of the function below.

Sketch the graph of $f:x \mapsto -4x + 5$ , $x<2$ and state the range. I got the graph, but can't state the range...how to find them?