0
$\begingroup$

I have two types of objects, X and Y, each are recursive structures, and contain different structures sets of tuples containing sets.. etc. The number of elements in X and Y are is the same.

I need to proof that for every x in X, there is a unique y in Y.

Can this be achieved by defining a bijective function which uses recursion to construct a y from each x?

Could I also achieve this proof using a proof by induction, if so how would I lay this out?

Is proof by induction the same a defining a recursive function between two recursive structures?

$\endgroup$
1
  • $\begingroup$ "etc" is not enough to allow clear generalization of your idea. $\endgroup$
    – user16034
    Sep 11, 2023 at 8:28

2 Answers 2

1
$\begingroup$

If you can establish that the function you define is a bijection from $X$ to $Y$, then that constitutes a proof, whatever technique you use, induction or other.

The proposition you wish to prove is essentially the definition of bijection.

$\endgroup$
1
$\begingroup$

Induction applies to infinite processes. Unless you address a special theoretical problem, I don't think that induction can be of any use. In any case, you would not establish equal values, but equicardinality.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.