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

3
votes
3answers
93 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
63 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
51 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
31 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
39 views

state the relations of a set

Consider the following relations: ...
0
votes
1answer
34 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
778 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
32 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
60 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
57 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
46 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
38 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
42 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
20 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
39 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
132 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
17 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
79 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
42 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
28 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
43 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
97 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
28 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
32 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
58 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
34 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
31 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
102 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
55 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
45 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
26 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
24 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
26 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
21 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
106 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
88 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?
0
votes
0answers
176 views

Draw arrow diagram to show the following function.

Draw arrow diagram with two parallel lines to show the function $f:x \mapsto 3 - 2x^2$. Let the domain be the set of integers and draw six arrows for the function. How to draw it?
0
votes
1answer
33 views

Proving equivalence relations in special symbols

For a function $f: A\to B$, I have a relation $@$ on $A$ described by $(\forall x,y \in A)\quad x @ y \Leftrightarrow f(x) + f(y)$ Is there any way to show that $@$ is an equivalence relation?
0
votes
1answer
75 views

Equivalence Relation on R (real numbers)

Let R be the relation on R(real numbers) defined by: For all x, y (that belong) to R(real numbers), x relates y <=> x-y (that belongs) to Z. (a) Is R an equivalence relation? Prove your answer. ...
1
vote
1answer
63 views

Let A = {1,2,3,4} Let F be the set of all functions from A to A. (check the parts)

Let $\operatorname{S}$ be a relation on $F$ defined by: $\forall f, g \in F, f\,\operatorname{S}\,g \iff f(i) = g(i), \exists i \in A$. (a) Recall that the identity function $I_A : A \mapsto A$ is ...
1
vote
2answers
39 views

How to show properties of a given relation?

I am given that R is a relation on the given set X, and I have to show if the relation is (i) reflexive, (ii) symmetric, (iii) transitive, (iv) asymmetric, and (v) give an example of an element of ...
1
vote
1answer
52 views

$M_{R^n}$; how to derive $n$ for transitive closure?

When finding the transitive closure of a relation $R$, I convert $R$ into a boolean matrix $M_R$, and find the union between $M_R$ and its powers up to $n$. $$M_{R^*} = M_{R^1} \lor M_{R^2} \lor ...
0
votes
1answer
75 views

Show that if $R$ is a strict partial order on $X$, and $R$ is not linear, then there exists a strict partial order $R'$ and $R' \supsetneqq R$.

Question: Show that if $R$ is a strict partial order on $X$, and $R$ is not linear, then there exists a strict partial order $R'$ and $R' \supsetneqq R$. My attempt: By definition 6.23,6.3.1, and ...