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
56 views

I have two symmetric relations on a set. How can I prove that the symmetric difference is irreflexive?

I have this problem. Let R and S be symmetric relations on a set A. Prove or disprove: $R \oplus S$ is irreflexive. Now I'm assuming it's not true, because $(x,x)$ can be an element of $R$ ...
-1
votes
3answers
91 views

A big list of non-trivial examples of functions from outside mathematics

I will be teaching my students about functions, and want to stress that functions are not only the usual mathematical ones (linear, logs, exponential, ...), but that function is fundamentally a ...
5
votes
1answer
127 views

Where can I learn more about the Galois connection induced by a graph on its own powerset?

Given a binary relation $R \subseteq X \times Y$, we get an antitone Galois connection $(F,U) : \mathcal{P}(X) \rightarrow \mathcal{P}(Y)$ in the usual way: The function $U : \mathcal{P}(X) ...
2
votes
2answers
35 views

Determining if the relation is an equivalence one.

Determine if the relation : $$x \sim y \iff |y-x| \text{ is an integer multiple of } 3$$ is an equivalence one. Now, I think this is an equivalence relation but I am having troubles formally ...
1
vote
1answer
28 views

Why is this relation a function?

I need to determine whether or not the relation $\{ (a^2,a) | a \in \Bbb {R}, a \geq 0\}$ is a function from $\Bbb {R}$ to $\Bbb {R}$. I think that it is a function. But I don't know how to ...
2
votes
2answers
69 views

Is the relation a function

I'm trying to determine if the relation $\{(\frac{a}{b}, a-b) | a,b \in \Bbb {Z}, b \neq 0\}$ is a function from $\Bbb {Q}$ to $\Bbb {Z}$. I know that a relation is a function from A to B if dom(f)=A ...
1
vote
2answers
42 views

Is the relation a function?

Is the relation on $\Bbb {R}$ a function from $\Bbb {R}$ to $\Bbb {R}$? $$\{(a^2,a)\mid a \in \Bbb {R}\}$$ How do I determine whether or not the relation is a funtion? Would I treat $(a^2,a)$ as ...
1
vote
1answer
28 views

Transitive closure of $H=\{(a,b) \in \mathbb{R}^2: |a-b| \leq 0.1\}$

$$H = \{(a, b) \in \mathbb{R}^2: |a − b| \leq 0.1\}$$ In class today we went over this problem as an example to show transitive closure. I know that the transitive closure of $H$ is "All real ...
0
votes
1answer
49 views

What is the cardinality?

Let $A=\left\{1,2,\cdots,10\right\}$ Let $f,g:A\to A$. Consider the equivalence relation $$ fRg \iff \exists h:A\to A. f=h\circ g$$ where $h$ is invertible. Now, let $g(x)=5$: Why is $\left| ...
3
votes
3answers
528 views

How many functions are transitive?

Let the set of all functions defined as: $\left\{a,b,c,d\right\} \rightarrow \{a,b,c,d\}$ How many functions are transitive? I've been told to use the fact that a function is transitive iff "it's ...
0
votes
2answers
64 views

Prove that the binary relation “is a subset of” is a…

Prove that the binary relation "is a subset of" is a partial order (POSET)? Should I try to prove this in reference to the power set of a general set? When is this relation a total order?
1
vote
1answer
23 views

An accessible example of a preorder that is neither symmetric nor antisymmetric

