0
votes
1answer
93 views

Is an anti-symmetric and asymmetric relation the same? Are irreflexive and anti reflexive the same?

I don't understand the difference between an anti symmetric and asymmetric relation. From my understanding, it is asymmetric if there is not any element where: if (x,y) (y,x). But what if you have ...
1
vote
1answer
48 views

Is there way to classify the quantifier rank $m$ first order sentence in first order logic

In its simplest situation, for example, if the signature contains only a binary relation $\sigma$, so the signature $\tau = \{ \sigma \}$, what are the inequivalent classes of all first order ...
0
votes
2answers
33 views

Use of “for all” in definition of reflexive and symmetric relations.

My book says that a relation R on A is reflexive, if $\ (a,a) \in R, \ for\ every \ a \in A$ symmetric, if $\ (a_1,a_2) \in R \implies (a_2,a_1) \in R,\ for\ all\ a_1,a_2 \in A$ Although I ...
4
votes
2answers
95 views

Is $a \le b$ a true statement if $a < b$? [duplicate]

My question is: Is $a \le b$ true if $a < b$? For instance: Is $3 \le 4$ a true statement? I think yes, because $a \le b$ is defined as $a < b\vee a = b$ and this should be true, even if $a = ...
0
votes
3answers
55 views

Check the following Relation $R=\{(x,y) |\exists k\in \mathbb{Z} \cdot x*y=3k \}$

I would like to check the following relation: $$R=\{(x,y) |\exists k\in \mathbb{Z} \cdot x*y=3k \},R\subseteq \mathbb{Z} \times \mathbb{Z}$$ Reflexivity Symmetric Transitivity Asymmetric Can I ...
3
votes
1answer
83 views

$\mathrm{Pol}_m(\mathbb{A})$ viewed as a relation pp-definable from $\mathbb{A}$

First let me recall some (abbreviated, and possibly simplified to suit my situation) definitions: Let $A$ be a finite set and $\mathbb{A}$ some set of relations on $A$. Let $m, n$ be positive ...
1
vote
3answers
49 views

Why $(a,b)\mid a+b\le3$ is not reflexive and is symmetric?

Why $(a,b)\mid a+b\le3$ is not reflexive and is symmetric? I read because a€ Z so by counter example $(5,5)$, $5+5$ is not less than or equal to $3$ So it's not reflexive But why it's symmetric ? I ...
1
vote
1answer
200 views

Why the divides relation on the set of positive integers antisymmetric

I'd like to know why the divides relation on the set of positive integers antisymmetric. The book says $a|b$ and $b|a$ then $a=b$. But I think if a|b and b not divides a for example $1|2$ but not ...
2
votes
1answer
53 views

Relations and equivalence relation

Let $R=\{ (x,y) \vert x=1 \,\, or\,\, y=1 \}$ When I see something written like this to represent "or", I immediately think XOR. But is that necessarily true? This would greatly change the ...
5
votes
1answer
63 views

Why is this binary-relation antisymmetric?

