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
-2 votes
0 answers
33 views

Find a set of minimal elements in set $\langle \mathbb N\setminus\{0\},|\rangle$

We consider a relation $|$ on set $\mathbb N\setminus\{0\}$ Find set of minimal elements in set $\langle \mathbb N\setminus\{0\},|\rangle$ Prove that in set $\langle \mathbb N\setminus\{0\},|\rangle$...
  • 1
1 vote
1 answer
49 views

Consider two relations $R$ and $S$ on a set $A$ with $R$ being antisymmetric. Prove $R \cap S$ is antisymmetric.

Consider two relations $R$ and $S$ on a set $A$ with $R$ being antisymmetric. Prove $R \cap S$ is antisymmetric. Theorem The subset of an antisymmetric relation is also antisymmetric. The intersection ...
0 votes
0 answers
35 views

Find equivalence classes of a relation $x\mathcal{R}y \iff (\exists{t}\ne 0)(tx=y)$

On a set $X = \mathbb{R}^2$ is defined an equvalance relatiion $x\mathcal{R}y \iff (\exists{t}\ne 0)(tx=y)$ What are the equvalance classes? I think that equvalance classes of some x are y that by ...
  • 1
0 votes
1 answer
19 views

Finding transitive closure

Answer the following, related to the relation $R$ on domain $D$, where $D = \{1,2,3,4,5\}$ and $R=\{(1,1), (2,2), (3,3), (4,4), (5,5), (4,3), (3,4), (5,4), (4,5), (5,2), (2,4)\}$: List the elements in ...
1 vote
2 answers
43 views

Find cardinality of a set {$f \in \mathbb{N}^{\mathbb{N}}|f\le h$} where $h(n)=n+1$

On a set $\mathbb{N}$ is defined a partial order relation $f \le g \iff \forall{n\in\mathbb{N}} f(n) \le g(n) $. Also let $h: \mathbb{N}\to\mathbb{N}$ given by a formula $h(n)=n+1$. Find cardinality ...
  • 33
-2 votes
0 answers
54 views

What are the equivalence classes of a relation $\mathbb{R}: f \sim g \iff f′ = g′$. [closed]

What are the equivalence classes of a relation $\mathbb{R}: f \sim g \iff f′ = g′$. I can’t understand how this relation should be partitioned.
  • 33
1 vote
1 answer
43 views

Check if this function injective or surjective $ f(x,y)=[x]_R \cap[y]_R$

Let $ R \subseteq \mathbb{N}\times\mathbb{N}$ be an equivalance relation. Function $ f: \mathbb{N}\times\mathbb{N} \to \mathcal{P}(\mathbb{N})$ is describes as $ f(x,y)=[x]_R \cap[y]_R$ 1)Check if it ...
  • 33
1 vote
0 answers
40 views

About 2 operators such that $X*(Y+Z) = (X*Y)+(X*Z)$ , $W+(U+V)\neq (W+U)+V$

This question is a follow-up and analogue of a previous very similar question. I have to seperate questions since it is a bit of a rule ; 1 question at a time , hence this seperate one. Looking at the ...
  • 13.3k
0 votes
1 answer
21 views

Proof that order on $A \times B$ is linear only if $A$ or $B$ has no more than 1 element

$\le_A$ is linear order on $A$ and $\le_B$ is linear order on $B$, relation $\le$ on $A\times B$ denote by: $\lt a_1,b_1\gt \le \lt a_1, b_2 \gt$ $\iff$ $a_1 \le_A a_2 \land b_1 \le_B b_2$ Question is ...
3 votes
1 answer
66 views

About 2 operators and $A*(B+C) =(A+B)*(A+C)$

Consider $2$ binary operators defined for a finite set with $n$ elements. Operator $*$ behaves like a commutative latin quandle : $$x*x = x$$ $$a*b=b*a$$ $$a*(b*c)=(a*b)*(a*c)$$ And forms a latin ...
  • 13.3k
-1 votes
0 answers
54 views

Question about mistake in relationship [closed]

Isn't this definition of compounding a relationship wrong? That's what it says in my lecturer's script enter image description here, but I think it should be: $R\circ S = \left\{(x,z):(\exists y)(x,y)\...
-1 votes
0 answers
29 views

Can you define a function that changes the argument of a function?

It may be a stupid question, because it's my first question. But is there a way to define a function $\phi$, such that this function changes the argument of the function $f(x)$. For example $\phi$:$f(...
0 votes
4 answers
36 views

Can a strict order relation imply an equality relation?

Let's assume we have a partial or total order relation $R$ defined on a set $S$. If $R$ was not strict (i.e. it denoted $\leq$ instead of $<$), an equality relation $E$ could be defined as such: $$ ...
  • 193
0 votes
1 answer
51 views

Why can't a set {(1,1)} be an equivalence relation of set A={1,2,3}?

I know that {(1,1),(2,2),(3,3)} is an equivalence relation of the set A. But I am not sure why can't the set{(1,1)} be an equivalence relation? I think it is because the equivalnce relation is ...
-1 votes
1 answer
40 views

Proving that $\in_\alpha$ is transitive [closed]

