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

Alegebra- Function or NOT a function

if you have a relation with the domains: 0,1,2,3,4 and a range of: 3,1,2,4,2 does this mean it is not a function because there are two outputs of the number 2? Or can it only not be function if there ...
2
votes
0answers
28 views

Properties of a specific antichain of a lattice formed by the cartesian product of finite ordered sets

Introduction Let $X$ be a poset of all $n$-tuples, $x = (x_1, x_2, ..., x_n)$, where $0 \leq x_i \leq m_i - 1$ for $i = 1, ..., n$ together with the relation $x \prec y$ defined so that for ...
0
votes
2answers
24 views

Discrete Math: Relations

Why is it necessary for a relation to be a subset of the Cartesian product of two sets. Why couldn't we say that a relation is a relationship between any two elements of one or more sets.
0
votes
1answer
16 views

Partial ordered sets and supremum.

Let $A,B$ subsets of a partial ordered set $(X,\succeq)$, such that $A\subseteq B$. Suppose that $sup(B)$ exists, Do $sup(A)$ exists? I could prove that all upper bound of $B$ is an upper bound of ...
3
votes
1answer
40 views

How can you prove the equivalance relation for the following model?

Given two Kripke-frames $M=(W,R)$ and $U=(E,S)$ where $W,E$ are 'possible worlds' and $R,S$ are equivalence relations on $W,E$ respectively. we define $M\otimes U = (W',R')$ as follows: $W'=\{\ ...
0
votes
1answer
10 views

Is this relation considered antisymmetric and transitive?

I'm having trouble understanding whether or not this relation would be considered antisymmetric and transitive. The a relation R on the set of real numbers by (x,y) ϵ R if and only if x-y=0. If I am ...
0
votes
0answers
11 views

Finding the Equivalence of this Relation (Maximum)

I have this inequality relation where $\frac{\log(1+X_k^2)}{A_k} \geq \max_{m \in \mathcal{K} \setminus k} \frac{\log(1+X_m^2)}{A_m}$ Since the maximum is irrespective of the $k$'s, I reduce it to ...
1
vote
1answer
35 views

how to define a function?

If we define a function by set theory it states that it is relation in the sets of inputs and outputs such that each input is exactly related to one out put . so if $A=\{9,25,36\} ;\, B=\{3,5,6\}$ ...
-3
votes
1answer
26 views

Distinct elements of relations

R is the relation on Z (integers) given by xRy ( X is related to Y ) if 3 divides (x-y), what are the distinct elements of R?
0
votes
1answer
23 views

Is this always true about symmetric relations?

Statement : If $R_1$ and $R_2$ are both symmetric, then $R_1 \cap R_2$ is symmetric. Is this always true? As far as I could understand this with an example, suppose I have a set $A = \{1,2,3\}$ And ...
0
votes
2answers
13 views

Equivalence classes of relation $\rho: (x,y)\in \rho \Leftrightarrow (\exists k \in \mathbb{Z})x-y=3k$

I don't understand how equivalence classes are $$C(1)=\{3k+1:k\in \mathbb{Z}\}$$ $$C(2)=\{3k+2:k\in \mathbb{Z}\}$$ $$C(3)=\{3k:k \in \mathbb{Z}\}$$ Could someone explain?
0
votes
0answers
22 views

Let $R$ be a relation on $A$ and let $S$ be the transitive closure of $R$. Prove that $\text{Dom}(S) = \text{Dom}(R)$.

This is from "How To Prove It". The full exercise also asks to prove that $\text{Ran}(S) = \text{Ran}(R)$ but I was set from the outset on proving that $\text{Dom}(S) = \text{Dom}(R)$ first. Since the ...
1
vote
1answer
40 views

The cardinality of the set all symmetric relations on the set of natural numbers is $\mathfrak{c} = | \mathbb{R} | = 2^{\aleph_0}$

Prove that a set of all symmetric relations on the set of natural numbers has cardinality $\mathfrak{c} = | \mathbb{R} | = 2^{\aleph_0}$. Here I think that the $(a,b)b$ - will be every number ...
2
votes
1answer
30 views

Finding a unique relation $T$

This is one question I have been solving from Velleman's How to prove book: Suppose $R$ and $S$ are relations on a set $A$, and $S$ is an equivalence relation. We will say that $R$ is compatible ...
0
votes
1answer
26 views

Cardinality of a Quotient Set

Let $X = \{1, 2, 3, 4, 5, 6, 7, 8, 9,10\}$ and $P=\{2,3,5,7\}$. In $P(X)$ define the equivalence $A\mathcal{R}B$ if $A\setminus P = B \setminus P$ . Then what is the cardinal of the quotient set? I ...
0
votes
1answer
20 views

An example of a lattice that's not totally ordered

The following is an excerpt from my textbook: A lattice need not be a totally ordered set. Consider the partially ordered set $(ω,D)$ where D is the relation on $ω$ defined by $x D y$ iff $x | ...
2
votes
3answers
29 views

