i) Let $S$ be $\{x, y, z\}$, then the power set of $S$ is $\{\{\}, \{x\}, \{y\}, \{z\}, \{x, y\}, \{x, z\}, \{y, z\}, \{x, y, z\}\}$

The following elements are equivalent representations of the same value in a characteristic $2$ finite field:

$\{\} = 000 = 0, \{x\} = 100 = x^2, \{y\} = 010 = x, \{z\} = 001 = 1, \{x,y\} = 110 = x^2+x, \{x,z\} = 101 = x^2+1, \{y,z\} = 011 = x+1, \{x,y,z\} = 111 = x^2+x+1$

P.S.: In fact, $x²+x+1$ is a universal set (of everything). see https://www.wolframalpha.com/input/?i=(x+and+x)+xor+x+xor+1

ii) The set of subsets of a given set (its power set) is a standard example of partially ordered set (poset)


For all $a, b \in S$, it must satisfy:

$ a\leq a$ (reflexivity).

If $a \leq b$ and $b \leq a$, then $a = b$ (antisymmetry)

Being $S$ a poset, it is self-evident that:

$x^2+x+1 \leq x^2+x$ and $x^2+x \leq x^2+x+1$, then $x^2+x+1 = x^2+x$, where $x^2+x+1 = NOT(x^2+x)$ for $x=\{0,1\}$. Because $x^2+x+1 \leq x^2+x+1$.

Notice that:

Let $a$ be $x^2+x+1=1$ for $x=\{0,1\}$ and let $b$ be $x^2+x=0$ for $x=\{0,1\}$, hence every element in $a$ also is in $b$ and every element in $b$ is also in $a$.

P.S.: $x^2+x$ is empty set. see https://www.wolframalpha.com/input/?i=(x+and+x)+xor+x

Is this system of axioms complete and inconsistent ?


Is this system of axioms incomplete and consistent ?


5 Answers 5


You wrote:

Consequently, $2(0)=2(1)$ and, as a result, $0=1$

Why do you think the second phrase is a result of the first?

It's definitely true in the integers that $2a=2b$ implies $a=b$. But there's no reason to assume that's true in other number systems -- unless you can prove it. In fact, the very result you've come up with can be re-interpreted as a demonstration that $2a =2b$ does not imply $a=b$ in the integers modulo $2$, because if it did, it would lead to a false conclusion.

EDITED TO ADD: In a few comments the OP has asked about the fact that $0 + 0 = 1 + 1$, so I thought I should add some (hopefully clarifying) remarks about that here.

