Proof Math Question

[Terrestrialrage]

Have a tough question on this take home test and I have no idea where to begin. I come to the BG math community for assistance.

5. Let B^A denote the set of all functions from set A to set B. Prove/disprove: there is an isomorphism (bijection) from {0,1}a to Ƥ(A) for any nonempty set A.

[Ferion]

Read the section "Representing Subsets as Functions", that should give you some kind of clue of where to start.

http://en.wikipedia.org/wiki/Power_set

[Terrestrialrage]

Another question. I'm at a point in a problem where I need to prove (p → q) → r ⇔ p → (q → r) and i dont have any identities that are helpful. Any ideas on some identities that I could use to prove this with? I tried a truth table and it didnt come out as planned.

[Fairy-Killer]

A truth table should always work on a tautology. Let me look up in my book something that might help there...

[Fairy-Killer]

Do you have the 4 biconditional logical equivalences? p <> q = (p > q ) ^ (q > p), p <> q = p' <> q', p <> q = (p^q) v (p' ^ q'), and not(p <> q) = p <> q'. I think the first or third could be particularly helpful in this case, I might be wrong, however.

[bori]

Another question. I'm at a point in a problem where I need to prove (p → q) → r ⇔ p → (q → r) and i dont have any identities that are helpful. Any ideas on some identities that I could use to prove this with? I tried a truth table and it didnt come out as planned.

Try making a detailed table in which you list out each element in that expression. For example, the columns would be:
p, q, r, (p → q), (q → r), (p → q) → r, p → (q → r), then finally (p → q) → r ⇔ p → (q → r).

In this systematic way, you find the truth value of the smaller parts first, then use those pieces to figure out the bigger parts. For example, if you have for example, p = T, q = T, r =T, then you can figure out (p → q), then follow with (p → q) → r.

Let me know if you have any more questions.

[Terrestrialrage]

Heres the truth table i laid out:

p | q | r | (p → q) | (q → r) | (p →q) → r | p → (q → r)
T T T T T T T
T T F T F F F
T F T F T T T
T F F F T T T
F T T T T T T
F T F T F F T
F F T T T T T
F F F T T F T

As can be seen, the 6th and 8th rows make the statement not a tautology. I looked over the table many times and cant find error. The only thing i can think of is that you don't have to consider all 8 circumstances? i dont know at this point.

[Scyz]

Hey, first post on these forums after browins the General Discussion section for years

Anyways, I can help you with all the logic that you need help with. As for "(p → q) → r ⇔ p → (q → r)" you can do the truth table method, or you could do a natural deduction proof, the former is quicker whilst the latter goes into more detail on how one might come to such a conclusion in a more natural way, also natural deduction systems are very useful for predicate and modal logics.

(p → q) → r ⇔ p → (q → r) : This is not really something to be proved as it is merely a formula containing and has no "┤" or "├" or " "┤├" indicating that one thing entails another. I do assume you are using the bi-conditional (⇔) as such however and so to prove whether it is valid or not you can use a truth table as the person above posted, or you could just do a proof for each direction, which I will do.

(p → q) → r ├ p → (q → r)
T__T_T_T_F__T_F__T_F_F

So for this proof, I just made the right side of the turnstile false, and that to the left of it true, and if you get a contradiction then its proven to be valid. We have a contradiction in the "(p → q) → r", since the antecedent is true, whilst the consequent is false.

Now we can test the opposite direction
(p → q) → r ┤ p → (q → r)
_F_T_F_F_F__F_T__F_T_F

Here I am just showing a possible truth table for the formula, and as you can see it is invalid, as there is no contradiction when making the antecedent true, with the consequent false.

Conclusion - the sequent you asked about is invalid, furthermore the way I have done my proof, also works for modal logic, and possibly predicate logic too, I just prefer it since it works so wonderfully when applying possible world semantics. Of course if you find what I posted a little confusing, stick with plain old truth tables or tableau if you have done them too.

Anyway, good luck with your logic work, and post if you need more assistance.

[Brutala]

As can be seen, the 6th and 8th rows make the statement not a tautology. I looked over the table many times and cant find error. The only thing i can think of is that you don't have to consider all 8 circumstances? i dont know at this point.

It's not proven if it doesn't hold in all 8. Why not give us the original problem in which I guess a mistake lead you to needing to prove this line? When I took logic they wouldn't accept a table as "proof". They only let use such quick methods to show that a proof doesn't exist. If you guys work like this, give me the axioms you guys work with and I'll derive the theorem you need, but you can't possibly need the one you wrote since, as you've shown, it's not a tautology.

As for your OP, if by "{0,1}a" you actually meant the cartesian product "{0,1}A", then your answer is simple. {0,1}A has 2*n elements while the power set of A has 2^n elements, where n is the number of elements in A. Obviously, a bijection does not exist for just any non-empty A. There's only a bijection if n=1 or n=2.

[Ferion]

I think he meant {0,1}, the set theory representation of the natural number 2. Figured the extra "a" was just a typo, I could be wrong though.

[Brutala]

That would just make the problem even more trivial: "Prove/disprove that a set of 2 elements has the same number of elements as the power set of ANY nonempty set A." lol 2 isn't always equal to 2^n (again n is the number of elements in A).