For a project I am working on, I need an example of a preorder (reflexive and transitive relation) that is neither symmetric (like an equivalence relation) nor antisymmetric (like less than or equal ...
1
vote
1answer
90 views

Example of relation that is neither transitive nor intransitive?

I have been struggling to think of an example of a relation that is neither transitive nor intransitive, does anyone have any tips? I ended up finding one website that described this as non ...
0
votes
1answer
30 views

Is it Preference relation?

I need to check if the relation $ \succeq ( \space \succeq \space \subset X × X, \space X=VB[0,1] ) $ define as below $$ f \succeq g \Longleftrightarrow Var(f+g) \geq Varf $$ is preference ...
2
votes
1answer
81 views

A relation that is Reflexive & Transitive but neither an equivalence nor partial order relation

Set $A = \{0,7,1\}$ 1. So for a relation that is reflexive and transitive but neither an equivalence relation nor partial order...Can a relation be both partial order and equivalence? Attempt: ...
2
votes
1answer
73 views

Proving that a relation is an equivalence relation

I am having difficulties proving the relation IS an equivalence relation. Let $f: X\longrightarrow Y$ be a function from a set $X$ onto a set $Y$. Let $R$ be the subset of $X \times X$ consisting ...
1
vote
2answers
36 views

The relation on the set of functions

Let $\varphi: \mathbb{R}^{2} \to \mathbb{R}$ be a symmetric (not necessarily continuous) function (so, $\varphi(x,y)=\varphi(y,x)$ $\forall (x,y)\in \mathbb{R}^{2}$), let $\mathcal{F}$ be the set of ...
0
votes
1answer
45 views

What does it mean for a binary relation to be an order on “equivalence classes” under another binary relation

I am a bit confused about this statement in "Introduction to Set Theory" by Hrbackek and Jech. The statement is as follows: "|A| <= |B| behaves like an ordering on the "equvivalence classes" under ...
2
votes
1answer
110 views

The category with binary relations as objects

I have reconsidered my ideas and remember how I thought ones upon a time. I will make a last try and delete if it doesn't work: Set is the category where sets are objects and functions are morphisms ...
1
vote
1answer
19 views

Re-calculating Value of $100 in Each State by Specific State

I'm using this Tax Foundations graphic for data. How would I re-calculate each state based on a specific state? For example, what if I wanted to base the control state on Missouri, which is $113.51. ...
1
vote
1answer
85 views

how to show a function is bijection

I have taken two numbers $p$ and $r$ where $p,r\in A = \{0,1,\ldots,4i + 1\}$ where $i\geq 1$ and $q\in B = \{0,1,\ldots,n-1\}$. Let $X$ contains all elements obtained by cartesian product of $A$ and ...
4
votes
1answer
154 views

Some questions concerning continuity and relations

A lot of equivalent conditions for functions between topological spaces $$ X\overset f\longrightarrow Y $$ are proved on this site. Here some of them formulated from the perspective of 'relations': ...
1
vote
1answer
63 views

Is the relation $a\mathrel R b \iff f(a) \equiv f(b)$ an equivalence relation?

Suppose that I have a relation $R$ of the form $a\mathrel R b \iff f(a) \equiv f(b)$, where $\equiv$ is an equivalence relation. In general, is $R$ also an equivalence relation? If not, what are the ...
3
votes
1answer
38 views

A question about equivalence classes

Theorem: Let $P$ be a partition of a set $S$, and let $a$ and $b$ be $\in S$. Define the relation $R$ on $S$ as follows: $aRb$ iff there exists an $X \in P$ such that $a \in X$ and $b \in X$. ...
7
votes
3answers
328 views

Can only one ordered pair be a relation?

I'm sorry, but I really can't find an answer to this no matter how deep I dig. A relation is defined as any set of ordered pairs. But what about a set of only one ordered pair? Is it still a ...
1
vote
1answer
36 views

Composition of Ordered Pair

I'm doing math exercises from a Computer Science book and I am confused as to how the following result (from the solutions manual) is obtained: Given the function f={(a,b), (a,c), (c,d), (a,a), ...
2
votes
1answer
108 views

Defining a partial order on $A\times B$, given partial orders on $A$ and on $B$

Let $(A,\preceq_A)$ and $(B,\preceq_B)$ be partially ordered sets. Define $C = A \times B$ and define the relation $\preccurlyeq$ on $C$ to be $(a,b) \preccurlyeq$ $(a',b')$ if and only if ...
0
votes
0answers
20 views

similarities between two binary matrices

I want to measure the similarities between two matrices A and B. Both A and B contains the feature vectors of sounds and are in binary format. i want to see what is the similarities between these two ...
0
votes
1answer
39 views

What is the name of this property of relation?

What is the name of property of a binary relation $R$ that states that $\lnot(a\mathrel{R} b) \iff \lnot(b \mathrel{R} a)$ for all $a, b$?
1
vote
1answer
37 views

Quotient set cardinal in $\mathbb{Z}_{12}$

In $\mathbb{Z}_{12}$ define the equivalence relation xRy if $x^2 = y^2$ Then what is the cardinal of the quotient set?
0
votes
1answer
32 views

Cardinal of the quotient set

Let $X = \{1, 2, 3, 4, 5, 6, 7, 8, 9\}$. In $X \times X$ define the equivalence $(a,b)\:\mathcal{R}\:(c,d)$ if $a+b=c+d$. Then what is the cardinal of the quotient set? I know that $|X| = 9$, so $| X ...
2
votes
3answers
41 views

Composite Relations

I'm new to functions and relations, and I've only just figured out that there are 16 relations on a set with 2 elements. I can't figure out what is meant by R ; R ⊆ R other than the fact it is a ...
1
vote
1answer
47 views

What are the steps to calculate the number of elements in a quotient?

Let $X = \{0,1,2,3,4,5,6,7,8,9\}$ and $ Y = \{0,2,4,6,8,9\}$. In $P(X) =$ power set of $X $ define the following relation: $$A R B \Leftrightarrow A \setminus Y = B \setminus Y $$ Then, how many ...
0
votes
2answers
44 views

how to find the equation of this set of points?

What the relation (Equation) between these numbers (X, Y, Z)? Your answer will be highly appreciated.
0
votes
0answers
39 views

Is a set of some $m \times n$ matrices a relation?

A relation between sets $A_i, i = 1, \dots, n$ is defined as a subset of $\prod_i A_i$. Given $m, n \in \mathbb N$, is a set of (some or all) $m \times n$ matrices over $\mathbb R$ considered a ...
2
votes
1answer
32 views

Is this relation symmetric

$R = \{(X, Y) \in \mathscr{P}(A)^2| X \subset Y \text{ and }X \neq Y \}$ I know that $(X,Y) \in R$ holds true since $X \subset Y$. However I'm unsure if $(Y,X) \in R$ since if $Y \subset X$ then ...
1
vote
1answer
94 views

Is the subset relation on the powerset of a set, with qualification, reflexive?

I was wondering if the subset relation is reflexive? $R = \{(X, Y ) \in P(A)^2\mid X\subseteq Y \text{ and } X \neq Y \}$ I assumed they it was reflexive since for all $X \in P(A), X \subseteq X$ is ...
-2
votes
2answers
35 views

Finding Domaing and Range [closed]

Can you please tell me how i am going to solve these? $R=\{(x,y)\in \mathbb R^2 | x^2=y^2\}$ $R^{-1}=?$ $R\circ R^{-1}=?$ $\text{dom} (R)=?$ $\text{range}(R)=?$ Thanks..
1
vote
2answers
49 views

Anti-symmetric relations

I'm having issues wrapping my head around anti-symmetric examples in specific contexts. I understand that if BOTH $a$, $b$ belong to $\mathbb{R}$ then $a = b$ and if $a \ne b$ then they aren't ...
0
votes
0answers
32 views

Properties of R, R^n, R*

I was talking to a friend who mentioned that eventually, R^n and R* are equivalent. This confuses me because I don't see how it's necessarily the case. But it does seem to hold, for instance: R = ...
1
vote
1answer
42 views

Let R be the relation on ℤ+→ℤ+ defined by (a,b)R(c,d) if and only if a-2d=c-2b. List all the elements of the equivalence class [(3,3)].

I'm confused on how to find all the elements. I know how to find some but not all, wouldn't they be infinite? This is affecting me with the other questions as well. Thanks in advance!
3
votes
1answer
37 views

Is there a specific name for a directed graph that is composed of only loops?

Recently I have been doing practice questions for my Final exam tomorrow and this one question appeared that was interesting, but I couldn't seem to find the other half of the answer to it. Q: Given ...
3
votes
1answer
47 views

Geometric/visual interpretation of transitivity for equivalence relations on $\mathbb{R}$

If we graph equivalence relations on $\mathbb{R}$ on the plane $\mathbb{R} \times \mathbb{R}$, the properties of reflexivity and symmetry give rise to certain geometric properties--i.e. reflexivity ...
5
votes
4answers
321 views

Can functions be defined by relations?

So let us say that for whatever reasons, we are not allowed to use function symbols in first-order logic. Then can we define and use a function only by relations?
2
votes
1answer
35 views

Proving that this relation is transitive

I have seen this question on a book I am reading and could not figure it out fully. The question is as follows: "Suppose A is a set, and $F\subseteq P(A)$. Let $$R_F=\{ (a,b)\in AxA|\text{ for every ...
0
votes
1answer
30 views

suppose $R$ is an equivalence relation on $A$ such that there are only finitely many distinct equivalence classes $A_1,A_2,\ldots,A_k$ w.r.t $R$

Suppose $R$ is an equivalence relation on $A$ such that there are only finitely many distinct equivalence classes $A_1,A_2,\ldots,A_k$ w.r.t $R$. Show that $$A=\bigcup_{i=1}^k A_i$$ Since $A_i\subset ...
0
votes
0answers
38 views

Is there a standard symbol that denotes the set of relational operators

I am writing a research paper, and I would like to somehow denote the set of relational operators $$ \left\{ =,>,<,\leq,\geq,\neq\right\} $$ Before I use some random symbol for that purpose, ...
2
votes
1answer
177 views

Proving Transitivity

Consider a relation defined by $Z$ where $(a,b) = 2a^2 + b^2 -3ab = 0$ Is the relation $R_1$ reflexive? symmetric? transitive? Is it an equivalence relation? I have said that it is ...
0
votes
4answers
143 views

If R is $(a,b)R(c,d) \iff a+d =b+c$ show that R is an equivalence relation.

The relation R is defined n all positive integers such that, $(a,b)R(c,d) \iff a+d =b+c$ . Show that R is an equivalence relation. In order to be an equivalence relation, R has to be reflexive, ...
0
votes
1answer
38 views

Proof for a relation

Define a relationship $R$ on $\mathbb{Z}$ by declaring that $xRy$ if and only if $x^2 \equiv y^2 (mod 4)$. Prove that $R$ is reflexive, symmetric and transitive. I'm unsure of where to start with ...