Yes, when working with the integers modulo $2$, it is true that $0 + 0 = 1 + 1$, and it is also true that $1 = -1$. Those true statements do not lead to the (false) conclusion that $0 = 1$. If you think they do lead to that conclusion, you should explain what algebraic operation you are using to get there. Are you adding or subtracting something on both sides? If so, what is it? Are you multiplying by something on both sides? If so, what is it (and make sure it's actually an object that exists in the system of the integers modulo 2)?

In fact there is no way to deduce the conclusion $0 = 1$ from the equations $0 + 0 = 1 + 1$ or $1 = -1$, so there is no contradiction. Again, if you think there is a way to reach that conclusion, the burden is on you to explain how you think you can do it.

EDITED: The original post has been essentially replaced with a different question, so let me take one last crack at clarifying what I think is going on here.

Being $S$ a poset, it is self-evident that:

$x^2+x+1 \leq x^2+x+1$

We are fine up to here.

Because $x^2+x \leq x^2+x+1$

Still fine to here. But:

and $x^2+x+1 \leq x^2+x$,

Here is where the argument breaks down. You have established the representation that $x^2 + x + 1$ stands for the element $111$, which in turn stands for the element $\{x,y,z\}$. In the same representation, $x^2 + x$ stands for the element $110$, which represents the set $\{x, y\}$. And the partial order you are using is set-theoretical inclusion. But it most certainly is not "self-evident" that $\{x, y, z\} \subset \{x, y\}$. On the contrary this is self-evidently false, since $z \in \{x,y,z\}$ but $z \notin \{z,y\}$.

In various comments you have claimed that this is true because of antisymmetry, giving many of us the impression that you think antisymmetry says ""If $a \le b$ then $b \le a$". That is not at all what antisymmetry says. Antisymmetry says that if $a \le b$ and $b \le a$ then $a=b$". (I notice you left out the word "if" from your statement of the antisymmetry property -- I have since edited it in -- which suggests you may have some trouble with this.)

Elsewhere, in a comment on someone else's reply (now deleted or moved to chat) you stated that $x^2 + x + 1 \le x^2 + x$ is true because "it is a property that $a \le b$ implies $a + c \le b + c$." But this is not a true property of all partial orders, and in particular it is not true for this partial order.

P.S.: $x^2+x$ is empty set. see https://www.wolframalpha.com/input/?i=(x+and+x)+xor+x

While it is true that $x^2 + x$ evaluates to $0$ on the integers mod 2, and therefore (when interpreted as truth value) can be regarded as "false", you have already said yourself that $x^2 + x$ corresponds to the set $\{x,y\}$, so clearly is is not the empty set.

  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ Jun 16, 2017 at 6:16

EDIT: Actually, the OP has claimed below that they think "$a\le b\implies b\le a$" follows from the axioms of posets, so there's a much more fundamental error here.

Based on the comments, here's what's going on.

Your argument basically consists of the following:

  • The powerset $\{x, y,z\}$ can be given a poset structure: $a\le b$ if $a\subseteq b$.

  • It can also be given a field structure - as a copy of $F_{2^3}$.

  • Now, it's easy to check that $\{x, y\}\le \{x, y,z\}$.

  • $\color{red}{\mbox{And clearly that means $\{x, y\}+\{z\}\le \{x, y, z\}+\{z\}$},}$ $\color{red}{\mbox{since we can add the same thing to both sides of an inequality.}}$

  • So we get $\{x, y, z\}\le\{x, y\}$, which is a problem!

The problem (as might be evident) is the bullet point in red. That line assumes that "$+$" and "$\le$," as we've defined them, interact the way we're used to such things interacting - namely, that $$a\le b\implies a+c\le b+c.$$ But while this is true for the usual things we call "$+$" and "$\le$,", it's not true for the specific things we're calling "$+$" and "$\le$" in this context. And you haven't tried to justify this at all.

Note that this isn't about either one separately. $\le$ is a partial order, and $+$ is a group operation; the point is that they don't interact with each other the way one might hope. This is a general thing in math: often, you can put two "reasonable" structures on a given set, and you're interested in how they interact - well, you have to be very careful to prove everything rigorously, you can't just assume they interact nicely!

  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ Jun 16, 2017 at 6:15

Since $2\equiv 0$, you are "dividing by zero" or did not notice that $2$ does not have a multiplicative inverse.

In order to go from $2\times 0\equiv 2\times 1$ to $0\equiv 1$, you need to find an inverse $n$ such that $2n\equiv1$, and multiply $n$ to both sides of $2\times 0\equiv 2\times 1$.


Operations modulo $2$ are not the same as the operations they look like - $+$ modulo $2$ is not the same operation as the usual $+$, for example. And since they're different, they don't necessarily behave the same way! In fact, it's clearer if you just don't use the same symbol for them. Say $\oplus$ is addition modulo $2$, and $\otimes$ is multiplication modulo $2$. It's certainly true that $2x = 2y$ implies $x = y$; but what does "$2x$" have to do with "$2 \otimes x$"? It's not even clear that $2 \otimes x = x \otimes 2$ right away. In short, whenever you want to use a standard property of regular arithmetic in modular arithmetic, you have to prove that it still works when $+$ and $\times$ are replaced with $\oplus$ and $\otimes$. And what you've just given is an excellent proof that the law that $2 \times x = 2 \times y$ implies $x = y$ is not true for $\otimes$.


The problematic claim here is that $$x^2+x + 1 \le x^2+x$$ under the poset defined in the preliminaries.

The left hand side corresponds to $\{x,y,z\}$ and the right hand side corresponds to $\{x,y\}$, but the left hand side is not a subset of the right hand side.


Not the answer you're looking for? Browse other questions tagged .