Questions tagged [relations]

For questions concerning partial orders, equivalence relations, properties of relations (transitive, symmetric, etc), a composition of relations, or anything else concerning a relation on a set.

Filter by
Sorted by
Tagged with
0 votes
0 answers
48 views

Can a partially ordered set contain an infinite cycle?

A partially ordered set is defined as a set with a relation that is symmetric, transitive, and anti-reflexive. The transitivity and anti-reflexivity rule out cycles. We can't have "a < b < ...
user avatar
0 votes
0 answers
40 views

What kind of operation is cube root extraction?

I came across this question in a random test and the correct answer was marked as "Binary Operation". I am pretty sure that to find the cube root of a number you only need that number alone ...
user avatar
0 votes
1 answer
21 views

Completeness of Binary Relations

Completeness of binary relations often is defined as: The binary relation R of a set A is complete iff for any pair x,y ∈ A: xRy or yRx. My question is: what does one mean by „pair“? To me it seems ...
user avatar
-1 votes
1 answer
38 views

Assume $g: A \to B$ and $f: B \to C$. If $f\circ g$ is surjective, then $f$ would be injective. True or false?

Assume $g: A \to B$ and $f: B \to C$. If $f\circ g$ is surjective, then $f$ would be injective. Would this proposition be true or false?
user avatar
-3 votes
1 answer
33 views

Question about Equivalence class [closed]

I believe I understand the concept of equivalence class. However, I found this example from my lecture slides very confusing. Could someone explain to me why ...
user avatar
0 votes
2 answers
43 views

Proving reflexivity, symmetry, and transitivity for the relation $\sim$ on $\Bbb{R}$ such that $x\sim y$ iff $x+y\in\Bbb{Q}$

I am going through past papers for my university exam, and a question in this format appears often: Define a relation $\sim$ on $\Bbb{R}$ by $x\sim y$ if and only if $x+y \in \Bbb{Q}$. Justify your ...
user avatar
-1 votes
0 answers
46 views

Abstract: symmetry, reflexivity, and transitivity!

