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
23 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
41 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
32 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
23 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 ...
1
vote
1answer
19 views

Irreflexivity of relations on sets [closed]

How can I know if the relations: $xy\geq1$ and $x=y+1$ or $x=y-1$ Are irreflexive on $\mathbb Z$? Thank you!
-2
votes
2answers
24 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
37 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
25 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
20 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
34 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... ...
0
votes
0answers
30 views

Help with logical equivalence proof regarding a lemma for equivalence relations.

So the question is this: Suppose A is a set. Let ~ be an equivalence relation on A and let a,b be elements of A. Then Ta = Tb if and only if a ~ b. I need to prove this statement to be true. I know ...
1
vote
0answers
38 views

Finding Equivalence Classes for Infinite Sets

Let R be the relation on the set of rational numbers Q defined as follows: for all q, r ∈ Q, qRr iff q − r ∈ Z, where Z is the set of integers. R is an equivalence relation on Q. What is the ...
2
votes
1answer
39 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
24 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) ...
-2
votes
0answers
37 views

Why is a linear order called linear?

Why does the definition of linearly ordered set imply that we can make a diagram of this set as a line in which a < b if and only if a is to the left of b?
0
votes
1answer
31 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
11 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
31 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
31 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
27 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
12 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
0answers
23 views

Define another Equivalence Relation from Geometric Figure?

Define relation $W$ on $R^2$ by $(x_1,y_1)W(x_2,y_2)$ whenever $x_1−y_1=x_2−y_2$. I have the equivalence classes to be given by $f^{-1}(r)=\{(x,y)\mid x−y=r\}$, where $r∈R$. So how would you define ...
0
votes
1answer
22 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
34 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
30 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
28 views

Relations on set based off Cardinality [closed]

Let A be a set with cardinality 6. How many relations on A are there? How many are reflexive? symmetric? Not sure where to go with only this information. Thanks!
0
votes
1answer
18 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
31 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 ...
0
votes
0answers
36 views

Poker Hand Equivalent Relation

Let $P$ be the set of all possible poker hands. Define a relation $J$ of $P$ by $a$ is $J$-related to $b$ iff $a$ and $b$ have no cards in common. Is $J$ reflexive? Symmetric? Transitive? Having a ...
0
votes
1answer
24 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
45 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
35 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
22 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
34 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
47 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
38 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
32 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
50 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
24 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
55 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 ...
1
vote
3answers
39 views

Proving various relations are partial orders

I am given these relations, in which I have to prove or disprove each and every one. a. The relation $\trianglelefteq$ defined on ℕ by a $\trianglelefteq$ b if a ≤ b² b. The relation $\preceq$ defined ...
0
votes
1answer
24 views

Prove the relation {(1, 1),(2, 2),(3, 3),(4, 4),(3, 2),(2, 1),(3, 1),(4, 1)} on the set S = {1, 2, 3, 4} is a partial ordering.

I know that to prove something is a partial order, the relation ≤ has to be reflexive, transitive, and anti-symmetric. So, given this relation {(1, 1),(2, 2),(3, 3),(4, 4),(3, 2),(2, 1),(3, 1),(4, 1)} ...
1
vote
1answer
29 views

Question About Set Relations?

Prove that $\text{Domain}(S\circ R) \subset \text{Domain}(R)$ where $ R $ is a relation from $ A $ to $ B $ and $ S $ is a relation from $ B$ to $ C $. My solution: I suppose that there is an ...
0
votes
2answers
33 views

Finding the equivalence class of this relation

I am having this relation: $$ A=\mathcal P(\mathbb {N} \diagdown 0) , $$ A~B :<=> min A = min B I haved already ...
1
vote
0answers
17 views

Finding Relations algebraically

I have selfstudy on this subject and want to know if I am grasping the concept well. Here is the question: Let $A=Z^+$, all integers that are positive; Let $R$= relation defined by $aRb$ iff there ...
0
votes
0answers
6 views

Prove that $cl_{eq}(R) = (cl_{sym}(R))^*$

Prove that $cl_{eq}(R) = (cl_{sym}(R))^*$ $cl_{eq}(R) = \bigcap\{S | $ S is an equivalence relation and $R \subseteq S\}$ is the equivalence closure of R. $R^* = \bigcap\{S | $ S is reflexive, ...
0
votes
2answers
36 views

Calculate an arbitrary value based on a two points

I am working in Fruity Loops studio, and funnily enough, I need to solve something with math. I want a way to calculate the track tempo I get based on an arbitrary value. I know the following values ...
0
votes
1answer
23 views

Ordered Pair Proof

Below are two relations on $R.$ For each one, determine (with proof) whether or not it is an equivalence relation. If it is an equivalence relation, describe the partition it induces (i.e., describe ...
1
vote
2answers
32 views

Why is {(0,1), (1,2)} an antisymmetric relation?

This is my relation: $R= \{(0,1), (1,2)\}$ I know it is not transitive, because: $$ 0R1 \wedge 1R2 \Rightarrow 0R2,$$ but this is false Now I want to check, if it is antisymmetric. How can I write ...
0
votes
1answer
45 views

Understanding relations: Are these examples correct?

The task is to find examples for the following relations on the set of (and prove its correctness) : 1: antisymmetric and transitiv 2: antisymmetric and not transitiv (intransitiv) 3: not ...