반드시 ∀x ∀y (x+y=y+x) 를 보이는 형식적인 증명 자체를 길게 쓰실 필요는 없고, 

그냥 증명 가능한지, Q에서 성립하는지 여부만 증명하셔도 됩니다.

arca.live/b/math/22612082

저기서 0이 최솟값이라는 부분은, 

x<y iff y=SS...S(x)꼴이라고 할 때, 

0이 minimal 원소 (극소 원소)라는 걸 의도한 것입니다.

S : Q->Q,
+: Q^2 ->Q,
* : Q^2 ->Q 여야 합니다.  

(즉, Q에 대해서 닫혀 있음.)

2. ∀x ∀y ( (S(x) = S(y)) → x = y )    (임의의 수에 대해, 그 다음수는 유일하다.)
이 해석이 조금 이상하게 보이는데요, 그 다음수가 유일하다는 것은 S(x)가 function 이라는 조건에서 자동으로 나오는 거고, 2번 조건의 의미는 "임의의 수에 대해 그 수가 다음 수가 되는 수(즉 그 이전의 수)는 유일하다" 가 아닐까요.

저는 저 주어진 조건에서 "최소값"이라는 개념이 성립할 수 있는지 의심스럽습니다. 
N = {0, 1, 2, ...}
T =  {..., -3t, -2t, -t, 0t, t, 2t, 3t, ...} 이라고 하고, t는 허수단위처럼 자연수와는 별개로 존재하는 어떤 단위로 간주합니다. (0t ≠ 0 입니다)
Q = N ⋃ T 로 놓고 S() 와 ⊕, ⊗를 다음과 같이 정의합니다. (편의상 연산을 설명할 때 일반적으로 사용하는 + 와 * 를 사용할 것이므로 문제에서 요구하는 연산은 ⊕, ⊗ 로 표기를 바꿨습니다.)

n 혹은 n_i 는 0 이상의 정수, m 혹은 m_i 는 정수일 때
S(n)  =  n + 1
S(m t)  =  (m + 1) t
n_1 ⊕ n_2  =  n_1 + n_2
m_1 t ⊕ m_2 t  =  (m_1 + m_2) t
n ⊕ m t  =  m t ⊕ n  =  (m + n) t
즉 ⊕ 는 + 와 유사한 연산이며, 두 수가 모두 N 의 원소일 때만 결과가 N의 원소이고 둘 중 하나라도 T의 원소이면 결과는 T의 원소라는 점이 추가되었습니다.
이렇게 정의하면 문제의 조건 1, 2, 3, 4, 5 를 모두 만족한다는 점을 쉽게 보일 수 있습니다.

이제 ⊗는 다음과 같이 정의합니다.
n_1 ⊗ n_2  =  n_1 * n_2
m t ⊗ 0  =  0 ⊗ m t  =  0
n ⊗ m t  =  m t ⊗ n  = (m * n) t
m_1 t ⊗ m_2 t  =  (m_1 * m_2) t
이 ⊗ 연산 또한 6 의 조건과 7의 조건을 모두 만족합니다. 

물론 이 ⊕ 연산은 문제의 조건 ∀x ∀y (x+y=y+x) 에 대한 반례가 되지 않기 때문에 문제의 답과 직접적인 관계는 없습니다. 하지만 Q의 모든 원소 x 를 S(S(S(...S(0)...))) 의 형태로 나타내거나 귀납법을 사용하는 등의 방법을 적용할 수 없다는 점은 보여준다고 생각합니다.