My Math Forum Finding an ordered set example

 Applied Math Applied Math Forum

 February 4th, 2014, 03:52 AM #1 Newbie   Joined: Jan 2014 Posts: 23 Thanks: 0 Finding an ordered set example Hello, I try to solve an exercise which confuses me a bit. The task is to: "Find an example of an ordered set, which is not type $\omega$ even though it has the first element and each element has a direct successor and (except the first one) a direct predecessor". Lets call this set A. What I assume about this exercise (but I am not sure if it is correct) is: 1) The ordering we are talking about is not a linear ordering (i.e. we have only reflexivity, antisymmetry and transitivity, no guarantee that $\forall a,b \in A: a \leq b \vee b \leq a)$ 2) The first element is an element x that satisfies $\forall a \in A: x \leq a$. As opposed to a maximal element m which satisfies $\neg \exists a \in A: m \leq a$. 3) A direct successor of an element a is an element b which satisfies $(a \leq b) \wedge \neg \exists c \in A: a \leq c \leq b$. A direct predecessor of a is defined similarly as the element b which satisfies $(b \leq a) \wedge \neg \exists c \in A: b \leq c \leq a$. 4) The direct successor and the direct predecessor must be unique, so it we are not allowed to have two predecessors b and b' of an element a, like: $(b \leq a) \wedge \neg \exists c \in A: b \leq c \leq a$ $(b' \leq a) \wedge \neg \exists c \in A: b' \leq c \leq a$ event though under assumption 1) we are not required to have $b \leq b'$ nor $b' \leq b$. I though of a construct which I would call "two omegas with a common first element", formally: $A= \{ z \} \cup \bigcup_{n=1}^{\infty} \{ a_n \} \cup \bigcup_{n=1}^{\infty} \{ b_n \}$ with the ordering defined as: $z \leq a_1 \leq a_2 \leq \ldots \leq a_n \leq \ldots$ $z \leq b_1 \leq b_2 \leq \ldots \leq b_n \leq \ldots$ The set A is obviously countable and it could be made isomorphic with $\omega$ (e.g. by adding $\forall n: a_n \leq b_n$) but in the current state it is not. My question is: are my assumptions/definitions 1-4 correct and is the example o.k.? I am equally interested in the verification of my understanding of definitions and my assumptions as in verifying my example. Especially assumption 4) is interesting to me, not only in the context of this exercise, but also in the general context (i.e. does the direct successor always have to be unique or not?) Note: this is not a homework so don't tell me to go and ask the lecturer. I don't have one, that's why I am asking the question here.
 February 4th, 2014, 04:25 AM #2 Newbie   Joined: Jan 2014 Posts: 23 Thanks: 0 Re: Finding an ordered set example After some more thinking I realized that my example is not consistent with the assumption 4) (because z has two successors $a_1$ and $b_1$) and also I think that it can be proven by induction that an ordered set that satisfies all the conditions 1-4 is isomorphic with $\omega$. So, something must be done differently, maybe assumption 4) is not o.k. or there exist a different example?
 February 4th, 2014, 06:55 AM #3 Global Moderator     Joined: Nov 2006 From: UTC -5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms Re: Finding an ordered set example I didn't read your post closely, but what about this example? Elements are of the form ("N", n) with n a positive integer, or ("Z", n) with n an integer. (S, m) < (S, n) if and only if m < n, and ("N", m) < ("Z", n) for any m and n (and the reverse is never true). Thanks from smieci
 February 4th, 2014, 08:33 AM #4 Newbie   Joined: Jan 2014 Posts: 23 Thanks: 0 Re: Finding an ordered set example Nice example, thanks! As for showing that the proposed set (let's call it A) is not type $\omega$ (which is pretty obvious, but I would like to have a formal proof) does it suffice to say that in $\omega$ for any two elements a $\leq$ b there is always a finite number of elements between a and b and in A for any elements ("N", a) and ("Z", b) there is an infinite number of elements $x \in A$ such that ("N", a) $\leq$ x $\leq$ ("Z", b) ?
 February 4th, 2014, 11:22 AM #5 Global Moderator     Joined: Nov 2006 From: UTC -5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms Re: Finding an ordered set example Sure, that should do.

 Tags finding, ordered, set

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post panky Number Theory 2 December 6th, 2013 11:52 PM Mathforum1000 Number Theory 2 June 20th, 2012 04:19 PM xYlem Applied Math 1 January 27th, 2012 04:24 PM panky Algebra 3 July 20th, 2011 08:07 PM roncarlston Algebra 10 June 21st, 2009 07:21 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top