It is easy to prove that an apple is an apple: The equation x=x is a tautology, for all x. So if x=apple, we can substitute it in the equation x=x and get apple=apple, so an apple is an apple.

But how can one prove (using standard deductive logic) that an apple is not an orange, since x!=y is not a tautology for all x,y?
['https://philosophy.stackexchange.com/questions/8459', 'https://philosophy.stackexchange.com', 'https://philosophy.stackexchange.com/users/4639/']
In mathematics, an equals sign connects subject and predicate.

The statement, apple=orange, is the same as the statement, an apple is an orange.

In order to determine an apple is an apple, you used the principle of identity. That which is the same is the same.

In order to determine an apple is not an orange, we use the principle of difference. That which is the same is not different, or two different things are not the same. 

General reasoning from sense infers that apples are not oranges. However, if we use the power of abstraction, we can take the concept of an apple, its "appleness", and a concept of an orange, its "orangeness". These conceptions are known though general reasoning from sense and are often informed from the rest of society, e.g. academia. 

An apple's "appleness" can only belong to apples. An orange's "orangeness" can only belong to oranges. "appleness" contains no "orangeness". Therefore, something containing "orangeness", namely an orange, is never something containing "appleness", namely an apple, i.e. apples are never oranges.
Use *types*:

So that x:Apple, y:Orange 

This means that x is an apple, y is an orange.

Then we cannot even compare oranges to apples - they're not of the same type; showing that they *must* be different.

If one had an additional type Fruit from which these descend, then the types Orange and Apple would be comparable; but this would be *additional* type information that is unneccessary to implement and demonstrate the question asked by the OP.

It's also worth noting that in an actually existing type system like Haskell, it would not be legal to construct two types of the same nature and name.