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

13
votes
5answers
208 views

Does “=” have to be interpreted as equality?

To put it briefly: In model theory, we are allowed to interpret any relation symbol in any way we like. So why do people seem to require that "$=$" is interpreted as the actual equality? Let me ...
0
votes
1answer
11 views

Difference between Inclusion and continuation

Halmos defines the order continuation as follows: We shall say that a well ordered set A is a continuation of well ordered set B if B is a subset of A, if, in fact, B is an intial segment of A and ...
0
votes
1answer
18 views

$aRb$ iff $a=b(10)^k$ for some $k \in \mathbb{Z}$ [Prove Equivalence Relation]

The question: $R$ is a relation on $\mathbb{N}$ defined by $aRb$ iff $a=b(10)^k$ for some $k \in \mathbb{Z}$. Prove that $R$ is an Equivalence relation. The problem: I can define an ...
0
votes
3answers
71 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 ...
0
votes
2answers
28 views

How to find relation between 2 numbers

I have been practicing programming for many months now and what I found difficult is not about solving problem. But it is how to find the "how to solve problem" to make computer solves that for me! ...
4
votes
1answer
67 views
+50

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) ...
0
votes
1answer
18 views

Does an asymmetric relation entail an antisymmetric relation?

So if there exists an asymmetric relation within a set, does it also entail that there will be an antisymmetric relation in that same set? If so, then it is possible to find out whether a set ...
-1
votes
1answer
28 views

How is a relation defined on ordered sets?

I am reading that $(\mathbb{Z}, \leq )$ is a total ordered set. I understand how it satisfies reflexivity, antisymmetry, transitivity. But it says that because for any $a,b \in \mathbb{Z}$, either ...
0
votes
0answers
9 views

Partial Order Matrix Representaion

What would be the general matrix representation of a partial ordering ? i.e. since the relation must be reflexive, mat(i,i) = 1.
3
votes
3answers
506 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
0answers
21 views

Good book for self-studying Binary Relations

I am studying economics and I frequently encounter Binary Relations. But without any good knowledge of it, I get confused. Here is some background, if it's helpful: I know calculus(single and ...
1
vote
1answer
301 views

What are some concrete examples of kinds of relations in math?

I'm writing an undergrad philosophy paper. My take on the issue is that the conceptual problem I'm addressing is only a problem because the word 'is' and 'relation' are too slippery. By more precisely ...
0
votes
1answer
49 views

Why is this relation recursive?

A relation $R \subset \mathbb{N}^d$ is called recursive if there exists a primitive recursive function f with $$ (x_1 ,\dots,x_d) \in R \Leftrightarrow f(x_1,\dots,x_d)=0.$$ In Kurt Gödel's article ...
2
votes
1answer
22 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
1answer
41 views

condition for transitivity

In transitive relations, $aRb$ and $bRc$ implies $aRc$. But what if there are no $bRc$, can we say that the relation is transitive? For example, are relations $R\subseteq V\times V$, corresponding to ...
4
votes
1answer
145 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': ...
2
votes
2answers
33 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 ...
11
votes
2answers
300 views

Can we extend the definition of a continuous function to binary relations?

Let $X,Y$ be topological spaces. A function $\phi:X\to Y$ is continuous iff for any open subset $A\subseteq Y,$ the preimage $\phi^{-1}(A)$ is open in $X.$ We could similarly define a relation ...
1
vote
2answers
40 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

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
64 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 ...
2
votes
1answer
41 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: ...
1
vote
1answer
24 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 ...
9
votes
5answers
347 views

A problem about symmetric relations on finite sets.

We have these assumptions: $X$ is a finite set. $\sim$ is an irreflexive symmetric relation on $X$. for any subset $Y\subseteq X$ we define $$\mathcal{Cl}(Y)=\{A\subseteq Y\mid(\forall a,b\in ...
0
votes
1answer
45 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| ...
0
votes
2answers
53 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
18 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
63 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
28 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 ...
3
votes
4answers
2k views

Equivalence relation $(a,b) R (c,d) \Leftrightarrow a + d = b + c$

Suppose $A$ is the set composed of all ordered pairs of positive integers. Let $R$ be the relation defined on $A$ where $(a,b) R (c,d)$ means that $a + d = b + c$. (a) Prove that $R$ is an ...
2
votes
1answer
48 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
33 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 ...
2
votes
1answer
95 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 ...
0
votes
1answer
37 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 ...
1
vote
1answer
80 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 ...
2
votes
1answer
100 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 ...
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. ...
0
votes
1answer
35 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 ...
2
votes
3answers
34 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
62 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
35 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
313 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
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
1answer
30 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 ...
1
vote
1answer
33 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?
1
vote
1answer
24 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), ...
0
votes
0answers
11 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
2answers
30 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
2answers
43 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.