How to Prove It, 2nd Ed. Sec. 4.4 #1b

  • Thread starter IntroAnalysis
  • Start date
However, if x=-2 and z=2, then you have a contradiction, so the relation is not transitive. In summary, the relation R is a partial order on the set A = ℝ, as it is reflexive and transitive. However, it is not a total order as it is not antisymmetric.
  • #1
IntroAnalysis
64
0

Homework Statement


A = ℝ, R = {(x, y) [itex]\in[/itex] ℝ X ℝ l lxl ≤ lyl }

Say whether R is a partial order on A. If so, is it total order?


Homework Equations


Suppose R is a relation on a set A. Then R is called a partial order on A if it is reflexive, transitive and antisymmetric.

1. R is said to be reflexive on A if [itex]\forall[/itex]x [itex]\in[/itex]A((x,x)[itex]\in[/itex]R.

2. R is said to be transitive on A if [itex]\forall[/itex]x[itex]\in[/itex]A[itex]\forall[/itex]y[itex]\in[/itex]A[itex]\forall[/itex]z[itex]\in[/itex]A((xRy[itex]\wedge[/itex]yRz)[itex]\rightarrow[/itex]xRz).

3. R is said to be antisymmetric if [itex]\forall[/itex]x[itex]\in[/itex]A((xRy[itex]\wedge[/itex]
yRx)→x=y).

The Attempt at a Solution


1. For all x element of A, lxl ≤ lxl. Reflexive, Yes.
2. [itex]\forall[/itex]x[itex]\in[/itex]A[itex]\forall[/itex]y[itex]\in[/itex]A[itex]\forall[/itex]z[itex]\in[/itex]A((xRy[itex]\wedge[/itex]yRz)[itex]\rightarrow[/itex]xRz). Transitive, Yes.
3. If x = -2 and y = 2, then xRy [itex]\wedge[/itex]yRx, but -2 ≠ 2. So it is not antisymmetric, and thus not a partial order.

Is this correct?
 
Physics news on Phys.org
  • #2
Looks good, I assume you worked out the transitivity property yourself, but if not you should show your work. xRy ^ yRz => |x|<= |y| and |y|<= |z|, and since <= is transitive (do you need to or have you shown this before?) |x|<=|z|, so xRz.
 

1. What is the definition of a universal quantifier in mathematical logic?

A universal quantifier in mathematical logic is a symbol (∀) that represents the phrase "for all." It is used to express that a statement is true for all elements in a given set.

2. How is a universal quantifier used in mathematical proofs?

In mathematical proofs, a universal quantifier is used to assert that a statement is true for all elements in a set. It allows the proof to be generalized and apply to all possible cases within the set.

3. What is the difference between a universal quantifier and an existential quantifier?

A universal quantifier (∀) asserts that a statement is true for all elements in a set, while an existential quantifier (∃) asserts that there exists at least one element in a set for which the statement is true. In other words, the universal quantifier is a statement about all elements, while an existential quantifier is a statement about at least one element.

4. How do you negate a statement with a universal quantifier?

To negate a statement with a universal quantifier, you can use the logical rule: ¬(∀x)(P(x)) = (∃x)(¬P(x)). This means that "not all" is equivalent to "there exists at least one that is not."

5. Can a statement with a universal quantifier be proven using a counterexample?

Yes, a statement with a universal quantifier can be proven using a counterexample. If a statement is false for even one element in the set, then it cannot be true for all elements, and the universal quantifier is negated. This is known as a proof by counterexample.

Similar threads

  • Calculus and Beyond Homework Help
Replies
3
Views
4K
  • Calculus and Beyond Homework Help
Replies
5
Views
3K
  • Calculus and Beyond Homework Help
Replies
1
Views
2K
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
5
Views
11K
  • Calculus and Beyond Homework Help
Replies
3
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
7
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
6K
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
Back
Top