Definition of antisymmetric binary-relation is $$\forall a,b\in\mathrm{A},\left[ \left(aRb\wedge bRa\right)\rightarrow\left(a=b\right)\right].$$ Let $\mathrm{A}=\left\{a\mid ...
2
votes
1answer
30 views

Generated equivalence relations in logics

Let $L$ be some logic (FO or stronger which is not important for this purpose). Given a $\tau$-structure $A$ and a formula $\varphi(x_1, \dots x_n) \in L[\tau]$ with free variables $x_1, \dots, x_n$. ...
0
votes
2answers
65 views

Model and countermodel to $\exists x.\forall y. x<y$ (with $<$ an arbitrary relation)

Can someone please help me with this question. I have been struggling with it for ages and can't quite seem to work it out: Let $<$ be a binary relation symbol that we will write infix. Let ...
0
votes
2answers
38 views

Is my transitivity proof correct for the relation over $\mathbb{Z} \times \mathbb{Z}$ where $(a,b)R(c,d) \iff (a \le c \lor b \le d)$?

I'm having a hard time developing abstract thinking to solve problems regarding a relation's properties. I've spend quite an absurd amount of time on this one, but I think I finally grasped a bit of ...
1
vote
1answer
39 views

Proving a relation's inverse's properties by knowing the original's.

I'm getting fairly confused with two exercises related to proving a relation's inverse's properties by knowing the original's. I couldn't do either. Any hint is appreciated. If $R$ is a ...
2
votes
2answers
61 views

How can I further simplify $(a \le b) \lor (b \le a)$ to prove that it is a tautology?

Over $\mathbb{Z}$, $aRb \iff a \le b \lor a = 3b$. Determine if it is total. I think it is: Have arbitrary elements $a,b \in \mathbb{Z}$. We have to prove that $aRb \lor bRa$, which can be ...
2
votes
2answers
63 views

Proving that $aRb \iff a = b \lor a = b^2$ is antisymmetric.

Over $\mathbb{N}$, $aRb \iff a = b \lor a = b^2$. I'm having problems determining if this relation is antisymmetric. I think it is. I did the following: Direct proof attempt (got stucked) We ...
1
vote
1answer
47 views

discrete mathematics relations question 2

I am a little confused by this relation R3 is a subset of Z×Z defined by (x,y) in the set R3 if and only if x>2y is it reflexive? Symmetric? antisymmetric? or transitive? i say its NOT reflexive ...
1
vote
1answer
77 views

Discrete mathematics Relations Question

if r2 is in the set of N*N ( natural numbers) with (X,y) in the subset of r2, if and only if x+y=0 is it reflexive? is it symmetric? is it anti symmetric? is it Transitive? i said it is reflective ...
1
vote
1answer
196 views

Proving the symmetry of an equivalence relation

When proving the symmetry of an equivalence relation, must each equivalence class be closed under symmetry. for example: the relation both x and y > 10 or both x and y < 10 across all ...
0
votes
1answer
114 views

Partial order relation

Define the relation $\leq$ on a boolean algebra $B$ by for all $x,y\in B$, $x\leq y \iff x\lor y=y$, show that $\leq$ is a partial order relation. First of all what exactly does boolean ...
3
votes
1answer
68 views

Prove that $D_r \circ D_s = \{ (x,y) \in \mathbb{R}^2 \ | \ |x-y|<r+s \}$, where $D_a = \{ (x,y) \in \mathbb{R}^2\ | \ |x-y| < a \}$

Suppose $r$ and $s$ are two positive real numbers. Let $D_r = \{ (x,y) \in \mathbb{R}^2\ | \ |x-y| < r \}$ and $D_s = \{ (x,y) \in \mathbb{R}^2 \ | \ |x-y| < s \}$. Prove that $D_r \circ D_s = ...
1
vote
2answers
226 views

Two questions about monotonicity of entailment.

I wonder about two things. First, how do we prove that entailment in some logic is monotonic? The second one - What is the relationship between monotonicity of logic and deduction theorem? It seems ...
2
votes
2answers
96 views

Ted Sider's Definition of a Total Relation over a Set D

I'm working through Ted Sider's book "Logic for Philosophy," and I'm noticing some discrepancies between the definition of a "Total Relation" that he uses and the definition used in other places, ...
0
votes
1answer
312 views

Proving that a pair of equivalence classes must be identical or disjoint

Give an equivalence $R$ relation over a set $A$: $$C_x=\{y\in{A}:xRy\}$$ I'm trying to prove that if $x,y\in{A}$, Either $C_x=C_y$ or $C_x\cap{C_y}=\{\}$. In other words, $C_x$ and $C_y$ must be ...
0
votes
1answer
75 views

Question concerning satisfiability in a certain Kripke model

My question concerns the exercise on p.77 of Boolos, Logic of Provability: True or false: if $A$ is satisfiable in some finite transitive and irreflexive [FIT] model and contains at most one ...
2
votes
4answers
349 views

Transitivity of union of two transitive relations

I have a question concerning proving properties of Relations. The question is this: How would I go about proving that, if R and S (R and S both being different Relations) are transitive, then R union ...
1
vote
3answers
128 views

Proof of $\;\text{Asymmetric}(\sqsubset)\rightarrow \text{Antireflexive}(\sqsubset)$

The relation $\;\sqsubset\;\subseteq S\times S$ is asymmetric if $$\forall a,b\in S:(a,b)\in\sqsubset\rightarrow (b,a)\notin\sqsubset$$ and it is antireflexive if $$\forall a\in ...
0
votes
1answer
66 views

Need Assistance Setting Up Equation(s)

I am in a discrete mathematics class for information technology. I need some help setting up the equation(s) for a particular problem. It has been difficult to get individual attention with my rather ...
3
votes
2answers
245 views

Would this relation be an equivalence relation?

I am a bit stuck on this one question from my homework and for some reason it isn't making any sense to me. I would really appreciate it if somebody could explain it to me how I can go about to ...
2
votes
1answer
621 views

Modus Ponens: implication versus entailment

Would it be inconsistent to write Modus Ponens using only implication, not entailment? $(p \wedge (p \to q)) \to q$ The way I understand is that implication ($ \to$) is an operator that yields a new ...
0
votes
2answers
87 views

xRy if and only if x is a descendant of y, on the set of all humans. Explain the relations

xRy if and only if x is a descendant of y, on the set of all humans. I have the solution to this. I just don't understand how transitivity follows.
4
votes
1answer
213 views

Motivation behind Theory of Relations?

I looked through the nice paper by Tarski On the Calculus of Relations. In the beginning he touched a motivation behind Theory of Relations but this part was not clear to me (page 1, very beginning): ...
1
vote
2answers
321 views

Proving a relation between 2 sets as antisymmetric

Let $U = \{1,...,n\}$ And let $A$ and $B$ be partitions of the set $U$ such that: $\bigcup A = \bigcup B = U$ and $|A|=s, |B|=t$ Let's define a relation between the sets $A$ and $B$ as follows: $B ...
0
votes
1answer
101 views

Monotonic Relation

Consider the relations $r_1, r_2, \ldots , r_n$ and consider a relational expression language as follows: $r_i$ is a relational expression, $1 \le i \le n$ $e_1 \circ e_2$ is a relational ...
1
vote
2answers
247 views

Unnecessary property in definition of equivalence relation [duplicate]

Possible Duplicates: Symmetric, Transitive and reflexive Why isn't reflexivity redundant in the definition of equivalence relation? Dependence of Axioms of Equivalence Relation? Let ...
4
votes
5answers
533 views

Interesting properties of ternary relations?

Many people are familiar with some properties of binary relations, such as reflexivity, symmetry and transitivity. What are the commonly studied properties of ternary (3-ary) relations? If you ...