# set identities

• Apr 11th 2009, 05:42 PM
xalk
set identities
Are the following provable:

a) if, xεΑ===>yεA,then x=y.If not write a counter example

b) (SxT)xU = Sx(TxU) <=====> $S=\emptyset\vee T=\emptyset\vee U=\emptyset$
• Apr 11th 2009, 05:58 PM
Jhevon
Quote:

Originally Posted by xalk
Are the following provable:

a) if, xεΑ===>yεA,then x=y.If not write a counter example

nope, let
$A = \{ x \mid x \in \mathbb{Z}, x \ge 1 \}$

now, consider some integer $x \ge 1$, and take $y = x+ 1$. then we have $x \in A \implies y \in A$, but $x \ne y$

you may also consider the contrapostive. it would probably be more straight forward to you. just make sure you know what the negation of an implication is ;)

Quote:

b) (SxT)xU = Sx(TxU) <=====> $S=\emptyset\vee T=\emptyset\vee U=\emptyset$
this is true, and provable. give a direct proof of the (<=) direction and a proof by contrapositive of the (=>) direction
• Apr 11th 2009, 07:05 PM
xalk
Quote:

Originally Posted by Jhevon
nope, let
$A = \{ x \mid x \in \mathbb{Z}, x \ge 1 \}$

now, consider some integer $x \ge 1$, and take $y = x+ 1$. then we have $x \in A \implies y \in A$, but $x \ne y$

you may also consider the contrapostive. it would probably be more straight forward to you. just make sure you know what the negation of an implication is ;)

this is true, and provable. give a direct proof of the (<=) direction and a proof by contrapositive of the (=>) direction

What you proved is:

$(x\in A\Longrightarrow\exists y\in A)\wedge x\neq y$

And not:

$(x\in A\Longrightarrow y\in A)\wedge x\neq y$

The problem is for all x,y.

AS for the 2nd problem ,suppose $S\neq\emptyset\wedge T\neq\emptyset\wedge U\neq\emptyset$,then what??
• Apr 11th 2009, 07:13 PM
Jhevon
Quote:

Originally Posted by xalk
What you proved is:

$(x\in A\Longrightarrow\exists y\in A)\wedge x\neq y$

And not:

$(x\in A\Longrightarrow y\in A)\wedge x\neq y$

The problem is for all x,y.

very well. use the contrapositive then. assume x and y are different, does this mean we will have x in A but y not in A?

Quote:

AS for the 2nd problem ,suppose $S\neq\emptyset\wedge T\neq\emptyset\wedge U\neq\emptyset$,then what??
ok, if they are not empty, then there is some element in each. then we can form the Cartesian products. the elements on the left side are of the form ((s,t),u) for s in S, t in T and u in U, while the right side has elements of the form (s,(t,u)), clearly these are not the same
• Apr 12th 2009, 02:34 PM
xalk
Quote:

Originally Posted by Jhevon
very well. use the contrapositive then. assume x and y are different, does this mean we will have x in A but y not in A?

ok, if they are not empty, then there is some element in each. then we can form the Cartesian products. the elements on the left side are of the form ((s,t),u) for s in S, t in T and u in U, while the right side has elements of the form (s,(t,u)), clearly these are not the same

Here is the proof for the 1st part:

assume xεA===>yεA AND let x=/=y
then put A={x} and so we have:

xε{x} ====> yε{x},but

x=x <===> xε{x},but

x=x and so

yε{x} <===> y=x thus

y=x ,but also x=/=y and we have a contradiction.

Hence x=y

Now for the 2nd proof :

Let [(s,t),u]ε[(SxT)xU] <====> (sεS and tεT)and uεU <=====> sεS and(tεTand uεU) <====> [s,(t,u)]ε[Sx(TxU)].

Now we have to use the 1st proved theorem : (xεA====>yεA) ===> x=y

and :

[(s,t),u] =[s,(t,u)],but also [(s,t),u] =/=[s,(t,u)],hence a contradiction and so:

$S=\emptyset\vee T=\emptyset\vee U=\emptyset$
• Apr 12th 2009, 02:57 PM
Plato
Quote:

Originally Posted by xalk
Here is the proof for the 1st part:
assume xεA===>yεA AND let x=/=y
then put A={x} and so we have:
xε{x} ====> yε{x},but
x=x <===> xε{x},but
x=x and so
yε{x} <===> y=x thus
y=x ,but also x=/=y and we have a contradiction.
Hence x=y

Is that really a proof of the original statement?
This is a true statement: $\color{blue}1 \in \emptyset \Rightarrow 2 \in \emptyset$.
But this is a false statement: $\color{red}\left[ {1 \in \emptyset \Rightarrow 2 \in \emptyset } \right] \Rightarrow 1 = 2$.

If you can pick $A=\{x\}$, I can pick $A=\emptyset$.