$A$ is the power set of set $C$, and $S$ is the relation on $A$ defined by $x S y$ iff $x \subseteq y$.

The following is an exercise from my textbook: Let $C$ be a set and let $A=\mathcal{P}(C)$, the set of all subsets of $C$. Let $S$ be the relation on $A$ defined by $x S y$ iff $x \subseteq y$. ...
0
votes
1answer
38 views

Transitive relation that I don't understand

I have a relation $S$ on $A = \{1, 2, 3, 4, 5\}$, which isn't transitive, and I don't get why. $S = \{(1, 1),(1, 2),(1, 4),(2, 1),(2, 2),(2, 3),(3, 2),(3, 3),(3, 4),(4, 1),(4, 3),(4, 4)\}$ According ...
0
votes
2answers
25 views

$(A,\leq)$ is a partially ordered set. That each finite non-empty subset of $A$ has a $maxB$ implies $(A,\leq)$ is totally ordered.

My textbook contains the following exercise: Let $(A,\leq)$ be a partially ordered set. Prove that if each finite non-empty subset of $A$ has a greatest element, then $(A,\leq)$ is totally ...
0
votes
1answer
20 views

Relation and closure

I have difficulties understanding what is exactly the relations $\leftrightarrow$ (symmetric closure) (and friends: $\stackrel{+}{\leftrightarrow}$ (transtive symmetric closure), ...
3
votes
3answers
41 views

Java comparator documentation: confused about the terminology “total order.”

I was recently reading the documentation for the Comparator type in the Java programming language. This type is used to let the programmer define custom ordering ...
1
vote
2answers
62 views

What is a usual order relation?

I've just started learning about relations and now I'm at partial order relations and total order relations; essentially, I'm trying to convey that I'm very much a beginner to this relations stuff. ...
0
votes
2answers
45 views

Relations, Equivalence class

Define the relation $R$ on the set $\Bbb Z^+$ of all positive integers by: for all $a, b \in \Bbb Z^+$, $aRb$ if and only if the largest digit of a is equal to the largest digit of $b$. For example, ...
2
votes
0answers
34 views

Reflexive, Symmetric, Transitive

Let $X = \{0, 1, 2, ... , 10\}$, Define the relation $R$ on $X$ by: for all $a, b \in X, aRb$ if and only if $a + b = 10$ Is R reflexive? symmetric, transitive? Give reasons. Here are my answers, ...
0
votes
2answers
61 views

Confusion about reflexivity proof and properties of inequality with regards to a partial order proof

The confusions stem from this question: Let $R$ be a relation over a set $A$. For all $a∈A$ and $b∈A$, given that $a < b$ iff $a\leq b$ but $a\neq b$, and $a\leq b$ iff either $a < b$ or ...
1
vote
1answer
29 views

Enumeration of trichotomous relations

I stuck with Logic, Computation and Set Theory by T. Forster. In Ex. 9 p. 14 it is stated that on the given set the amount of antisymmetrical relations equals to the amount of trichotomous ones. ...
1
vote
2answers
29 views

Reflexive, Symmetric, and Transitive on a relationship defined as “m-n is odd” proof

Main question: Is my solution for this proof correct? Also, I have some questions about my solution and the definitions of Reflexive, Symmetric, and Transitive. Here is the question and here is my ...
0
votes
1answer
29 views

Functions, identity functions

Let $A = \{1, 2, 3, ... , n\}$ where $n$ is a positive integer. Let $F$ be the set of all functions from $A$ to $A$. Let $R$ be the relation on $F$ defined by: for all $g, f \in F, fRg$ if and only ...
3
votes
2answers
60 views

Proving $Y$ such that $Y \cap B = \emptyset$

I have been solving this problem from Velleman's How to prove book: Suppose $B \subseteq A$ and define a relation $R$ on $\mathcal{P}(A)$ as follows: ...
1
vote
1answer
43 views

Discrete Mathematics Relations and Functions

I'm stuck on this question, and I'm unsure if my though process for the question is correct or not, as my understanding of relations isn't the greatest. Let A = {1, 2, 3, ..., n} where n is a ...
1
vote
2answers
38 views

What relations compose the language of ZFC?

On Tent and Ziegler's textbook "Model Theory", it is stated that the language of Set Theory contains only the binary relation $\in$. How is that possible, as ZFC contains only sets and $\in$ is a ...
1
vote
1answer
31 views

set-theory (anti-symmetric)

in relation, anti-symmetric -> if xRy and yRx, then x=y. Today, my lecturer said that relation $<$, which represents $(\le \bigwedge\ne)$, satisfies anti-symmetric. He did not prove it and He ...
0
votes
1answer
18 views

Trivial Question : Union of Relation

$ A,B $ are sets. Let Relation $ R \subseteq A \times A. \; $ Relation $ S \subseteq B \times B $. Can we have $ R \cup S $ ? where the underlying sets are different and if so, what is the ...
2
votes
1answer
45 views

Number of edges in the Hasse diagram for the $\subseteq$ relation on the set $\mathcal{P}\{1,2,…,n\}$

I am stucked at this problem: Let $G$ be the graph defined as the the Hasse diagram for the $\subseteq$ relation on the set $\mathcal{P}\{1,2,...,n\}$. ($n>0$) Determine how many edges ...
0
votes
2answers
22 views

I have been asked to determine whether this binary relation is reflexive or irreflexive and symmetric

I have been asked to determine whether this binary relation is reflexive or irreflexive and symmetric or not On the set $\{1,2,3\}$, the relation $\{(1,1), (1,2), (2,2), (3,3) \}$ I haven't been ...
-1
votes
1answer
57 views

Transitive closure of a relation [closed]

Having trouble answering the question. Let $A=\{1,2,3,4,5\}$ and $\mathcal{R}$ the relation on $A$ with matrix representation: $$\begin{array}{c|ccccc} &1&2&3&4&5\\ \hline ...
0
votes
4answers
41 views

Confusion about proof of every asymmetric relation being an irreflexive relation

Let R be asymmetric. We need to show R is irreflexive. So by definition, we assume: (x,y)∈R⟹(y,x)∉R Definition of irreflexivity: (x,x)∉R Let's do an indirect proof, so we assume: (x,x)∈R ...
1
vote
1answer
24 views

Proving that a relation $R$ is transitive iff $R \circ R \subset R$.

Problem: Let $R$ be a relation over $X$, i.e. let $R = \left\{ (x,y) \in X \times X \mid x \in X \wedge y \in X \right\}$. Prove that $R$ is transitive if and only if $R \circ R \subset R$. Attempt ...
1
vote
3answers
58 views

Is the relation $x \geq 2y$ transitive?

I am trying to understand if the relation $x \geq 2y$ is transitive. I think the answer is no for the following reasons. Can someone please let me know if I am correct or incorrect. If incorrect, ...
3
votes
1answer
39 views

How to draw Hasse diagram

How would you draw a Hasse diagram of the divisibility relation? when A = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15} Any help would be appreciated, thank you.
0
votes
1answer
22 views