In a proof my teacher used the following result without proving it: Let $\alpha$ be an ordinal and let $\in_\alpha \subseteq \alpha\times \alpha$ be a relation on $\alpha$ defined as: $$x\in_\alpha y\...
0 votes
1 answer
28 views

Function Mapping: What does $FunctionName: Domain\rightarrow 2^{something}$ mean?

I hope you are all doing well! I am taking two courses in theoretical computer science, and in both courses I have come across a notation that I am unfamiliar with. It is of the form: $FunctionName: ...
0 votes
0 answers
28 views

Calculating actual object size from inverse relation of size & distance [duplicate]

If I have the ratio of an object's perceived size & distance, how can I extend it to estimate the distance of any object based on perceived size? For instance, let's say a pencil is 50 pixels wide ...
0 votes
1 answer
49 views

Finding $\inf(\{30, 40\})$ and $\sup(\{2, 5\})$ in Hasse diagram

I would like to ask what is $\inf(\{30, 40\})$ and $\sup(\{2, 5\})$. I think that $\sup(\{2, 5\})$ is $20$ and $\inf(\{30, 40\})$ does not exist, but it may be $2$, but $5$ is on the same level and I ...
0 votes
1 answer
27 views

For transitive relations, do a, b and c have to be unique? [closed]

Theorem: If a relation is symmetric and transitive then it is reflexive. Proof. Let R be a symmetric and transitive relation. Take elements x,y satisfying x R y. Then y R x (since R is symmetric), and ...
0 votes
1 answer
37 views

Understanding the relation between transitive closure and convergent series

