Question

Let $\sigma =\mathrm{\exists }x\mathrm{\forall }y(x\le y\vee y\le x)$. Find posets $\mathfrak{A}$ and $\mathfrak{B}$ such that $\mathfrak{A}\models \sigma$ and $\mathfrak{B}\models \mathrm{\neg }\sigma$.

Short answer

$\mathfrak{A}$ could be a single element set; $\mathfrak{B}$ could have two incomparable elements.

Step-by-step solution

Understanding the Expression

The expression $\sigma =\mathrm{\exists }x\mathrm{\forall }y(x\le y\vee y\le x)$ needs to be interpreted in terms of order theory. This asserts that there exists an element $x$ such that for all elements $y$ in the poset, either $x$ is comparable to $y$ because $x\le y$ or $y\le x$. Such an element is typically called a comparable element to all others.

Example of Poset $\mathfrak{A}$ Satisfying $\sigma$

Consider a poset with only one element $\{a\}$. In this poset, any $x$ must satisfy the condition since there are no other elements for comparison. Thus, $\mathfrak{A}=\{a\}$ satisfies $\mathrm{\exists }x\mathrm{\forall }y(x\le y\vee y\le x)$. Another example is a totally ordered set like $\{1,2\}$ with the natural order where every element is inherently comparable to every other element.

Constructing a Poset $\mathfrak{B}$ Not Satisfying $\sigma$

To find a poset for $eg\sigma$, choose a poset where no single element is comparable to every other element. An example is the following poset: $\{a,b\}$ with no defined order between $a$ and $b$: $(a\parallel b)$. In this structure, neither $a$ nor $b$ satisfies the requirement of being comparable to every other element, so $\mathfrak{B}=\{a,b\}$ with $a\parallel b$ satisfies $eg\sigma$.

Key concepts

Order Theory

Order theory is a branch of mathematics dealing with the study of order relations. These relations are defined typically by a set along with a binary relation that is reflexive, antisymmetric, and transitive. These properties establish a framework where elements can be compared based on order. The common types of order relations include total orders and partial orders, which vary by the complexity of element comparability.

In the context of posets, a partially ordered set, you have a set equipped with a partial order. This means not all elements need to be comparable. In contrast, a total order requires every pair of elements to be comparable. As we dive deeper into examples and specific elements like maximal and minimal ones, order theory provides the essential tools to understand these structures. It is central to the interpretation of posets and relates to the concept of comparable elements.

Comparable Elements

Comparable elements in a poset are elements that can be directly compared through the partial order relationship. If two elements, say, $x$ and $y$, satisfy $x\le y$ or $y\le x$, they are said to be comparable.

This concept becomes particularly significant in posets under total orders, where all pairs of elements are comparable. However, in general posets, not all elements are required to be comparable, which introduces scenarios like $a\parallel b$ where neither element is less than the other.

• In the exercise, for a poset $\mathfrak{A}$ to satisfy the given existential formula $\sigma =\mathrm{\exists }x\mathrm{\forall }y(x\le y\vee y\le x)$, the element $x$ must be comparable with all elements $y$.
• Alternatively, in poset $\mathfrak{B}$, such comparability does not exist, exemplifying a non-total order.

Order Structure

Order structure refers to the way elements are organized in a poset according to the order relation. This structure can significantly influence the properties of the set and elements involved.

Posets can be represented as directed graphs, with elements as vertices and order relations as directed edges. The absence or presence of certain directed paths signifies the comparability between elements. For instance, a totally ordered set resembles a line where each element is connected consecutively, while a partially ordered set may appear more like a branched network.

• A poset's complexity can be understood as the degree of interconnectedness of its elements through these order relations, giving insight into the poset's structural dynamics.
• In the exercise, $\mathfrak{A}$ is structured to have a comprehensive order, while $\mathfrak{B}$ lacks certain connections, leading to a complex structure without general comparability.

Existential Quantifier in Posets

The existential quantifier is a vital concept in logic, often symbolized by $\mathrm{\exists }$. It is used within the context of posets to assert the existence of an element with a specific property.

In the given expression $\sigma =\mathrm{\exists }x\mathrm{\forall }y(x\le y\vee y\le x)$, the existential quantifier $\mathrm{\exists }x$ suggests that there is at least one element $x$ such that for every element $y$, $x$ is comparable to $y$. This highlights a specific condition or role that $x$ plays within the poset’s order structure.

• Understanding and identifying such an element is crucial since it dictates the poset's satisfaction of the formula.
• The lack of this particular element in $\mathfrak{B}$ demonstrates a scenario of $eg\sigma$, where the structure prohibits such satisfaction.