I need help with how to approach and start a problem regarding a relation $R$. Define a relation $R$ on sets as follows. $$\small R=\{(A,B):{A\text{ and }B\text{ are sets and there is a function }f:A\...
user avatar
0 votes
0 answers
51 views

Possible partial order relations U with Hasse Diagrams for each possible relation

How many possible partial order relations U there are on the set {a, b, c,d} such that ● bUa, cUa, dUa; and ● this condition How to draw a Hasse diagram for each possible relation. Please provide a ...
user avatar
1 vote
2 answers
90 views

Is it true that if $f:X\rightarrow Y$ and $g:Y\rightarrow X$ such that $g∘f=I_X,~~f\circ g=I_y$ then $f,g$ must be one-one and onto (i.e. bijective)?

Is it true that if $f:X\rightarrow Y$ and $g:Y\rightarrow X$ such that $g\circ f=I_X,~~f\circ g=I_y$ then $f,g$ must be one-one and onto (i.e. bijective)? Claim. Yes. Proof. Since $g(f(x))=x \implies ...
user avatar
  • 3,981
0 votes
0 answers
33 views

Proving Inequality Operation is Well-Defined

Preliminary information: Let $\sim$ be a relation on $\mathbb{N^2}$ defined by $(a,b)\sim(c,d)$ if $a+d=b+c$. I am trying to prove that $\le$ is well-defined. Define $[(a,b)]\le[(c,d)]$ if $a+c \le b +...
user avatar
0 votes
1 answer
26 views

Relations Definition [duplicate]

according to wikipedia the definition of relation is a set ordered pairs that is subset to cartesian product. My question is ''Is this all about relations ?'' so it's just ordered pairs even if it ...
user avatar
  • 1
0 votes
1 answer
30 views

Are Relations just ordered pairs?

The definition of a Relation is a set of ordered pairs So are Relations just sets of ordered pairs ? I mean if there is a set of ordered pairs that carries no definite relation between it's pairs [...
user avatar
0 votes
1 answer
50 views

What is a Relation?

In discrete math we define the relation as a sets of pairs of numbers, I understand when we write (a,b) we mean that (a) and (b) are realted what I don't grasp at all why the realtion between two ...
user avatar
0 votes
1 answer
35 views

The Meaning of Relations [closed]

I'm studying relations and I've been told that relations are sets of ordered pairs. My tutors provide examples like these: The less than relation (<) consists of all ($a$,$b$) such that $b-a$ is a ...
user avatar
  • 1
0 votes
1 answer
24 views

For $a \equiv b$ (mod n), where n is greater than 1 and positive, must the factor of n also be greater than 1? [duplicate]

So I am working on a relation problem on the set of positive integers if and only if $a \equiv b \pmod n$. That in itself is fine. But when I want to prove that the relation is for example reflexive, ...
user avatar
  • 77
0 votes
0 answers
18 views

Proving Equivalance relation (transitivity)

$$relation = {(a, b) | b − 3 < a ∧ a < b + 3}$$ Unsure how to proof transitivity. Also is my reflexive and symetric proof strong enough? A = $\{\mathbb{Z}\}$ Reflexive: yes because $\forall x \...
user avatar
0 votes
1 answer
37 views

Reflexive relation on all integers

Let $R = \{(a,b)\mid a\cdot b=21\}$ be a relation on all integers. so $R = \{(1,21), (3,7), (7,3), (21,1)\}$ I fail to understand if the domain here is all integers or only A, the domain, $= \{1,3,7,...
user avatar
0 votes
0 answers
33 views

Is Sqrt(x) not well defined? [duplicate]

I recently came across the notion of a function being "well defined" in some exercises in an abstract algebra book I'm reading. What I could gather about the definition (of which there seems ...
user avatar
0 votes
1 answer
187 views

How many possible partial order relation U are there in this set?

How should I tackle this question? Note: A relation is Partial Order relation if it is Reflexive Anti-Symmetric Transitive
user avatar
  • 11
0 votes
0 answers
13 views

Construction of order-preserving map on Bourbakian poset

Given an order preserving map $$f:\alpha\to P$$ with $\alpha$ an ordinal and $P$ a Bourbakian poset, I'm trying to construct an order preserving map $$g: P\to P$$ whose fixed points are precisely the ...
user avatar
0 votes
1 answer
69 views

If the function f is defined as a set of ordered pairs that fullfill certain criteria, then how can I define f(x)?

Assume that $f=\{(x,y)|Pxy\}$ is a function. My best attempts so far include the following: $f(x)=y \iff (x,y)\in f$ The problem with this method is that I still don't have a standalone definition ...
user avatar
0 votes
1 answer
36 views

Construct transitive relation of ancestors from relation of parents in a family tree

For my thesis I'm trying to think of an intuitive example to illustrate properties of different relations. For a set of family members $S = \{\texttt{A1}, \texttt{A2}, \dots, \texttt{C3}\}$, I created ...
user avatar
0 votes
1 answer
40 views

Transitive binary Relation on sets

Consider a set , A = { 1 , 2 , 3 } Subset = { (1,3) , (1,2) } is a transitive relation . But I don't get that how it is transitive relation because there is no ...
user avatar
0 votes
0 answers
9 views

What properties does a relation need to have in order for sorting algorithms to work on it?

Suppose $R$ is a relation on an $n$-element list $A$ and I want to find a permutation $(a_1, a_2,\dots, a_n)$ of $A$ such that $$a_1 R a_2 \quad \text{and} \quad a_2 R a_3\quad \text{and} \quad \cdots ...
user avatar
0 votes
0 answers
44 views

Is there any proof of $\#(F/N)=2n$ which doesn't use any group other than $F/N$ itself? (Michael Artin "Algebra 1st Edition")

I am reading "Algebra 1st Edition" by Michael Artin. The following proposition is Proposition (8.3) on p.221 in this book. (8.3) Proposition. The elements $x^n,y^2,xyxy$ form a set of ...
user avatar
  • 6,051
0 votes
0 answers
19 views

Question about a proposition about free groups, generators and relations. Is it true or false that $N=\ker\phi$ holds? Michael Artin "Algebra 1st Ed."

I am reading "Algebra 1st Edition" by Michael Artin. I feel free groups, generators and relations are very difficult. The following proposition is Proposition (8.3) on p.221 in this book. (...
user avatar
  • 6,051
3 votes
1 answer
87 views

How do I prove symmetry without a defined set?

I have a formula: ∀x,y, z(xRy ∧ xRz → yRz) If the formula holds for a relation, then the relation is Euclidean. If a relation is Euclidean and reflexive, what are the steps for proving it is also ...
user avatar
0 votes
1 answer
69 views

What does the author want to say about generators and relations in group theory? ("Algebra 1st Edition" by Michael Artin) [closed]

I am reading "Algebra 1st Edition" by Michael Artin. I want to know about generators and relations because I think I need to know about generators and relations when I use the GAP software. ...
user avatar
  • 6,051
1 vote
0 answers
40 views

Meaning of "a function $f$ defined on $\mathbb{R}$

When we say a function $f$ is defined on $\mathbb{R}$, does it mean the domain is $\mathbb{R}$ but not necessarily the co-domain is $\mathbb{R}$, or does it mean both the domain and co-domain is $\...
user avatar
  • 455
0 votes
0 answers
103 views

The definition of equality of sets and functions are contradictory. [duplicate]

Suppose we have two functions $f=\{(1,2),(3,4)\}$ and $g=\{(1,2),(3,4)\}$ with codomains $A$ and $B$ respectively so that $A\not=B.$ Then since $f$ and $g$ are sets, then the definition of equality of ...
user avatar
  • 273
0 votes
0 answers
8 views

confusion with an order relationship on $\mathbb{C}$ [duplicate]

In the additive group $(\mathbb{C},+)$ define a relation by placing: $a+bi \leq c + id$ if $b < d$ or $b = d$ and $a \leq c$. $(\mathbb{C},\leq)$ is a total order? I think not because for example $...
user avatar
0 votes
1 answer
23 views

Gelfand's corrolaries counterexample?

Gelfand's corrolaries (https://en.wikipedia.org/wiki/Spectral_radius#Gelfand_corollaries) state that, for any $2$ matrices $\mathbf{A}_1$, $\mathbf{A}_2$, the following relation is true: $ \rho(\...
user avatar
  • 5
0 votes
0 answers
51 views

Relations and Cartesian Product: why does $X^1$ differ from $X^0$ and $X^2$?

Question Why are functions of a single variable specified with a tuple argument $(x)$ as in $f(x)$, when this pattern suggests they should be specified without parenthesis as $fx$? This pattern (1): $$...
user avatar
  • 941
0 votes
0 answers
40 views

Confusion about what a relation is

I am having trouble understanding what a relation actually is. The way I understand it is, if $A$ and $B$ are sets, then a relation from $A$ to $B$, $R$, is simply any subset of $A \times B$. This ...
user avatar
  • 317
0 votes
0 answers
12 views

Closure of a fuzzy relation

In paper Special properties, closures and interiors of crips and fuzzy relations https://doi.org/10.1016/0165-0114(88)90126-1, can anyone explain what is the point of introducing the closure of a ...
user avatar
  • 241
0 votes
2 answers
40 views

Is $y > x$ or $y < x$ the converse of $x > y$?

$G \subseteq A^2$ $G = \{(x|y): x > y\}$ $G^{-1} = \{(y|x): x > y\} = \{(y|x): y > x\}$ or $G^{-1} = \{(y|x): y < x\}$ ? The converse of the "greater than"-relation is the "...
user avatar
0 votes
1 answer
34 views

Find the supremum and infimum of $B = \{g(x)=x,g(x)=x^2\}$ on the partially ordered set $Y=\Bbb R^{[0,2]}$ by pointwise relation.

Find the supremum and infimum of $B=\{g(x)=x,g(x)=x^2\}$ on the partially ordered set $Y=\Bbb R^{[0,2]}$ (set of all functions from $[0,2]$ to $\Bbb R$) by pointwise relation. Edit: Definition. A set $...
user avatar
  • 1,951
1 vote
1 answer
72 views

Is this a valid justification that the relation $R$ is not transitive?

The question I was working on was asking to find whether the relation $R$ defined on $\mathbb{Z}$ by $a\,R\,b$ if $|a-b|\leq 2$ is reflexive, symmetric, and/or transitive and provide justification. I ...
user avatar
2 votes
1 answer
30 views

Finding and drawing equivalence class with a binary set defined on RxR

In the question, it has been asked to find and draw the equivalence classes of the relation $∼$ on $(\Bbb R\times\Bbb R)\setminus\{(0, 0)\}$ which is defined as $$(x_1, x_2) \sim (y_1, y_2)~\text{if}~(...
user avatar
  • 125
0 votes
3 answers
99 views

Why is $\lor$ used in cases where xor is intended?

A binary relation $R$ on a set $X$ is trichotomous if the following is true: $$\forall x,y \in X ([\neg(x <y) \land\neg(x=y) \land (x>y)] \lor [\neg(x <y) \land(x=y) \land \neg(x>y)] \lor [...
user avatar
2 votes
1 answer
37 views

Prove that a relation isn't transitive

Let \begin{eqnarray*} M_{R}= \begin{pmatrix} 1 & 1 & 0\\ 1 & 1 & 1\\ 0 & 1 & 0 \end{pmatrix} \end{eqnarray*} Where $M_{R}$ is the relation matrix for a relation $R$. ...
user avatar
0 votes
0 answers
37 views

Cartesian equation of a trapezium

Is there a single (not piecewise or parametric) equation for a trapezium (trapezoid for our American members)? EDIT: Since someone asked me to provide a more specific example for them, there is one ...
user avatar
0 votes
0 answers
21 views

Statements about relations and functions but no restriction on sets

In "Elements of Set Theory" 41p and 44p Exercise 3-8. Show that for any set $\mathscr A$: $dom\,\bigcup \mathscr A = \bigcup\{dom\,R\,|\,R\in\mathscr A\}$ $ran\,\bigcup \mathscr A = \...
user avatar
  • 467
0 votes
1 answer
33 views

What makes one relation stronger than another?

I'm trying to remember a shorthand for a binary relation on relations: Suppose relation $R_2$ contains every tuple that is in $R_1$, and at least one additional tuple. Do we say "$R_2$ is ...
user avatar
-1 votes
1 answer
21 views

Set of elements of an idempotent semirings are totally ordered.

An element $S$ is said to be totally ordered set if for all $a, b\in S\implies$ either $a\leq b$ or $b\leq a.$ An algebraic structure $(S, +, \cdot)$ is said to be an idempotent semiring if $x\cdot x=...
user avatar
  • 1,174
0 votes
0 answers
62 views

Is there a name for non-reflexive "equivalence" relation?

An equivalence relation $a \sim b$ is a binary relation which is symmetric, transitive, and reflexive. What if I give up on reflexiveness? I mean, in the set where the binary operation $\sim$ is ...
user avatar
  • 305
0 votes
1 answer
31 views

What are reflexive relations?

I am having some confusing regarding reflexive relations. Let's take an example $$\{(a,b):a+2b\ \text{must be divisible by 3, a and b are natural numbers}\}$$ Some elements of the relation are $(1,1),(...
user avatar
6 votes
2 answers
127 views

An order that lacks "infinite" transitivity?

The ordering on the real line "$<$" possesses the property that if we have a sequence $(a_n)_{n=1}^{\infty}$ such that $a_n < a_{n+1}$ and if we have a finite limit $a$, then $a_1 < ...
user avatar
1 vote
0 answers
22 views

Composed relations and simplicial complexes?

Say you have two relations $R$ and $S$ on finite sets such that the composition $RS$ is well-defined. Each of these has a corresponding Dowker complex (actually two, but they are homotopy equivalent). ...
user avatar
1 vote
2 answers
66 views

Number of element in a relation $R$ of $\{1, \cdots, n\}$. [closed]

Let $A = \{1,2,...,n\}$, and $R$ be a relation on $A$ (so $R \subset A \times A$) i) What is the minimal possible number of elements in $R$? I tried calculating this as just a normal cartesian product ...
user avatar
  • 95

1
2 3 4 5
88