I am trying to better understand the concept of a transitive closure of a relation in the infinite case. Suppose we have the set {$ q \in \mathbb{Q}| \exists n \in \mathbb{N}, q = 1 - (\frac{1}{2})^n ...
2 votes
1 answer
58 views

Is "substitution" an axiom?

SUBSTITUTION: Let $\mathbf{F}$ be any algebraic structure. For each $a$, $b\in \mathbf{F}$ if $a=b$ then $a$ can be replaced with $b$ in any mathematical statement involving $a$ and the statement will ...
0 votes
1 answer
57 views

How to write a function as a relation?

How do we write a function as a relation?: In this thread the top answer has written a function as a relation as "$aRf(a)$" where I assume we can just define $b=f(a)$? I'm sure this is ...
  • 323
0 votes
1 answer
45 views

When is a function $f$ transitive?

I want to understand/unpack this definition of a transitive function: "A function is transitive iff it's restriction to it's image is the identity function on it's image" (From This post). ...
  • 323
0 votes
0 answers
20 views

Proving that the composition of relations preserves countability

Suppose there exists a relation $R$ such that $R$ is countable. I would like to prove that for all $k \in \mathbb{N}_1$, $R^{k}$ is countable (assuming that this actually is a true statement, which I ...
0 votes
0 answers
13 views

Understanding deviation and squared error

I'm wondering if set of numbers 1 can have a lower standard deviation and a lower variance than an other set of numbers 2 while having a higher mean squared error comparing to the other set 2?
1 vote
0 answers
22 views

Composition of congruence relations modulo n

I have the following exercise: In set $X$, let $\mathrel{R_1}$ be the congruence relation modulo 2, and let $\mathrel{R_2}$ be the relation of congruence modulo 3. Determine $\mathrel{R_1}\circ\...
-2 votes
1 answer
39 views

Prove if two relations are antisymmetric then their composition is also antisymmetric [closed]

I need someone to check if check if my reasoning is correct. I've got to proof that: if $\mathrel{R_1}$ and $\mathrel{R_2}$ are antisymmetric then $\mathrel{R_1} \circ \mathrel{R_2}$ is also ...
2 votes
0 answers
44 views

Transitive Relations clarification

Given set $A = \{1,2,3,4,5\}$. is it okay to say that {(1,2),(2,3),(1,3)} is transitive? Even though not all the elements of $A$ are not present inside the ordered pairs?
1 vote
1 answer
47 views

Is this a partial order relation?

Let $\;C$ = set of cities. The relation $\,S=\big\{(x,y)\;|\;x\in C\text{ and }y\in C$ are less than $50$ miles from each other$\big\}$ to me understanding is : reflexive: all cities are less than $...
0 votes
0 answers
43 views

What is the mathematical relation that can best represent the following curve?

Polynomial functions do not seem to represent the curve well. I do know the curve, but can not arrive at the mathematical relation that represents it. Please help me identify the equation for the ...
  • 1
0 votes
1 answer
83 views

Step in a proof that $G:=\langle x,y \mid x^n,y^2, (xy)^2\rangle$ is isomorphic to the dihedral group $D_n$

I’m reading a proof of the fact that the group given by the presentation $G:=\langle x,y \mid x^n,y^2, (xy)^2\rangle$ is isomorphic to the dihedral group $D_n$. It begins like this: Let $G=\langle \...
  • 107
-1 votes
1 answer
49 views

How can I prove symmetry for the following relation [closed]

For the following relation how can I prove symmetry? $R=\{(x,y)\mid\,\,\, 7\mid(3x+4y)\,\, x,y\in \mathbb{Z}\}$ I started with for every $xRy : (3x+4y)/7 = t$ ,when $t \in \mathbb{Z}$ but how can I ...
  • 17
1 vote
1 answer
100 views

What makes multiplication a basic operation on natural numbers but exponentiation is not?

Dear StackExchange Math Community: It has puzzled me for some time why multiplication is considered a basic arithmetic operation on natural numbers, but exponentiation is just viewed as a shorthand of ...
  • 31
0 votes
0 answers
30 views

Reflexive relation of sharing with yourself?

I'm looking at Sets, Logic and Maths for Computing by David Makinson and on page 56 is an example Identify the status of the following relations as reflexive/irreflexive/neither over the set of all ...
  • 804
0 votes
0 answers
39 views

Order relation notation $\succeq$

My main concern is with the notation around order relations, specifically the use of $\succeq$, I briefly outline relations more generally to set up my thinking. But the questions really starts at the ...
  • 323
0 votes
0 answers
24 views

Decomposability of Finitary Relations

I have an intuitive impression that a finitary relation of arity 3 or greater can always be decomposed into nested binary relations. However, I’m having trouble finding any reference for such a ...
  • 1
0 votes
1 answer
24 views

Relations: Completness implies reflexivity

I just wanted to check if this proof works, as I couldn't find anything online. Thanks! A relation is complete: $(_xR_y) \cup (_yR_x)\; \forall x,y \in X $ A relation is reflexive: $(_xR_x) \; \...
  • 323
0 votes
1 answer
24 views

Number of different relations that are both symmetric and reflexive on a set with 4 elements [duplicate]

Let S = {x | x is a prime number and 1 < x < 10}. Let N be the number of different relations that are both reflexive and symmetric that can be defined on S. Since there is only 4 elements in S={...
  • 11
0 votes
0 answers
27 views

Is my understanding of partial functions and total functions correct?

After reading this Math.SE answer, I wanted to know if my understanding of partial vs. total functions is correct. $$ \newcommand{\+}{\mkern2mu} \newcommand{\viff}{\Big\Updownarrow} \begin{gather*} f \...
0 votes
1 answer
27 views

A relation $R$ on $A$ which is symmetric and total but not transitive.

Exercise: Let $A = \left\{ a,b,c,d,e\right\}$. Find a relation $R$ on $A$ which is summetric and total but not transitive. Question: We want to find a relation $R$ on $A$, namely $R \subseteq A \...
  • 21.1k
0 votes
0 answers
38 views

Confusion with definition of antisymmetric relation

$\hspace{1cm}$ I am confused about the definition of antisymmetric relations. I understand that an equivalence relation $E$ on $X$ is a subset $E\subset X^2$ such that, for all $x,y,z\in X$, $\hspace{...
0 votes
1 answer
39 views

Relations, Transitive functions & Idempotent functions

I've read all the stack threads I can find on transitive functions and want to pull together the ideas/questions it leaves me with. This all started because as per this thread I wrongly thought ...
  • 323
0 votes
1 answer
44 views

Discrete Mathematics - Trees and Relations Question

I am completely stuck on this multiple choice trees question. In this multiple-choice question, more than one option can be correct. I believe this is a trees question; if it is not, then I have gone ...
  • 1
3 votes
1 answer
98 views

Understanding in what sense does the 'equals to' sign indicate equality in different scenarios.

I recently came to the realization that I've been taking the equals to sign for granted in mathematics and all of science. So I started to study about it in detail, and came to the understanding that -...
1 vote
0 answers
49 views

Set Theory: with an introduction to Real point sets

In the book Set Theory: with an introduction to real point sets (problem 15 on page 9) The problem states: If $\mathcal{R}$ is a relation, then $\mathcal{R}$ is a relation on some set $A$. How can I ...
0 votes
1 answer
28 views

Can a relation be transitive without a direct relation?

Say there is a set {x,y,z} and there is a relation R {(x,y), (y,z)}. Does that make the relation transitive, as x=y and y=z, making x=z? Or is it not transitive because there is no (x,z) relation?
0 votes
1 answer
42 views

Is 1-place relation just a single element set of N ?N is the set of natural numbers

I am confused about the 1-place relation. In the textbook, the definition of the 1-place relation is a subset of natural numbers. In the book, {1} is a an example oof 1-place relation. So according to ...
0 votes
1 answer
49 views

Why function is separated from relation in model definition

A model is defined as a universe together with symbols of relations, functions, and constants. I find this definition odd because a function can generally be considered a special case of a relation (...
  • 198
1 vote
1 answer
49 views

Prove or disprove : For every function f : B→C we have that if 1≤∣C∣<∣B∣ then f is not surjective. [closed]

Probably a trivial question, I do not know how can i visualise this problem and how can i provide a clear solution.
1 vote
1 answer
123 views

Is '=' or 'equals to' a relationship between Mathematical objects.

The Wikipedia definiton of equality gives it as a 'relationship between two expressions' This confuses me as when we define mathematical expressions like $2+2=4$ it makes no sense to say that '=' or '...
  • 151

1
2 3 4 5
90