Can I make the following assumption about symmetric relations?

If $R$ is a symmetric relation then: $$(x,y) \not \in R \rightarrow (y,x) \not \in R$$
-1
votes
1answer
30 views

Find logical errors in the proof

I'm finding it really hard to find the logical errors in this proof. I'm still new at this and trying to learn it. Claim: for all $n$ is in set $\mathbb{N}$(Natural numbers), if $2n+1$ is a ...
-1
votes
2answers
28 views

Is it a transitive relation [closed]

Determine relation $R$ in the set $\mathbb N$ of natural numbers defined as $$ R=\{(x,\,y)\mid y=x+5\text{ and }x<4\} $$ Since the data is insufficient to prove it is transitive, will it be a ...
0
votes
1answer
27 views

Properties of transitive modal frames

I am working through Fitting and Mendelsohn's First Order Modal Logic and have come across the following exercise: Prove that a frame $\langle \mathcal{G}, \mathcal{R} \rangle$ is transitive if ...
-1
votes
2answers
25 views

Find if the given relation equivalence?

Let $A=\{x \in \mathbb Z:1 \le x \le 7\}$ and $R= \{(a,b):\vert a-b\vert \text{ is multiple of 4}\}$ a relation defined on set $A$. Is $R$ an equivalence relation? What are all ordered pairs of $R$?
2
votes
2answers
41 views

The relation x=1

This one stumped me: Determine if the relations R on $\mathbb{R} $ are reflexive, symmetric, transitive, antisymmetric: $ (x,y) \in R$ iff $x=1$. It is reflexive since 1=1. It is symmetric since it ...
0
votes
1answer
37 views

Can someone present an example of linear ordering less trivial than $A = [1,2,3,4,5,6…]$

A linear ordering (loset) is a poset that also satisfies the trichotomy law. For any $x,y \in A$, we have $x \leq y$ or $y \leq x$ A common example is presented as $A = [1,2,3,4,5,6...]$ Can ...
1
vote
1answer
40 views

How can an asymmetric relation be antisymmetric?

Let R be asymmetric. So we have: Assumption: (x,y)∈R⟹(y,x)∉R We need to show R is antisymmetric, i.e. (x,y)∈R∧(y,x)∈R⟹x=y Since 2 is a conditional, we can assume Assumption:(x,y)∈R∧(y,x)∈R ...
2
votes
1answer
27 views

Can someone present a visualization of the partitioning of a $L^p$ space into equivalent classes?

I am a bit confused by what it means for a $L^p$ space to be partitioned into equivalent classes instead of functions. I understand that give two or more functions $f$, $g$, $h,\ldots$ of which are ...
0
votes
3answers
46 views

Why ordered sequences can be reduced to sets?

I am trying to understand why ordered sequences can be reduced to basic sets. I understand most of the following proof: Sequences can be defined as functions Functions are a special case of ...