Questions in discrete mathematics So , I am working on some past papers and these are the questions I am not sure about:
**Choose the correct answer
$ f \equiv [\neg P(x,x) \land \neg \exists x \exists y (P(x,y) \land P(y,x)) \land \forall x \forall y \forall z(P(x,y) \land P(y,z) \rightarrow P(x,z))] \rightarrow \exists x \forall y P(x,y)$**

*

*f is logically valid

*f is true for every interpretation in a finite world

*f is true for every interpretation in a infinite world

*none of the above


I am trying firstly to make sense of what it tries to say: ''if P is not a reflexive relation , and they are not two elements related in both directions and if P is transitive then there is an x for every y such that x is related to y . How can I judge if this is true? If my world was integers ans $P(x,y) \equiv x<y$ the sentense holds true but that's not strong enough to answer the question

The set of all subsets of natural numbers has the same cardinality with the set of real numbers
This statement can not be proved
6. - This statemnt is true

7. - this statement is false

8. - this statement is equivalent to the "continuum hypothesis" by Cantor


I went for 8 . The $P(N)$ is uncountable , so is the the set of real numbers and  because I think the continuum hypothesis, states that there is no cardinality between the one of natural numbers and the one of real ones , then it must be $|P(N)| = |R|$ . But I think , that the statement is also true and can not be proved?

We define as A sets that satisfiy this property: "There is a set $B \subset A$, such that $|A| = |B|$. The number of subsets A of
natural numbers that satisfiy this property is countable

*

*True

*False


To be honest, I am not even sure that I get this question. So for example A could be the set of even - positive  numbers (subset of natural ), or odd , or primes or even something more abstract like {1,6,8,...,2n+4,...}. So basically A could be a random subset of naturals so the numbers of A set is equal to the P(N)? (or I did not get the statement). If so, the statement is false ,P(N) is uncountable.

***The powerset of prime numbers has the same cardinality with rational numbers .

*

*True or False***


False. Rationals are countable. But the powerset of prime numbers can be proved by diagonalisation that it's not.

 A: For the first question consider the empty relation on any set $A$, finite or infinite: it is certainly irrelflexive and asymmetric, and it is vacuously transitive, so $f$ is not necessarily true either in a finite world or in an infinite world. This also shows that it is not logically valid.
Note that your own example, taking $P$ to be $<$, shows that $f$ can be either true or false in an infinite world: it’s true on $\Bbb N$, but it’s false on $\Bbb Z$. And if you take the relation to be $\{\langle 0,1\rangle\}$ on the set $\{0,1,2\}$, you get a non-empty counterexample to $f$ on a finite set.
The statement in the second question is true and can be proved; it is not equivalent to the continuum hypothesis.
A subset $A$ of $\Bbb N$ has the property in the third question if and only if some proper subset of $A$ has the same cardinality as $A$. This is the case for every infinite subset of $\Bbb N$. If $A\subseteq\Bbb N$ is infinite, let $a=\min A$, the smallest integer in $A$; then $A\setminus\{a\}$ is a proper subset of $A$ that is also countably infinite, so $|A\setminus\{a\}|=|A|$. $\Bbb N$ has uncountably many infinite subsets, so it has uncountably many subsets with the property in question. It is not true, however, that every subset of $\Bbb N$ has the property: the finite subsets do not. If you remove even just one element from a finite set, you get a set with a strictly smaller cardinality.
Your answer to the last question is correct.
