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

0
votes
1answer
58 views

Is relation a partial order?

can you give me few hints how to solve this problem ? Relation R on the set P(A) A = {a,b,c,d} is a set of four elements. We also have relation R on the set P(A), which is defined R={(A,B)│A ⊆ B. ...
0
votes
1answer
24 views

Transitive closure relation

I have a following relation on the set {A,B,C,D} R = {(a,a);(a,c);(b,d);(c,d);(d,c)} What is the smallest number of tuples that has to be added in order for the relation to become transitive? It is ...
1
vote
2answers
298 views

Proofs with Relations and functions

I need help with setting up a homework problem. I am having trouble finding where to start. Problem: Suppose A is a set. Show that $i_A$ is the only relation on A that is both an equivalence relation ...
2
votes
1answer
603 views

how to find relation R^2

Suppose S is a set of airports, and R is the following relation on S: aRb if and only if there is a direct flight from a to b. Explain your answers to the following questions and use common sense. a. ...
1
vote
0answers
340 views

Real life example of relations with various combination of properties

Attempted a set of questions as below: ...
1
vote
2answers
208 views

to find total number of subsets

I was working out some problem where I needed permutation and combination. I took the cartesian product of $n$ sets where number of elements in each set is even. Further the elements of this cartesian ...
0
votes
1answer
134 views

Prove: The relation $R$ on $\mathbb{N}$ is reflexive, symmetric and transitive

Prove: The relation $R$ on $\mathbb{N}$ given by $mRn$ iff there are natural numbers $p$, $q$ with $m^p$ = $n^q$ is reflexive, symmetric and transitive. Proving $R$ is reflexive: Proof. Suppose $m$ ...
0
votes
1answer
260 views

Proving properties of binary relations

Attempting to find answers to solve these questions. I've been looking all over the web for references since my textbooks aren't being helpful. Now, I'm still at the starting point. ...
14
votes
3answers
1k views

Sole minimal element: Why not also the minimum?

A minimal element (any number thereof) of a partially ordered set $S$ is an element that is not greater than any other element in $S$. The minimum (at most one) of a partially ordered set $S$ is an ...
1
vote
1answer
2k views

Example of an antisymmetric, transitive, but not reflexive relation

The question I'm tackling right now is this: Give an example of a relation R on a set S that is not reflexive, transitive and not symmetric. My answer: Let S = {1,2,3} and let R = {(1,1), (2,2), ...
1
vote
2answers
183 views

Tell whether the relation is reflexive, symmetric, asymmetric, antisymmetric or transitive.

Tell whether the relation is reflexive, symmetric, asymmetric, antisymmetric or transitive.Identify equivalence relations or partial orders. $R$ is the relation on people such that $a R b$ if $a$ ...
1
vote
3answers
78 views

Prove a relation for a set

If $ R,S $ are relations on the set $ A $, where $ S $ is reflexive $ S \subseteq R $ Prove that: $ R $ is reflexive How do I begin? How could a relation be a subset of another relation ? thanks
3
votes
2answers
96 views

In $\mathsf{Rel}$, are any two objects isomoprhic?

My knowledge of categories is rather basic, and I was just trying to find out what are isomoprhisms in $\mathsf{Rel}$ where objects are sets and morphisms are relations. As far as I got, an ...
0
votes
1answer
23 views

Relationship Between 4 Variables

Let (a-1) d = b (c-1) such that $ a,b,c,d \in \mathbb{R} $. How do you find the relationships between a,b,c,d? Do you look at what makes both sides equivalent? I considered 3 cases where: a = 1, ...
5
votes
1answer
94 views

Composition of relations. Both relations are functional and mutually inverse mappings. Zorich - MAI p22

$\def\R{\mathcal{R}}$ The composition $\mathcal{R}_2 \circ \mathcal{R}_1$ of the relations $\mathcal{R}_1$ and $\mathcal{R}_2$ is defined as follows: $$\mathcal{R}_2 \circ \mathcal{R}_1 := ...
1
vote
0answers
78 views

Inverse Relation of Irreflexive Property.

We are taking the inverse of relation to check that inverse of R is transitive, reflexive , symmetric and anti-symmetric to as it is on R (not inverse).. My question is that why we are not taking the ...
0
votes
1answer
65 views

Properties of Relations and their negations.

There are three properties of relation, 1. Reflexive 2. Symmetric 3. Transitive and if all properties are satisfy by a relation then its known as ...
0
votes
2answers
46 views

Why does $A = X-B$ is equivalent to $A \cup B = X$ and $A \cap B = \emptyset$

I was looking at a solution to the problem and it says that $A = X-B$ is equivalent to $A \cup B = X$ and $A \cap B = \emptyset$. I am wondering why this is true? Any help would be highly ...
1
vote
3answers
45 views

Determining the list elements of $U = \{(A,B)\in \mathcal P(X) ×\mathcal P(X)\mid A=(X−B)\}$

Define $X = \{1,2,3,\ldots,n\}$, for some positive integer $n$. The set $U$, is defined as: $U =\{(A,B)\in \mathcal P(X) ×\mathcal P (X)\mid A=(X−B)\}$. If $n=3$, show the elements of $U$. I ...
0
votes
1answer
44 views

Proving equivalence relation and classes

I was wondering how I could prove aRb if and only if 5 | (a + 4b) , on the set of all integers I'm used to proving for sets of numbers so I have no idea how to start out for this... Equivalence ...
-2
votes
2answers
40 views

Proving a Relation that is a Function by Division Algorithm [duplicate]

Let A=B=$\mathbb{N}$ R is: (a,b)$\in$R iff for some q$\in$Integers a=5q+b WHERE 0$\leq$b<5 Given a relation, show that it's a function. To Show: 1) $\forall$a$\in$A$\exists$b$\in$B((a,b)$\in$R) ...
0
votes
1answer
41 views

Is the relation on integers, defined by $(a,b)\in R\iff a=5q+b$, a function? [closed]

Let $A=B=\mathbb N$. Relation $R$ is: $(a,b)\in R$ iff for some $q \in \mathbb Z$ we have $a=5q+b$ Given a relation, show that it's a function. To Show: $\forall a \in A \ \exists b \in B$ such ...
0
votes
1answer
47 views

Language and Finite Models

Let us consider the language consisting of one symbol $R$ for a binary relation. Let $\sigma$ denote the following sentence: $\forall x \exists y \exists z \ x\neq y \wedge y \neq z \wedge x \neq z ...
0
votes
1answer
93 views

number of antisymmetric and not irreflexive relations

What is the number of relations on a n element set that are antisymmetric and not irreflexive? I have tried doing this as fallows- no of antisymmetric relations having atleast one self pair[like ...
0
votes
1answer
45 views

Number of relations on a set

What is the number of relations on a $n$ element set that are antisymmetric and not symmetric? I have soved this question using the fact that 'antisymmetric and not symmetric' means asymmetric... ...
1
vote
0answers
89 views

Finding Equivalence Classes for Infinite Sets

Let $R$ be the relation on the set of rational numbers $\Bbb Q$ defined as follows: for all $q, r \in \Bbb Q$, $qRr$ iff $q − r \in \Bbb Z$. Then $R$ is an equivalence relation on $\Bbb Q$. What is ...
2
votes
1answer
49 views

Well founded relations.

I'm reading a proof in Jech Set theory and I cannot understand a line. Why is it the case that the replacement axiom guarantees the existence of $\theta$ such that $P_\theta = P_{\theta + 1}$? Last ...
0
votes
2answers
78 views

Transitivity relation in the set of Integers

Prove or disprove that R is transitive, where $R=\{ (a,a^2)| a \in \Bbb Z \}$ is a relation on $\Bbb Z$ By definition: $R$ is transitive $iff$ $$ (a,b)\in R \wedge (b,c) \in R\implies (a,c) ...
0
votes
1answer
45 views

How to prove that a set is not totally ordered?

I know that a set to be totally ordered and for example $A,B \in P(X)$ must either be $A \le B$ or $B \le A$. And also $\le$ is equivalent to $\subset$ for sets. But I am not sure how I would prove ...
0
votes
1answer
13 views

Congruence question, does -1 matter?

I am proving symmetry in a relation. Assume: I have $a\,R\,b$ which is $x+y\equiv z+w\pmod 2$. I want to show $b\,R\,a$ which would be $z +w\equiv x+y\pmod 2$. ("$x\mid y$" is the divides symbol.) ...
2
votes
1answer
148 views

Finding number of relations on a set with 3 elements

How do I find find out how many non reflexive relations X on the set P = {1, 2, 3}? I know $2^{n^2 - n}$ returns how many reflexive relations there on a set. Do I subtract that from something to get ...
1
vote
1answer
38 views

Is this undergrad equivalence class question solvable?

Let x,y be real numbers. Define the relation S as x S y if |x - y| $\epsilon$ Q where Q is the set of rational numbers. Find all equivalence classes of S. I work in the undergrad tutor center ...
0
votes
1answer
33 views

How to proove that smallest upper bound exists und it is cleary determined?

Let X be a set. Then a relation '$\le$' on $\mathcal P(X)$ is defined by: $A \le B :\Leftrightarrow A \subset B$ . Let $\mathcal A \subset \mathcal P(X)$. One set $B \in \mathcal P(X)$ for which ...
0
votes
1answer
13 views

Give a relation $X\subseteq A\times A$, so that $R\subseteq X$ and $X$ is symmetric

$R=\{(2,5),(3,4)\}$ $A=\{2,3,4,5\}$ my answer: $X=\{(2,5)(5,2)\}$ $X$ is a proper subset because it contains not all elements of $A\times A$ and not all elements of $R$. And $X$ is symmetric ...
0
votes
1answer
81 views

How many relations on a set with 6 elements?

I know there is a lot of information on this internet for this, I've been going through it the past 30 minutes. I'm getting confused to if the answer is actually 203 relations, because when I try to ...
2
votes
3answers
61 views

Why is a Symmetric Relation also Transitive?

A relation R on set A is as follows: R = {(1,1), (2,2), (3,3)} R is symmetric! But WHY is R Transitive?
1
vote
1answer
38 views

Prove that it is transitive

Below is what I have so far. I'm pretty sure that it is transitive, but I'm not sure how to prove that it is. Prove that A is or isn't transitive.
0
votes
1answer
23 views

Show that $W$ equivalence relation on $\mathbb{R}^2$

Define relation $W$ on $\mathbb{R}^2$ by $(x_1,y_1)W(x_2,y_2)$ whenever $x_1-y_1=x_2-y_2$. Show that $W$ is an equivalence relation on $\mathbb{R}^2$. I believe it is reflexive, not sure about ...
0
votes
2answers
34 views

A pair of questions about isomorphism between two posets.

Theorem: Let $P = (X, \le)$ be a finite total order containing n elements. Let $Q = (\{1, 2, \ldots , n\}, \le')$. Then $P \cong Q$. I have a few questions about the proof of this theorem. In my ...
1
vote
1answer
94 views

Consider the relation R given by divisibility on positive integers that is xRy <-> x|y

Consider the relation R given by divisibility on positive integers that is xRy <-> x|y Is this relation reflexive? symmetric? anti-symmetric? transitive?? I understand it is reflexive and ...
1
vote
4answers
60 views

Celsius to Fahrenheit Conversion

Consider the following question: "The maximum temperature of a day is 42 degrees celsius. The minimum temperature is 28 degrees celsius. What is the difference of these temperatures on the Fahrenheit ...
0
votes
2answers
38 views

$A\neq \varnothing $, $B\neq \varnothing$, $A\neq B.$ Prove $A\times B \neq B\times A$ [closed]

$$A\neq \varnothing ,B\neq \varnothing,A\neq B. \\\text{Prove }A\times B \neq B\times A$$ I'm pretty sure this has to do with inverse for relations. But I'm not sure how to begin proofing ...
0
votes
1answer
40 views

Determining the transversal for an equivalance relation

If you have an equivalence relation $c$ on $\Bbb{Z}$ defined by $$\{x,y\in\Bbb{Z}:p\in\Bbb{Z},x=5p+y\}$$ How would you proceed to determine if the following subset of $\Bbb{Z}$ $$\{-8,1,10,13,19\}$$ ...
1
vote
1answer
61 views

How many equivalence classes does this relation have?

I have this relation: $$A = \mathbb {R} \\ \quad\;\; x\sim y \iff x-y \in \mathbb {Z} $$ I have already proved if it is an equivalence relation. Now I am just searching for the equivalence classes ...
1
vote
4answers
76 views

Transitivity in set relations

According to my book: R = {(1,2), (2,3), (1,3), (2,1)} is not transitive because (1,1) and (2,2) are missing. I don't see why (1,1) & (2,2) would be relevant here since aRb and bRc => aRc has ...
0
votes
1answer
59 views

Find the equivalence class of this relation!

I am having the following relation with the set A and B: $$ (x_1, y_1) \sim_{A\times B} (x_2, y_2) \iff\; x_1 \sim_A x_2\ \;\land\; \; y_1 \sim_B \; y_2 $$ I haved already proved, that it is a ...
0
votes
2answers
35 views

Relation of any set A

I've been learning of relations and I'm having trouble on how to proceed with this problem: $$ \begin{align} \text{On any set } A: a\sim b \enspace\enspace\forall \enspace a,b \in A \end{align} $$ ...
0
votes
2answers
65 views

Check if a relation on a set is a function [duplicate]

What do I need to look for in order to tell if a relation on a set is a function? Can somebody provide some advice? For example, the relation is defined by $H$ on $A \times \mathcal P(A)$ for $a ∈ ...
1
vote
1answer
38 views

Proving a simple partially ordered set

I am losing my mind over this: (a) The relation $A=\{(1,1),(2,2),(3,3),(4,4),(3,2),(2,1),(3,1),(4,1)\}$ on the set $S=\{1,2,3,4\}.$ I'm having trouble figuring out if it's reflexive, symmetric, ...
3
votes
1answer
304 views

Define a relation | on the set of natural numbers by aRb if a|b

So for the division relation (or divides relation, depending on how one says it), I have to show the following: a. Prove that | is a partial order on the set of Natural Numbers. b. Prove that | has ...